给出一个字符串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();
}
}
