打家劫舍 II

213. 打家劫舍 II

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1,2,3]
输出：3

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 1000

相似题目

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int rob(vector<int>& nums) { } };

php 解法, 执行用时: 4 ms, 内存消耗: 18.9 MB, 提交时间: 2023-09-17 10:01:16

class Solution {

    /**
     * 打家劫舍 II
     * @access public
     * @param array $num
     * @return int
     */
    public function rob(array $num = []): int
    {
        $length = count($num);

        if ($length == 1) {
            return $num[0];
        } else if ($length == 2) {
            return max($num[0], $num[1]);
        }

        return max($this->doRob($num, 0, $length-2), $this->doRob($num, 1, $length-1));
    }

    /**
     * 处理打家劫舍
     * @access private
     * @param array $num
     * @param int $start
     * @param int $end
     * @return int
     */
    private function doRob(array $num = [], $start = 0, $end = 0): int
    {
        $first = $num[$start];
        $second = max($num[$start], $num[$start+1]);
        for ($i= $start + 2; $i <= $end; $i++) { 
            $temp = $second;
            $second = max($first + $num[$i], $second);
            $first = $temp;
        }
        return $second;
    }
}

python3 解法, 执行用时: 44 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-17 10:00:11

class Solution:
    # 198. 打家劫舍
    def rob1(self, nums: List[int]) -> int:
        f0 = f1 = 0
        for x in nums:
            f0, f1 = f1, max(f1, f0 + x)
        return f1

    def rob(self, nums: List[int]) -> int:
        return max(nums[0] + self.rob1(nums[2:-1]), self.rob1(nums[1:]))

rust 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-09-16 11:06:24

impl Solution {
    pub fn rob2(nums: Vec<i32>) -> i32 {
        nums[0..(nums.len() - 1)].iter().
        fold((0, 0), |(a, b), &x| (b, b.max(a + x))).1
        .max(
            nums[1..nums.len()]
            .iter()
            .fold((0, 0), |(a, b), &x| (b, b.max(a + x))).1
        )
        .max(nums[0])
    }

    pub fn rob(nums: Vec<i32>) -> i32 {
        if nums.len() == 1 {
            return nums[0];
        }
        let mut dp0 = vec![0; nums.len()];
        let mut dp1 = vec![0; nums.len()];
        dp0[1] = nums[0];
        dp1[1] = nums[1];
        for i in 2..nums.len() {
            dp0[i] = dp0[i - 1].max(dp0[i - 2] + nums[i - 1]);
            dp1[i] = dp1[i - 1].max(dp1[i - 2] + nums[i]);
        }
        *dp0.last().unwrap().max(dp1.last().unwrap())
    }
}

cpp 解法, 执行用时: 0 ms, 内存消耗: 7.8 MB, 提交时间: 2023-09-16 11:03:44

class Solution {
public:
    int robRange(vector<int>& nums, int start, int end) {
        int first = nums[start], second = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

    int rob(vector<int>& nums) {
        int length = nums.size();
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return max(nums[0], nums[1]);
        }
        return max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }
};

python3 解法, 执行用时: 36 ms, 内存消耗: 15.8 MB, 提交时间: 2023-09-16 11:03:17

class Solution:
    def rob(self, nums: List[int]) -> int:
        def robRange(start: int, end: int) -> int:
            first = nums[start]
            second = max(nums[start], nums[start + 1])
            for i in range(start + 2, end + 1):
                first, second = second, max(first + nums[i], second)
            return second
        
        length = len(nums)
        if length == 1:
            return nums[0]
        elif length == 2:
            return max(nums[0], nums[1])
        else:
            return max(robRange(0, length - 2), robRange(1, length - 1))

javascript 解法, 执行用时: 60 ms, 内存消耗: 40.7 MB, 提交时间: 2023-09-16 11:03:05

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const length = nums.length;
    if (length === 1) {
        return nums[0];
    } else if (length === 2) {
        return Math.max(nums[0], nums[1]);
    }
    return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
};

const robRange = (nums, start, end) => {
    let first = nums[start], second = Math.max(nums[start], nums[start + 1]);
    for (let i = start + 2; i <= end; i++) {
        const temp = second;
        second = Math.max(first + nums[i], second);
        first = temp;
    }
    return second;
}

java 解法, 执行用时: 0 ms, 内存消耗: 39 MB, 提交时间: 2023-09-16 11:02:53

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }

    public int robRange(int[] nums, int start, int end) {
        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2021-07-18 09:01:35

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    if n == 2 {
        return max(nums[0], nums[1])
    }
    return max(_rob(nums[:n-1]), _rob(nums[1:]))
}

func _rob(nums []int) int {
    first, second := nums[0], max(nums[0], nums[1])
    for _, v := range nums[2:] {
        first, second = second, max(first+v, second)
    }
    return second
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

上一题

下一题

详情