Algorithm 06:删数问题

问题：键盘输入一个高精度的正整数N（N<=240位），去掉任意S个数字后剩下的数字按原来左右次序组成一个新的正整数。编程实现对给定的N和S，寻找一种解决方案，使得剩下的数最小。

例如，给定的N＝178543，S=4，则得到的结果为13


答：实现代码如下：

/**
  * @author: YuHuang
  * @date: 2011-11-30
  * @summary: Just for fun.
  */

public class DeleteNumberProblem {

        public static String doDelete(String n,int s){
                char[] numberArray = n.toCharArray();
                int len = numberArray.length;

                if(len<=s) {
                        System.out.println("invalid s!");
                        return null;
                }else{
                        int deleteLength = 0;
                        int pos = 1;
                        while(pos<len){
                                if(numberArray[pos]<numberArray[pos-1]) {
                                        int i=pos;
                                        while(i<len){
                                                numberArray[i-1] = numberArray[i];
                                                ++i;
                                        }
                                        pos = pos>1 ? --pos:pos;
                                        --len;
                                        ++deleteLength;
                                }else{
                                        pos++;
                                }
                                if(deleteLength==s) break;
                        }

                        len = len-(s-deleteLength);
                }

                StringBuilder sb = new StringBuilder();
                for(int index=0;index<len;++index){
                        sb.append(numberArray[index]);
                }

                return sb.toString();
        }

        public static void main(String[] args) {
                String n = "178543";
                int s = 4;
                String result = DeleteNumberProblem.doDelete(n,s);
                System.out.println(result);
        }
}

代码运行结果：
Lab-Computer-0db2f6:JavaExercises labuser$ javac DeleteNumberProblem.java
Lab-Computer-0db2f6:JavaExercises labuser$ java DeleteNumberProblem
13
Lab-Computer-0db2f6:JavaExercises labuser$