Lintcode182 Delete Digits solution 题解
发布在lintcode2018年1月20日view:381
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Given string A representative a positive integer which hasNdigits, remove anykdigits of the number, the remaining digits are arranged according to the original order to become a new positive integer.

给出一个字符串A, 表示一个n位正整数, 删除其中k位数字, 使得剩余的数字仍然按照原来的顺序排列产生一个新的正整数。

找到删除k个数字之后的最小正整数。

N<= 240,k<=N

【题目链接】

www.lintcode.com/en/problem/delete-digits/

【题目解析】

此题可使用stack,找第一个递减的值。从这个数的左边开始,找第一个递减的位置所在。

要让一个数尽量小,那么就要把小的数字尽量放到前面,如果前面有比它大的数字,那么就到把在它前面且比它大的数字都要删除掉,直到已经删掉k个数字,所以最后留下的是一个递增数列。同时要考虑一些特殊情况,比如前置0要去掉,以及如果遍历一遍之后发现删去的数不足k个,则删去最后的k-count个数。

【参考答案】

www.jiuzhang.com/solutions/delete-digits/

作者:程风破浪会有时 链接:https://www.jianshu.com/p/ff3bc60fdf02 來源:简书 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN
lintcode

lintcode题解

我的收藏