Leecode 402. 移掉 K 位数字 贪心+栈
原题链接:Leecode 402. 移掉 K 位数字代码一:class Solution {public:string removeKdigits(string num, int k) {int n=num.size();if(n==k) return "0";stack<int> st;int cnt=0;for(int i=0;i<num.size();i++){
·
原题链接:Leecode 402. 移掉 K 位数字
代码一:(直接使用栈)
class Solution {
public:
string removeKdigits(string num, int k) {
int n=num.size();
if(n==k) return "0";
stack<int> st;
int cnt=0;
for(int i=0;i<num.size();i++)
{
int tmp=num[i]-'0';
while(!st.empty() && tmp<st.top() && cnt<k )
{
st.pop();
cnt++;
}
st.push(tmp);
}
//得到最终序列
string res;
while(!st.empty())
{
char tmp=st.top()+'0';
if(st.size()<=n-k) res+=tmp;
st.pop();
}
reverse(res.begin(),res.end());
//去除前导0
int i=0;
for(;i<res.size();i++)
{
if(res[i]!='0')
break;
}
res=res.substr(i);
if(res=="") return "0";
return res;
}
};
代码二:(字符串模拟栈,思路和一一样,但是代码要更简洁漂亮)
class Solution {
public:
string removeKdigits(string num, int k) {
int n=num.size();
if(n==k) return "0";
string st;
for(auto c:num)
{
while(!st.empty() && c<st.back() && k>0 )
{
st.pop_back();
k--;
}
if( st.empty() && c=='0' ) continue;
st.push_back(c);
}
while(!st.empty() && k>0)
{
st.pop_back();
k--;
}
return st=="" ? "0" : st;
}
};
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)