2023-04-03：给定一个数组arr，和一个正数k
你可以随意删除arr中的数字，最多删除k个
目的是让连续出现一种数字的长度尽量长
返回这个尽量长的长度
比如数组arr = { 3, -2, 3, 3, 5, 6, 3, -2 }, k = 3
你可以删掉-2、5、6(最多3个)，这样数组arr = { 3, 3, 3, 3, -2 }
可以看到连续出现3的长度为4
这是所有删除方法里的最长结果，所以返回4
1 <= arr长度 <= 3 * 10^5
-10^9 <= arr中的数值 <= 10^9
0 <= k <= 3 * 10^5
来自亚马逊。
答案2023-04-03：
算法1：暴力回溯算法
1.定义一个表示当前子序列的数组 path，初始时全部置为 0。
2.在 process1 函数中，首先判断删除次数 k 是否小于 0。如果是，则返回 0。
3.然后判断当前下标 i 是否等于 arr 的长度。如果是，则说明已经遍历到了数组末尾，需要统计当前子序列中最长的连续相同元素的长度，并返回该长度。
4.如果当前下标 i 小于 arr 的长度，则有两种情况：
选择保留当前元素：把当前元素加入到 path 数组末尾，然后递归调用 process1 函数，更新 path、size 和 i 的值。
选择删除当前元素：将 k 的值减 1，然后递归调用 process1 函数，更新 size 和 i 的值。
5.最后返回两种情况的最大值。
算法2：滑动窗口算法
1.使用 HashMap 来记录每个数最后出现的位置，初始化答案 ans 为 1。
2.遍历数组 arr，对于数组中的每个元素 value，做如下操作：
如果 value 已经在 HashMap 中存在，则取出它最后一次出现的位置 indies，将其左侧超过 k 个元素的位置都从 indies 中删除（即删除长度超过 k 的区间），并将当前位置 i 加入 indies 末尾。
如果 value 在 HashMap 中不存在，则新建一个 LinkedList，将当前位置 i 加入其中。
更新 ans 为 indies 的长度和 ans 中的较大值。
3.遍历完数组后返回 ans。
两种算法中，暴力回溯算法时间复杂度为 O(2^n)，空间复杂度为 O(n)。滑动窗口算法时间复杂度为 O(n)，空间复杂度为 O(n)。其中，滑动窗口算法在处理大规模数据时更加高效。
rust完整代码如下：
代码语言：rust复制use rand::Rng;
use std::collections::HashMap;
use std::collections::LinkedList;
pub fn longest1(arr: &[i32], k: i32) -> i32 {
let mut path = vec![0; arr.len()];
process1(arr, 0, &mut path, 0, k)
}
fn process1(arr: &[i32], i: usize, path: &mut [i32], size: usize, k: i32) -> i32 {
if k < 0 {
return 0;
} else if i == arr.len() {
if size == 0 {
return 0;
}
let mut ans = 0;
let mut cnt = 1;
for j in 1..size {
if path[j - 1] != path[j] {
ans = ans.max(cnt);
cnt = 1;
} else {
cnt = 1;
}
}
ans = ans.max(cnt);
return ans;
} else {
path[size] = arr[i];
let p1 = process1(arr, i 1, path, size 1, k);
let p2 = process1(arr, i 1, path, size, k - 1);
return p1.max(p2);
}
}
pub fn longest2(arr: &[i32], k: i32) -> i32 {
let mut value_indies = HashMap::<i32, LinkedList<usize>>::new();
let mut ans = 1;
for (i, &value) in arr.iter().enumerate() {
let indies = value_indies.entry(value).or_insert(LinkedList::new());
while !indies.is_empty() && i - indies.front().unwrap() - indies.len() as usize > k as usize
{
indies.pop_front();
}
indies.push_back(i);
ans = ans.max(indies.len() as i32);
}
ans
}
pub fn random_array(n: usize, v: i32) -> Vec<i32> {
let mut ans = vec![0; n];
for i in 0..n {
ans[i] = rand::thread_rng().gen_range(-v, v 1);
}
ans
}
pub fn main() {
let n = 20;
let v = 10;
let k = 5;
let test_time = 5000;
println!("测试开始");
for _ in 0..test_time {
let n = rand::thread_rng().gen_range(1, n 1);
let arr = random_array(n, v);
let k = rand::thread_rng().gen_range(0, k);
let ans1 = longest1(&arr, k);
let ans2 = longest2(&arr, k);
if ans1 != ans2 {
println!("出错了!");
}
}
println!("测试结束");
}
