Leetcode数据结构入门第四天（数组）
566. 重塑矩阵
题目描述
在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。
给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。
如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
示例1：
输入：mat = [[1,2],[3,4]], r = 1, c = 4
输出：[[1,2,3,4]]
示例2：
输入：mat = [[1,2],[3,4]], r = 2, c = 4
输出：[[1,2],[3,4]]
思路一
这道题要求重塑矩阵，简单的思路就是直接根据重塑前后的行数*列数是否相等来判断能否重塑，不可以重塑就返回原始矩阵，可以重塑就开始赋值，通过两层循环遍历原始矩阵实现赋值过程，利用重塑后矩阵的横纵坐标来标识，一行一行给重塑矩阵赋值，直到当前列满了，就到下一行，列重新置0，不断重复直至遍历完成
知识点补充：
C++ 动态二维数组(二维vector）
vector<vector<int>> mat(row,vector<int> (col));//创建二维数组
//获取行数，列数
int row=mat.size();//获取行数
int col=mat[0].size();//获取列数
参考代码
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
int row=mat.size();//获取行数
int col=mat[0].size();//获取列数
//如果给定参数的 reshape 操作不可行，输出原始矩阵
if(row*col!=r*c)
{
return mat;
}
//否则：重塑矩阵
vector<vector<int>> res(r,vector<int> (c));
int ir=0,jc=0;//重塑矩阵的横纵下标
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
//一行一行给转置矩阵赋值，直到列满了，就到下一行
if(jc>=c)
{
jc=0;
ir++;
}
res[ir][jc++]=mat[i][j];
}
}
return res;
}
};
思路二(数组映射方法)
对于一个行数为 m，列数为 n，行列下标都从 0 开始编号的二维数组，将其中的每个元素 (i, j) 映射到整数域内，并且它们按照行优先的顺序一一对应着 [0, mn)中的每一个整数。
二维数组映射到一维数组：(i,j)→i×n+j
相反地，整数i映射回矩阵的下标（设矩阵列数为n）：
横坐标：i=x / n
纵坐标：j=x % n
这道题就是先把原数组映射成一维数组，再把一维组映射回r行n列的二维数组，因为一维数组只是一个过渡作用，所以可以省略它直接映射，只需要遍历所有下标0~row*col（原来矩阵转换为一维数组的所有下标）
res[i/c][i%c]=mat[i/col][i%col];
参考代码
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
int row=mat.size();//获取行数
int col=mat[0].size();//获取列数
//如果给定参数的 reshape 操作不可行，输出原始矩阵
if(row*col!=r*c)
{
return mat;
}
//否则：重塑矩阵
vector<vector<int>> res(r,vector<int> (c));
//整数x映射回二维数组(利用除法和取余列数实现)：横纵坐标i=x/col;j=x%col
for(int i=0;i<row*col;i++)
{
res[i/c][i%c]=mat[i/col][i%col];
}
return res;
}
};
118. 杨辉三角
题目描述
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
样例
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
输入: numRows = 1
输出: [[1]]
思路
通过杨辉三角的观察，会发现第i行（i从0开始）的元素个数为i+1,每一行的首尾都是1，其他元素是前一行元素的对应列和前一列两个元素之和，所以通过遍历，动态更改每一行元素的个数，实时赋值即可。
知识点
由vector实现的二维数组，可以通过**resize()**的方法来改变行、列值
//定义一个row行col列的数组
vector<vector<int>> array(row);
for (i = 0; i < array.size(); i++)
array[i].resize(col);
参考代码
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector <int>> res(numRows);
for(int i=0;i<numRows;i++)
{
//resize():改变实际元素的个数。
res[i].resize(i+1);//元素个数是i+1，因为下标i是从0开始的
for(int j=0;j<i+1;j++)
{
if(j==0||j==i) res[i][j]=1;//首尾都是1
else
{
res[i][j]=res[i-1][j-1]+res[i-1][j];//其他是前一行元素的对应列和前一列之和
}
}
}
return res;
}
};