写点什么

2025-01-11:求出最长好子序列Ⅰ。用 go 语言,给定一个整数数组 nums 和一个非负整数 k,我们需要找出满足特定条件的子序列。 具体来说,如果一个整数序列 seq 在下标范围 [0, seq

  • 2025-01-11
    北京
  • 本文字数:2895 字

    阅读完需:约 9 分钟

2025-01-11:求出最长好子序列Ⅰ。用 go 语言,给定一个整数数组 nums 和一个非负整数 k,我们需要找出满足特定条件的子序列。


具体来说,如果一个整数序列 seq 在下标范围 [0, seq.length - 2] 内最多有 k 个下标 i 使得 seq[i] 不等于 seq[i + 1],我们就称这个整数序列为“好序列”。


我们的目标是返回数组 nums 中“好子序列”的最长长度。


1 <= nums.length <= 500。


1 <= nums[i] <= 1000000000。


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


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


输出:4。


解释:


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


答案 2025-01-11:


chatgpt


题目来自 leetcode3176。

大体步骤如下:

1.定义一个名为 maximumLength 的函数,接收一个整数数组 nums 和一个非负整数 k 作为参数,返回最长好子序列的长度。


2.创建一个空间为 (k+1) 的整型数组 zd,用于存储最终的结果。


3.创建一个空的 map dp,用于保存每个数字 v(nums 中的元素)对应的一个长度为 k+1 的动态数组。


4.遍历整数数组 nums,对于每个元素 v,若该元素不在 map 中,则在 map 中新建一个 k+1 长度的数组。


5.对于当前元素 v,从 0 到 k 遍历,利用动态数组 tmp 记录(i, j)的好子序列的长度为多少。


6.在内部遍历时,逐个更新 tmp 数组,如果 j 大于 0,则比较 tmp[j] 的值和 zd[j-1] + 1 的值的大小,取较大值。


7.在内部遍历结束后,更新 zd 数组,比较 zd[j]tmp[j] 以及 zd[j-1] 的值,取较大值。


8.返回 zd[k],即最终结果。


总的时间复杂度:


  • 遍历整数数组 nums 需要 O(n)的时间复杂度,其中 n 为nums数组的长度。

  • 内部的循环在 k 范围内,所以是 O(k)。

  • 因此,总的时间复杂度为 O(n*k)。


总的额外空间复杂度:


  • 需要一个大小为 (k+1) 的数组 zd 存储结果,一个 map dp 存储动态数组,一个长度为 k+1 的数组 tmp 用于临时存储好子序列长度。

  • 所以总的额外空间复杂度为 O(k)。


因此,根据所描述的操作和代码,整个算法的时间复杂度为 O(n*k),额外空间复杂度为 O(k),其中 n 为数组 nums 的长度,k 为传入的非负整数 k 的值。

Go 完整代码如下:

package main
import ( "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]) if j > 0 { zd[j] = max(zd[j], zd[j - 1]) } } } 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 max(a: i32, b: i32) -> i32 { if a > b { a } else { b }}
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<i32> = vec![0; (k + 1) as usize];
for i in 0..len_nums { let v = nums[i]; if !dp.contains_key(&v) { dp.insert(v, vec![0; (k + 1) as usize]); }
let mut tmp = dp.get_mut(&v).unwrap(); for j in 0..=k { tmp[j as usize] += 1; if j > 0 { tmp[j as usize] = max(tmp[j as usize], zd[(j - 1) as usize] + 1); } }
for j in 0..=k { zd[j as usize] = max(zd[j as usize], tmp[j as usize]); if j > 0 { zd[j as usize] = max(zd[j as usize], zd[(j - 1) 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]); if (j > 0) { zd[j] = std::max(zd[j], zd[j - 1]); } } } 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):    dp = {}    zd = [0] * (k + 1)
for v in nums: 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]) if j > 0: zd[j] = max(zd[j], zd[j - 1])
return zd[k]
if __name__ == "__main__": nums = [1, 2, 1, 1, 3] k = 2 result = maximum_length(nums, k) print(result)
复制代码


JavaScript 完整代码如下:

function maximumLength(nums, k) {    let dp = {};    let zd = new Array(k + 1).fill(0);
for (let i = 0; i < nums.length; i++) { let v = nums[i]; if (!dp[v]) { 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]); if (j > 0) { zd[j] = Math.max(zd[j], zd[j - 1]); } } } return zd[k];}
let nums = [1, 2, 1, 1, 3];let k = 2;let result = maximumLength(nums, k);console.log(result);
复制代码



发布于: 刚刚阅读数: 2
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2025-01-11:求出最长好子序列Ⅰ。用go语言,给定一个整数数组 nums 和一个非负整数 k,我们需要找出满足特定条件的子序列。 具体来说,如果一个整数序列 seq 在下标范围 [0, seq_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区