楼主:
yam276 ('_')
2024-06-24 17:08:49※ 引述《oin1104 (是oin的说)》之铭言：
: 今天什么死妈题目
: 好想打手枪
思路：
这一题给你的k绑死了你
代表说要翻转就只能翻转k长度
所以会遇到1被前面牵连 被翻转之后是0
还要再被翻转一次才能变1
因此翻转会有奇数跟偶数次的差别
可以画出真值表
翻转次数
奇数 偶数
当前为0 0 1
当前为1 1 0
意思就是
你遇到0 又翻转过偶数次
代表它还是0 要翻转一次变成1
你遇到1 又翻转过奇数次
代表它变成0 要翻转一次变成1
并且翻转次数要随着sliding windows更新
但也只有一开始没出k之前不需要 之后都要
Code:
impl Solution {
pub fn min_k_bit_flips(nums: Vec<i32>, k: i32) -> i32 {
let n = nums.len();
let mut flip_count = 0;
let mut current_flips = 0;
let mut is_flipped = vec![0; n];
for i in 0..n {
if i - k as usize >= 0 {
current_flips ^= is_flipped[i - k as usize];
}
if current_flips % 2 == nums[i] as i32 {
if i + k as usize > n {
return -1;
}
flip_count += 1;
current_flips += 1;
is_flipped[i] += 1;
}
}
flip_count
}
}