数据结构入门（第四天）

566. 重塑矩阵

给定一个mxn的数组，重构为rxc的数组。 比较简单的想法是把数组拉平为一位数组，然后逐个填充到新的数组中：

class Solution: def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]: m,n = len(mat), len(mat[0]) if m*n != r*c: return mat arr = [] for row in mat: for x in row: arr.append(x) arr_index = 0 newmat = [[0 for j in range(c)]for i in range(r)] for i in range(r): for j in range(c): newmat[i][j] = arr[arr_index] arr_index += 1 return newmat

官方提供了一种直接计算下标的方法：

class Solution: def matrixReshape(self, nums: List[List[int]], r: int, c: int) -> List[List[int]]: m, n = len(nums), len(nums[0]) if m * n != r * c: return nums ans = [[0] * c for _ in range(r)] for x in range(m * n): ans[x // c][x % c] = nums[x // n][x % n] return ans

118. 杨辉三角

找规律题。可以直接按照生成的规律生成数组。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。

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