Leetcode402 remove-k-digits贪心+vector模拟栈的思想

题目

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。

示例 1 : 输入: num = "1432219", k = 3 输出: "1219" 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。 示例 2 : 输入: num = "10200", k = 1 输出: "200" 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。 示例 3 : 输入: num = "10", k = 2 输出: "0" 解释: 从原数字移除所有的数字，剩余为空就是0。

来源：力扣（LeetCode）
链接：原题链接

实现思路

贪心规律：从高位向低位遍历，如果对应的数字＞下一位数字，则把该位去掉得到的数字最小。

相邻位进行比较，两者小的进栈

(这里需要注意存在零的情况。举例，“10234” ，0比1小，1出栈，0入栈，此时如果0位于栈底，最后弹出显示则0位于首位，这是错误的)

栈顶弹出条件是：

栈非空，

k大于0，

栈顶元素＞后面的元素

接下来如果不是0，则可以直接进栈。
如果是0，需要考虑之前的栈非空。
这里结合为一句代码：

if(number!=0||!v.empty())v.push_back(number); //使用vector实现栈的思想

核心代码

for(size_t i=0;i<num.size();++i){number=num[i]-'0';//转换为数字while(k>0&&!v.empty()&&v.back()>number)//弹出栈顶的条件{v.pop_back();//使用vector模拟栈，这里弹出k--;//需要减掉的元素数少1}if(number!=0||!v.empty())v.push_back(number); }

AC代码

class Solution { public:string removeKdigits(string num, int k) {vector<int> v;//模拟栈的思想string result="";int number;for(size_t i=0;i<num.size();++i){number=num[i]-'0';//转换为数字while(k>0&&!v.empty()&&v.back()>number)//弹出栈顶的条件{v.pop_back();k--;}if(number!=0||!v.empty())v.push_back(number); }while(k>0&&!v.empty()){k--;v.pop_back();}//数字转换为字符串for(size_t i=0;i<v.size();++i){result.append(1,v[i]+'0');}if(result=="")//空串return "0";return result;} };

未考虑到0的情况的代码

问题出现在出现前导0，如下是问题代码

while(k>0&&!v.empty()&&v.back()>number)//弹出栈顶的条件{v.pop_back();k--;}if(number==0){//已知没有前导0v.push_back(number);}else//直接入栈v.push_back(number);}

总结

后续整体添加。也可能遗忘。

数字转换为字符串
使用字符串result的append()函数追加字符
append()函数请参考：博客：C++append()函数的功能
数字转化为字符通过num+'0’

//数字转换为字符串for(size_t i=0;i<v.size();++i){result.append(1,v[i]+'0');}

字符串转化为数字：

这个使用较多，比较简单
字符串转化为数字通过 num-'0’

//一位一位的转换for(size_t i=0;i<num.size();++i){number=num[i]-'0';//转换为数字//后续处理...}

希望对你有帮助。

总结

以上是生活随笔为你收集整理的Leetcode402 remove-k-digits贪心+vector模拟栈的思想的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。