Contents

ARST打卡第211周[211/521]

Algorithm

lc1373_二叉搜索子树的最大键值和

思路: 贪心递归回溯每一个子节点是否是搜索二叉树,是的话贪心维护最大值

贪心回溯不好用中序遍历,因为中序遍历最后不是遍历根,如何让中序遍历返回根? 或者用后序遍历,但是要最终判断左孩子比自己小,右孩子比自己大 – 这个比中序遍历好实现一点 判断是二叉搜索树之后再求和,那会导致时间复杂度到 O($n^2$),会超时 所以需要遍历的时候就记录,直接给每个节点加一个sum值,是否是二叉搜索树bool的属性就是递归回溯了,嗯嗯

数据范围16*1e8不会爆int

思路应该是对的,但是好久没写了,手生,先学习一下题解吧,嗯嗯

与题解的差距: 理解小偏差,不是只看左右孩子的大小比较,是和左右子树最小最大值比较,嗯嗯,搞错了,所以需要多记录一下子树最小最大值

题解代码写得很简洁,nice

 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
class Solution {
public:
    static constexpr int inf = 0x3f3f3f3f;
    int res;
    struct SubTree {
        bool isBST;
        int minValue;
        int maxValue;
        int sumValue;
        SubTree(bool isBST, int minValue, int maxValue, int sumValue) : isBST(isBST), minValue(minValue), maxValue(maxValue), sumValue(sumValue) {}
    };

    SubTree dfs(TreeNode* root) {
        if (root == nullptr) {
            return SubTree(true, inf, -inf, 0);
        }
        auto left = dfs(root->left);
        auto right = dfs(root->right);

        if (left.isBST && right.isBST &&
                root->val > left.maxValue && 
                root->val < right.minValue) {
            int sum = root->val + left.sumValue + right.sumValue;
            res = max(res, sum);
            return SubTree(true, min(left.minValue, root->val), 
                           max(root->val, right.maxValue), sum);
        } else {
            return SubTree(false, 0, 0, 0);
        }
    }

    int maxSumBST(TreeNode* root) {
        res = 0;
        dfs(root);
        return res;
    }
};

Review

【TED演讲】拖延症人的内心世界

拖延症的原因: 人类是动物进化来的,动物只需要吃饱睡好,繁殖,所以人类在现代社会里,这些都很容易满足的时候,做其他更多有意义的事情的动力就会降低为0。

就相当于我们的脑海里有一个理智的人,然后有一个贪图及时享受的猴子

  • 一般情况下,及时享乐的猴子都会占据上风,让人变得拖延
  • 当然在应对一些有deadline截止日期的任务,我们可能会在deadline快到的时候突然爆发一个恐惧怪兽。 恐惧怪兽把猴子吓跑,然后理智的人开始干活,这对有deadline的任务很有效
  • 但是有些任务是没有deadline的,比如健身,陪伴家人,改善亲密关系,等等,这样我们就无法召唤我们的恐惧怪兽,所以我们需要思考我们的大限将至,把每天当做人生最后两年来活,给许多事情都设置一个deadline,这样我们就会好好去做了–不过当然也包括享受生活

Tips

理解 LSM Tree:一种高效读写的存储引擎

Share

感谢耗子叔,永远怀念耗子叔