Loại bỏ chữ số K trong C ++

Giả sử chúng ta có 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ố khỏi số để số mới là nhỏ nhất có thể. Vì vậy, nếu đầu vào là “1432219” và k =3, thì kết quả sẽ là “1219”.

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• Xác định một st ngăn xếp, tạo một chuỗi rỗng ret

• n:=kích thước của num

• cho tôi trong phạm vi từ 0 đến n - 1

  • trong khi k khác 0 và ngăn xếp không trống và đầu ngăn xếp> num [i]

    • xóa khỏi ngăn xếp và giảm k đi 1

  • chèn num [i] vào st

• trong khi k không phải là 0, hãy xóa phần tử khỏi ngăn xếp

• trong khi ngăn xếp không trống

  • ret:=ret + đầu ngăn xếp, xóa phần tử khỏi ngăn xếp

• bây giờ đảo ngược chuỗi ret

• ans:=một chuỗi trống và i:=0

• trong khi i

  • tăng tôi lên 1

• cho tôi

  • ans:=ans + ret [i]

• ret:=ans

• trả về “0” nếu kích thước của ret là 0, ngược lại, ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

class Solution {
public:
   string removeKdigits(string num, int k) {
      stack 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"