leetcode_day42

今日内容：

• 198. 打家劫舍 medium
• 213. 打家劫舍Ⅱ medium
• 337. 打家劫舍Ⅲ medium

198. 打家劫舍

题目：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

• 示例 1：

• 输入：[1,2,3,1]

• 输出：4

• 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

• 示例 2：

• 输入：[2,7,9,3,1]

• 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

• 提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400

思路：

跟着随想录刷题相当于做题看了tag，所以有思路提示，一开始就知道能够用动态规划来解。

dp[i]代表打劫[0, i]区间内的房屋的最高金额，状态转换方程如下：

\[ dp[i]\ = \begin{cases} nums[0], & \text{$i\ =\ 0$} \\ max(nums[0],\ nums[1]), & \text{$i\ =\ 1$} \\ max(dp[i - 2] + nums[i],\ dp[i - 1]), & \text{else} \end{cases} \]

代码

class Solution {
public:
  int rob(vector<int>& nums) {
    vector<int> dp(nums.size());
    dp[0] = nums[0];
    for(int i = 1;i < nums.size();i++) {
      if(i == 1) dp[i] = max(nums[0], nums[1]);
      else dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[nums.size() - 1];
  }

};

213. 打家劫舍Ⅱ

题目：

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

思路：

一开始想复杂了： 由于循环，所以从某处开始，相当于把上一个给去掉，然后仍然按线性来遍历，于是遍历物品，把每种物品都做一次开头再遍历背包，然后选出最多的一个。这样时间复杂度来到了\(O(n^2)\)

实际上这道题和前一道题区别不大，多出的循环机制可以分成两种情况：

• 含首不含尾
• 含尾不含首

所以只需要两种情况都走一遍取最大值就好了。

代码

自己过题的复杂代码

class Solution {
public:
  int rob(vector<int>& nums) {
    if(nums.size() == 1) return nums[0];
    vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
    for(int i = 0;i < nums.size();i++) {//每个nums[i]作起点的初始化
      dp[i][0] = nums[i];
      dp[i][1] = max(nums[i], nums[(i+1)%nums.size()]);
    }

    for(int i = 0;i < nums.size();i++) {
      for(int j = 2;j < nums.size() - 1;j++) {//每个i都做一次起点，都打劫一遍，去掉i之前的一个
        dp[i][j] = max(dp[i][j - 2] + nums[(i + j) % nums.size()], dp[i][j - 1]);
      }
    }
    int ans = 0;
    for(int i = 0;i < nums.size();i++) {
      ans = max(ans, dp[i][nums.size() - 2]);
    }
    return ans;
  }
};

carl的更优代码

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int result1 = robRange(nums, 0, nums.size() - 2); // 情况二
        int result2 = robRange(nums, 1, nums.size() - 1); // 情况三
        return max(result1, result2);
    }
    // 198.打家劫舍的逻辑
    int robRange(vector<int>& nums, int start, int end) {
        if (end == start) return nums[start];
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
};

代码随想录 | 打家劫舍Ⅱ

337. 打家劫舍Ⅲ

题目：

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

思路：

暴力递归：

跟之前的按监控的题很像，然后思维定势直接后序遍历了，结果美美TLE。又用map来记录已经算过的值防止重复计算，这才AC。

这个思路和监控题很类似，当前树有两种打劫法：

• 打劫儿子，放过根和孙子
• 打劫根和孙子，放过儿子

只要找出最大的就行了。

树形DP：

由于是树，还是单向指针，所以不能像之前那样靠dp[i - 2]来做到间隔抢劫，得不断上传“抢没抢”的信息，所以每次递归都要返回两个值，抢了当前节点的最大赃款和不抢当前节点的最大赃款。

递归终止条件自然是遇到null，直接返回0就行，遍历肯定后序遍历，因为处理root得先得到子树的信息，那么单层遍历就是先左再右，最后求出抢root的最大赃款和不抢root的最大赃款，全都返回，再返回最大的一个。

代码

暴力递归

class Solution {
public:
  unordered_map<TreeNode *, int> map;
  int rob(TreeNode* root) {
    if(root == nullptr) return 0;
    int left = 0, right = 0, grandson = 0;
    if(!root->left && !root->right) {
      return root->val;
    }
    else if(root->right) {
      if(map[root->right]) right = map[root->right];
      else {
        right = rob(root->right);
        map[root->right] = right;
      }
      if(!map[root->right->left]) {
        map[root->right->left] = rob(root->right->left);
      }
      grandson += map[root->right->left];
      if(!map[root->right->right]) map[root->right->left] = rob(root->right->right);
      grandson += map[root->right->right];
    }
    if(root->left){
      if(map[root->left]) left = map[root->left];
      else {
        left = rob(root->left);
        map[root->left] = left;
      }
      if(!map[root->left->left]) {
        map[root->left->left] = rob(root->left->left);
      }
      grandson += map[root->left->left];
      if(!map[root->left->right]) map[root->left->left] = rob(root->left->right);
      grandson += map[root->left->right];
    }
    return max(root->val + grandson, left + right);
  }
};

树形dp

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    // 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷cur，那么就不能偷左右节点。
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};