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 个数字，使得最后的数字最小。
不难发现以下的规律：
- 如果字符串长度和 k 相等，或者字符串长度为 0，均返回 ‘0’。
- 如果 k 为 0，直接返回 num。
- 对于 num = “1432219”，k = 3，遍历 num 中的每一个数字，如果前一个数字比后一个数字大，则移除前一个数字，然后将 k 减 1；否则，将 下标 i 往后移动移。如此循环直到 k = 0 为止。因此对于这个例子，num 和 k 先后的值为：
num = "132219", k = 2 # 4比3大，删除4num = "12219", k = 1 # 3比（第一个）2大，删除3num = "1219", k = 0 # （第二个）2比（第二个）1大，删除(第二个)2 - 对于 num = "124"、"112" 等，k = 1，发现 i = 2 时仍然不能删除，说明前面的数字是递增的（非严格），因此只需要删除后 k 个字符就能得到最终的结果。
- 对于 num = "110"，k = 2，当下标 i 等于 1 时，（第二个）1 > 0，可以删除 （第二个）1，得到 num = "10"，k = 1，并且发现 i 的下标大于 0 ，因此还要将 i 向前移动一个位置（目的是让第一个 1 与 0）比较。
- 最后，如果得到的结果有前导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本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018.10.08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
