class Solution {
public:
int maximumLength(vector<int>& nums, int k) {
}
};
100327. 求出最长好子序列 II
给你一个整数数组 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 <= 5 * 1031 <= nums[i] <= 1090 <= k <= min(50, nums.length)原站题解
golang 解法, 执行用时: 18 ms, 内存消耗: 9.6 MB, 提交时间: 2024-06-10 00:27:52
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 解法, 执行用时: 784 ms, 内存消耗: 19.2 MB, 提交时间: 2024-06-10 00:27:06
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 解法, 执行用时: 17 ms, 内存消耗: 44.5 MB, 提交时间: 2024-06-10 00:26:09
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 解法, 执行用时: 61 ms, 内存消耗: 44.4 MB, 提交时间: 2024-06-10 00:24:52
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];
}
};