删数问题
本实验符合贪心法原则，使用贪心算法实现。
贪心法的核心是贪心策略的选择。在本题中，要求最后结果最小，则要保证每次删除的数都能确保局部最小。故我们将贪心策略定义为：从高位向低位遍历，若前一位大于后一位，则删去前一位。
删数伪代码如下：
for(int i=0;i<str.length();i++){
if(str[i]>=str[i+1]) delete str[i];
else i++;
}同时，我们要保证贪心策略的执行次数（即删数代码的执行次数），故用k来限制。我们一共需要删除k位，删数代码每执行一次，k减1。可以使用while(k--)包裹删数代码：
While(k--){
For(int i=0;i<str.length();i++){
If(str[i]>=str[i+1]) delete str[i];
Else i++;
}
}然后必须解决另一个问题，如果还没删够k个数字，原数各位从高到低已经递增排列了。这种情况，我们应该跳出while循环，从低位向高位删除相应位数。
代码实现：
package delnum;
import java.util.Scanner;
public class solution {
public static void main(String []args){
String str;
int k;
Scanner in=new Scanner(System.in); //输入数字串
str = in.nextLine();
Scanner iin=new Scanner(System.in);//输入k值
k = iin.nextInt();
char a[] = str.toCharArray();
int len = str.length();
while(k--!=0){
int i=0;
while (i < len - 1 && a[i] <= a[i + 1]) i++;
if(i==len-1){
len--;
while (k--!=0) len--;
break;
}else {//本位大于下一位，则删去本位
for (int j = i; j<len - 1; j++)
a[j] = a[j + 1];
len--;
}
}
for (int i = 0; i < len; i++)
System.out.print(a[i]);
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.12.06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读