Delete Digits
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,
http://www.lintcode.com/en/problem/delete-digits/
Discussion
N个数字删去k个，求剩余N-K个数字能组成的最小的那个整数。不就是combination问题的变形嘛，果断DFS 求combination。
Solutioin
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 DeleteDigits(string A, int k) {
string result;
if(k > A.length()) return result;
string current;
result.append(A.length() - k, '9');
dfs(A, A.length() - k, current, result, 0);
//remove '0' at the begining
int idx = 0;
while(idx < result.length()) {
if(result[idx] == '0'){
idx++;
} else {
break;
}
}
string final (result.begin()+idx, result.end());
return final;
}
void dfs(string A, int k, string ¤t, string &smallest, int pos) {
if(current.length() == k) {
if(current < smallest) {
smallest = current;
}
return;
}
for(int i = pos; i < A.length(); i++) {
current.push_back(A[i]);
dfs(A, k, current, smallest, i+1);
current.pop_back();
}
}
};
Follow up
上述方法显然效率太低了，而且提交的时候也超时了。第一个改进想到了剪枝prunning，在dfs里面扩展动作之前加了if(current > smallest) return;，但是没用。。。
DFS方法是最基础的，三分钟之内写出来，边写边想别的方法。
问题来了，如果删除一个，那删除的是哪一个？删除的是破坏升序的地方，比如178542 --> 17542 --> 1542 --> 142 --> 12。如果整个都是升序呢，删除的是最后一个，比如178 --> 17
所以问题就转换成了调用删除一个字符的函数k次的问题了。
//rum time O(N*k)
//sapce: O(1)
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 DeleteDigits(string A, int k) {
string result;
if(k > A.length()) return result;
for(int i=0; i<k; i++) {
DeleteOneDigit(A);
}
//remove '0' at the begining
int idx = 0;
while(idx < A.length()) {
if(A[idx] == '0'){
idx++;
} else {
break;
}
}
//string final (A.begin()+idx, A.end());
//return final;
return A.substr(idx);
}
//delete the first A[i] which satifies A[i]>A[i+1]
void DeleteOneDigit(string &A) {
int idx = A.length()-1;//is A is asending, erase the last digit
for(int i=0; i < A.length() - 1; i++) {
if(A[i] > A[i+1]) {
idx = i;
break;
}
}
A.erase(idx, 1);
}
};
rum time O(N*k).删除一个digit的复杂度是O(N). 有没有更好的方法呢？
我试图通过一次遍历就找出所有K个要删除的char
string DeleteDigits2(string A, int k) {
string result;
if (A.length() < k) return result;
vector<bool> i_del(A.length(), false);//i_del[i] = true: should delete A[i]
int n = A.length();
int start = 0;
int cnt = 0; //how many digited removed
for (int i = start; i < n - 1; i++) {
if (A[i] > A[i + 1]) {
int j = i;
while (cnt < k && j >= start) {
if (A[j] > A[i + 1]) {
i_del[j] = true;
cnt++;
j--;
}
else {
break;
}
}
if (cnt == k) {
break;
}
start = i + 1;
}
}
//it's possible that cnt < k, then remove the last k-cnt digits
int diff = k - cnt;
for (int i = 0, j = 0; i<diff;) {
if (i_del[n - 1 - j] == false) {
i_del[n - 1 - j] = true;
i++;
}
j++;
}//这里会出错，有可能前面有0的情况呢？报错的case：
for (int i = 0; i<n; i++) {
if (i_del[i]) {
continue;
}
if (result.length() == 0 && A[i] == '0') {
continue;
}
result.push_back(A[i]);
}
return result;
}
上面的方法是有bug的，没有办法处理有0的情况。我是用个vector来保存每个char是否应该delete，中间有回退的情况（j--），用一个栈来保存当前留下来的char就完美了。用栈顶元素和下一个元素去比较，如果下一个元素小，那就弹出栈顶元素，一直弹到栈顶元素不再比下一个元素大。同时记录弹了多少次，就是删除元素的次数了。
//O(n) run time
//O(n) space
string DeleteDigits(string A, int k) {
string result;
if(A.length() < k) return result;
int n = A.length();
stack<char> stk;
int i = 0;
while(i < n) {
while(k >0 && !stk.empty() && stk.top() > A[i]) {
stk.pop();
k--;
}
stk.emplace(A[i]);
i++;
}
while(k >0) {
stk.pop();
k--;
}
//out put left chars and reverse it
while(stk.empty() == false) {
result.push_back(stk.top());
stk.pop();
}
reverse(result.begin(), result.end());
//deal with 0s at the begin;
int idx = 0;
while(result[idx] == '0') {
idx++;
}
return result.substr(idx);
}
其实用个vector来保存留下来的char也可以的，只在vector尾部增删，最后就不用reverse了。
string DeleteDigits(string A, int k) {
string result;
if(A.length() < k) return result;
int n = A.length();
vector<char> remaining;
remaining.emplace_back(A[0]);
for(int i=1; i < n; i++) {
while(k>0 && remaining.empty() == false && remaining.back() > A[i]) {
k--;
remaining.pop_back();
}
remaining.emplace_back(A[i]);
}
while(k > 0) {
remaining.pop_back();
k--;
}
//deal with initial 0
int idx = 0;
while(remaining[idx] == '0') {
idx++;
}
result = string(remaining.begin()+idx, remaining.end());
return result;
}
kamyu104大神的写法：
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 DeleteDigits(string A, int k) {
// If a digit is greater than next one, delete it.
string s;
for (const auto c : A) {
while (k > 0 && !s.empty() && s.back() > c) {
s.pop_back();
--k;
}
s.push_back(c);
}
// If all digits are increasingly sorted, delete last.
s.resize(s.length() - k);
// Strip all leading '0'
return s.empty() ? "0" : s.substr(s.find_first_not_of('0'));
}
};