【蓝桥杯训练】【力扣训练】【初级算法——数组】_输入示例1 4 5 7 1 6 输出示例1 排序后: 1 4 5 6 7

---

一、删除排序数组中的重复项（简单）

题目：

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array

分析：

因为题目要求原地修改数组，并且数据是有序的，我们可以判断某个数与其相邻之间的数是否相同，可以去掉重复数，所以我们可以用快慢指针来进行求解。
首先定义一个慢指针 j ，快指针 i 。i 从数组下标 1 开始遍历整个数组，j 从 下标 0 开始。当nums[i] != nums[j] 时，j 便加一。
i 遍历数组结束后，j + 1 便是最后数组的长度。

代码：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        j = 0
        for i in range(1,n):
            if nums[i] != nums[j]:
                j += 1
                nums[j] = nums[i]
        nums = nums[:j + 1]
        return j + 1
1
2
3
4
5
6
7
8
9
10
11
12

---

二、买卖股票的最佳时机（中等）

题目：

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii

分析：

这道题有很多解法都可以，动态规划，贪心都可以，我选择了相对比较简单的贪心算法。就是当当天的股票价格比第二天的高时，我们便购入，第二天就出售，不管利润多大，只要有利润就购入。比如： prices = [7,1,3,2,6,8]，
第一天：7<1 不购；
第二天：1<3 买入第二天卖出，利润：2；
第三天：3>2，不购；
第四天：2<6，买入第二天卖出，利润：4；
第五天：6<8，买入第二天卖出，利润：2；
总利润为：2+4+2=8
代码：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        get = 0 #利润
        for i in range(len(prices) - 1):
            n = prices[i + 1] - prices[i] 
            if n > 0:
                get += n
        return get
1
2
3
4
5
6
7
8

---

三、旋转数组（中等）

题目：
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-array

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

来源：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/

分析：

题目为数组元素向右轮转 k 个位置，将它理解为数组的后 k 个元素移到最前面。这样我们就可以用Python中的切片操作很轻松完成。如果你还不了解切片操作，可以先去了解一下哦。

代码：

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        #当轮转次数大于数组长度时，我们对它取余，我当时写了个循环，但是更好的是直接取余
        while k > len(nums): 
            k -= len(nums)
        if k != 0:
            n = len(nums) - k
            a = nums[n:] #原数组的后k个位置的元素，现在做头
            b = nums[:n] #原数组的头，现在做尾
            for i in range(n):
                a.append(b[i])  #将尾元素添加到a的后面
            for i in range(len(nums)):
                nums[i] = a[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

四、存在重复元素（简单）

题目：

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true

示例 2：

输入：nums = [1,2,3,4]
输出：false

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contains-duplicate

分析：

这道题的解法挺多的。
我们可以排序后判断相邻位置是否存在相同数来判断是否存在重复数；
也可以定义一个空数组，遍历 nums 将其中元素一个个添加到空数组中，若某一次添加时，发现该数已存在于空数组，则说明该数重复；
当然更简单的是直接调用 Python 自带的函数 set()对数组去重。然后判断长度是否余原数组长度相同，便可以判断是否存在重复数。

代码：

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))
1
2
3

---

五、只出现一次的数字（简单）

题目：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number

分析：

前面几题是判断是否存在重复数，这题变成了求不重复数，思路也大体相同。
我们可以对数组进行排序，然后遍历数组，找出其中的某个元素，与其相邻的数不同，则那个数便是只出现一次的数。

代码：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort() #原地排序
        if len(nums) == 1:
            return nums[0]
        for i in range(len(nums)):
            if i == 0: #首
                if nums[i] != nums[i + 1]:
                    return nums[i]
            elif i == len(nums) - 1: #尾
                if nums[i] != nums[i - 1]:
                    return nums[i]
            else: #中间元素
                if nums[i] != nums[i - 1] and nums[i] != nums[i + 1]:
                    return nums[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

六、两个数组的交集（简单）

题目：

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii

分析：

这道题需要找到两数组的交集，并且交集中出现的元素次数必须和原来的两数组相同，若两数组出现次数不一样，取小的。一开始我的想法是把两个数组中短数组元素遍历，判断它其中的元素是否存在长数组中，这样就能找到相同元素。但是这样元素出现次数的问题就无法轻易解决。
因为题目中有提到元素中的位置可以改变，所以我们可以两数组排序，然后利用快慢指针来解决这个问题。先定义一个空数组 nums，判断两个数组的长度，再对两个数组进行排序。分别用 i 和 j 来遍历两个数组。当 nums1[i] == nums2[j] 便可将 nums1[i] 放入定义的空数组中，最后短数据遍历结束，nums 就是最后的结果。

代码：

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        l1 = len(nums1)
        l2 = len(nums2)
        nums = []
        nums1.sort()
        nums2.sort()
        j,i = 0,0
        if l1 < l2:
            while i < l1:
                if nums1[i] == nums2[j]:
                    nums.append(nums1[i])
                    j += 1
                    i += 1
                    if j == l2:
                        return nums
                elif nums1[i] > nums2[j]:
                    j += 1
                    if j == l2:
                        return nums
                else:
                    i += 1
            return nums
        else:
            while i < l2:
                if nums2[i] == nums1[j]:
                    nums.append(nums2[i])
                    j += 1
                    i += 1
                    if j == l1:
                        return nums
                elif nums2[i] > nums1[j]:
                    j += 1
                    if j == l1:
                        return nums
                else:
                    i += 1
            return nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

七、加一（简单）

题目：

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：

输入：digits = [0]
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/plus-one

分析：

这是一道挺简单的题目，我们可以直接判断数组的长度确定这个数是几位数，然后遍历数组，对每个元素乘以相应的位数得到一个整型的数，直接把这个数加一，最后再把他们每个位数上的数存入数组中即可。
但是，我用的并不是这个方法，我的做法是类似于竖式加法，向数组的最后一个元素加一，如果最后一个元素是‘9’，我们便倒序遍历数组，将‘9’的元素变为‘0’，再向前继续遍历，若不为‘9’，我们便将该元素‘+1’，最后若遍历到数组元素的第一个仍为‘9’，我们便将其变为‘1’，再向数组末尾添加一个‘0’。

代码：

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits) - 1 
        if n == 0 and digits[n] == 9: #数组元素长度为1，并且该元素为9
            digits[n] = 1
            digits.append(0) 
            return digits
        if digits[n] == 9: #末尾元素为9
            m = n
            while True:
                if m == n: #元素位置为末尾
                    digits[m] = 0 #将元素变为0
                m -= 1
                if digits[m] != 9: #末尾前一位元素不是9
                    digits[m] += 1  #元素 +1
                    return digits
                elif digits[m] == 9 and m == 0: #头元素为9
                    digits[m] =1  #将其变为1
                    digits.append(0)  #末尾加一个0
                    return digits
                else:
                    digits[m] = 0  #中间元素为9将其变为0
        else:
            digits[n] += 1  #末尾不为0，直接+1
        return digits
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

八、移动零（简单）

题目：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes

分析：

这道题也是挺简单的一道题，我们遍历数组，若数组元素为‘0’，我们就可以将该元素删除，再向数组末尾加一个‘0’即可，这样也保证了非‘0’元素的顺序。

代码：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i = 0
        while True:
            if nums[i] == 0:
                nums.remove(0) #删除为0的元素
                nums.append(0) #向数组元素末尾添加0
                n -= 1
            else:
                i += 1
            if n == i:
                break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

九、两数之和（简单）

题目：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

分析：

这道题其实很容易想到，直接用暴力解决，可以直接遍历元素，然后相加得到target。其实可以优化一下，把 target 减去数组元素得到差，我们再判断该差值是否在数组中，若在便找到差在该数组中的位置即可。

代码：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = [] #存两个元素的数组下标
        for i in range(len(nums)):
            n = target - nums[i] #差值
            if n in nums: #判断差值是否在数组中
                for j in range(len(nums)):
                    if j != i and nums[j] == n: #判断是否为元素值是否为差值和当前元素本身
                        ans.append(i)  
                        ans.append(j)
                        return(ans)
1
2
3
4
5
6
7
8
9
10
11

---

十、有效的数独（中等）

题目：

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。

示例 1：

输入：board =
[[“5”,“3”,".",".",“7”,".",".",".","."]
,[“6”,".",".",“1”,“9”,“5”,".",".","."]
,[".",“9”,“8”,".",".",".",".",“6”,"."]
,[“8”,".",".",".",“6”,".",".",".",“3”]
,[“4”,".",".",“8”,".",“3”,".",".",“1”]
,[“7”,".",".",".",“2”,".",".",".",“6”]
,[".",“6”,".",".",".",".",“2”,“8”,"."]
,[".",".",".",“4”,“1”,“9”,".",".",“5”]
,[".",".",".",".",“8”,".",".",“7”,“9”]]
输出：true

示例 2：

输入：board =
[[“8”,“3”,".",".",“7”,".",".",".","."]
,[“6”,".",".",“1”,“9”,“5”,".",".","."]
,[".",“9”,“8”,".",".",".",".",“6”,"."]
,[“8”,".",".",".",“6”,".",".",".",“3”]
,[“4”,".",".",“8”,".",“3”,".",".",“1”]
,[“7”,".",".",".",“2”,".",".",".",“6”]
,[".",“6”,".",".",".",".",“2”,“8”,"."]
,[".",".",".",“4”,“1”,“9”,".",".",“5”]
,[".",".",".",".",“8”,".",".",“7”,“9”]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-sudoku

分析：

题目中已经告诉了条件，就是判断每一行，每一列，3*3的格子内是否有重复的数。至于如何判断是否有重复的数，上面有类似的题。

代码：

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        point = [[0,0],[0,3],[0,6],[3,0],[3,3],[3,6],[6,0],[6,3],[6,6]] #找出3*3宫格左上角元素
        for i in range(9): #判断行
            x = []
            for j in range(9):
                if board[i][j] != '.':
                    if board[i][j] in x:
                        return False
                    x.append(board[i][j])
        for i in range(9): #判断列
            y = []
            for j in range(9):
                if board[j][i] != '.':
                    if board[j][i] in y:
                        return False
                    y.append(board[j][i])           
        for p in range(9): #判断3*3宫格
            z = []
            a = point[p][0]
            b = point[p][1]
            for i in range(a,a + 3):
                for j in range(b,b + 3):
                    if board[i][j] != '.':
                        if board[i][j] in z:
                            return False
                        z.append(board[i][j])
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

---

十一、旋转图像（中等）

题目：

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-image

分析：

这道题有两种方法，第一种直接暴力求解，直接通过变换数组元素得到，但是这种方法写代码我绝的挺复杂的就没有尝试。
第二种就是将数组上下对称变化之后，再按照对角线元素进行对称变换。就得到了最后的结果，可以自己动手画图看看结果。我这里就不放图了。

代码：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        l = len(matrix)
        n = l - 1
        for i in range(l//2):  #上下对称变换
            x = matrix[i]
            matrix[i] = matrix[n]
            matrix[n] = x
            n -= 1
        for i in range(l - 1):  #对角线对称变换
            for j in range(i + 1,l):
                x = matrix[i][j]
                matrix[i][j] = matrix[j][i]
                matrix[j][i] = x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

码字不易，点个赞叭。
都看到这里了，点一个赞再走叭。