402. 移掉K位数字——n位数去除m位数,剩下的数组成的新数最大或者最小_一个n位数k,从n位中去掉m个数字,使剩下的数字最大-程序员宅基地

技术标签: 编程题  

# encoding=utf-8

class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """

        # 特殊情况
        if k == 0:
            return num
        if k == len(num):
            return "0"

        # 将num转换为list好处理,结果:123  --> ["1","2","3"]
        num = list(num)

        # 循环k趟,每趟去掉一位数,所以一共去除k位数
        while k > 0:
            flag = 1

            # 如果num[idx] > num[idx + 1],那么应该去掉 num[idx]
            for idx in range(len(num) - 1):
                if num[idx] > num[idx + 1]:
                    num.pop(idx)

                    k -= 1
                    flag = 0
                    break

            # 如果这一趟没有找到,那么意思就是对每一个位置,都有num[idx] <= num[idx + 1],那么此时,去掉最后一位上的数,剩下的数组成的当前趟的新数就是最小的,因为当前趟最后一个数是最大的。
            if flag == 1:
                k -= 1
                num.pop(-1)

        # 去除结果中的前导0。
        while len(num) > 0:
            if num[0] == "0":
                num.pop(0)
            else:
                break

        # 有可能走完k趟,并且去掉前导0后,num就为空了,此时需要返回0. 例如:num=1000   k=1
        if len(num) == 0:
            return "0"
        else:
            return "".join(num)

# print Solution().removeKdigits(num="112", k=1)

2.同理也可以寻找最大数:即n位数去除m位数,使得剩下的数组成的新数最大,原理同上,只改一个条件即可。

即将  if num[idx] > num[idx + 1]  改为:  if num[idx] < num[idx + 1]   即可。
# encoding=utf-8
'''
leetcode402 是n位数去除m位数剩下的数最小,那么同理也可以做n位数去除m位数剩下的数最大

'''


class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """

        # 特殊情况
        if k == 0:
            return num
        if k == len(num):
            return "0"

        # 将num转换为list好处理,结果:123  --> ["1","2","3"]
        num = list(num)

        # 循环k趟,每趟去掉一位数,所以一共去除k位数
        while k > 0:
            flag = 1

            # 如果num[idx] < num[idx + 1],那么应该去掉 num[idx]
            for idx in range(len(num) - 1):
                if num[idx] < num[idx + 1]:
                    num.pop(idx)

                    k -= 1
                    flag = 0
                    break

            # 如果这一趟没有找到,那么意思就是对每一个位置,都有num[idx] >= num[idx + 1],那么此时,去掉最后一位上的数,剩下的数组成的当前趟的新数就是最大的,因为当前趟最后一个数是最小的。
            if flag == 1:
                k -= 1
                num.pop(-1)

        # 去除结果中的前导0。
        while len(num) > 0:
            if num[0] == "0":
                num.pop(0)
            else:
                break

        # 有可能走完k趟,并且去掉前导0后,num就为空了,此时需要返回0. 例如:num=1000   k=1
        if len(num) == 0:
            return "0"
        else:
            return "".join(num)

print Solution().removeKdigits(num="1008908",k=5)

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/moshiyaofei/article/details/100599431

智能推荐

Java线程(七):锁对象Lock-同步问题更完美的处理方式-程序员宅基地

文章浏览阅读151次。上一篇:Java线程(六) Lock是java.util.concurrent.locks包下的接口,Lock 实现提供了比使用synchronized 方法和语句可获得的更广泛的锁定操作,它能以更优雅的方式处理线程同步问题,我们拿Java线程(二)中的一个例子简单的实现一下和sychronized一样的效果,代码如下:public class LockTest { p..._线程同步 lock对象

Java动态编译JavaCompiler_java 动态编译导入包-程序员宅基地

文章浏览阅读3.9k次。一、tools.jar问题:Java在进行动态编译的时候需要用到tools.jar资源包,此包在jdk\lib目录中。若tools.jar不存在则会出现进行编译时提示空指针异常:对于缺少jar包,首先想到的解决办法是找到需要的jar包并且将其加入到buildpath,但是我们发现只是将tools.jar加入到java buildpath中仍然会出现空指针异常。后来经过查询相关资料,java..._java 动态编译导入包

openwrt安装aliddns使用阿里云ddns_aliddns ipk-程序员宅基地

文章浏览阅读2.9w次,点赞2次,收藏11次。openwrt安装aliddns使用阿里云ddns一些小伙伴安装了openwrt之后发现没法使用阿里云的ddns解析这里告诉你怎么添加aliddns插件需要会一些linux基础命令和ssh分四步安装依赖下载插件上传插件安装插件安装ddns-scripts、luci-app-ddns、openssl-util、wget 依赖包使用luci web界面里面的软件包管理,或者ssh使用opkg安装都一样有的openwrt自带的源地址可能下载很慢或根本无法下载,得换源下载alid_aliddns ipk

【最全笔记】基础Python爬虫入门,看完包你会写爬虫_python爬虫知识笔记集合-程序员宅基地

文章浏览阅读856次,点赞3次,收藏24次。第一章 网络爬虫之规则一、Requests库入门request库:http://www.python-requests.org安装方法:pip install requests抓取百度import requestsr=requests.get("http://www.baidu.com")r.status_coder.encoding='utf-8'r.textre..._python爬虫知识笔记集合

[cdq分治] bzoj3262: 陌上花开_cdq分治bzoj-程序员宅基地

文章浏览阅读179次。bzoj 3262: 陌上花开:http://www.lydsy.com/JudgeOnline/problem.php?id=3262三维偏序(向我一样不懂啥偏序的先戳这里:http://www.cnblogs.com/AKCqhzdy/p/8017372.html) 第一个维度直接排序解决 第二个维度的话cdq搞一搞 符合条件就直接丢到树状数组里去 sum=树状数组的getsum..._cdq分治bzoj

[OpenBMC] 简单解析 smbios-mdr_bmc entity manager configuration-程序员宅基地

文章浏览阅读2.2k次。(*如果之后架构有变,这边不会更新)smbios-mdrGitHub - openbmc/smbios-mdrhttps://github.com/openbmc/smbios-mdrMDR(Managed Data Region) 是 OpenBMC中取得SMBIOS Table并解析其內容的一个功能,目前网上(在没有特别帐号权限下)能找到的资料蛮少的,所以这边会尽量用公开资料做个分析 如果還不認識SMBIOS 可以先看之前寫的文章非专业的SMBIOS笔记-程序员宅基地https://.._bmc entity manager configuration

随便推点

1261:【例9.5】城市交通路网 《信息学奥赛一本通:动态规划基础》_t1261:城市交通路网 逆推法 l f[i]=1000000;-程序员宅基地

文章浏览阅读527次。http://ybt.ssoier.cn:8088/problem_show.php?pid=1261图表示城市之间的交通路网,线段上的数字表示费用,单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。【算法分析】逆推法设f[i]表示点i到v10的最短路径长度,则 f[10]=0f[i]=min{ a[i][x]+f[x] 当a[i][x]>0 ..._t1261:城市交通路网 逆推法 l f[i]=1000000;

leetcode:516. 最长回文子序列_leetcode 516. 最长回文子序列-程序员宅基地

文章浏览阅读272次。题目来源leetcode题目描述题目解析动态规划(1)确定状态最后一步:最优策略产生最长的回文子串T,长度是M情况一:回文串长度是1,即一个字母情况二:回文串长度大于1,那么必须有T[0] = T[M-1]设T[0]为S[i],T[M-1]是S[j],则T剩下的部分T[1…M-2]仍然是一个回文串,而且是S[i+1…j-1]的最长回文串子问题:要求S[i...j]的最长回文子串如果S[i] = S[j],需要知道S[i+1…j-1]的最长回文子串如果S[_leetcode 516. 最长回文子序列

DBCP连接池配置详解,参数列表-程序员宅基地

文章浏览阅读9.5k次。Spring DBCP配置&amp;lt;bean id=“dataSource” class=“org.apache.commons.dbcp.BasicDataSource” destroy-method=“close”&amp;gt; &amp;lt;property name=“driverClassNa..._dbcp连接池配置详解

log 的抓取与分析_什么问题需要抓modem log-程序员宅基地

文章浏览阅读3.2k次。http://blog.csdn.net/yaoming168/article/details/38777727 log 的抓取与分析一、Android log框架简介二、log获取方式1、Eclipse 抓取1)根据信息类型过滤log那个显示框上面还有个下拉列表选项可以选择过滤哪些信息。a、Log.v 的调试颜色为黑色的,任何消息都会输出,这里的v代表verb_什么问题需要抓modem log

com.qq.ac.android,腾讯动漫(com.qq.ac.android) - 9.2.5 - 应用 - 酷安-程序员宅基地

文章浏览阅读240次。权限信息· 修改或删除您的USB存储设备中的内容· 读取您的USB存储设备中的内容· 读取手机状态和身份· 在其他应用之上显示内容· 修改系统设置· com.android.launcher.permission.READ_SETTINGS· com.android.launcher.permission.INSTALL_SHORTCUT· com.android.launcher.permiss..._qq tmf_shark

python3超简代码爬取桌面壁纸_四象限电脑壁纸-程序员宅基地

文章浏览阅读720次。 我们要爬取的是彼岸壁纸,官网是http://www.netbian.com/,不说了,上代码: for j in range(100, 120):#想爬取更多修改100 和 120数值 url = "http://www.netbian.com/desk/20" + str(j) + "-1920x1080.htm" response = requests.get(u..._四象限电脑壁纸