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;
}
