Xóa K Chữ Số Trong C++

Giả sử chúng ta có một số nguyên không âm num được biểu diễn dưới dạng chuỗi, chúng ta phải xóa k chữ số từ số đó để số mới là nhỏ nhất có thể. Ví dụ: num = "1432219", k = 3 → kết quả "1219".

Để giải quyết, chúng ta làm theo các bước:

• Định nghĩa stack st, chuỗi rỗng ret.

• n := độ dài num.

• Với i từ 0 đến n-1: trong khi k > 0 và st không rỗng và st.top() > num[i]: st.pop(); k--. Sau đó st.push(num[i]).

• Khi k > 0: st.pop().

• Khi st không rỗng: ret += st.top(); st.pop().

• Đảo ngược ret.

• Loại bỏ các số 0 ở đầu: ans = chuỗi rỗng, i = 0; khi i < ret.size() và ret[i] == '0': i++; sau đó nối các ký tự còn lại vào ans.

• Trả về "0" nếu ans rỗng, ngược lại trả về ans.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

class Solution {
public:
    string removeKdigits(string num, int k) {
        stack<char> st;
        string ret = "";
        int n = num.size();
        for(int i = 0; i < n; i++){
            while(k && !st.empty() && st.top() > num[i]){
                st.pop();
                k--;
            }
            st.push(num[i]);
        }
        while(k--) st.pop();
        while(!st.empty()){
            ret += st.top();
            st.pop();
        }
        reverse(ret.begin(), ret.end());
        string ans = "";
        int i = 0;
        while(i < ret.size() && ret[i] == '0') i++;
        for(; i < ret.size(); i++) ans += ret[i];
        ret = ans;
        return ret.size() == 0? "0" : ret;
    }
};

Đầu vào

"1432219" 3

Đầu ra

"1219"