Leetcode数据结构入门第四天(数组)

Leetcode数据结构入门第四天(数组)

566. 重塑矩阵

题目描述

在 MATLAB 中,有一个非常有用的函数 reshape ,它可以将一个 m x n 矩阵重塑为另一个大小不同(r x c)的新矩阵,但保留其原始数据。

给你一个由二维数组 mat 表示的 m x n 矩阵,以及两个正整数 r 和 c ,分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。

如果具有给定参数的 reshape 操作是可行且合理的,则输出新的重塑矩阵;否则,输出原始矩阵。

示例1:

Leetcode数据结构入门第四天(数组)

输入:mat = [[1,2],[3,4]], r = 1, c = 4
输出:[[1,2,3,4]]

示例2:

Leetcode数据结构入门第四天(数组)

输入: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;


    }
};
上一篇:uniapp swiper组件


下一篇:剑指offer56:数组中数字出现的次数