Delete Digits

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”

分析：

  题目是要去除 k 个字符，我们可以逆向考虑，从A中选取 A.size() - k 个字符。由于选取的字符需要保留原来的位置，所以从左边最高位开始依次向右边低位选取。直觉上：如果我们每次都选去最小的字符，最终就可以得到最小的数字。事实上它也满足贪心的性质：

1. 最优子结构：局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
2. 无后效性：某个状态以后的过程不会影响以前的状态，只与当前状态有关

这种方法的时间复杂度是 O(n^2) 。

思路：

  按照上面分析所说的方法进行选取，由于最后的数字的位数为 A.size() - k ，所以左边第一位必须从 A 的 0 ~ k 位（即 A[0] ~ A[k]）选取，假设选取的为 i 位（即 A[i]），则接下来的左边第二位必须从 i+1 ~ k+1 位（即 A[i+1] ~ A[k+1] ）选取，重复此步骤直到选取了A.size() - k 位，得到的结果就是最终的结果。
  

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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) {
        // wirte your code here
        int count = A.size() - k;
        int start = 0;
        int startIndex = 0;
        int end = k;
        string rs = "";

        while (count > 0) {
            char tem = A[start];
            startIndex = start;
            for (; start <= end && end < A.size(); start++) {
                if (A[start] < tem) {
                    tem = A[start];
                    startIndex = start;
                }
            }
			
            rs += tem;
            start = startIndex + 1;
            end++;
            count--;
        }
		
        rs.erase(0, rs.find_first_not_of("0")); 
        return rs;
    }
};