前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >移除K个数字

移除K个数字

作者头像
小飞侠xp
发布2018-08-29 14:23:23
8260
发布2018-08-29 14:23:23
举报

LeetCode 402. Remove K Digits 已知一个使用字符串表示的非负整数num,将num中的k个数字移除, 求移除k个数字后,可以获得的最小的可能的新数字。(num不会以0开头,num长度小于10002)

输入 : num = “1432219” , k = 3 在去掉3个数字后得到的很多很多可能里,如1432、4322、2219、1219、 1229...;去掉数字4、3、2得到的1219最小!

代码语言:javascript
复制
class Solution{
public:
    std::string removeKdigits(std::string num, int k){// 返回的结果用字符串来表示
    }
};
分析

假设 num = 1432219 ; k = 1, 分别去掉1, 4, 3, 2, 2, 1, 9 得到数字:

分析与常识: 若去掉某一位数字,为了使得到的新数字最小,需要尽可能让得到的新数字优先 最高位最小,其次次高位最小, 再其次第3位最小...

算法设计

使用栈存储最终结果或删除工作,从高位向低位遍历num, 如果遍历的数字大于栈顶元素,则将该数字push入栈 如果小于栈顶元素则进行pop弹栈,直到栈为空或不能再删除数字 (k==0)或栈顶小于当前元素为止。 最终栈中从栈底到栈顶存储的数字,即为结果。

边界条件

1.当所有数字都扫描完成后,k仍然>0,应该做怎样的处理? 例如: num = 12345, k = 3 时。 2.当数字中有0出现时,应该有怎样的特殊处理? 例如: num = 100200, k = 1 时。 3.如何将最后结果存储为字符串并返回?

代码语言:javascript
复制
class Solution{
public:
    std::string removeKdigits(std::string num, int k){
    std::vector<int> S;//使用vector当作栈(因为vector可以遍历)
    std::string result = "";存储最终结果的字符串
    for(int i = 0;i <num.length();i++){//最高位循环扫描数字num
        int number = num[i] - '0';//将字符型num转换整数;
        while(S.size() != 0 && S[S.size() -1]>number  && k>0){//当栈不空,栈顶元素大于number
            S.pop_back();
            k --;
        }
        if(number !=0 || S.size() != 0){
            S.push_back(number);
        }
    while(S.size() && k>0){//如果栈不空仍然可以删除数字
        S.pop_back();
        k--;
    for(int i = 0;i<S.size();i++){
        result.append(1,'0'+S[i]);//转换成字符串
      }
    if(result == ""){
          result = "0";
      }
    return result;
      
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.03.13 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 分析
  • 算法设计
  • 边界条件
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档