→ Furina: 我好崇拜你 06/24 17:11
→ DJYOMIYAHINA: 我好崇拜你 06/24 17:11
推 oin1104: 大師 06/24 18:04
※ 引述《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
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.48.170 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719220131.A.C18.html
※ 編輯: yam276 (114.32.48.170 臺灣), 06/24/2024 17:09:38