Leetcode数据结构题目集第四天,重塑矩阵
和杨辉三角
.
重塑矩阵
在MATLAB中,有一个非常有用的函数 reshape,它可以将一个矩阵重塑为另一个大小不同的新矩阵,但保留其原始数据。 给出一个由二维数组表示的矩阵,以及两个正整数r和c,分别表示想要的重构的矩阵的行数和列数。 重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。 如果具有给定参数的reshape操作是可行且合理的,则输出新的重塑矩阵;否则,输出原始矩阵。
示例 1:
1 2 3 4 5 6 7 8 9 输入: nums = [[1 ,2 ], [3 ,4 ]] r = 1 , c = 4 输出: [[1 ,2 ,3 ,4 ]] 解释: 行遍历nums的结果是 [1 ,2 ,3 ,4 ]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
示例 2:
1 2 3 4 5 6 7 8 9 10 输入: nums = [[1 ,2 ], [3 ,4 ]] r = 2 , c = 4 输出: [[1 ,2 ], [3 ,4 ]] 解释: 没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
注意:
1 2 给定矩阵的宽和高范围在 [1 , 100 ]。 给定的 r 和 c 都是正数。
解题思路&题解 解题思路大体就是先转成一维矩阵,然后再转成目标矩阵。核心思想是下面的公式:
(i, j) -> i * n + j => x
i=x / n
j=x % n
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 func matrixReshape (mat [][]int , r int , c int ) [][]int { m, n := len (mat), len (mat[0 ]) if m*n != r*c { return mat } res := make ([][]int , r) for r := range res { res[r] = make ([]int , c) } for i := 0 ; i < m*n; i++ { res[i/c][i%c] = mat[i/n][i%n] } return res }
杨辉三角
给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。 在杨辉三角中,每个数是它左上方和右上方的数的和。
示例:
1 2 3 4 5 6 7 8 9 输入: 5 输出: [ [1 ], [1 ,1 ], [1 ,2 ,1 ], [1 ,3 ,3 ,1 ], [1 ,4 ,6 ,4 ,1 ] ]
解题思路&题解 杨辉三角这算是一道经典题目了,大一就开始接触。这里主要用到这个特性->每行长度等于当前列数 -> 第一行只有一个,第二行有两个,第三行有三个。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 func generate (numRows int ) [][]int { res := [][]int {} for i := 0 ; i < numRows; i++ { temp := make ([]int , i+1 ) for j := 0 ; j <= i; j++ { if j == 0 || j == i { temp[j] = 1 } else { temp[j] = res[i-1 ][j-1 ] + res[i-1 ][j] } } res = append (res, temp) } return res }