'''时间复杂度O(n), 空间复杂度O(n)''' classSolution: defrotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ tmp, n = nums.copy(), len(nums) for i inrange(n): nums[(i+k)%n] = tmp[i]
方案二： 不另外创建数组。
classSolution: defrotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ N = len(nums) if N == 1: return # 题目给的例子中，有k>N的情况，所以先求模运算 k = k % N if k == 0: return
classSolution: defpivotIndex(self, nums: List[int]) -> int: N = len(nums) # 把左右结果放入中间变量缓存，就不用每次都调用sum了 left, right = 0, sum(nums) for i inrange(N): cur_val = nums[i] if left == right - cur_val: return i else: left += cur_val right -= cur_val return -1
classSolution: deffindMaxConsecutiveOnes(self, nums: List[int]) -> int: # index_0 用来记录上一次0出现的位置，作为连续1区间的左边界 index_0 = -1 N, gap = len(nums), 0 # 在原始数组后面多加一个0，表示区域的最大右边界 nums.append(0) for i inrange(N+1): if nums[i] == 0: # 当遇到为0的时候，取该次i作为右边界，计算两个0之间的间隔 gap = max(gap, i-index_0-1) # 更新完gap之后也要把index0更新为当前的0的索引。 index_0 = i return gap
''' 当然也可以使用1来作为计算gap的判断条件，原理是一样的 index_0 = -1 N, gap = len(nums), 0 for i in range(N): if nums[i] == 1: gap = max(gap, i-index_0) else: index_0 = i return gap '''
classSolution: deffindDiagonalOrder(self, mat: List[List[int]]) -> List[int]: m,n = len(mat), len(mat[0]) res = [] left, top, right, bottom = 0, 0, n-1, m-1 # i,j表示矩阵的i 行 j 列, k表示矩阵已经遍历了多少个元素 i, j, k = 0, 0, 0 while k < m*n: # 朝着右上遍历 while i >= top and j <= right and k < m*n: # 当 i 未超过上边界, j 未超过右边界, k 未超过元素总数 res.append(mat[i][j]) i -= 1# 往上移动, 故 i 减小 j += 1# 往右移动, 故 j 增大 k += 1# 已经遍历过一个元素 # 当跳出了这个while循环时: # 1.如果是 k < m*n 不满足, 可以不用管 # 2.如果是 i >= top 不满足, 说明上方出界, i要往下回来一行才能继续遍历 # 3.如果是 j <= right 不满足, 说明右侧出界, j要往左侧回来一列才能继续遍历; # 同时, 出右界, 说明刚刚那一行已经被遍历完了！！所以i即使没有越上界，依然要向下, 而且是向下两行！ # 比如如果是 3行2列 的矩阵,（行多列少，j一定先出界） 就会出现这种情况 # 如果是2.3都出现不满足, 说明刚刚遍历过的位置是右上角, 和情况3一样 # 总结起来, 伪代码 就为 : # i = i + 1 (j没有越右界) or i + 2(j越了右界) # j = j (j没有越右界) or j - 1 (j越了右界) i, j = (i+1, j) if (j <=right) else (i+2, j-1)
# 朝着左下遍历 while i <= bottom and j >= left and k<m*n: res.append(mat[i][j]) i += 1# 往下移动, 故 i 增大 j -= 1# 往左移动, 故 j 减小 k += 1# 已经遍历过一个元素 # 分析同上（可以用3行4列的矩阵帮助思考，列多行少，i一定先出界）, 此处不赘述, 伪代码 就为 : # j = j + 1 (i没有越下界) or j + 2(i越了下界) # i = i (i没有越下界) or i - 1 (i越了下界) j, i = (j+1, i) if (i<=bottom) else (j+2, i-1) return res
classSolution: defspiralOrder(self, matrix: List[List[int]]) -> List[int]: res = [] m, n = len(matrix), len(matrix[0]) i, j, k = 0, 0, 0 left, up, right, down = 0, 0, n-1, m-1 while1: for j inrange(left, right+1): res.append(matrix[i][j]) k+=1 if k >= m*n : break up += 1
for i inrange(up, down+1): res.append(matrix[i][j]) k+=1 if k >= m*n : break right -=1
for j inrange(right, left-1, -1): res.append(matrix[i][j]) k+=1 if k >= m*n : break down -=1
for i inrange(down, up-1, -1): res.append(matrix[i][j]) k+=1 if k >= m*n : break left +=1 return res
classSolution: defsetZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ # 如果在遍历的时候就修改，那么前面如果出现了0，修改完之后，后面很可能都被改为0 # 所以先记住这些为0的行/列索引 # 再改 rows, cols = [], [] M, N = len(matrix), len(matrix[0]) for i inrange(M): for j inrange(N): if matrix[i][j] == 0: ifnot i in rows: rows.append(i) ifnot j in cols: cols.append(j) '''注意，python的二维list不支持以下写法： for i in rows: matrix[i][:] =0 for j in cols: matrix[:][j] = 0 这是 numpy array 才支持的写法 ''' for i inrange(M): for j inrange(N): if i in rows or j in cols: matrix[i][j] =0
'''思路2.直接用第一列来记录哪一行出现过0，用第一行来记录哪一列出现过0； 后续的元素出现0时，虽然第一行和第一列被修改了，但是第一行第一列对应的位置，按照规则本来也会被改成0. 不过要提前记录第一行和第一列是否有0元素，有的话，最后再把他们全部变为0；没有的话就不用管''' classSolution: defsetZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ m, n = len(matrix), len(matrix[0]) flag_col0 = any(matrix[i][0] == 0for i inrange(m)) flag_row0 = any(matrix[0][j] == 0for j inrange(n)) # 先用第一行和第一列来记录出现0的列和行 for i inrange(1, m): for j inrange(1, n): if matrix[i][j] == 0: matrix[i][0] = matrix[0][j] = 0 # 根据第一行和第一列的记录，来修改原始矩阵 for i inrange(1, m): for j inrange(1, n): if matrix[i][0] == 0or matrix[0][j] == 0: matrix[i][j] = 0 # 再来处理第一列 if flag_col0: for i inrange(m): matrix[i][0] = 0 # 再来处理第一行 if flag_row0: for j inrange(n): matrix[0][j] = 0
classSolution: defgameOfLife(self, board: List[List[int]]) -> None: """ Do not return anything, modify board in-place instead. """ # 因为是同时发生的，所以我们不能在原有矩阵上直接修改 # 而是参照原有矩阵的值，对一个新的矩阵的值进行判定 # 二维数组的 深度拷贝的方式有以下几种，不能直接用 = 号去拷贝，那样是python的浅拷贝，会共享存储区域 import copy copy_board = copy.deepcopy(board) # copy_board = [copy.deepcopy(row) for row in board] # copy_board = [[board[i][j] for j in range(n)] for i in range(m)] m, n = len(board), len(board[0])
for i inrange(m): for j inrange(n): # left: max(0, j-1), right: min(n, j+1+1), top: max(0, i-1), bottom: min(m, i+1+1) if copy_board[i][j] == 1: # 如果原始状态是1，进入下面的规则 # 由于我们要算周围8个格子的和 # 先将初始值置为-1，这样就直接考虑9宫格的和（相当于减去当前元素1） area_sum = -1 # 然后就是如何遍历以当前元素为中心的9宫格的问题了 # 理想情况下，i的遍历范围[i-1, i+1 +1), j的遍历范围 [j-1, j+1 +1) # 但是要考虑格子本身就在矩阵边界的情况，所以: # 上边界最小只能到 0: 取max(0, i-1); 左边界最小只能到 0: 取max(0, j-1) # 下边界最大只能到 m: 取min(m, i+1 +1); 右边界最大只能到 n：取min(n, j+1 +1); for p inrange(max(0,i-1), min(m,i+1 +1)): for q inrange(max(0,j-1), min(n, j+1 +1)): area_sum += copy_board[p][q] if area_sum < 2: board[i][j] = 0 elif area_sum > 3: board[i][j] = 0 else: pass else: # 如果原始状态是0，进入下面的规则 area_sum = 0 for p inrange(max(i-1,0), min(m,i+1+1)): for q inrange(max(0,j-1), min(n, j+1+1)): area_sum += copy_board[p][q] if area_sum == 3: board[i][j] = 1 else: pass
