資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 中移除 K 個數字
假設我們有一個用字串表示的非負整數 num，我們需要從中移除 k 個數字，使得新的數字儘可能小。例如，如果輸入是“1432219”且 k = 3，則結果將是“1219”。
為了解決這個問題，我們將遵循以下步驟：
定義一個棧 st，建立一個空字串 ret
n := num 的長度
對於 i 從 0 到 n – 1
當 k 不為零且棧不為空且棧頂 > num[i]
從棧中刪除元素並將 k 減 1
將 num[i] 插入到 st 中
當 k 不為 0 時，從棧中刪除元素
當棧不為空時
ret := ret + 棧頂元素，從棧中刪除元素
現在反轉 ret 字串
ans := 一個空字串，i := 0
當 i < ret 的長度且 ret[i] 不為 ‘0’
將 i 加 1
對於 i < ret 的長度
ans := ans + ret[i]
ret := ans
如果 ret 的長度為 0，則返回“0”，否則返回 ret
示例 (C++)
讓我們來看下面的實現，以便更好地理解：
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;
}
};輸入
"1432219" 3
輸出
"1219"
更新於：2020年3月31日
627 次瀏覽
廣告