数据结构刷题：第四天
目录
一，重塑矩阵
思路与算法
复杂度分析
二，杨辉三角
思路及解法
复杂度分析
一，重塑矩阵
566. 重塑矩阵 - 力扣（LeetCode）
https://leetcode.cn/problems/reshape-the-matrix/
思路与算法
对于一个行数为m,列数为n,行列下标都从0开始编号的二维数组，我们可以通过下面的方式，将
其中的每个元素(i, j)映射到整数域内，并且它们按照行优先的顺序一-对应着 [0, mn)中的每一个整
数。形象化地来说，我们把这个二维数组「排扁」成了一个-维数组。如果读者对机器学习有一定了解，可以知道这就是flatten操作。
这样的映射即为:
(i,j)→i*n+j
同样地，我们可以将整数x映射回其在矩阵中的下标，即
i=x/n
j=x%n
其中/表示整数除法，%示取模运算。
那么题目需要我们做的事情相当于:
●将二维数组nums映射成一 个一维数组;
●将这个一维数组映射回r行c列的二维数组。
我们当然可以直接使用一个一维数组进行过渡，但我们也可以直接从二维数组nums 得到r行c列的
重塑矩阵:
●设nums本身为m行n列,如果mn≠rc,那么二包含的元素个数不相同，因此无法进行重
塑;
●否则，对于x∈[0,mn), 第x个元素在nums中对应的下标为(x / n,x % n),而在新的重塑矩
阵中对应的下标为(x/ c,x % c)。我们直接进行赋值即可。
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
int m = nums.size();
int n = nums[0].size();
if (m * n != r * c) {
return nums;
}
vector<vector<int>> ans(r, vector<int>(c));
for (int x = 0; x < m * n; ++x) {
ans[x / c][x % c] = nums[x / n][x % n];
}
return ans;
}
};
复杂度分析
●时间复杂度: O(rc)。 这里的时间复杂度是在重塑矩阵成功的前提下的时间复杂度，否则当
mn≠rc时, C++语言中返回的是原数组的一份拷贝，本质上需要的时间复杂度为O(mn),而
期语可以直接返回原数组的对象,需要的时间复杂度仅为0(1)。
●空间复杂度: 0(1)。 这里的空间复杂度不包含返回的重塑矩阵需要的空间。
二，杨辉三角
118. 杨辉三角 - 力扣（LeetCode）https://leetcode.cn/problems/pascals-triangle/
思路及解法
杨辉三角，是二项式系数在三角形中的一种几何排列。它是中国古代数学的杰出研究成果之一,它把
二项赋系数图形化，把组合数内在的- -些代数性质直观地从图形中体现出来,是一种离散型的数与形
的结合。
杨辉三角具有以下性质:
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ret(numRows);
for (int i = 0; i < numRows; ++i) {
ret[i].resize(i + 1);//每行的列表大小不同，需要加1
ret[i][0] = ret[i][i] = 1;
for (int j = 1; j < i; ++j) {
ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
}
}
return ret;
}
};
复杂度分析
-
时间复杂度：O(numRows2)。
-
空间复杂度：O(1)。不考虑返回值的空间占用。