在C ++中删除K位
假设我们有一个以字符串表示的非负整数num,我们必须从该数字中删除k个数字,以便使新数字最小。因此,如果输入像“1432219”并且k=3,那么结果将是“1219”。
为了解决这个问题,我们将遵循以下步骤-
定义一个堆栈st,创建一个空字符串ret
n:=num的大小
对于i,范围为0至n–1
从堆栈中删除并将k减1
而k为非零且堆栈不为空且堆栈顶部>num[i]
将num[i]插入st
当k不为0时,从堆栈中删除元素
当堆栈不为空时
ret:=ret+栈顶,从栈中删除元素
现在反转ret字符串
ans:=一个空字符串,而i:=0
当我<ret的大小,而ret[i]不是'0'时
使我增加1
因为我<视网膜的大小
ans:=ans+ret[i]
ret:=ans
如果ret的大小为0,则返回“0”,否则返回
范例(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"