JAVA:一串整数抹掉k个数后的最小值

题目描述

小明发现一种魔水,这种魔水可以把一串数字里的一个数字消掉。例如,123用魔水消除2,则变成了13。如果123用魔水消除1,则变成了23。这种魔水是有使用限制的,一次使用只能消除一个数字。已知这串数字,和魔水的使用次数限制,小明现在想知道使用这种魔水后,这串数字最小会变成几。

输入格式

输入一串数字n,和魔水的使用限制次数s,用空格隔开

输出格式

输出一串数字,即使用魔水后的数字。

输入输出样例

输入 #1

175439 4

输出 #1

13

输入 #2

10005 1

输出 #2

5

说明/提示

【样例1解释】原数字是175439(即十七万五千四百三十九),魔水可以使用4次,使用魔水消除数字7,数字5,数字4,数字9之后变成了13(即十三),这是所有使用魔水后的情况中最小的数字。

【样例2解释】原数字是10005(即一万零五),魔水可以使用1次,使用魔水消除数字1,剩下的数串为0005,即五,化简得正确答案5,这是使用魔水后的所有情况中最小的数字。

【数据范围】 对于100%的数据,n最多有50位。


解:

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int n,s;
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        s=sc.nextInt();
        String input=String.valueOf(n);
        String out=new String(removeKDigits(input,s));

        System.out.println(Integer.valueOf(out));
    }
    /**
     * 删去k个数字后的最小值
     * 时间复杂度0(n)
     * @param str
     * @param k
     */
    public static char[] removeKDigits(String str,int k ){
        char[] c=new char[str.length()-k];//定义最小值
        int n=0;
        for (int i=0;i<str.length();i++){
            char j=str.charAt(i);
            //循环判断新产生数据和要比较数据的大小
            while(n>0&&j<c[n-1]&&k>0){//删数据
                //类似栈原理
                System.out.println("删除数据:"+c[n-1]);
                k--;//要删除长度减一
                n--;//字符串减一
            }
            if(n<c.length) {//还有空位时才能存
                c[n++]=j;//放数据
            }
        }
        return c;
    }
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!

客官,赏一瓶怡宝吧。

支付宝
微信