4.2 京东算法笔试-递增子序列的最少删除个数

题目描述：

小明有一个长度为 n 的正整数序列，序列中每个数字都在范围[1，K]内。小明现在想要删除这个序列中的若千数字，使得这个序列的最长上升子序列的长度严格小于 k。他现在想知道：最少需要删除多少个数字？

题解：如果有帮助的话，求个赞谢谢~

注：这题确实难度非常大，oj时并没有完全跑通，实现起来有点复杂，欢迎大家提出更好的实现
此外，问题转化后，与LeetCode中的《使字符串平衡的最少删除次数》是类似的，上面说的双指针解法并不能保证是最少的次数，下面的实现已经更新为枚举法，也可以用动态规划来解，具体解法参考LeetCode中的那道题即可。



import sys
from sortedcontainers import SortedDict
import bisect

m = int(input())

def get_ans(a,b):
    if not a or not b:
        return 0
    mincout = float('inf')
    for i in range(len(a)):
        index = bisect.bisect(b, a[i])
        mincout = min(mincout, i+len(b)-index)
    for j in range(len(b)):
        index = bisect.bisect(a, b[j])
        mincout = min(mincout, len(b)-1-j+index)
    return mincout

for _ in range(m):
    N, K = [int(s) for s in input().strip().split()]
    nums = [int(s) for s in input().strip().split()]

    # 数值范围在[1.k],所以不可能有长度超过k的递增子序列，最长就是k
    # 要保证每一层均是长度为k的路径上的结点
    dic = SortedDict({})
    for i in range(len(nums)):
        if nums[i] not in dic:
            dic[nums[i]] = []
        flag = 1
        for j in range(1,nums[i]): # 需要过滤比如23 123中第一个23这种无效结点的情况
            if j not in dic:
                flag = 0
                break
        if flag:
            dic[nums[i]].append(i)

    for i in range(K-1, 0, -1): # 需要过滤比如123 12中第二个12这种无效结点的情况
        if i in dic:
            if i+1 in dic:
                while dic[i] and dic[i+1] and dic[i][-1] > dic[i+1][-1]:
                    del dic[i][-1]
    
    if len(dic.keys()) != K: # 最长递增子序列长度不是k的时候，就不需要删除了，比如12122 k=3的情况
        print(0)
        continue

    minans = N
    for k, v in dic.items(): # 对每一层进行双指针判断最少删除结点，使得层断开连接
        if k+1 in dic:
            alist = v
            blist = dic[k+1]
            ans = get_ans(alist, blist)
            minans = min(minans, ans)
    print(minans)

测试样例

答案分别是：1 5 2 2 1 1 1 0 2 2

带括号的是需要删除的数

10

5(N) 3(K)
1 (2) 3 1 2

5 1
1 1 1 1 1

10 4
1 (2) 1 (2) 3 4 3 3 4 4

9 3
(1) 2 2 1 1 3 (2) 3 3

8 4
4 3 (1) 2 3 2 4 3

8 5
(1) 2 3 2 1 3 4 5

14 3
(1) 2 2 1 1 3 3 2 1 1 2 1 1 2

4 3
2 3 1 2

9 3
1 (2) 1 3 1 3 2 2 (3)

5 2
1 1 1 (2) (2)

#京东笔试##内推##春招##实习##笔试题目#