【LeetCode】 402. Remove K Digits

Description

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

給予一個非負數num用一個字串去表示，移除掉k個位元讓新的數字越小越好。

注意：

• num的長度小於10002且會 ≥ k。
• 給予的num不會有零在開頭。

Example:

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.


Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.


Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Solution

• 我們從高位元往低位元看，因為高位元的影響力比較高。
• 如果第i個位元大於i + 1個位元，那我們就移除掉i。
  • 這樣就可以讓高位元的數字變小。
  • 例如：1432，就移除4。
• 如果因為移除而導致最前面出現零，直接移除。
  • 例如：102，移除1會變成02，無條件移除0(k不需要變)。
• 如果沒有任何位元i比i + 1大，那麼就移除最低位元(因為它數字最大)
  • 例如：12345，就移除5。
• 如果num已經空了，補一個0然後直接回傳。

Code

class Solution {
public:
    string removeKdigits(string num, int k) {
        while(k > 0 && !num.empty())
        {
            bool f = false;
            
            if(num[0] == '0')
            {
                num.erase(num.begin());
                continue;
            }
            
            for(int i = 0; i < num.length(); i++)
            {
                if(num[i] > num[i + 1])
                {
                    num.erase(num.begin() + i);
                    k--;
                    f = true;
                    break;
                }
            }
            
            if(!f)
            {
                num.pop_back();
                k--;
            }
        }
        while(num[0] == '0')
        {
            num.erase(num.begin());
        }
        if(num.empty())
            return "0";
        
        return num;
    }
};

tags: LeetCode C++