我的Lintcode之路——删除数字

给出一个字符串A, 表示一个n位正整数, 删除其中k位数字, 使得剩余的数字仍然按照原来的顺序排列产生一个新的正整数。

找到删除k个数字之后的最小正整数。

N<= 240,k<=N

您在真实的面试中是否遇到过这个题？

Yes

样例

给出一个字符串代表的正整数A和一个整数k, 其中A = 178542,k = 4

返回一个字符串"12"

思路：

我的思路是这样的。

第一个数字在[0,k]之间选一个，如果选到第一个数字，下标为i；

第二个数字一定从i+1继续选。在[i+1，k+1]中选一个最小的，下标为i1；

第三个数字一定要在第i1+1后继续选。即在[i1+1,k+2]中选一个最小的；

。。。依此类推。

所以在这里，我是要注意的两个地方，即如何判断是否第一次选数字？

还有一个如果出现了"012"这样的情况，它不是我们需要的，而是需要“12”。所以需要判断如果StringBuffer为空的时候，0不要加进去~以下为我的参考代码。

public class Solution {
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
     */
    public String DeleteDigits(String A, int k) {
        // write your code here
        char[] array=A.toCharArray();
        int length=A.length();
        int step=length-k;
        if(length==k)
            return "0";
        StringBuffer sb=new StringBuffer();
        
        int index=0;
        int j=0;
        
        while(step>0)
        {   
            int flag=1;
            if(step==length-k)//如果是第一次的话，就让flag=0；
            {
                flag=0;
            }
            char min=58;
            for(int i=index+flag;i<=k+j;i++)
            {   
                
                int temp=array[i]-min;
                if(temp<0)
                {
                    index=i;
                    min=array[i];
                }
            }
            if(sb.length()==0&&array[index]=='0')
            {}
            else{
            sb.append(array[index]);
            }
            step--;
            j++;
        }
        return sb.toString();
    }
}