Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LeetCode 213. 打家劫舍 II #67

Open
Chocolate1999 opened this issue Oct 6, 2020 · 0 comments
Open

LeetCode 213. 打家劫舍 II #67

Chocolate1999 opened this issue Oct 6, 2020 · 0 comments
Labels
动态规划 动态规划DP

Comments

@Chocolate1999
Copy link
Owner

仰望星空的人,不应该被嘲笑

题目描述

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

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

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2, 因为他们是相邻的。

示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/house-robber-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

这道题相比于198.打家劫舍 更有趣味一点,房子变成环状的了,那么我们就没办法同时取第一个房子和最后一个房子了,但是我们依然可以使用单向排列的代码,我们直接进行两次遍历不就好了吗,第一次遍历,我们不偷第一家房子,取得单向排列的最大值,第二次遍历,我们不偷最后一家房子,取得单向排列的最大值,那么最终结果就是这两个最大值中的最大值!

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
    // 对于长度为 0 和 1进行特判一下
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];
    let arr1 = nums.slice();
    arr1.shift();
    let arr2 = nums.slice();
    arr2.pop();
    // 求不偷第一家房子和不偷最后一家房子的单向排列的最大值
    return Math.max(oneRob(arr1), oneRob(arr2));
}
var oneRob = function (nums) {
    let n = nums.length;
    if (n === 0) return 0; // 长度为0 值为0
    if (n === 1) return nums[0]; // 长度为1,默认最多就当前值
    if (n === 2) return Math.max(nums[0], nums[1]); // 长度为2,由于不能相邻偷,就取最大
    let dp = [];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    // 当前能够偷的金额总和,就看前一家房子的金额加上当前金额,与相邻房间比较
    for (let i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    // 最后就看最后两间房子金额总和的最大值
    return Math.max(dp[n - 1], dp[n - 2]);
};

最后

文章产出不易,还望各位小伙伴们支持一波!

往期精选:

小狮子前端の笔记仓库

leetcode-javascript:LeetCode 力扣的 JavaScript 解题仓库,前端刷题路线(思维导图)

小伙伴们可以在Issues中提交自己的解题代码,🤝 欢迎Contributing,可打卡刷题,Give a ⭐️ if this project helped you!

访问超逸の博客,方便小伙伴阅读玩耍~

学如逆水行舟,不进则退
@Chocolate1999 Chocolate1999 added the 动态规划 动态规划DP label Oct 6, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
动态规划 动态规划DP
Projects
None yet
Development

No branches or pull requests

1 participant