贪心算法——删数问题
【问题描述】
假设正整数n、s,s<n。设计算法对任一给定n位数,删除其中的s位后,使得剩下的位新数最小。
【输入形式】
ex:1 2 3 9 5;删掉一个数;
1:1 2 3 5
2:1 2 3
3:1 2
【个人思路】
从第一个数开始遍历,到寻找到单调递减的第一个数(即单调递增的最后一个数),则删除,若无单调递减子序列,则删掉最后一个非递减序列的数;每找到一个就又从头开始。即每做一次删数,就是一次贪心选择,删掉此数剩下的数为组成最小
【代码演示】
import java.util.Scanner;
public class shanshuwenti2 {
public static int Delete(int a,int k)
{
StringBuffer sb=new StringBuffer(a+"");
int i=0,j=0;
for(i=0;i<k;i++)
{
for(j=0;j<sb.length()-1&&sb.charAt(j)<=sb.charAt(j+1);j++)
{
}
sb.delete(j,j+1);
}
return sb.length()==0?0:Integer.parseInt(sb.toString());
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
int a=in.nextInt();
int b=in.nextInt();
if(a<=0||b<=0)
System.exit(0);
System.out.println(Delete(a,b));
}
}