leetcode
leetcode 901 ~ 950
K 连续位的最小翻转次数

K 连续位的最小翻转次数

难度:

标签:

题目描述

代码结果

运行时间: 85 ms, 内存: 19.4 MB


/*
 思路: 
 1. 与普通 Java 版本类似, 只是使用 Java Stream 来处理数组。
 2. 使用 List 来存储 tracking 信息, 使用 forEach 来遍历数组。
 */

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        List<Integer> tracking = IntStream.range(0, n).map(i -> 0).boxed().collect(Collectors.toList());
        final int[] flips = {0};
        final int[] isFlipped = {0};
        IntStream.range(0, n).forEach(i -> {
            if (i >= k) isFlipped[0] ^= tracking.get(i - k);
            if (nums[i] == isFlipped[0]) {
                if (i + k > n) {
                    flips[0] = -1;
                    return;
                }
                tracking.set(i, 1);
                isFlipped[0] ^= 1;
                flips[0]++;
            }
        });
        return flips[0];
    }
}

解释

方法:

该题解采用了滑动窗口的思路。通过一个额外的数组 `is_flipped` 来记录每个位置是否进行了翻转。变量 `flip` 用于记录当前位置的翻转状态(0或1,表示无翻转或有翻转)。在遍历数组 `nums` 时,如果当前位置 i 大于或等于 k,根据 `is_flipped` 数组更新 `flip` 的状态。如果 `nums[i]` 与 `flip` 相同,说明需要进行翻转,此时检查是否有足够的空间进行翻转(即 i + k 是否超过数组长度),如果不够则返回 -1,否则在 `is_flipped` 标记此位置,并更新翻转次数 `res` 和翻转状态 `flip`。最终返回翻转次数 `res`。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在实现中使用了数组`is_flipped`来记录每个位置是否进行了翻转,这个方法与直接修改原数组`nums`相比有何优势?
使用`is_flipped`数组的优势在于它保持了原数组`nums`的不变性,这样原始数据可以在算法执行后仍然可用于其他目的。此外,直接修改`nums`可能会使原始数据丢失,增加错误翻转或重复翻转的风险。`is_flipped`数组仅记录翻转操作而不改变原数组,使得操作更清晰、逻辑更容易理解和维护。
🦆
为什么在判断当前位置是否需要翻转时,只检查了`nums[i]`与`flip`是否相同?在什么情况下这两者会不同?
检查`nums[i]`与`flip`是否相同是为了确定当前位置的实际值是否符合目标值(即0变为1,1变为0)。`flip`变量记录了当前位置由于之前的翻转操作导致的值变化。如果`nums[i]`与`flip`相同,表示当前位的值未达到目标状态,需要翻转。这两者会不同的情况出现在之前的翻转操作使得当前位的实际值已经是期望值,此时无需再次翻转。
🦆
如果`i + k > n`时返回`-1`,这种情况下为什么不能继续翻转直到数组末尾?
如果`i + k > n`,意味着从当前位置开始的k位翻转将超出数组边界,无法形成一个完整的k长度的翻转区间。这样的部分翻转将无法保证每个元素都被正确处理,从而无法达到题目要求所有元素满足条件的目标。因此,当无法进行完整的k位翻转时,返回`-1`表示无法通过翻转达到要求的状态。
🦆
变量`flip`是如何确保在每个位置正确反映当前的翻转状态的?能否详细解释其作用和更新机制?
`flip`变量是一个关键的状态指示器,用于跟踪到当前位置为止的累积翻转影响。在遍历数组时,`flip`会根据`is_flipped`数组的值进行更新。每当处理到一个新的位置时,如果该位置之前的距离为k的位置被翻转过(即`is_flipped[i - k] == 1`),则`flip`的值会改变(0变1,1变0),以反映该翻转操作对当前位置及后续位置的影响。这样,每个位置的`flip`值都会准确表示由于之前所有翻转操作导致的当前位置的实际值变化。

相关问题

灯泡开关

初始时有 n 个灯泡处于关闭状态。第一轮,你将会打开所有灯泡。接下来的第二轮,你将会每两个灯泡关闭第二个。

第三轮,你每三个灯泡就切换第三个灯泡的开关(即,打开变关闭,关闭变打开)。第 i 轮,你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮,你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

 

示例 1:

输入:n = 3
输出:1 
解释:
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 

你应该返回 1,因为只有一个灯泡还亮着。

示例 2:

输入:n = 0
输出:0

示例 3:

输入:n = 1
输出:1

 

提示:

  • 0 <= n <= 109