Delete Digits
今天是一道有关字符串和贪婪算法的题目，来自LintCode，难度为Medium，Acceptance为16%。还是需要一定的技巧的。
题目如下
Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.
Find the smallest integer after remove k digits.
N <= 240 and k <= N,
Example
Given an integerA = "178542", k = 4
return a string"12"
思路如下
其实这道题的思路和Largest Number（回复009查看）的思路相似，都是贪婪算法，不同的是在Largest Number中，是较大的数在前，较小的数在后；这道题目中是较小的数在前，较大的数在后。
在Largest Number一题中，是将两个数先合并，然后比较合并后的大小；然而在该题中，我们不需要这样做：
首先，还是以一个简单的输入为例，如输入字符串A="859", k=1，因此我们在这里要删除一个字符。很明显这里删除字符8就可以得到结果。如输入字符串A="859", k=1，则再删除9即可。
然后，我们推导思路：因为我们要求最小的数，所以需要让排在最前的数字较小就可以，要做到这一点，我们依次比较两个相邻的数字，如果前一个数字比后一个数字大，则将前一个数字删除；如果前一个数字比后一个数字小，则不变，继续比较后面的数字。当进行到最后一个数字时，不需要再比较，直接将其删除即可。在上面的例子中，首先比较8和5，因为8比5大，所以删去8即可。如果k=2，那么继续比较5和9，因为5比9小，所以不用删除；下面到了最后一个字符，不用再比较，直接将其删除即可。
最后，按照上面的思路，我们可以写出代码。
这里有一点需要注意就是，当处理之后的字符串中前面的数有可能是0，此时我们应该跳过前面的0，从第一个非0的字符处返回。
代码如下
java版
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
if(k == A.length())
return "";
StringBuilder builder = new StringBuilder(A);
for(int i = 0; i < k; i++)
for(int j = 0; j < builder.length(); j++)
if(j == builder.length() - 1 || builder.charAt(j) > builder.charAt(j + 1)) {
builder.deleteCharAt(j);
break;
}
int i = 0;
for(; i < builder.length(); i++) {
if(builder.charAt(i) != '0')
break;
}
return builder.substring(i, builder.length());
}
}
C++版
class Solution {
public:
/**
*@param A: A positive integer which has N digits, A is a string.
*@param k: Remove k digits.
*@return: A string
*/
string remove(string A, int pos) {
return A.substr(0, pos) + A.substr(pos + 1, A.length() - pos - 1);
}
string DeleteDigits(string A, int k) {
if (A.length() == k) {
return "";
}
for (int i = 0; i < k; i++) {
for (int j = 0; j < A.length(); j++) {
if (j == A.length() - 1 || A[j + 1] < A[j]) {
A = remove(A, j);
break;
}
}
}
int i = 0;
while (i < A.length() - 1 && A[i] == '0') {
i++;
}
return A.substr(i, A.length() - i);
}
};
如果觉得文章有帮助的话，不妨关注一下本公众号，当然也希望能帮作者推广一下，更多人关注我也会更有动力，在此先谢过了。
关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助
