贪心算法：N位数删除K个数字，使剩下的数字串最小
·
题目：一个n位的数，去掉其中的k位，问怎样去掉使得留下来的那个（n-k）位的数最小？
分析：（删数问题，可用贪心算法求解），方法就是从简单入手，慢慢复杂。从n=1开始推导就会发现规律，
现在假设有一个数，124682385，
假如k = 1，则结果为12462385,k = 2，结果为1242385……
可以知道：最优解是删除出现的第一个左边>右边的数，因为删除之后高位减小，很容易想...那全局最优解也就是这个了，因为删除S个数字就相当于执行了S次删除一个数，因为留下的数总是当前最优解...
def solution(num, k):
s = str(num)
flag = True
while k:
for i in range(len(s)-1):
#每次删除第一个比下一个数字大的数
if s[i] > s[i+1]:
s = s.replace(s[i],'',1)
flag = False
break
#如果所有数字递增，则删除最后几个数字直接返回
if flag:
s = s[:len(s)-k]
k -= 1
return int(s)
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
8
0- 0
已为社区贡献9条内容
所有评论(0)