问题描述
有一个由数字组成的字符串num1,我们从其中删掉n个字符得到一个新的数字num2,找到num2的最小值。
保证num1 有‘0-9’组成, n 小于 num1 的长度,‘012’等情况算作合法解(整数12)。
示例:
num1 = ‘2651321’
n = 4
预期结果:121
解题思路:
从字符串中删除n个字符,可以看做在长度为 l 的num1中按顺序挑选 m =(l-n)个字符组成最小的数字。
首先想到的就是num2的第一位数字要尽量小,同时,因为不能改变num1中字符的顺序,所以还要保证取出第一位后,后面的数字可以满足 (l-n)- 1 的长度。
之后的数字需要在第一位数字之后的数字中再按上述方式查找,直到满足 m 长度。
代码实现
num1 = '2651321'
n = 4
def find_min(start: int, end: int, nums: str):
# 搜索 nums[start:end+1]中最小的数字
index, num = 0, '9'
for i, c in enumerate(nums[start:end + 1]):
if c < num:
index = i
num = c
return index, num
m = len(num1) - n
res = []
i, start = 1, 0
while len(res) < m:
end = n + i # l - (m - i) - 1 = n + i - 1, 这里i表示结果中的第i个数,end表示下标,所以要 - 1
index, min_num = find_min(start, end, num1)
start = index + 1
res.append(min_num)
i += 1
print(''.join(res))
注:
没有找到leetcode中对应的题目,无法对代码的完备性进行测试。


![删除字符获取字符串中的最大整数 [python] 删除字符获取字符串中的最大整数 [python]](http://www.mshxw.com/aiimages/31/976883.png)
