帆软笔试算法题
给定两个数组,给定一个k。求这两个数组中选择k个数组合成的最小值,注意相对位置不能改变,数首不能为0。
输入1 0 3 2
2 0 4 1
4
输出:1001
思路:两数组先合并成一个数组,要按从小到大合并,同时保证相对位置不变,然后使用最小堆选择k个数。注意可能会超,最好用string.
最后没ac,过了25%
输入1 0 3 2
2 0 4 1
4
输出:1001
思路:两数组先合并成一个数组,要按从小到大合并,同时保证相对位置不变,然后使用最小堆选择k个数。注意可能会超,最好用string.
最后没ac,过了25%
全部评论
这个思路是错误的,合并的最小数的子序列不一定符合要求,比如15402 和 20431 取k为4,两个数组合并的最小值为1204315402,其最小的4的长度为子序列为1002,但实际最小为1001。
楼主知道题解了吗,或者lc原题。我想了是背包状态dp,三维两个背包,一个状态,但是没a,不知道对不对。
干脆就直接dp获得所有长度为k的数,然后再排序好了,过程中减减枝,不知道能过多少。
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
02-05 21:35
河南推拿职业学院 Java 点赞 评论 收藏
分享
点赞 评论 收藏
分享