用Java解决贪心算法——删数问题

贪心算法——删数问题

【问题描述】

假设正整数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));
	    }


}