LeetCode刷题笔记 小偷三题 打家劫舍系列 198. 打家劫舍 213. 打家劫舍 II 337. 打家劫舍 III

198.打家劫舍

完全相同的题目，优化过程见：
程序员面试金典 面试题 17.16. 按摩师

最优

class Solution {
public:
    int rob(vector<int>& nums) {
        int a=0,b=0;
        for(int i=0;i<nums.size();i++){
            int c=max(b,a+nums[i]);
            a=b;
            b=c;
        }
        return b;
    }
};

213. 打家劫舍 II

通用思路团灭打家劫舍问题

class Solution {
public:
    int robRange(vector<int>& nums,int start,int end){
        int a=0,b=0;
        for(int i=start;i<=end;i++){
            int c=max(b,nums[i]+a);
            a=b;
            b=c;
        }
        return b;
    }
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==0) return 0;
        if(n==1) return nums[0];
        return max(robRange(nums,0,n-2),robRange(nums,1,n-1));
    }
};

337. 打家劫舍 III

三种方法解决树形动态规划问题-从入门级代码到高效树形动态规划代码实现

递归超时

class Solution {
public:
    int rob(TreeNode* root) {
        if(!root) return 0;
        int money=root->val;
        if(root->left) money+=rob(root->left->left)+rob(root->left->right);
        if(root->right) money+=rob(root->right->left)+rob(root->right->right);
        return max(money,rob(root->left)+rob(root->right));
    }
};

哈希表记录

class Solution {
public:
    map<TreeNode*,int> memo;
    int rob(TreeNode* root) {
        if(!root) return 0;
        if(memo.find(root)!=memo.end()) return memo[root];
        int money=root->val;
        if(root->left) money+=rob(root->left->left)+rob(root->left->right);
        if(root->right) money+=rob(root->right->left)+rob(root->right->right);
        int result=max(money,rob(root->left)+rob(root->right));
        memo[root]=result;
        return result;
    }
};

执行用时	内存消耗
32 ms	25 MB

另一

据作者讲，此法在JAVA中是优于上解的。

class Solution {
public:
    vector<int> robInternal(TreeNode* root){
        vector<int> result(2);
        if(!root) return result;
        vector<int> left=robInternal(root->left);
        vector<int> right=robInternal(root->right);
        result[0]=max(left[0],left[1])+max(right[0],right[1]);
        result[1]=left[0]+right[0]+root->val;
        return result;
    }
    int rob(TreeNode* root){
        vector<int> result=robInternal(root);
        return max(result[0],result[1]);
    }
};

执行用时	内存消耗
32 ms	32.5 MB