LintCode 182: Delete Digits (贪婪算法经典题)

1. Delete Digits

   中文English

   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

Example 1:

Input: A = “178542”, k = 4

Output:“12”

Example 2:

Input: A = “568431”, k = 3

Output:“431”

解法1：每次从A[0…A.size() - m + i]中取一个最小的，一共取m = N - k个 (即剩下多少个)，记得每次A要重组，所以A.size()不能总是用N代替。

比如A=“179542”, k = 4, N = 6, m = N - k = 2。

i = 0, 从A[0…4]中取一个最小的, 为1。result = “1”, A = “79542”, A.size()=5。

i = 1, 从A[0…4]中取一个最小的, 为2。result = “12”, A = “7954”, A.size()=4。

return “12”。

再比如A=“791542”, k = 4, N = 6, m = N - k = 2。

i = 0, 从A[0…4]中取一个最小的, 为1。result = “1”, A = “542”, A.size()=3。

i = 1, 从A[0…2]中取一个最小的, 为2。result = “12”, A = “54”, A.size()=2。

return “12”。

A.size() - m + i是什么意思呢？它可以写成A.size-(m-i)，其中m-i就是当前的A里面要剩下的数目，因为后面m-i个元素不能动。然后从A[0…A.size() - m + i]中取一个最小的。

代码如下：

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) {
        int N = A.size();
        if (N == 0) return "";
        if (k == 0) return A;
        
        int m = N - k;  // the rest numbers
        string result = "";
        for (int i = 0; i < m; ++i) {
            int pos = 0; 
            char minChar = A[pos];
 
            for (int j = 0; j <= A.size() - m + i; ++j) {
                if (A[j] < minChar) {
                    pos = j;
                    minChar = A[j];
               }
            }
            result = result + A[pos];
            A = A.substr(pos + 1);
        }
        
        int posZero = -1;
        for (int i = 0; i < result.size(); ++i) {
            if (result[i] != '0') {
                posZero = i;
                result = result.substr(posZero);
                return result;
            }
        }
        
        return "0";
    }
};