2025-01-12：求出最长好子序列Ⅱ。用go语言，给定一个整数数组 nums 和一个非负整数 k，我们认为一个整数序列 se

福大大架构师每日一题

发布于 2025-01-13 12:31:53

9200

代码可运行

运行总次数：0

代码可运行

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

fnmaximum_length(nums: Vec<i32>, k: i32) ->i32 {
    letlen_nums = nums.len();
    letmut dp: HashMap<i32, Vec<i32>> = HashMap::new();
    letmut zd = vec![0; (k + 1) asusize];

    foriin0..len_nums {
        letv = nums[i];
        dp.entry(v).or_insert(vec![0; (k + 1) asusize]);
        lettmp = dp.get_mut(&v).unwrap();
        forjin0..=k {
            tmp[j asusize] += 1;
            if j > 0 {
                tmp[j asusize] = tmp[j asusize].max(zd[(j - 1) asusize] + 1);
            }
        }
        forjin0..=k {
            zd[j asusize] = zd[j asusize].max(tmp[j asusize]);
        }
    }

    return zd[k asusize];
}

fnmain() {
    letnums = vec![1, 2, 1, 1, 3];
    letk = 2;
    letresult = 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;

    return0;
}

Python完整代码如下：

def maximum_length(nums, k):
    len_nums = len(nums)
    dp = {}
    zd = [0] * (k + 1)

    for i inrange(len_nums):
        v = nums[i]
        if v notin dp:
            dp[v] = [0] * (k + 1)

        tmp = dp[v]
        for j inrange(k + 1):
            tmp[j] += 1
            if j > 0:
                tmp[j] = max(tmp[j], zd[j - 1] + 1)

        for j inrange(k + 1):
            zd[j] = max(zd[j], tmp[j])

    return zd[k]


defmain():
    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 = newArray(k + 1).fill(0);

    for (let i = 0; i < lenNums; i++) {
        let v = nums[i];
        if (!(v in dp)) {
            dp[v] = newArray(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;

publicclassMain {

    publicstaticintmaximumLength(int[] nums, int k) {
        intlenNums= nums.length;
        Map<Integer, int[]> dp = newHashMap<>();
        int[] zd = newint[k + 1];

        for (inti=0; i < lenNums; i++) {
            intv= nums[i];
            if (!dp.containsKey(v)) {
                dp.put(v, newint[k + 1]);
            }

            int[] tmp = dp.get(v);
            for (intj=0; j <= k; j++) {
                tmp[j]++;
                if (j > 0) {
                    tmp[j] = Math.max(tmp[j], zd[j - 1] + 1);
                }
            }

            for (intj=0; j <= k; j++) {
                zd[j] = Math.max(zd[j], tmp[j]);
            }
        }
        return zd[k];
    }

    publicstaticvoidmain(String[] args) {
        int[] nums = {1, 2, 1, 1, 3};
        intk=2;
        intresult= maximumLength(nums, k);
        System.out.println(result);
    }
}