专注Java领域技术
我们一直在努力

(Java实现) 删数问题

原文始发于:(Java实现) 删数问题

删数问题(需知道的数学定理)

给定n位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个新 的正整数。对于给定的n位正整数a和正整数 k,设计一个算法找出剩下数字组成的新数最 小的删数方案。

定理: ex:1 2 3 9 5;删掉一个数;

从第一个数开始遍历,到寻找到单调递减的第一个数(即单调递增的最后一个数),则删除,若无单调递减子序列,则删掉最后一个非递减序列的数;每找到一个就又从头开始。即每做一次删数,就是一次贪心选择,删掉此数剩下的数为组成最小,经过证明,此结论正确。

ex:1 2 3 9 5,删掉三个数;

1:1 2 3 5

2:1 2 3

3:1 2

注意一种情况:3 0 0 2,删去一个数;

应该是2,而不是002

Input

第 1 行是1 个正整数 a。第 2 行是正整数k。

Output

输出最小数

Sample Input

178543
4

Sample Output

13

import java.util.Scanner;   public class shanshuwenti2 { 	 public static int Delete(int a,int k) 	    { 	        StringBuffer sb=new StringBuffer(a+"");//把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)); 	    }   }  

赞(0) 打赏
未经允许不得转载:Java小咖秀 » (Java实现) 删数问题
免责声明

抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专注Java技术 100年

联系我们联系我们

你默默的关注就是最好的打赏~

支付宝扫一扫打赏

微信扫一扫打赏