这道题的正解是 单调栈 贪心求字典序最大子序列,但是我们用朴素解法 暴力枚举所有长度为k的子序列取最大 也能在考试时拿到一定的分数。
题意:在保持相对顺序的前提下,从码流中选出恰好 k 个子包 ID,使得到的长度为 k 的序列字典序最大。输入若含非十进制数字字符则输出 error。
朴素做法:用 DFS / 回溯枚举「选或不选」当前元素,最终恰好选满 k 个,在所有候选中取字典序最大的那一个。时间约为 O(C(n,k)⋅k)。
样例和很小的 n 可以算对;当 n 接近 2000、且 k 不太小也不太大时组合数爆炸,会超时,需要后面的单调栈做法。
网络侧需要给手机发送一个码流,一个码流由多个子包组成。例如:码流 3 4 5 6,该码流中含有四个子包,子包 ID 分别为 3、4、5、6 。
给定一个整数数组 nums 用于保存这条码流子包 ID ,另有一个正整数 k 需要找出长度为 k 且优先级最高 的 子包 ID 集合。
在子包 ID 集合 a 和子包 ID 集合 b 的 第一个不相同的位置上,如果 a 中的数字大于于 b 中对应的数字,那么我们称子包 ID 集合 a 比子包 ID 集合 b (相同长度下)优先级更高。
例如,[2,5,8] 比 [2,4,9] 优先级更高,在第一个不相同的位置,也就是第个位置上,5 大于 4 。
先输入码流,包含多个用 10 进制正整数表示的子包 ID ,每个子包 ID 之间用空格隔开,最大支持编号从 0 开始的 500 种不同的子包
再输入需要找出的优先级最高的子包长度
注:子包 ID 的先后顺序不可变更,但可删除或者不删除中间的子包 ID
最高优先级的子包 ID 集合,每个子包 ID 用空格隔开
输入
0x2 0x2
1
输出
error
说明
仅支持 10 进制数,输入中带有字母,打印 error
输入
6 3 2 4 4 3 8 5
4
输出
6 4 8 5
说明
在所有可能的长度为 4 的子包 ID 集合中,6 4 8 5 的优先级最高。
输入
5 7 4 8
2
输出
7 8
说明
在所有可能的长度为 2 的子包 ID 集合 [5,7],[5,4],[5,8],[7,4],[7,8],[4,8] 中,[7,8] 的优先级最高。
第一行码流最大长度: 2000
子包 ID 范围: 0<=nums[i]<500
子包长度范围: 1<=k<=nums.length
以上数字只考虑 10 进制数,不考虑其他,输入内容中带有非数字或者其他错误时打印 error
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.