删除K个数字后的最小值（贪心算法实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了删除K个数字后的最小值（贪心算法实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3077字，纯文字阅读大概需要5分钟。

内容图文

给出一个整数，从该整数中去掉k个数字，要求剩下的数字形成的新整数尽可能小。应该如何选取被去掉的数字？ 其中，整数的长度大于或等于k，给出的整数的大小可以超过long类型的数字范围。 ? 思路： 把原整数的所有数字从左到右进行比较，如果发现某一位数字大于它右面的数字，那么在删除该数字之后，必然会使该数位的值降低。这种求局部最优解，最终得到全局最优解的思想，叫作“贪心算法”。 如果要删除k个数字，那么将遍历数字作为外层循环，以k作为外层循环，再结合栈的使用。将遍历的数字逐个入栈，遇到入栈进来的数字小于栈顶的数字时，将栈顶的数字出栈，再将该遍历的数字入栈，否则就直接将数字压栈。当出栈的数字达到k个时，将剩下的数字全部入栈即可。 ? 举例："541270936"，去除3个数字。

1. 5入栈，stack=[5]
2. 4入栈，判断4<5，5出栈，4入栈。stack=[4]。出栈一次，num=1
3. 1入栈，判断1<4，4出栈，1入栈。stack=[1]。出栈一次，num=2
4. 2入栈，判断2>1，2直接入栈。stack=[1,2]
5. 7入栈，判断7>2，7直接入栈。stack=[1,2,7]
6. 0入栈，判断0<7，7出栈，0入栈。stack=[1,2,0]。出栈一次，num=3。此时出栈了3次，相当于去除了3个数字。满足要求。那么剩下的字符就直接入栈就可以了。
7. 剩余字符全部入栈。stack=[1,2,0,9,3,6]

代码实现：

 1 package blogSrc;
 2 
 3 import com.sun.deploy.util.StringUtils;
 4 
 5 import java.util.Arrays;
 6 import java.util.Stack;
 7 
 8 /**
 9  * 删除K个数字后的最小值
10  *
11  * 给出一个整数，从该整数中去掉k个数字，要求剩下的数字形成的新整数尽可能小。应该如何选取被去掉的数字？
12  * 其中，整数的长度大于或等于k，给出的整数的大小可以超过long类型的数字范围。
13  *
14  * 思路：把原整数的所有数字从左到右进行比较，如果发现某一位数字大于它右面的数字，那么在删除该数字之后，必然会使该数位的值降低。
15  * 如果要删除k个数字，那么将遍历数字作为外层循环，以k作为外层循环，再结合栈的使用。将遍历的数字逐个入栈，否则就直接将数字压栈。
16  * 遇到入栈进来的数字小于栈顶的数字时，将栈顶的数字出栈，再将该遍历的数字入栈，当出栈的数字达到k个时，
17  * 将剩下的数字全部入栈即可。
18  */
19 public class GetMinAfterRemoveKDigits {
20 
21     public static void main(String[] args){
22         String originStr = "541270936";
23         String newStr = new GetMinAfterRemoveKDigits().getMinAfterRemoveKDigits(originStr,3);
24         System.out.println("OldString is: " + originStr);
25         System.out.println("NewString is: " + newStr);
26     }
27 
28     public String getMinAfterRemoveKDigits(String originStr, int k){
29         char[] originArr = originStr.toCharArray();
30         Stack<Character> stack = new Stack<>();
31         stack.push(originArr[0]);
32         int num = 0;
33         for (int i=0; i<originArr.length; i++){
34             if (num == k){
35                 stack.push(originArr[i]);
36             }else {
37                 if (originArr[i] <= stack.peek()) {
38                     stack.pop();
39                     stack.push(originArr[i]);
40                     num++;
41                 }else {
42                     stack.push(originArr[i]);
43                 }
44             }
45 
46         }
47 
48         StringBuffer result = new StringBuffer();
49         for (int i=0; i<stack.size(); i++){
50             result.append(stack.get(i));
51         }
52         return result.toString();
53     }
54 }

结果：

OldString is: 541270936
NewString is: 1270936

 

?

内容总结

以上是互联网集市为您收集整理的删除K个数字后的最小值（贪心算法实现）全部内容，希望文章能够帮你解决删除K个数字后的最小值（贪心算法实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---