今天比较摸，忏悔。

1. 计算布尔二叉树的值

难度

• Easy
• Medium
• Hard

完成情况

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

思路

设定有点意思，直接根据题设遍历即可。应该算是先序遍历。

代码

class Solution {
private:
    bool dfs(TreeNode* root) {
        if (!root->left && !root->right) return root->val;
        if (root->val == 2) return dfs(root->left) | dfs(root->right);
        else return dfs(root->left) & dfs(root->right);
    }
public:
    bool evaluateTree(TreeNode* root) {
        return dfs(root);
    }
};

2. 坐上公交的最晚时间

难度

• Easy
• Medium
• Hard

完成情况

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

思路

这种要考虑很多情况的题写的好烦躁连续11次提交未通过，不能被这题影响心态，跳过先。

代码

class Solution {
public:
    int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) {
        sort(buses.begin(), buses.end());
        sort(passengers.begin(), passengers.end());
        int j = 0, c;
        for (int t : buses)
            for (c = capacity; c && j < passengers.size() && passengers[j] <= t; --c)
                ++j;
        --j;
        int ans = c ? buses.back() : passengers[j]; // 在发车时到达公交站 or 上一个上车的乘客
        while (j >= 0 && passengers[j--] == ans) --ans; // 往前找没人到达的时刻
        return ans;
    }
};

3. 最小差值平方和

难度

• Easy
• Medium
• Hard

完成情况

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

思路

相信越练越多，对细节能更好把握！

实际上要取得最小平方和，就是将差的绝对值的数列的最大值不断减小（到次最大值，直到0），并且我们并不用关心操作nums1还是nums2的问题，只要总的操作次数足够，我们总能够将一个差降到想要的值。比如4和19差的绝对值是15，如果总的操作数是2，那么我们一定可以把绝对值降到13，而不用关心是如何操作哪一个数字。

用一个map来存储差的绝对值及其对应数目，当k足够大时，将所有最大值（可能有负数相同最大值）减一；当k不够大时，尽可能将最大值减一，直到k为0或者map中只有0。

代码

class Solution {
public:
    long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
        int n = nums1.size();
        map<int, int> mp;
        for (int i = 0; i < n; ++i) mp[abs(nums1[i] - nums2[i])]++;
        int k = k1 + k2;
        while (k > 0) {
            int key = mp.rbegin()->first;
            int cnt = mp.rbegin()->second;
            if (key == 0) return 0;
            if (k >= cnt) {
                k -= cnt;
                mp.erase(key);
                mp[key - 1] += cnt;
            } else {
                mp[key] = cnt - k;
                mp[key - 1] += k;
                k=0;
            }
        }
        long long ans = 0LL;
        for (auto& elem : mp) {
            long long x = (long long)(elem.first);
            long long cnt = (long long)(elem.second);
            ans += x * x * cnt;
        }
        return ans;
    }
};

4. 元素值大于变化阈值的子数组

难度

• Easy
• Medium
• Hard

完成情况

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

思路

参考这篇

可以使用并查集或者单调栈，目前来讲能看懂单调栈解法，并查集还需要学习。（代码直接复制了，后续需要再复习）

代码

class Solution {
public:
    int validSubarraySize(vector<int> &nums, int threshold) {
        int n = nums.size();
        int left[n]; // left[i] 为左侧小于 nums[i] 的最近元素位置（不存在时为 -1）
        stack<int> s;
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && nums[s.top()] >= nums[i]) s.pop();
            left[i] = s.empty() ? -1 : s.top();
            s.push(i);
        }

        int right[n]; // right[i] 为右侧小于 nums[i] 的最近元素位置（不存在时为 n）
        s = stack<int>();
        for (int i = n - 1; i >= 0; --i) {
            while (!s.empty() && nums[s.top()] >= nums[i]) s.pop();
            right[i] = s.empty() ? n : s.top();
            s.push(i);
        }

        for (int i = 0; i < n; ++i) {
            int k = right[i] - left[i] - 1;
            if (nums[i] > threshold / k) return k;
        }
        return -1;
    }
};

5. 螺旋矩阵 IV

难度

• Easy
• Medium
• Hard

完成情况

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

思路

居然只debug一次就通过了，而且时间超过50%，太感动了……

想到每走完一圈再接着走内圈，可以用递归。每次分四个步骤，先从左往右铺满顶行，然后向下一格，从上到下铺满右边列，然后往左一格，从左往右铺满底层行，往上一格，从下往上铺满左边一列。且在初始化矩阵时把初始值设为-1，方便后面链表不够用时直接停止遍历矩阵。

代码

class Solution {
private:
    void construct(vector<vector<int>>& ans, int m, int n, ListNode* cur, int layer) {
        for (int i = layer; i < n - layer; ++i) {
            if (cur) {
                ans[layer][i] = cur->val;
                cur = cur->next;
            }
            // else ans[layer][i] = -1;
            else return;
        }
        for (int i = layer + 1; i < m - layer; ++i) {
            if (cur) {
                ans[i][n - 1 - layer] = cur->val;
                cur = cur->next;
            }
            // else ans[i][n - 1 - layer] = -1;
            else return;
        }
        for (int i = n - 1 -layer - 1; i >= layer; --i) {
            if (cur) {
                ans[m - 1 - layer][i] = cur->val;
                cur = cur->next;
            }
            // else ans[m - 1 - layer][i] = -1;
            else return;
        }
        for (int i = m - 1 - layer -1; i > layer; --i) {
            if (cur) {
                ans[i][layer] = cur->val;
                cur = cur->next;
            }
            // else ans[i][layer] = -1;
            else return;
        }
        if (layer < (m - 1) / 2) construct(ans, m, n, cur, layer + 1);
    }
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> ans(m, vector<int>(n, -1));
        construct(ans, m, n, head, 0);
        return ans;
    }
};

6. 知道秘密的人数

难度

• Easy
• Medium
• Hard

完成情况

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

思路

完全没意识到用DP。

用数组记录每一天新增的知道秘密的人数。对于第i天，对之后i+delay到i+forget天都有贡献，于是向后累加即可。

代码

class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        vector<int> dp(n, 0);
        const int MOD = 1000000007;
        dp[0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = i + delay; j < i + forget; ++j) {
                if (j < n) {
                    dp[j] += dp[i];
                    dp[j] %= MOD;
                }
            }
        }
        int ans = 0;
        for (int i = n - forget; i < n; ++i) {
            ans = (ans + dp[i]) % MOD;
        }
        return ans;
    }
};

7. 网格图中递增路径的数目

难度

• Easy
• Medium
• Hard

完成情况

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

思路

试图用DP做，遍历两轮，但失败了。

参考这篇记忆化搜索 。mark一下。

代码

8. 解密消息

难度

• Easy
• Medium
• Hard

完成情况

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

思路

直接用map模拟即可。实际上用数组更省空间。

代码

class Solution {
public:
    string decodeMessage(string key, string message) {
        map<char, char> mp;
        char x = 'a';
        for (auto& k : key) if (k != ' ' && !mp[k]) mp[k] = x++;
        string ans = "";
        for (auto& m : message) {
            if (m!=' ') ans += mp[m];
            else ans += " ";
        }
        return ans;
    }
};