Q402 Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

The length of num is less than 10002 and will be ≥ k. The given num does not contain any leading zero.

Example 1:
Input: num = "1432219", k = 3
Output: "1219"

Explanation: Remove the three digits 4, 3, and 2 
to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1
Output: "200"

Explanation: Remove the leading 1 and the number is 200. 
Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2
Output: "0"

Explanation: Remove all the digits from the number and 
it is left with nothing which is 0.
解题思路:

这道题是说,给定的一个字符串数字 num,从中移除 k 个数字,使得最后的数字最小。

不难发现以下的规律:

  1. 如果字符串长度和 k 相等,或者字符串长度为 0,均返回 ‘0’。
  2. 如果 k 为 0,直接返回 num。
  3. 对于 num = “1432219”,k = 3,遍历 num 中的每一个数字,如果前一个数字比后一个数字大,则移除前一个数字,然后将 k 减 1;否则,将 下标 i 往后移动移。如此循环直到 k = 0 为止。因此对于这个例子,num 和 k 先后的值为: num = "132219", k = 2 # 4比3大,删除4 num = "12219", k = 1 # 3比(第一个)2大,删除3 num = "1219", k = 0 # (第二个)2比(第二个)1大,删除(第二个)2
  4. 对于 num = "124"、"112" 等,k = 1,发现 i = 2 时仍然不能删除,说明前面的数字是递增的(非严格),因此只需要删除后 k 个字符就能得到最终的结果。
  5. 对于 num = "110",k = 2,当下标 i 等于 1 时,(第二个)1 > 0,可以删除 (第二个)1,得到 num = "10",k = 1,并且发现 i 的下标大于 0 ,因此还要将 i 向前移动一个位置(目的是让第一个 1 与 0)比较。
  6. 最后,如果得到的结果有前导0,要删除。

注:此题有很多边界情况,要综合考虑各种情况。

Python 实现:
class Solution:
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        lens = len(num)
        if lens == 0 or lens == k:
            return '0'
        if k == 0:
            return num
        i = 0
        while i < len(num) - 1 and k > 0:
            if num[i] > num[i+1]:
                num = num[:i] + num[i+1:]
                k -= 1
                if i > 0:  # "110"
                    i -= 1   
            else:
                i += 1
        if k > 0:  # 删除末尾k个数字
            num = num[:len(num)-k]
        while len(num) > 1 and num[0] == '0':  # 删除前导0
            num = num[1:]
        return num

print(Solution().removeKdigits("1432219", 3))  # 1219
print(Solution().removeKdigits("10200", 1))  # 200
print(Solution().removeKdigits("10", 2))  # 0
print(Solution().removeKdigits("112", 2))  # 1
print(Solution().removeKdigits("110", 2))  # 0
print(Solution().removeKdigits("996414", 2))  # 6414
print(Solution().removeKdigits("12345", 2))  # 123
print(Solution().removeKdigits("12354", 1))  # 1234

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

16(03)总结增强for循环,静态导入,可变参数

3:增强for循环(掌握) (1)是for循环的一种 (2)格式: for(元素的数据类型 变量名 : 数组或者Collection集合的对象) { 使...

3877
来自专栏赵俊的Java专栏

最小子数组

2623
来自专栏从零开始学 Web 前端

05 - JavaSE之数组

1554
来自专栏null的专栏

LeetCode——Two Sum

题目: Given an array of integers, find two numbers such that they add up to a spec...

3225
来自专栏用户画像

7.2.1 直接插入排序

插入排序是一种简单直观的排序方法,其基本思想在于每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列,直到全部记录插入完成。

942
来自专栏java一日一条

JAVA集合类汇总

数组(可以存储基本数据类型)是用来存现对象的一种容器,但是数组的长度固定,不适合在对象数量未知的情况下使用。 集合(只能存储对象,对象类型可以不一样)的长度可变...

1523
来自专栏武培轩的专栏

Leetcode#191. Number of 1 Bits(位1的个数)

编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

591
来自专栏赵俊的Java专栏

最长上升连续子序列

1674
来自专栏运维技术迷

PHP-数组排序

分别定义一个数值数组和一个关联数组. $age=array("lili"=&gt;"23","bob"=&gt;"30","ben"=&gt;"44"); $c...

3156
来自专栏desperate633

LintCode 翻转字符串题目分析代码

说明 单词的构成:无空格字母构成一个单词 输入字符串是否包括前导或者尾随空格?可以包括,但是反转后的字符不能包括 如何处理两个单词间的多个空格?在反转字符...

742

扫码关注云+社区

领取腾讯云代金券