Java 中的最小激活灯泡问题

在一个监狱里，有一个走廊。走廊的长度是 L 个单位。还有一个大小为 L 的数组 lightArr[]。lightArr[] 只包含 0 和 1。走廊的每个单位都有一个灯。如果输入数组 lightArr[] 的 j 索引处的值为 0，则表示该位置的灯是故障的；如果值为 1，则表示灯是好的。请注意，故障的灯永远无法打开。

走廊中的所有灯都有 lightPow 的功率。如果一个灯放在 j 索引处，它可以照亮从 (j - lightPow + 1) 到 (j + lightPow - 1) 的走廊。任务是打开最少数量的灯，以照亮整个走廊。最初，所有灯都处于关闭状态。

示例 1

输入: lightArr[] = {1, 1, 0, 1, 1}, lightPow = 3

输出 2

解释: 让我们看看每盏灯的范围。

对于第一个位置的灯，lightArr[0] 为 1。因此，范围是 [0 - 3 + 1, 0 + 3 - 1] = [-2, 2]。

对于第二个位置的灯，lightArr[1] 为 1。因此，范围是 [1 - 3 + 1, 1 + 3 - 1] = [-1, 3]。

对于第三个位置的灯，lightArr[2] 为 0。因此，无法计算范围，因为灯是故障的。

对于第四个位置的灯，lightArr[3] 为 1。因此，范围是 [3 - 3 + 1, 3 + 3 - 1] = [1, 5]。

对于第五个位置的灯，lightArr[4] 为 1。因此，范围是 [4 - 3 + 1, 4 + 3 - 1] = [2, 6]。

下图显示了相同的情况。

从上面的图可以看出，我们可以选择打开第 1 盏和第 4 盏灯，或者第 1 盏和第 5 盏灯。我们甚至可以打开第 2 盏和第 4 盏灯，或者第 2 盏和第 5 盏灯。因此，无论我们选择哪种组合，至少需要两盏灯来照亮整个走廊。所以，答案是 2。

示例 2

输入: lightArr[] = {0, 0, 0, 1, 1, 1, 1, 1, 1}, lightPow = 3

输出: 无法照亮整个走廊

解释: 即使我们打开所有灯，也无法照亮第一个位置。

使用动态规划

观察发现，当照亮整个走廊所需灯数最少时，照亮走廊的一部分也需要最少的灯数，即照亮从 0 到 1 个单位的走廊、0 到 2 个单位的走廊、0 到 3 个单位的走廊等等，都需要最少的灯数。因此，我们可以将大问题分解为小问题，找到它们的解，然后利用这些解来找到所需的答案。

步骤 1: 创建一个大小为 n + 1 的数组（也可以是 ArrayList），其中 n 是数组 lightArr[] 中的元素总数。在我们这里是 dpArr[]。

步骤 2: 将每个元素初始化为整数的最大值（Integer.MAX_VALUE）。

步骤 3: 将 dpArr[0] 赋值为 0，因为照亮 0 个单位的走廊不需要任何灯。

步骤 4: 定义 dpArr[j] 为 dpArr[j] 中包含的值，即照亮从 0 到 j 个单位走廊所需的最小灯数。

步骤 5: 开始一个循环，遍历输入数组 lightArr[] 的每个元素。如果元素的值为 0，则移动到下一个元素。否则，计算灯的范围（假设是第 k 盏灯），然后开始另一个循环，遍历这个范围。在这个范围内，计算覆盖走廊 0 到 k 个单位所需的最小灯数。如果 dpArr[n] 的值等于 Integer.MAX_VALUE，则无法照亮整个走廊；否则，是可以的。

步骤 6: 返回 dpArr[n] 的值。

实施

观察上述算法的实现。

文件名: MinLightActivate.java

输出

For the following lights: 
1 1 0 1 1 
The minimum number of lights to light up the whole corridor is: 2

For the following lights: 
0 0 0 1 1 1 1 1 1 
It is not possible to light up the whole corridor.

复杂度分析: 我们使用了嵌套的 for 循环来计算答案。因此，程序的 time complexity 是 O(n^2)。此外，我们使用了辅助数组来存储结果，因此 space complexity 是 O(n)，其中 n 是数组中的元素总数。

使用贪心方法

每盏灯的功率都是 B。因此，如果我们从左边开始，到达某个位置，然后选择最右边的灯来覆盖该位置，我们将获得覆盖整个走廊所需的最小灯数。

观察以下算法。

步骤 1: 使用一个变量 current，将其视为至少被一盏灯照亮的最后一个灯的位置。初始化 current = -1；

步骤 2: 开始如下迭代

对于每个 current 位置，我们在范围 [current - lightPow + 1, current + lightPower - 1] 中找到最右边的灯，然后将 current 更新为这个灯的位置，并对其他灯重复此过程。

实现：迭代

使用上面定义的算法观察上述算法的实现。

文件名: MinLightActivate1.java

输出

For the following lights: 
1 1 0 1 1 
The minimum number of lights to light up the whole corridor is: 2

For the following lights: 
0 0 0 1 1 1 1 1 1 
It is not possible to light up the whole corridor.

复杂度分析: 我们使用了嵌套循环来计算答案。然而，内部 for 循环正在调整变量 i 的值。因此，输入数组的元素只被遍历一次。因此，程序的 time complexity 是 O(n)。此外，我们没有使用任何额外的空间来存储结果，因此 space complexity 是常数，即 O(1)。

实现：递归

我们甚至可以使用递归来找到解决方案。观察以下程序。

文件名: MinLightActivate2.java

输出

For the following lights: 
1 1 0 1 1 
The minimum number of lights to light up the whole corridor is: 2

For the following lights: 
0 0 0 1 1 1 1 1 1 
It is not possible to light up the whole corridor.

复杂度分析: time complexity 为 O(n^2)，space complexity 为 O(n)。