Cinte's Leetcode Record
0%

337. House Robber III

Posted on Edited on In Disqus:
Symbols count in article: 3.7k Reading time ≈ 3 mins.

337. House Robber III

对于一个节点来说，如果rob这个点，那么他的child就不能rob, 如果不rob，那么他的child可以rob也可以不rob
对于rob这个节点来说，需要计算他的grandchild rob或者不rob的情况，不rob时也需要计算，如果递归则需要重复计算，因此每次的递归函数都计算这一个rob和不rob的情况
用pair保存起来rob和不rob的记过

于是这种情况下就不会产生重复计算。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        auto ret = helper(root);
        return max(ret.first, ret.second);
    }
private:
    pair<int, int> helper(TreeNode* node)
    {
        if(!node)
            return {0, 0};
        
        auto left = helper(node->left);
        auto right = helper(node->right);
        
        // if rob
        int rob = node->val + left.second + right.second;
        int notRob = max(left.first, left.second) + max(right.first, right.second);
        
        return {rob, notRob};
    }
};
approach 1 未改进前的算法使用memo优化

如果不用memo，则rob和不rob情况会重复计算

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        return max(helper(root, false), helper(root, true));
    }
private:
    unordered_map<TreeNode*, int> robed;
    unordered_map<TreeNode*, int> noRobed;
    int helper(TreeNode* node, bool isRobed)
    {
        if(!node)
            return 0;
        if(isRobed)
        {
            if(robed.find(node) != robed.end())
                return robed[node];
            else
            {
                int left = helper(node->left, false);
                int right = helper(node->right, false);
                int ret = node->val + left + right;
                robed[node] = ret;
                return ret;
            }
        }else
        {
            if(noRobed.find(node) != noRobed.end())
                return noRobed[node];
            else
            {
                int left = max(helper(node->left, false), helper(node->left, true));
                int right = max(helper(node->right, false), helper(node->right, true));
                int ret = left + right;
                noRobed[node] = ret;
                return ret;
            }
        }
    }
};
dp（复习时候看不懂了
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
57
58
59
60
61
62
63
64
65
66
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        unordered_map<int, vector<int>> pc;
        vector<int> val; // vector来存放节点的值
        queue<TreeNode*> qNode; // 用来遍历
        queue<int> qIndex; // 用来存放节点所对应的指标
        int index = -1;
        qNode.push(root);
        qIndex.push(index);
        // 将所有节点的值放入val，每个节点对应index
        while(!qNode.empty())
        {
            // 层级遍历
            auto node = qNode.front();
            qNode.pop();
            auto fatherI = qIndex.front();
            qIndex.pop();
            if(node)
            {
                ++index;
                pc[fatherI].push_back(index); // father中放入孩子
                val.push_back(node->val);
                qNode.push(node->left);
                qNode.push(node->right);
                qIndex.push(index);
                qIndex.push(index);
            }
        }
        
        // 开始dp
        vector<int> dpRob(index + 1);
        vector<int> dpNoRob(index + 1);
        
        // 从最后一层开始往上走
        for(int i = index; i >= 0; --i)
        {
            if(pc[i].empty()) // 叶子节点的情况
            {
                dpRob[i] = val[i];
                dpNoRob[i] = 0;
            }else
            {
                dpRob[i] = val[i];
                // 遍历孩子节点
                for(auto& j : pc[i])
                {
                    dpRob[i] += dpNoRob[j]; // 如果rob，那么就加上前面不rob的
                    dpNoRob[i] += max(dpRob[j], dpNoRob[j]); // 如果不rob，那么前面随便rob还是不rob，取最大值
                }
            }
        }
        return max(dpRob[0], dpNoRob[0]);
    }
};

base : leaf