目录
一,重塑矩阵
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)。不考虑返回值的空间占用。