class Solution {
public:
int rob(vector<int>& nums) {
}
};
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 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-09-16 10:56:25
impl Solution {
pub fn rob(nums: Vec<i32>) -> i32 {
let mut dp = [0; 2];
for num in nums {
dp = [dp[1], (dp[0] + num).max(dp[1])];
}
dp[1]
}
pub fn rob2(nums: Vec<i32>) -> i32 {
nums.iter()
.skip(1)
.fold((nums[0], 0), |dp, &n| (dp.0, dp.0).max((dp.1 + n, dp.0)))
.0
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.7 MB, 提交时间: 2023-09-16 10:55:05
class Solution {
public:
int rob(vector<int>& nums) {
if ( nums.size() == 0 ) return 0;
if ( nums.size() == 1 ) return nums[0];
int first = nums[0];
int second = max(nums[0], nums[1]);
for ( int i = 2; i < nums.size(); i++ ) {
int temp = first;
first = second;
second = max(temp + nums[i], second);
}
return second;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 38.9 MB, 提交时间: 2023-09-16 10:37:06
class Solution {
public int rob(int[] nums) {
if ( nums.length == 0 ) return 0;
if ( nums. length == 1 ) return nums[0];
int first = nums[0];
int second = Math.max(nums[0], nums[1]);
for ( int i = 2; i < nums.length; i++ ) {
int temp = first;
first = second;
second = Math.max(temp + nums[i], second);
}
return second;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-08-18 10:37:49
func rob(nums []int) int {
if len(nums) == 0 {
return 0
}
if len(nums) == 1 {
return nums[0]
}
first := nums[0]
second := max(nums[0], nums[1])
for i := 2; i < len(nums); i++ {
first, second = second, max(first + nums[i], second)
}
return second
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2021-07-23 10:16:09
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[:]), _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
}
python3 解法, 执行用时: 44 ms, 内存消耗: 13.4 MB, 提交时间: 2020-11-19 15:33:48
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
if n == 1:
return nums[0]
first, second = nums[0], max(nums[0], nums[1])
for i in range(2, n):
first, second = second, max(first+nums[i], second)
return second