2023-11-01：用 go 语言，沿街有一排连续的房屋。每间房屋内都藏有一定的现金，
现在有一位小偷计划从这些房屋中窃取现金，
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋，
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额，
给你一个整数数组 nums 表示每间房屋存放的现金金额，
形式上，从左起第 i 间房屋中放有 nums[i] 美元，
另给你一个整数 k ，表示窃贼将会窃取的最少房屋数。
小偷一定要要窃取至少 k 间房屋，返回小偷的 最小 窃取能力。
输入：nums = [2,3,5,9], k = 2。
输出：5。
来自左程云。
答案 2023-11-01：
go 代码用 chatgpt 编写，不需要修改。
rust、c++、c 代码用 灵捷 3.5 编写，不需要修改，个人怀疑是调用了 chatgpt 的 api，问了一下，并不是用的 chatgpt。
大体步骤如下：
1.如果房屋数量为 0，则返回 0。
2.如果房屋数量为 1，则返回该房屋内的现金金额。
3.如果房屋数量为 2，则返回较大金额的房屋的现金金额。
4.初始化变量 lastLast 为第一个房屋的现金金额，last 为第一和第二个房屋中较大金额的现金金额。
5.从第三个房屋开始，循环遍历每个房屋：
计算两种情况下的窃取金额：不窃取当前房屋的金额 p1，窃取当前房屋的金额与上上个房屋的金额之和 p2。
取两者中较大的金额为当前房屋窃取的最大金额 cur。
更新 lastLast 和 last 为上一个房屋的现金金额 last 和当前房屋的现金金额 cur。
6.返回最后一个房屋的现金金额 last 作为小偷的最小窃取能力。
总的时间复杂度为 O(n)，其中 n 是房屋的数量。总的额外空间复杂度为 O(1)，只需要几个变量来存储中间结果。
go 完整代码如下：
package main
import ( "fmt")
func rob(nums []int) int { n := len(nums) if n == 0 { return 0 } if n == 1 { return nums[0] } if n == 2 { return max(nums[0], nums[1]) }
lastLast := nums[0] last := max(nums[0], nums[1]) for i := 2; i < n; i++ { p1 := last p2 := nums[i] + lastLast cur := max(p1, p2) lastLast = last last = cur } return last}
func max(a, b int) int { if a > b { return a } return b}
func main() { nums := []int{1, 2, 3, 1} result := rob(nums) fmt.Println(result)}
复制代码
rust 完整代码如下：
fn rob(nums: Vec<i32>) -> i32 { let n = nums.len(); if n == 1 { return nums[0]; } if n == 2 { return nums[0].max(nums[1]); } let mut last_last = nums[0]; let mut last = nums[0].max(nums[1]); for i in 2..n { let p1 = last; let p2 = nums[i] + last_last; let cur = p1.max(p2); last_last = last; last = cur; } last}
fn main() { let nums = vec![1, 2, 3, 1]; let result = rob(nums); println!("{}", result);}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>#include <algorithm>
int rob(std::vector<int>& nums) { int n = nums.size(); if (n == 1) { return nums[0]; } if (n == 2) { return std::max(nums[0], nums[1]); }
int lastLast = nums[0]; int last = std::max(nums[0], nums[1]); for (int i = 2; i < n; i++) { int p1 = last; int p2 = nums[i] + lastLast; int cur = std::max(p1, p2); lastLast = last; last = cur; } return last;}
int main() { std::vector<int> nums = { 1, 2, 3, 1 }; int result = rob(nums); std::cout << "Maximum amount that can be robbed: " << result << std::endl; return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdlib.h>
int rob(int* nums, int numsSize) { if (numsSize == 0) { return 0; } if (numsSize == 1) { return nums[0]; } if (numsSize == 2) { return (nums[0] > nums[1]) ? nums[0] : nums[1]; }
int lastLast = nums[0]; int last = (nums[0] > nums[1]) ? nums[0] : nums[1]; int cur;
for (int i = 2; i < numsSize; i++) { int p1 = last; int p2 = nums[i] + lastLast; cur = (p1 > p2) ? p1 : p2; lastLast = last; last = cur; } return cur;}
int main() { int nums[] = { 1, 2, 3, 1 }; int numsSize = sizeof(nums) / sizeof(nums[0]); int result = rob(nums, numsSize); printf("%d\n", result);
return 0;}
复制代码
评论