算法学习——贪心算法之删数字（求最小值）
算法描述
在给定的n位数字，删除其中的k位数字（ k < n），使得最后的n-k为数字为最小值（原次序不变）
算法思路
-
考虑到是要移出数字，我们使用链表设计此算法较为方便，链表可以直接移出某个位置的元素
-
使用贪心算法，每一步都要达到最优
-
从最高位开始，若下一位比上一位要小，则将上一位的数字移出，结束之后再次从最高位开始
这里需要注意，会有特例
当输入从小到大的的一个数的时候，上述算法将会无法运行，比如123456，删除1个数字变为最小，我们把6删去，这样才是最小的（即从末尾删除数字）
算法实现
Scanner scanner = new Scanner(System.in);
System.out.println("请输入整数：");
String s = scanner.nextLine();
System.out.println("删除数字的个数：");
int n = scanner.nextInt();
scanner.close();
int a[] = new int[s.length()];
for(int i=0;i<s.length();i++){
char temp =s.charAt(i);
a[i] = temp -'0';//不减去‘0’则会获得Ascii码
}
LinkedList<Integer> linkedList = new LinkedList<Integer>();
for(int i=0;i<a.length;i++){
linkedList.add(a[i]);
}
int flag =0;
while(flag<n){
for(int i=0;i<linkedList.size()-1;i++){
if(linkedList.get(i)>linkedList.get(i+1)){
linkedList.remove(i);//使用链表移出元素
flag++;
break;//结束本次循环，跳转到while循环中
}
//考虑到特殊情况，当遍历完全部数字都不满足条件，从末尾删除数字
if(i==linkedList.size()-2){
linkedList.removeLast();
flag++;
}
}
}
System.out.print("截取的"+n+"个数字后的最小值为");
for(int i=0;i<linkedList.size();i++){
System.out.print(linkedList.get(i));
}
结果
版权声明：本文为kexing原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。