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）个数字后的最小值。

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

代码实现：

def remove_k_digits(num, k):
    num = list(num)
    for i in range(k):
        hasCut = False
        #从左向右遍历，找到比自己右侧数字大的数字并删除它那个数字
        for j in range(len(num)-1):
            if num[j] > num[j+1]:
                num.remove(num[j+1])
                hasCut = True
                break

    #如果没有找到，则删除最后一个数字
    if hasCut == False:
        num.pop()

    #清除整数左侧的数字0
    start = 0
    for j in range(len(num)-1):
        if num[j] != '0':
            break
        start += 1
    num = num[start:len(num)]
    #如果所有数字都被删除了，就返回0
    if len(num) == 0:
        return '0'
    
    return num

print(remove_k_digits('1593212', 3))

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