Leetcode数组基础题目总结（Python实现）

2022-06-26 08:47:46

1.数组基础题目

189.轮转数组

题目：题目链接

解法1（自创：列表特性）：

思路：利用Python列表中的特殊方法pop和insert实现尾部元素多次删除后添加到列表首部的方式实现轮转。
缺点：执行用时过长

代码：

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(k):
        	del_elem = nums.pop(-1)
            nums.insert(0,del_elem)
        return nums

解法2（切片处理）：
- 思路：利用Python列表切片可以进行组合的特性实现尾部元素和首部元素的重组
- 重点：
  - k需要预先除列表长度取余，因为移动n次相当于没动
  - 复制列表的时候要用代码中所示的方法将旧列表的值赋给新列表，直接使用变量只是确定了指向，并非创建了新列表。
- 代码
```
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        nums[:] = nums[n - k:] + nums[:n - k]
```

66.加一

题目：题目链接

解法1（字符串与整型的转化）：

思路：将数组元素全部取出转化为字符串，再将字符串进行数据加一处理后改回整型列表形式，避免了多个位置上情况的讨论。

代码

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits_str = map(str,digits)
        all_str = ""
        for i in digits_str:
            all_str += i
        all_str = str(int(all_str) + 1)
        end = list(map(int,list(all_str)))
        return end

解法2（官方解法：多情况讨论）
- 思路：当我们对数组digits加一时，我们只需要关注digits的末尾出现了多少个9即可。我们可以考虑如下的三种情况：如果digits的末尾没有9，例如1,2,3，那么我们直接将末尾的数加一，得到1,2,4并返回；如果digits的末尾有若干个9，例如1,2,3,9,9，那么我们只需要找出从末尾开始的第一个不为9的元素，即3，将该元素加一，得到1,2,4,9,9。随后将末尾的9全部置零，得到1,2,4,0,0并返回。如果digits的所有元素都是9，例如9,9,9,9,9，那么答案为1,0,0,0,0,0。我们只需要构造一个长度比digits多1的新数组，将首元素置为1，其余元素置为0即可。
- 代码：
```
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        for i in range(n - 1, -1, -1):
            if digits[i] != 9:
                digits[i] += 1
                for j in range(i + 1, n):
                    digits[j] = 0
                return digits

        # digits 中所有的元素均为 9
        return [1] + [0] * n
```

724.寻找数组的中心下标

题目：题目链接

解法1（区间和）：

思路：看代码

代码：

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if ((i == 0) and (sum(nums[i+1:]) == 0)):
                return i
            if ((i == (len(nums)-1)) and (sum(nums[0:i]) == 0)):
                return i
            if sum(nums[0:i]) == sum(nums[i+1:]):
                return i
        return -1

解法2（前缀和）：

思路：

代码：

class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        N = len(nums)
        sums_ = sum(nums)
        preSum = 0
        for i in range(N):
            if preSum == sums_ - preSum - nums[i]:
                return i
            preSum += nums[i]
        return -1

485.最大连续1的个数

题目：题目链接

解法1（自创）：

思路：重新取一列表对连续1的个数进行存储，此时即使遇到不为1的数存储到0也没有关系，因为最大连续1最小就是0。

代码：

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        lianxu_one = []
        count = 0
        for i in range(len(nums)):
            if nums[i] == 1:
                count += 1
            if (nums[i] != 1) or (i == (len(nums)-1)):
                lianxu_one.append(count)
                count = 0
        return max(lianxu_one)

解法2（解法1优化）：

思路：一次遍历，遇到1让cur加一，遇到0则更新cur和ans，速度最优。

代码：

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        cur, ans = 0, 0
        for i in range(len(nums)):
            if nums[i] == 1:
                cur += 1
            else:
                ans = max(ans, cur)
                cur = 0
        return max(ans, cur)

238. 除自身以外数组的乘积

题目：题目链接

解法1（O(n)）：

思路：LeetCode官方解答

代码：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        
        # L 和 R 分别表示左右两侧的乘积列表
        L, R, answer = [0]*length, [0]*length, [0]*length
        
        # L[i] 为索引 i 左侧所有元素的乘积
        # 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
        L[0] = 1
        for i in range(1, length):
            L[i] = nums[i - 1] * L[i - 1]
        
        # R[i] 为索引 i 右侧所有元素的乘积
        # 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
        R[length - 1] = 1
        for i in reversed(range(length - 1)):
            R[i] = nums[i + 1] * R[i + 1]

        # 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
        for i in range(length):
            answer[i] = L[i] * R[i]
        
        return answer

解法2（O(1)）：

思路：同上

代码：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        answer = [0]*length
        
        # answer[i] 表示索引 i 左侧所有元素的乘积
        # 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
        answer[0] = 1
        for i in range(1, length):
            answer[i] = nums[i - 1] * answer[i - 1]
        
        # R 为右侧所有元素的乘积
        # 刚开始右边没有元素，所以 R = 1
        R = 1;
        for i in reversed(range(length)):
            # 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
            answer[i] = answer[i] * R
            # R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
            R *= nums[i]
        
        return answer

面试题 01.07. 旋转矩阵

题目：题目链接

解法（O(n^2)）：

思路：反转矩阵，然后对称元素替换即可

代码：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        matrix.reverse()
        for i in range(len(matrix)):
            for j in range(i+1, len(matrix[i])):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        return matrix

面试题 01.08. 零矩阵

题目：题目链接

解法1（O(mn)）：

思路：首先创建一个新列表，存放原列表中元素为0的行索引与列索引。然后调用新列表，将行索引和列索引上的元素全部置零。

代码：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        li = []
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == 0:
                    li.append([i,j])
        for i in li:
            matrix[i[0]][:] = [0 for i in range(len(matrix[i[0]]))]
            for j in range(len(matrix)):
                matrix[j][i[1]] = 0
        return matrix

解法2（O(mn)/O(1)）：

思路：
- 我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1)O(1) 的额外空间。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 00。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 00。
- 在实际代码中，我们首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。

代码：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        flag_col0 = any(matrix[i][0] == 0 for i in range(m))
        flag_row0 = any(matrix[0][j] == 0 for j in range(n))
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        
        if flag_col0:
            for i in range(m):
                matrix[i][0] = 0
        
        if flag_row0:
            for j in range(n):
                matrix[0][j] = 0

498.对角线遍历

题目：题目链接
解法：
- 思路（转自ikaruga）：
  - 每一趟对角线中元素的坐标（x, y）相加的和是递增的。
    
    第一趟：1 的坐标(0, 0)。x + y == 0。
    第二趟：2 的坐标(1, 0)，4 的坐标(0, 1)。x + y == 1。
    第三趟：7 的坐标(0, 2), 5 的坐标(1, 1)，3 的坐标(2, 0)。第三趟 x + y == 2。
    第四趟：……
  - 每一趟都是 x 或 y 其中一个从大到小（每次-1），另一个从小到大（每次+1）。
    
    第二趟：2 的坐标(1, 0)，4 的坐标(0, 1)。x 每次-1，y 每次+1。
    第三趟：7 的坐标(0, 2), 5 的坐标(1, 1)，3 的坐标(2, 0)。x 每次 +1，y 每次 -1。
  - 确定初始值。例如这一趟是 x 从大到小， x 尽量取最大，当初始值超过 x 的上限时，不足的部分加到 y 上面。
    
    第二趟：2 的坐标(1, 0)，4 的坐标(0, 1)。x + y == 1，x 初始值取 1，y 取 0。
    第四趟：6 的坐标(2, 1)，8 的坐标(1, 2)。x + y == 3，x 初始值取 2，剩下的加到 y上，y 取 1。
  - 确定结束值。例如这一趟是 x 从大到小，这一趟结束的判断是， x 减到 0 或者 y 加到上限。
    
    第二趟：2 的坐标(1, 0)，4 的坐标(0, 1)。x 减到 0 为止。
    第四趟：6 的坐标(2, 1)，8 的坐标(1, 2)。x 虽然才减到 1，但是 y 已经加到上限了。
  - 这一趟是 x 从大到小，那么下一趟是 y 从大到小，循环进行。并且方向相反时，逻辑处理是一样的，除了x，y和他们各自的上限值是相反的。
    
    x 从大到小，第二趟：2 的坐标(1, 0)，4 的坐标(0, 1)。x + y == 1，x 初始值取 1，y 取 0。结束值 x 减到 0 为止。
    x 从小到大，第三趟：7 的坐标(0, 2)，5 的坐标(1, 1)，3 的坐标(2, 0)。x + y == 2，y 初始值取 2，x 取 0。结束值 y 减到 0 为止。
- 代码：
```
class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        m=len(mat)
        n=len(mat[0])
        s=0
        ans=[]
        while s<m+n:
            #第1,3,5趟
            x1=s if s<m else m-1
            y1=s-x1
            while x1>=0 and y1<n:
                ans.append(mat[x1][y1])
                x1-=1
                y1+=1

            s+=1
            if s>=m+n:
                break
            #第2,4,6趟
            y2=s if s<n else n-1
            x2=s-y2
            while y2>=0 and x2<m:
                ans.append(mat[x2][y2])
                x2+=1
                y2-=1
            s+=1
        return ans
```

118.杨辉三角

题目：题目链接

解法（O(n)）：

思路：首先定义与杨辉三角相同规模的全为1的列表，然后利用生成的列表组成新列表。

代码：

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        start_matrix = []
        for i in range(numRows):
            start_matrix.append([1 for i in range(i+1)] )
        for i in range(2,numRows):
            for j in range(1,i):
                start_matrix[i][j] = start_matrix[i-1][j-1]+start_matrix[i-1][j]
        return start_matrix

119.杨辉三角 Ⅱ

题目：题目链接

解法：

思想：和118思想一样，只不过固定生成行数之后输出最后一行即可。

代码：

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        start_matrix = []
        for i in range(rowIndex+1):
            start_matrix.append([1 for i in range(i+1)] )
        for i in range(2,rowIndex+1):
            for j in range(1,i):
                start_matrix[i][j] = start_matrix[i-1][j-1]+start_matrix[i-1][j]
        return start_matrix[-1]

71.矩阵置零

题目：题目链接

解法：

思想：同面试题01.08解法2

代码：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        flag_col0 = any(matrix[i][0] == 0 for i in range(m))
        flag_row0 = any(matrix[0][j] == 0 for j in range(n))
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        
        if flag_col0:
            for i in range(m):
                matrix[i][0] = 0
        
        if flag_row0:
            for j in range(n):
                matrix[0][j] = 0

54.螺旋矩阵

题目：题目链接

思路（见注释）和解法1：

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:return []

        x=y=0                                 # 矩阵元素位置初始化
        res = []                              # 初始化，存储遍历后的矩阵元素
        dx = [ 0, 1, 0,-1]                    # 方向：右，下，左，上
        dy = [ 1, 0,-1, 0]                    # 注：与通常平面坐标系 记号 不同
        di = 0                                # 初始化方向变量
        visited = set()                       # 初始化集合，存储已走过的坐标
        m,n = len(matrix),len(matrix[0])      # 矩阵的行列 
                
        for i in range(m*n):            
            res.append(matrix[x][y])     # 存储遍历矩阵过的元素
            visited.add((x,y))           # 存储遍历过的坐标
            tx,ty = x+dx[di],y+dy[di]    # 先记录下一步坐标，用于判断下一步怎么走
            if 0<=tx<m and 0<=ty<n and (tx,ty) not in visited:   # 判断坐标是否需变向，且没有遍历过
                x,y = tx,ty                                       
            else:                                                
                di = (di+1)%4      # 改变方向，右下左上为一圈，防止方向坐标越界
                x,y = x + dx[di],y+dy[di]           # 下一步坐标
        return res

解法2：

思路：

代码：

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix or not matrix[0]: return []
        M, N = len(matrix), len(matrix[0])
        left, right, up, down = 0, N - 1, 0, M - 1
        res = []
        x, y = 0, 0
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        cur_d = 0
        while len(res) != M * N:
            res.append(matrix[x][y])
            if cur_d == 0 and y == right:
                cur_d += 1
                up += 1
            elif cur_d == 1 and x == down:
                cur_d += 1
                right -= 1
            elif cur_d == 2 and y == left:
                cur_d += 1
                down -= 1
            elif cur_d == 3 and x == up:
                cur_d += 1
                left += 1
            cur_d %= 4
            x += dirs[cur_d][0]
            y += dirs[cur_d][1]
        return res

289.生命游戏

题目：题目链接

解法：

代码：

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        neighbors = [(1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1)]

        rows = len(board)
        cols = len(board[0])

        # 从原数组复制一份到 copy_board 中
        copy_board = [[board[row][col] for col in range(cols)] for row in range(rows)]

        # 遍历面板每一个格子里的细胞
        for row in range(rows):
            for col in range(cols):

                # 对于每一个细胞统计其八个相邻位置里的活细胞数量
                live_neighbors = 0
                for neighbor in neighbors:

                    r = (row + neighbor[0])
                    c = (col + neighbor[1])

                    # 查看相邻的细胞是否是活细胞
                    if (r < rows and r >= 0) and (c < cols and c >= 0) and (copy_board[r][c] == 1):
                        live_neighbors += 1

                # 规则 1 或规则 3        
                if copy_board[row][col] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                    board[row][col] = 0
                # 规则 4
                if copy_board[row][col] == 0 and live_neighbors == 3:
                    board[row][col] = 1

码农公寓