class Solution {
public:
int maximumLength(vector<int>& nums, int k) {
}
};
100331. 求出最长好子序列 I
给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。
请你返回 nums 中 好 子序列 的最长长度
示例 1：
输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1,3] 。
示例 2：
输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,2,3,4,5,1] 。
提示：
1 <= nums.length <= 5001 <= nums[i] <= 1090 <= k <= min(nums.length, 25)原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2024-09-06 09:52:39
use std::collections::HashMap;
impl Solution {
pub fn maximum_length(nums: Vec<i32>, k: i32) -> i32 {
let mut dp = HashMap::new();
let mut zd = vec![0; k as usize + 1];
for &v in &nums {
let mut tmp = dp.entry(v).or_insert(vec![0; k as usize + 1]);
for j in 0..=k as usize {
tmp[j] += 1;
if j > 0 {
tmp[j] = tmp[j].max(zd[j - 1] + 1);
}
}
for j in 0..=k as usize {
zd[j] = zd[j].max(tmp[j]);
if j > 0 {
zd[j] = zd[j].max(zd[j - 1]);
}
}
}
zd[k as usize]
}
}
javascript 解法, 执行用时: 75 ms, 内存消耗: 51.3 MB, 提交时间: 2024-09-06 09:52:14
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maximumLength = function(nums, k) {
const dp = new Map();
const zd = Array(k + 1).fill(0);
nums.forEach(v => {
if (!dp.has(v)) {
dp.set(v, Array(k + 1).fill(0));
}
const tmp = dp.get(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];
};
golang 解法, 执行用时: 5 ms, 内存消耗: 3.5 MB, 提交时间: 2024-06-10 00:28:04
func maximumLength1(nums []int, k int) int {
fs := map[int][]int{}
records := make([]struct{ mx, mx2, num int }, k+1)
for _, x := range nums {
if fs[x] == nil {
fs[x] = make([]int, k+1)
}
f := fs[x]
for j := k; j >= 0; j-- {
f[j]++
if j > 0 {
p := records[j-1]
m := p.mx
if x == p.num {
m = p.mx2
}
f[j] = max(f[j], m+1)
}
// records[j] 维护 fs[.][j] 的 mx,mx2,num
v := f[j]
p := &records[j]
if v > p.mx {
if x != p.num {
p.num = x
p.mx2 = p.mx
}
p.mx = v
} else if x != p.num && v > p.mx2 {
p.mx2 = v
}
}
}
return records[k].mx
}
// 优化
func maximumLength(nums []int, k int) int {
fs := map[int][]int{}
mx := make([]int, k+2)
for _, x := range nums {
if fs[x] == nil {
fs[x] = make([]int, k+1)
}
f := fs[x]
for j := k; j >= 0; j-- {
f[j] = max(f[j], mx[j]) + 1
mx[j+1] = max(mx[j+1], f[j])
}
}
return mx[k+1]
}
python3 解法, 执行用时: 69 ms, 内存消耗: 16.6 MB, 提交时间: 2024-06-10 00:26:51
class Solution:
def maximumLength1(self, nums: List[int], k: int) -> int:
fs = {}
records = [[0] * 3 for _ in range(k + 1)]
for x in nums:
if x not in fs:
fs[x] = [0] * (k + 1)
f = fs[x]
for j in range(k, -1, -1):
f[j] += 1
if j > 0:
mx, mx2, num = records[j - 1]
f[j] = max(f[j], (mx if x != num else mx2) + 1)
# records[j] 维护 fs[.][j] 的 mx, mx2, num
v = f[j]
p = records[j]
if v > p[0]:
if x != p[2]:
p[2] = x
p[1] = p[0]
p[0] = v
elif x != p[2] and v > p[1]:
p[1] = v
return records[k][0]
# 优化
def maximumLength(self, nums: List[int], k: int) -> int:
fs = {}
mx = [0] * (k + 2)
for x in nums:
if x not in fs:
fs[x] = [0] * (k + 1)
f = fs[x]
for j in range(k, -1, -1):
f[j] = max(f[j], mx[j]) + 1
mx[j + 1] = max(mx[j + 1], f[j])
return mx[-1]
java 解法, 执行用时: 4 ms, 内存消耗: 43.3 MB, 提交时间: 2024-06-10 00:25:54
public class Solution {
public int maximumLength1(int[] nums, int k) {
Map<Integer, int[]> fs = new HashMap<>();
int[][] records = new int[k + 1][3];
for (int x : nums) {
int[] f = fs.computeIfAbsent(x, i -> new int[k + 1]);
for (int j = k; j >= 0; j--) {
f[j]++;
if (j > 0) {
int mx = records[j - 1][0], mx2 = records[j - 1][1], num = records[j - 1][2];
f[j] = Math.max(f[j], (x != num ? mx : mx2) + 1);
}
// records[j] 维护 fs[.][j] 的 mx, mx2, num
int v = f[j];
int[] p = records[j];
if (v > p[0]) {
if (x != p[2]) {
p[2] = x;
p[1] = p[0];
}
p[0] = v;
} else if (x != p[2] && v > p[1]) {
p[1] = v;
}
}
}
return records[k][0];
}
// 优化
public int maximumLength(int[] nums, int k) {
Map<Integer, int[]> fs = new HashMap<>();
int[] mx = new int[k + 2];
for (int x : nums) {
int[] f = fs.computeIfAbsent(x, i -> new int[k + 1]);
for (int j = k; j >= 0; j--) {
f[j] = Math.max(f[j], mx[j]) + 1;
mx[j + 1] = Math.max(mx[j + 1], f[j]);
}
}
return mx[k + 1];
}
}
cpp 解法, 执行用时: 7 ms, 内存消耗: 22.9 MB, 提交时间: 2024-06-10 00:25:14
class Solution {
public:
int maximumLength1(vector<int>& nums, int k) {
unordered_map<int, vector<int>> fs;
vector<array<int, 3>> records(k + 1);
for (int x : nums) {
if (!fs.contains(x)) {
fs[x] = vector<int>(k + 1);
}
auto& f = fs[x];
for (int j = k; j >= 0; j--) {
f[j]++;
if (j) {
auto& r = records[j - 1];
int mx = r[0], mx2 = r[1], num = r[2];
f[j] = max(f[j], (x != num ? mx : mx2) + 1);
}
// records[j] 维护 fs[.][j] 的 mx, mx2, num
int v = f[j];
auto& p = records[j];
if (v > p[0]) {
if (x != p[2]) {
p[2] = x;
p[1] = p[0];
}
p[0] = v;
} else if (x != p[2] && v > p[1]) {
p[1] = v;
}
}
}
return records[k][0];
}
// 优化
int maximumLength(vector<int>& nums, int k) {
unordered_map<int, vector<int>> fs;
vector<int> mx(k + 2);
for (int x : nums) {
if (!fs.contains(x)) {
fs[x] = vector<int>(k + 1);
}
auto& f = fs[x];
for (int j = k; j >= 0; j--) {
f[j] = max(f[j], mx[j]) + 1;
mx[j + 1] = max(mx[j + 1], f[j]);
}
}
return mx[k + 1];
}
};