2022-08-06：给定一个数组arr，长度为N，arr中所有的值都在1~K范围上，
你可以删除数字，目的是让arr的最长递增子序列长度小于K。
返回至少删除几个数字能达到目的。
N <= 10^4，K <= 10^2。
来自京东。4.2笔试。
答案2022-08-06：
动态规划。
时间复杂度：O(NK)。
额外空间复杂度：O(NK)。
rust和typescript的代码都有。
代码用rust编写。代码如下：
use rand::Rng;
fn main() {
let nn: i32 = 15;
let kk: i32 = 6;
let test_time: i32 = 10000;
println!("测试开始");
for _ in 0..test_time {
let len = rand::thread_rng().gen_range(0, nn) + 1;
let k = rand::thread_rng().gen_range(0, kk) + 1;
let mut arr = random_array(len, k);
let ans1 = min_remove1(&mut arr, k);
let ans2 = min_remove2(&mut arr, k);
if ans1 != ans2 {
println!("ans1 = {:?}", ans1);
println!("ans2 = {:?}", ans2);
println!("出错了!");
break;
}
}
println!("测试结束");
}
// 暴力方法
// 为了验证
fn min_remove1(arr: &mut Vec<i32>, k: i32) -> i32 {
let mut path0: Vec<i32> = vec![];
for _ in 0..arr.len() {
path0.push(0);
}
return process1(arr, 0, &mut path0, 0, k);
}
const MAX_VALUE: i32 = 2 << 31 - 1;
fn process1(arr: &mut Vec<i32>, index: i32, path0: &mut Vec<i32>, size: i32, k: i32) -> i32 {
if index == arr.len() as i32 {
return if length_of_lis(path0, size) < k {
arr.len() as i32 - size
} else {
MAX_VALUE
};
} else {
let p1 = process1(arr, index + 1, path0, size, k);
path0[size as usize] = arr[index as usize];
let p2 = process1(arr, index + 1, path0, size + 1, k);
return get_min(p1, p2);
}
}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
fn length_of_lis(arr: &mut Vec<i32>, size: i32) -> i32 {
if size == 0 {
return 0;
}
let mut ends: Vec<i32> = vec![];
for _ in 0..size {
ends.push(0);
}
ends[0] = arr[0];
let mut right: i32 = 0;
let mut l;
let mut r;
let mut m;
let mut max = 1;
for i in 1..size {
l = 0;
r = right;
while l <= r {
m = (l + r) / 2;
if arr[i as usize] > ends[m as usize] {
l = m + 1;
} else {
r = m - 1;
}
}
right = get_max(right, l);
ends[l as usize] = arr[i as usize];
max = get_max(max, l + 1);
}
return max;
}
// arr[0...index-1]上，选择了一些数字，之前的决定！
// len长度了！len = 3 ： 1 2 3
// arr[index....]是能够决定的，之前的，已经不能再决定了
// 返回：让最终保留的数字，凑不足k长度的情况下，至少要删几个！
fn zuo(arr: &mut Vec<i32>, index: i32, len: i32, k: i32) -> i32 {
if len == k {
return MAX_VALUE;
}
// 凑的(1...len)还不到(1...k)
if index == arr.len() as i32 {
return 0;
}
// 没凑到 < k, 有数字!
let cur = arr[index as usize];
// 可能性1：保留
// 可能性2：删除
// 1...3 3
if len >= cur || len + 1 < cur {
return zuo(arr, index + 1, len, k);
}
// 1..3 4
// len + 1 == cur
// 可能性1：保留
let p1 = zuo(arr, index + 1, len + 1, k);
// 可能性2：删除
let mut p2 = MAX_VALUE;
let next2 = zuo(arr, index + 1, len, k);
if next2 != MAX_VALUE {
p2 = 1 + next2;
}
return get_min(p1, p2);
}
// 正式方法
// 时间复杂度O(N*K)
fn min_remove2(arr: &mut Vec<i32>, k: i32) -> i32 {
let n = arr.len() as i32;
let mut dp: Vec<Vec<i32>> = vec![];
for i in 0..n {
dp.push(vec![]);
for _ in 0..k {
dp[i as usize].push(0);
}
}
for i in 0..n {
for j in 0..k {
dp[i as usize][j as usize] = -1;
}
}
return process2(arr, k, 0, 0, &mut dp);
}
fn process2(arr: &mut Vec<i32>, k: i32, index: i32, range: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
if range == k {
return MAX_VALUE;
}
if index == arr.len() as i32 {
return 0;
}
if dp[index as usize][range as usize] != -1 {
return dp[index as usize][range as usize];
}
let mut ans: i32;
if arr[index as usize] == range + 1 {
let mut p1 = process2(arr, k, index + 1, range, dp);
p1 += if p1 != MAX_VALUE { 1 } else { 0 };
let p2 = process2(arr, k, index + 1, range + 1, dp);
ans = get_min(p1, p2);
} else {
ans = process2(arr, k, index + 1, range, dp);
}
dp[index as usize][range as usize] = ans;
return ans;
}
// 为了测试
fn random_array(len: i32, k: i32) -> Vec<i32> {
let mut arr: Vec<i32> = vec![];
for _ in 0..len {
arr.push(rand::thread_rng().gen_range(0, k) + 1);
}
return arr;
}
执行结果如下：
代码用typescript编写。代码如下：
// 暴力方法
// 为了验证
function minRemove1(arr: number[], k: number): number {
return process1(arr, 0, new Array(arr.length), 0, k);
}
var MAX_VALUE: number = 2147483647;
function process1(
arr: number[],
index: number,
path: number[],
size: number,
k: number
): number {
if (index == arr.length) {
return lengthOfLIS(path, size) < k ? arr.length - size : MAX_VALUE;
} else {
var p1: number = process1(arr, index + 1, path, size, k);
path[size] = arr[index];
var p2: number = process1(arr, index + 1, path, size + 1, k);
return Math.min(p1, p2);
}
}
function lengthOfLIS(arr: number[], size: number): number {
if (size == 0) {
return 0;
}
var ends: number[] = new Array(size);
ends[0] = arr[0];
var right: number = 0;
var l: number = 0;
var r: number = 0;
var m: number = 0;
var max: number = 1;
for (var i: number = 1; i < size; i++) {
l = 0;
r = right;
while (l <= r) {
m = Math.floor((l + r) / 2);
if (arr[i] > ends[m]) {
l = m + 1;
} else {
r = m - 1;
}
}
right = Math.max(right, l);
ends[l] = arr[i];
max = Math.max(max, l + 1);
}
return max;
}
// arr[0...index-1]上，选择了一些数字，之前的决定！
// len长度了！len = 3 ： 1 2 3
// arr[index....]是能够决定的，之前的，已经不能再决定了
// 返回：让最终保留的数字，凑不足k长度的情况下，至少要删几个！
function zuo(arr: number[], index: number, len: number, k: number): number {
if (len == k) {
return MAX_VALUE;
}
// 凑的(1...len)还不到(1...k)
if (index == arr.length) {
return 0;
}
// 没凑到 < k, 有数字!
var cur: number = arr[index];
// 可能性1：保留
// 可能性2：删除
// 1...3 3
if (len >= cur || len + 1 < cur) {
return zuo(arr, index + 1, len, k);
}
// 1..3 4
// len + 1 == cur
// 可能性1：保留
var p1: number = zuo(arr, index + 1, len + 1, k);
// 可能性2：删除
var p2: number = MAX_VALUE;
var next2: number = zuo(arr, index + 1, len, k);
if (next2 != MAX_VALUE) {
p2 = 1 + next2;
}
return Math.min(p1, p2);
}
// 正式方法
// 时间复杂度O(N*K)
function minRemove2(arr: number[], k: number): number {
var n: number = arr.length;
var dp: number[][] = new Array(n);
for (var i: number = 0; i < n; i++) {
dp[i] = new Array(k);
}
for (var i: number = 0; i < n; i++) {
for (var j: number = 0; j < k; j++) {
dp[i][j] = -1;
}
}
return process2(arr, k, 0, 0, dp);
}
function process2(
arr: number[],
k: number,
index: number,
range: number,
dp: number[][]
): number {
if (range == k) {
return MAX_VALUE;
}
if (index == arr.length) {
return 0;
}
if (dp[index][range] != -1) {
return dp[index][range];
}
var ans: number = 0;
if (arr[index] == range + 1) {
var p1: number = process2(arr, k, index + 1, range, dp);
p1 += p1 != MAX_VALUE ? 1 : 0;
var p2: number = process2(arr, k, index + 1, range + 1, dp);
ans = Math.min(p1, p2);
} else {
ans = process2(arr, k, index + 1, range, dp);
}
dp[index][range] = ans;
return ans;
}
// 为了验证
function randomArray(len: number, k: number): number[] {
var arr: number[] = new Array(len);
for (var i: number = 0; i < len; i++) {
arr[i] = Math.floor(Math.random() * k) + 1;
}
return arr;
}
// 为了验证
function main() {
var N: number = 15;
var K: number = 6;
var testTime: number = 10000;
console.log("测试开始");
for (var i: number = 0; i < testTime; i++) {
var len: number = Math.floor(Math.random() * N) + 1;
var k: number = Math.floor(Math.random() * K) + 1;
var arr: number[] = randomArray(len, k);
var ans1: number = minRemove1(arr, k);
var ans2: number = minRemove2(arr, k);
if (ans1 != ans2) {
console.log("出错了！");
arr.forEach(function (num) {
console.log(num + " ");
});
console.log();
console.log("k : " + k);
console.log("ans1 : " + ans1);
console.log("ans2 : " + ans2);
break;
}
}
console.log("测试结束");
}
main();
执行结果如下：
左神java代码
