2025-01-12：求出最长好子序列Ⅱ。用go语言，给定一个整数数组 nums 和一个非负整数 k，我们认为一个整数序列 seq 是“好序列”，当且仅当在索引范围 [0, seq.length - 2] 内，最多有 k 个位置 i 满足 seq[i] 与 seq[i + 1] 不相等。

你的任务是找出 nums 中的“好子序列”的最长长度。

1 <= nums.length <= 5 * 1000。

1 <= nums[i] <= 1000000000。

0 <= k <= min(50, nums.length)。

输入：nums = [1,2,1,1,3], k = 2。

输出：4。

解释：

最长好子序列为 [1,2,1,1,3] 中的1,2,1,1。

答案2025-01-12：

chatgpt[1]

题目来自leetcode3177。

大体步骤如下：1. 首先定义了一个名为 maximumLength 的函数，它接收一个整数数组 nums 和一个非负整数 k 作为参数，返回一个整数值。2. 在函数中，首先初始化变量 lenNums 为数组 nums 的长度，创建一个映射 dp 用于存储计数信息，以及一个长度为 k+1 的数组 zd 用于存储结果。3. 接下来，对数组 nums 进行遍历，取出每个数字，并检查该数字是否在映射 dp 中。如果不在，则在 dp 中创建以该数字为 key 的数组，长度为 k+1。4. 对于每个数字，更新对应的数组 tmp，并根据规则进行更新，其中 max 函数用于取两者中的最大值。5. 最后更新数组 zd 的值，保持最大长度信息。6. 返回数组 zd 中索引为 k 的值作为最终结果。

总的时间复杂度较高，大致为 O(n*k)，其中 n 为 nums 数组的长度，k 为参数传入的非负整数。

总的额外空间复杂度也较高，为 O(n*k)。

Go完整代码如下：package mainimport ( "fmt")func maximumLength(nums []int, k int) int { lenNums := len(nums) dp := make(map[int][]int) zd := make([]int, k + 1) for i := 0; i < lenNums; i++ { v := nums[i] if _, ok := dp[v]; !ok { dp[v] = make([]int, k + 1) } tmp := dp[v] for j := 0; j <= k; j++ { tmp[j]++ if j > 0 { tmp[j] = max(tmp[j], zd[j - 1] + 1) } } for j := 0; j <= k; j++ { zd[j] = max(zd[j], tmp[j]) } } return zd[k]}func main() { nums := []int{1,2,1,1,3} k := 2 result := maximumLength(nums,k) fmt.Println(result)}

在这里插入图片描述

Rust完整代码如下：use std::collections::HashMap;fn maximum_length(nums: Vec<i32>, k: i32) -> i32 { let len_nums = nums.len(); let mut dp: HashMap<i32, Vec<i32>> = HashMap::new(); let mut zd = vec![0; (k + 1) as usize]; for i in 0..len_nums { let v = nums[i]; dp.entry(v).or_insert(vec![0; (k + 1) as usize]); let tmp = dp.get_mut(&v).unwrap(); for j in 0..=k { tmp[j as usize] += 1; if j > 0 { tmp[j as usize] = tmp[j as usize].max(zd[(j - 1) as usize] + 1); } } for j in 0..=k { zd[j as usize] = zd[j as usize].max(tmp[j as usize]); } } return zd[k as usize];}fn main() { let nums = vec![1, 2, 1, 1, 3]; let k = 2; let result = maximum_length(nums, k); println!("{}", result);}

在这里插入图片描述

C++完整代码如下：#include <iostream>#include <vector>#include <unordered_map>#include <algorithm>int maximumLength(std::vector<int>& nums, int k) { int lenNums = nums.size(); std::unordered_map<int, std::vector<int>> dp; std::vector<int> zd(k + 1, 0); for (int i = 0; i < lenNums; i++) { int v = nums[i]; if (dp.find(v) == dp.end()) { dp[v] = std::vector<int>(k + 1, 0); } std::vector<int>& tmp = dp[v]; for (int j = 0; j <= k; j++) { tmp[j]++; if (j > 0) { tmp[j] = std::max(tmp[j], zd[j - 1] + 1); } } for (int j = 0; j <= k; j++) { zd[j] = std::max(zd[j], tmp[j]); } } return zd[k];}int main() { std::vector<int> nums = {1, 2, 1, 1, 3}; int k = 2; int result = maximumLength(nums, k); std::cout << result << std::endl; return 0;}

在这里插入图片描述

Python完整代码如下：def maximum_length(nums, k): len_nums = len(nums) dp = {} zd = [0] * (k + 1) for i in range(len_nums): v = nums[i] if v not in dp: dp[v] = [0] * (k + 1) tmp = dp[v] for j in range(k + 1): tmp[j] += 1 if j > 0: tmp[j] = max(tmp[j], zd[j - 1] + 1) for j in range(k + 1): zd[j] = max(zd[j], tmp[j]) return zd[k]def main(): nums = [1, 2, 1, 1, 3] k = 2 result = maximum_length(nums, k) print(result)if __name__ == "__main__": main()

在这里插入图片描述

JavaScript完整代码如下：function maximumLength(nums, k) { let lenNums = nums.length; let dp = {}; let zd = new Array(k + 1).fill(0); for (let i = 0; i < lenNums; i++) { let v = nums[i]; if (!(v in dp)) { dp[v] = new Array(k + 1).fill(0); } let tmp = dp[v]; for (let j = 0; j <= k; j++) { tmp[j]++; if (j > 0) { tmp[j] = Math.max(tmp[j], zd[j - 1] + 1); } } for (let j = 0; j <= k; j++) { zd[j] = Math.max(zd[j], tmp[j]); } } return zd[k];}let nums = [1, 2, 1, 1, 3];let k = 2;let result = maximumLength(nums, k);console.log(result);

在这里插入图片描述

Java完整代码如下：import java.util.HashMap;import java.util.Map; public Main { public static int maximumLength(int[] nums, int k) { int lenNums = nums.length; Map<Integer, int[]> dp = new HashMap<>(); int[] zd = new int[k + 1]; for (int i = 0; i < lenNums; i++) { int v = nums[i]; if (!dp.containsKey(v)) { dp.put(v, new int[k + 1]); } int[] tmp = dp.get(v); for (int j = 0; j <= k; j++) { tmp[j]++; if (j > 0) { tmp[j] = Math.max(tmp[j], zd[j - 1] + 1); } } for (int j = 0; j <= k; j++) { zd[j] = Math.max(zd[j], tmp[j]); } } return zd[k]; } public static void main(String[] args) { int[] nums = {1, 2, 1, 1, 3}; int k = 2; int result = maximumLength(nums, k); System.out.println(result); }}

在这里插入图片描述

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP