1. 判断矩阵是否是一个 X 矩阵

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

遍历一遍，根据下标判断能否为0即可。

代码

class Solution {
public:
    bool checkXMatrix(vector<vector<int>>& grid) {
        int m = grid.size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < m; ++j) {
                if (i == j || i + j == m - 1) {
                    if (grid[i][j] == 0) return false;
                }
                else {
                    if (grid[i][j] != 0) return false;
                }
            }
        }
        return true;
    }
};

2. 统计放置房子的方式数

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

首先应当意识到，一侧的安排不影响另一侧，那么可以只看一侧，然后平方即可。

自己举例从1开始推导，发现每多一个位置，无非是两种情况，要么新位置不放房子，那么种数等于前一个位置的种数；要么新位置放房子，那么前一个位置就不能放房子，种数等于前前个位置的种数。那么就可以用DP做，状态转移方程： dp[i] = dp[i - 1] + dp[i - 2] ，当位置数为0时设为1，在实际含义和递推公式上都很合理。

代码

class Solution {
public:
    int countHousePlacements(int n) {
        long long dp[n + 1];
        dp[0] = 1;
        dp[1] = 2;
        const int MOD = 1000000007;
        for (int i = 2; i <= n; ++i) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }
        return (dp[n] * dp[n]) % MOD;
    }
};

3. 从树中删除边的最小分数

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

参考这篇 比较典型地应用了一个图的通用解题工具——全局时间戳，有待进一步学习。

代码

4. 统计星号

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

先是想用栈，但注意到我们不关心两根竖线间的字符到底是什么，所以用一个bool值就行了。

代码

class Solution {
public:
    int countAsterisks(string s) {
        bool flag = false;
        int ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (!flag) {
                if (s[i] != '|') {
                    if (s[i] == '*') ++ans;
                }
                else flag  =true;
            }
            else {
                if (s[i] == '|') flag = false;
            }
        }
        return ans;
    }
};

5. 统计无向图中无法互相到达点对数

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

参考这篇 DFS求连通块大小，维护一个变量存储之前所有连通块的总大小，每当求出一个新的连通块，它对返回值的贡献，是当前连通块大小乘以之前所有连通块总大小。

代码

6. 操作后的最大异或和

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

做出这题是真挺开心hhh

将两个例子都逐位分析一遍，发现每次得到的最大值总是所有数字含1的位的叠加。或者说，最大值的二进制表示中，只要数组中有一个数在这个位上是1，那么这位就是一，如果所有数字这位都是0，那么这位才是0，所以不管怎么操作或者操作多少次，我们总有方法达到这样的最大值。因为操作中，最右侧异或不会产生进位，左侧与操作，也不会发生进位，且操作后其高位也不会出现额外的1。

所以这题直接所有数字或和即可。

代码

class Solution {
public:
    int maximumXOR(vector<int>& nums) {
        int ans = 0;
        for (auto& num : nums) ans |= num;
        return ans;
    }
};

7. 不同骰子序列的数目

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

暴力枚举不出意外超时了。参考这篇 使用了三维DP数组。

代码