数据结构刷题：第四天

目录

 

一，重塑矩阵

 思路与算法

复杂度分析

二，杨辉三角

 思路及解法

复杂度分析

一，重塑矩阵

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>& 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(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)。不考虑返回值的空间占用。