Python 去掉 k 个整数后的最小值(贪心算法1）

qiuyouzhi

Python 去掉 k 个整数后的最小值

先理解一下要求:

给出一个整数1593212，删掉三个数字，新整数最小的情况是1212（删掉593）

给出一个整数30200，删去一个数字，新整数最小的情况是200.（删掉3,0不能作为数字的首位，也一起删掉）

给出一个整数10，删去两个数字，新整数最小情况是0（删掉1，还剩0，把0删掉，还是0）

思路：

肯定是先降低高位的数字，那怎么降低呢？很简单，

把原整数的所有数字从左到右进行比较，如果发现

某一位的数字大于它右面的数字，那么在删除这个

数字后，必然会使该数位的值降低。

再举个栗子：

给出整数41270936,删除一个数字的最小值是？

是4，因为4是第一个大于右边数字大的数（4>1）

那么再删除一个呢？

因为1<2,2<7,7>0,所以应该删除7！

这里每一步都要求得到删除一个数字后的最小值，经历3次，相当于求出了删除k（k = 3）个数字后的最小值。

像这样依次求得局部最优解，最终得到全局最优解的思想，叫做贪心算法。

代码实现：

1. def remove_k_digits(num, k):
   
2.     num = list(num)
   
3.     for i in range(k):
   
4.         hasCut = False
   
5.         #从左向右遍历，找到比自己右侧数字大的数字并删除它那个数字
   
6.         for j in range(len(num)-1):
   
7.             if num[j] > num[j+1]:
   
8.                 num.remove(num[j+1])
   
9.                 hasCut = True
   
10.                 break
    
11. 
    
12.     #如果没有找到，则删除最后一个数字
    
13.     if hasCut == False:
    
14.         num.pop()
    
15. 
    
16.     #清除整数左侧的数字0
    
17.     start = 0
    
18.     for j in range(len(num)-1):
    
19.         if num[j] != '0':
    
20.             break
    
21.         start += 1
    
22.     num = num[start:len(num)]
    
23.     #如果所有数字都被删除了，就返回0
    
24.     if len(num) == 0:
    
25.         return '0'
    
26.    
    
27.     return num
    
28. 
    
29. print(remove_k_digits('1593212', 3))

复制代码

当然，这样还不是最佳方案，我们会在下一节继续探讨！