Leetcode_14 天数据结构入门_day4

Posted on | Edited on | In ,
| 3k | 25 mins.

Let`s go go go!

566. Reshape the Matrix

Analysis

这个题目有点挂羊头卖狗肉的感觉。隐约记得数据结构那本书好像讲过一点关于矩阵的压缩存储的知识。

Code

直接做吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        int m = mat.size(), n = mat[0].size();
        if(m * n != r * c) return mat;
        int tr = 0, tc = 0;
        vector<vector<int>> ret(r, vector<int>(c));
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                ret[i][j] = mat[tr][tc++];
                if(tc == n) {
                    tr++;
                    tc = 0;
                }
            }
        }
        return ret;
    }
};

不过，好像可以结合矩阵的压缩存储知识优化一下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        int m = mat.size(), n = mat[0].size();
        if(m * n != r * c) return mat;
        vector<vector<int>> ret(r, vector<int>(c));
        for(int index = 0; index < m * n; index++) {
            ret[index / c][index % c] = mat[index / n][index % n];
        }
        return ret;
    }
};

118. Pascal’s Triangle

Analysis

dp 题，他又来了😂。
这个题就是求杨辉三角。
好像不是很复杂的样子，设置一个 dp 二维数组，显然，$dp[0][0] = 1$，$dp[1][0] = 1, dp[1][1] = 1$，$dp[2][0] = 1, dp[2][1] = dp[1][0] + dp[1][1] = 2, dp[2][2] = dp[1][1] = 1$。按照这种思路，可以得到状态转移方程：$dp[i][0] = dp[i - 1][0], dp[i][i] = dp[i - 1][i - 1], dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]$。

Code

因为最后的输出结果总没有多余的 0 存在，所以为了返回符合条件的矩阵，dp 数组只能与返回的矩阵分开了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret;
        int dp[31][31] = {0};
        dp[0][0] = 1;
        ret.push_back({dp[0][0]});
        for(int i = 1; i < numRows; i++) {
            vector<int> tmp;
            dp[i][0] = dp[i - 1][0];
            tmp.push_back(dp[i][0]);
            for(int j = 1; j < i; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                tmp.push_back(dp[i][j]);
            }
            dp[i][i] = dp[i - 1][i - 1];
            tmp.push_back(dp[i][i]);
            ret.push_back(tmp);
        }
        return ret;
    }
};

不过，这样写总感觉不太优雅，嗯，改一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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);
            ret[i][0] = ret[i][i] = 1;
            for(int j = 1; j < i; j++) {
                ret[i][j] = ret[i - 1][j - 1] + ret[i - 1][j];
            }
        }
        return ret;
    }
};

果然，这样写清爽很多。

Summary

今天的题目比较简单？感觉好像可以在多来几道题？
话说，杨辉三角这个东西性质还挺多的，说不定可能会出其他性质的题。

Buy me a coffee ? :)
0%