995。 K 连续位翻转的最小次数
难
给你一个二进制数组 nums 和一个整数 k。
k 位翻转是从 nums 中选择一个长度为 k 的子数组,同时将子数组中的每个 0 变为 1,将子数组中的每个 1 变为 0。
返回所需的k位翻转的最小次数,以使数组中不存在0。如果不可能,则返回-1.
子数组是数组的连续部分。
示例1:
- 输入: nums = [0,1,0], k = 1
- 输出: 2
- 说明: 翻转 nums[0],然后翻转 nums[2]。
示例2:
- 输入: nums = [1,1,0], k = 2
- 输出: -1
- 说明: 无论我们如何翻转大小为 2 的子数组,都不能让数组变成 [1,1,1]。
示例3:
- 输入: nums = [0,0,0,1,0,1,1,0], k = 3
- 输出: 3
- 说明:
翻转 nums[0],nums[1],nums[2]: nums 变为 [1,1,1,1,0,1,1,0]
翻转 nums[4],nums[5],nums[6]: nums 变为 [1,1,1,1,1,0,0,0]
翻转 nums[5],nums[6],nums[7]: nums 变为 [1,1,1,1,1,1,1,1]
限制:
- 1 5
- 1
解决方案:
类解决方案{
/*** @param 整数[] $nums
* @param 整数 $k
* @return 整数*/
函数 minKBitFlips($nums, $k) {
$flipped = array_fill(0, count($nums), false);
$validFlipsFromPastWindow = 0;
$翻转计数 = 0;
for ($i = 0; $i = $k) {
if ($flipped[$i - $k]) {
$validFlipsFromPastWindow--;
}
}
if ($validFlipsFromPastWindow % 2 == $nums[$i]) {
if ($i + $k > 计数($nums)) {
返回-1;
}
$validFlipsFromPastWindow++;
$翻转[$i] = true;
$flipCount++;
}
}
返回$flipCount;
}
}
联系链接
- 领英
- GitHub