6100 & 6101 LeetCode刷题

收获

最大的收获就是我觉得自己真的菜，和大佬们之间的差距不是一般的大。
总共四个题，第一道题倒是不难，差不多8分钟左右写完，但是这时候已经通过的人数就已经达到了3000人。
然后到了第二题，是一个典型的DP就可以解决的算法，但是我最后还是没做出来，这个可能是我对这类的题目训练太少。
第三个题是我看起来很熟悉的一道题，这不过这道题做了些改编，直到最后我也没能做出来。
第四道题我就是看都没看。

---

憧憬

希望能坚持下去，提升自己的算法水平。
今年剩余的目标是刷够100到题吧。

---

解题

第一题：判断一个矩阵是否是X矩阵。

class Solution {
public:
    bool checkXMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        for(int i = 0;i < n; i++){
            for(int j = 0;j < n;j++){
                if(i == j || i+j == n-1){
                    if(grid[i][j] == 0){
                        return false;
                    }
                }
                if(grid[i][j] != 0){
                    return false;
                }
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第二题：统计放置房子的个数（使用的是同一思路的两种不同方法，内存差距非常大）

/**
 * @brief
 * 像这种下一个由上一个决定的就用 DP 算法
 *  
 * 记录上一个位置放置和不放置的方法数,不相临可以解释为上一个位置不放,
 * 这一个位置才能放,所以下一个位置放置的方法数就是上一个不放置的方法数,而不放置的方法数就是上一个位置的所有方法数
 * 
 * 递推的公式就是：
 * f(i+1,1) = f(i,0)
 * f(i+1,0) = f(i,0) + f(i,1)
 * 
 * f(1,0) = 1
 * f(1,1) = 1
 * 
 */

//方法1，使用标准的 DP 算法
class Solution1 {
    const int MOD = 1e9 + 7;

public:
    int countHousePlacements(int n) {
        vector<vector<long>> dp;
        dp.resize(n,vector<long>(2,0));
        dp[0][0] = 1;
        dp[0][1] = 1;
        for(int i = 1; i < n ; i++){
            dp[i][0] = dp[i-1][0] + dp[i-1][1];
            dp[i][1] = dp[i-1][0];
        }
        return (dp[n-1][0]+dp[n-1][1])*(dp[n-1][0]+dp[n-1][1]) % MOD;
    }
};



/**
 * @brief 
 * 找规律和递推
 * 本质上是 DP 算法的简版
 */
class Solution {
    const int MOD = 1e7 + 9 ;

public:
    int countHousePlacements(int n) {
        long yes = 1,no = 1;
        for(int i = 1;i < n; i++){
            long temp = yes;
            yes = no;
            no = (temp + no) % MOD;
        } 

        return (yes+no) * (yes+no) % MOD;  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56