Build Lowest Number by Removing n digits from a given number
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Build Lowest Number by Removing n digits from a given number,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1549字,纯文字阅读大概需要3分钟。
内容图文
![Build Lowest Number by Removing n digits from a given number](/upload/InfoBanner/zyjiaocheng/1219/879ab41bdd554befb82fc767c537b3b9.jpg)
Given a string ‘str’ of digits and an integer ‘n’, build the lowest possible number by removing ‘n’ digits from the string and not changing the order of input digits.
Examples:
Input: str = "4325043", n = 3 Output: "2043"
Input: str = "765028321", n = 5 Output: "0221"
Input: str = "121198", n = 2 Output: "1118"
解法一:目标是要得到用字符串表示的最小数字,所以要使高位的数字尽量小,可以使用贪心策略,从左往右扫描字符串中的数字,比较相邻两个数字,如果左边的数字比右边的大,则应该删除左边的数字,否则,两个指针同时右移一位,直到比较到最后两个数字或者已经删除的数字的个数等于n为止;如果扫描完一遍,已经删除的数字的个数为n‘,假设n‘小于n,则对新的数字重复上述操作,此时有一种特殊情况是,假设n‘为0,说明字符串中的数字已经是升序排列,这时,只需要删除字符串最后的n个数字即可。java的代码如下:
public class LowestNumber {
public String lowestNumber(String str, int n){
if(n <= 0){
return str;
}
int len = str.length();
if(n >= len){
return "";
}
String rst = "";
int l = 0;
int r = 1;
int d = 0;
while((d < n)&&(r < len)){
char cl = str.charAt(l);
char cr = str.charAt(r);
if(cl <= cr){
rst += String.valueOf(cl);
} else {
d += 1;
}
l = r;
r += 1;
}
if(d == 0){
return str.substring(0, len-n);
}
rst += str.substring(l);
return lowestNumber(rst, n-d);
}
}
解法一的时间复杂度最差的情况下应该是O(nm),其中m表示输入字符串的长度。显然一位一位地删除太低效了,事实上,我们会注意到一个事实就是,假设输入字符串的长度为m,需要删除的字符的数目为n,则前n+1个字符中的最小值一定在结果字符串中,这一点可以用反正法来证明,假设前n+1个字符全不在结果字符串中,则输出字符串的长度小于m-n,所以不符合要求,而假设前n+1个字符串的非最小值在结果字符串中,则显然可以得到更小的结果字符串,所以基于这一点,我们可以一次找到前n+1个字符中的最小值,然后删除从第一位到最小值之前的所有数字,然后从最小值后的第一个字符开始,递归处理。这是解法二,可以参考:http://www.geeksforgeeks.org/build-lowest-number-by-removing-n-digits-from-a-given-number/ 中的code;
原文:http://www.cnblogs.com/wxyanglearning/p/4431511.html
内容总结
以上是互联网集市为您收集整理的Build Lowest Number by Removing n digits from a given number全部内容,希望文章能够帮你解决Build Lowest Number by Removing n digits from a given number所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。