求解删数问题 贪心法

删数问题可以使用贪心算法进行求解。贪心算法的思路是每次选择当前最优的解决方案，最终得到全局最优解。

具体来说，对于这个问题，我们可以从高位到低位扫描数字，如果当前数字比后面的一个数字大，那么就删除当前数字，这样可以保证删除的数字最小。如果删除的数字不足k个，那么我们可以从低位开始继续删除数字，直到删除了k个数字为止。

下面是一个具体的实现：

def delete_num(num, k):
    num_list = list(num)
    i = 0
    while k > 0 and i < len(num_list) - 1:
        if num_list[i] > num_list[i+1]:
            num_list.pop(i)
            k -= 1
            if i > 0:
                i -= 1
        else:
            i += 1
    # 如果还需要删除数字，从末尾开始删
    while k > 0:
        num_list.pop()
        k -= 1
    return "".join(num_list)

其中num是要删除数字的字符串，k是要删除的数字个数。该函数返回删除数字后的字符串。

时间复杂度为$O(n)$，其中n是数字的位数。

相关问题

求解汽车加油问题贪心法

汽车加油问题是一个经典的贪心算法问题，也被称为加油站问题。问题描述如下：

有一辆汽车要从起点出发到达终点，途中有若干个加油站，汽车行驶一定距离需要消耗一定的油量，且汽车的油箱有限，只能加满油才能出发。现在给定汽车的初始油量和行驶距离，求出汽车是否能到达终点，如果能，最少需要在哪些加油站加油。

解决这个问题的贪心策略是从起点开始依次遍历每个加油站，如果当前加油站可以到达终点，那么就不需要在该加油站加油，直接继续前往下一个加油站。如果无法到达终点，则需要在当前加油站加油，加足够的油量使汽车能够到达下一个加油站或者终点。

代码实现如下：

def min_refills(x, n, L, stops):
    num_refills = 0  # 加油次数
    current_refill = 0  # 当前加油站位置
    while current_refill <= n:
        last_refill = current_refill
        while current_refill <= n and stops[current_refill + 1] - stops[last_refill] <= L:
            current_refill += 1
        if current_refill == last_refill:
            return -1  # 无法到达终点
        if current_refill <= n:
            num_refills += 1  # 加油
    return num_refills

其中，x 表示汽车的初始油量，n 表示加油站的数量，L 表示汽车行驶的距离，stops 表示每个加油站距离起点的距离。函数返回值为汽车需要加油的次数，如果无法到达终点则返回 -1。

这个算法的时间复杂度为 O(n)，其中 n 表示加油站的数量，因为需要遍历每个加油站一次。

贪心法求解组合背包问题

根据提供的引用内容，我们可以了解到贪心算法是求解01背包问题的一种方法。而组合背包问题是指每个物品可以选取多次的情况下，如何选择物品使得总价值最大。下面是贪心法求解组合背包问题的步骤：

1. 计算每个物品的单位价值（即每个物品的价值除以重量）。
2. 将物品按照单位价值从大到小排序。
3. 从单位价值最大的物品开始，依次将该物品加入背包中，直到背包无法再加入该物品为止。
4. 重复步骤3，直到所有物品都被考虑过。

下面是一个Python实现的例子：

def knapsack(W, wt, val):
    n = len(wt)
    unit_val = [(val[i] / wt[i], wt[i], val[i]) for i in range(n)]
    unit_val.sort(reverse=True)
    max_val = 0
    for i in range(n):
        if W == 0:
            return max_val
        if unit_val[i][1] <= W:
            W -= unit_val[i][1]
            max_val += unit_val[i][2]
        else:
            max_val += unit_val[i][0] * W
            W = 0
    return max_val

其中，W表示背包的容量，wt表示每个物品的重量，val表示每个物品的价值。函数返回背包能够装下的最大价值。