Description:
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 integer A = "178542", k = 4
return a string "12"
Solution:
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) {
auto sz = (int)A.length();
if (sz == 0) return "0";
string rc = "0";
int cnt = 0;
for (int i = 0; i < sz; ++i) {
auto ch = A[i];
while (cnt < k && ch < rc.back()) {
++cnt;
rc.pop_back();
}
rc.push_back(ch);
}
while (cnt < k) {
rc.pop_back();
++cnt;
}
int pos = 0;
while (pos < rc.length() && rc[pos] == '0') ++pos;
return pos == rc.length() ? "0" : rc.substr(pos);
}
};
转载于:https://www.cnblogs.com/deofly/p/delete-digits.html
相关资源：JAVA上百实例源码以及开源项目
