leetcode
leetcode 1901 ~ 1950
移除所有载有违禁货物车厢所需的最少时间

移除所有载有违禁货物车厢所需的最少时间

难度:

标签:

题目描述

代码结果

运行时间: 716 ms, 内存: 17.1 MB


/*
 * 思路:
 * 1. 使用Stream处理字符串,计算从左端、右端和中间移除违禁车厢的最小时间。
 */
import java.util.stream.IntStream;

public class RemoveIllegalGoodsStream {
    public static int minimumTime(String s) {
        int n = s.length();
        int leftRemoval = (int) IntStream.range(0, n)
            .filter(i -> s.charAt(i) == '1')
            .map(i -> i)
            .average()
            .orElse(0) * 2;

        int rightRemoval = (int) IntStream.range(0, n)
            .filter(i -> s.charAt(n - 1 - i) == '1')
            .map(i -> i)
            .average()
            .orElse(0) * 2;

        int middleRemoval = (int) IntStream.range(0, n)
            .filter(i -> s.charAt(i) == '1')
            .count() * 2;

        return Math.min(leftRemoval, Math.min(rightRemoval, middleRemoval));
    }

    public static void main(String[] args) {
        System.out.println(minimumTime("1100101")); // 输出:5
        System.out.println(minimumTime("0010")); // 输出:2
    }
}

解释

方法:

此题解采用一种贪心策略,结合动态规划的思想,来找出移除所有违禁货物车厢所需的最少时间。算法思路包括计算两个主要值: 1. `re`:在处理到当前字符时,如果选择从左端或右端开始移除,到目前为止所需的最少时间。 2. `curmin`:在处理到当前字符时,如果选择从任意位置移除违禁货物车厢,到目前为止所需的最少时间。 对于每个字符,如果是'0'(不含违禁货物),则直接继续;如果是'1'(含违禁货物),则计算两种策略的最小值:即从左端开始移除到当前位置,或者从当前位置向右移除。同时更新`curmin`为直接移除当前位置的车厢或保持之前的最小值(即在此之前的任何位置移除车厢)。最终,返回所有字符处理完毕后的最小值。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
算法中的`curmin`变量是如何在不同迭代中更新的,能详细解释其逻辑和作用吗?
`curmin`变量在算法中非常关键,它记录了在当前迭代点之前,从任意位置开始移除车厢并处理到当前位置为止,所需的最小时间。在每次迭代中,如果当前字符为'1'(即包含违禁货物),则需要决定是继续保留之前的最小成本`curmin`,还是选择在当前位置新增一个移除操作(成本为2)。具体来说,`curmin`在每次迭代中通过`min(curmin + 2, i + 1)`进行更新。这里`curmin + 2`代表从前一字符的最佳位置继续处理,并增加2的成本(因为当前位置也是'1'),而`i + 1`代表从头开始直接移除到当前位置(包含当前位置)。这种更新确保了每个位置都考虑了从开始到当前位置的最低成本解决方案。
🦆
在代码中,`re = min(re, curmin + len(s) - i)`这一步的逻辑是基于什么考虑?这里的`len(s) - i`代表什么?
这行代码的目的是计算如果选择在当前位置或之前的某个位置处理完所有包含违禁货物的车厢,所需的总时间。`curmin`表示到当前位置前的任意位置处理完所需的最小时间,而`len(s) - i`代表从当前位置(包含)到字符串末尾的距离,即如果决定从当前位置开始向右移除所有车厢直到字符串末尾所需的操作数。因此,`curmin + len(s) - i`是一个综合考虑了从当前位置向右移除与之前的最优解的总成本。这一步的计算是为了找到一个全局最优,即整个字符串处理完毕时的最小时间。
🦆
题解提到了使用贪心策略结合动态规划,具体的贪心策略是如何体现在算法中的?
贪心策略在此算法中体现在每次迭代时都尝试找到最小的成本解决方案。具体地说,每次遇到一个'1'时,算法会贪心地选择两个选项中的最小值:继续沿用之前的最小成本`curmin`,或者从当前位置开始新的移除操作。这种每步选择当前最优解的策略是贪心算法的特征。同时,通过动态地更新`curmin`和`re`来保持记录并最终得到全局的最优解,这反映了动态规划的特点,即基于子问题的最优解构建全局最优解。

相关问题