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]
,即最终结果。
总的时间复杂度:
总的额外空间复杂度:
因此,根据所描述的操作和代码,整个算法的时间复杂度为 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);
复制代码
评论