2023-06-02：給定一個(gè)二進(jìn)制數(shù)組 nums 和一個(gè)整數(shù) k， k位翻轉(zhuǎn) 就是從 nums 中選擇一
2023-06-02：給定一個(gè)二進(jìn)制數(shù)組 nums 和一個(gè)整數(shù) k，
k位翻轉(zhuǎn) 就是從 nums 中選擇一個(gè)長(zhǎng)度為 k 的 子數(shù)組，
同時(shí)把子數(shù)組中的每一個(gè) 0 都改成 1 ，把子數(shù)組中的每一個(gè) 1 都改成 0。
返回?cái)?shù)組中不存在 0 所需的最小 k位翻轉(zhuǎn) 次數(shù)。如果不可能，則返回 -1。
子數(shù)組 是數(shù)組的 連續(xù) 部分。
輸入：nums = [0,1,0], K = 1。
輸出：2。
答案2023-06-02：
大體步驟如下：
1.初始化一個(gè)大小為 $n$ 的隊(duì)列?queue，用于存儲(chǔ)需要翻轉(zhuǎn)的子數(shù)組的起始下標(biāo)。
2.初始化三個(gè)變量?l、r?和?ans?分別為 0，表示當(dāng)前隊(duì)列的左端點(diǎn)、右端點(diǎn)和翻轉(zhuǎn)的次數(shù)。
3.循環(huán)遍歷數(shù)組?nums?中的每個(gè)元素?num：
??如果隊(duì)列?
queue?中存在元素，并且當(dāng)前元素下標(biāo)減去隊(duì)列左端點(diǎn)下標(biāo)等于?k，則說明隊(duì)列中的第一個(gè)元素已經(jīng)過期，將左端點(diǎn)右移一位。??如果隊(duì)列?
queue?中的元素個(gè)數(shù)為奇數(shù)，并且當(dāng)前元素與隊(duì)列最后一個(gè)元素不同，則將當(dāng)前元素下標(biāo)加入隊(duì)列尾部，同時(shí)將翻轉(zhuǎn)次數(shù)?ans?加 1。
4.如果隊(duì)列?queue?長(zhǎng)度大于 0 且隊(duì)列最后一個(gè)元素下標(biāo)加?k?大于數(shù)組長(zhǎng)度，則返回 -1 表示無法完成翻轉(zhuǎn)；否則，返回翻轉(zhuǎn)次數(shù)?ans。
時(shí)間復(fù)雜度為 $O(n)$，其中 $n$ 是數(shù)組?nums?的長(zhǎng)度。循環(huán)遍歷一次數(shù)組?nums，每個(gè)元素最多會(huì)被加入或彈出隊(duì)列一次，因此時(shí)間復(fù)雜度是線性的。
空間復(fù)雜度也是 $O(n)$，因?yàn)樾枰褂靡粋€(gè)大小為 $n$ 的隊(duì)列來存儲(chǔ)需要翻轉(zhuǎn)的子數(shù)組的下標(biāo)。同時(shí)，由于只保存了子數(shù)組的起始下標(biāo)，因此空間復(fù)雜度不會(huì)超過 $n$。需要注意的是，在 C 和 C++ 中，使用指針代替數(shù)組時(shí)需要手動(dòng)分配和釋放內(nèi)存，因此還需要額外的空間來存儲(chǔ)指向動(dòng)態(tài)分配內(nèi)存的指針。
go完整代碼如下：
package?main
import?"fmt"
func?minKBitFlips(nums?[]int,?k?int)?int?{
????n?:=?len(nums)
????queue?:=?make([]int,?n)
????l,?r,?ans?:=?0,?0,?0
????for?i?:=?0;?i?<?n;?i++?{
????????if?l?!=?r?&&?i-queue[l]?==?k?{
????????????l++
????????}
????????if?(r-l)%2?==?1?==?(nums[i]?==?1)?{
????????????queue[r]?=?i
????????????r++
????????????ans++
????????}
????}
????if?l?!=?r?&&?queue[r-1]+k?>?n?{
????????return?-1
????}
????return?ans
}
func?main()?{
????nums?:=?[]int{0,?1,?0}
????k?:=?1
????result?:=?minKBitFlips(nums,?k)
????fmt.Println("Result:",?result)
}
rust語言完整代碼如下：
fn?min_k_bit_flips(nums:?Vec<i32>,?k:?i32)?->?i32?{
????let?n?=?nums.len();
????let?mut?queue?=?vec![0;?n];
????let?(mut?l,?mut?r,?mut?ans)?=?(0,?0,?0);
????for?i?in?0..n?{
????????if?l?!=?r?&&?i?-?queue[l]?==?k?as?usize?{
????????????l?+=?1;
????????}
????????if?(r?as?i32?-?l?as?i32)?&?1?==?nums[i]?{
????????????queue[r]?=?i;
????????????r?+=?1;
????????????ans?+=?1;
????????}
????}
????return?if?l?!=?r?&&?queue[r?-?1]?+?k?as?usize?>?n?{
????????-1
????}?else?{
????????ans
????};
}
fn?main()?{
????let?nums?=?vec![0,?1,?0];
????let?k?=?1;
????let?result?=?min_k_bit_flips(nums,?k);
????println!("Result:?{}",?result);
}
c++完整代碼如下：
using?namespace?std;
int?minKBitFlips(vector<int>&?nums,?int?k)?{
????int?n?=?nums.size();
????vector<int>?queue(n);
????int?l?=?0,?r?=?0,?ans?=?0;
????for?(int?i?=?0;?i?<?n;?i++)?{
????????if?(l?!=?r?&&?i?-?queue[l]?==?k)?{
????????????l++;
????????}
????????if?(((r?-?l)?&?1)?==?nums[i])?{
????????????queue[r++]?=?i;
????????????ans++;
????????}
????}
????return?(l?!=?r?&&?queue[r?-?1]?+?k?>?n)???-1?:?ans;
}
int?main()?{
????vector<int>?nums?=?{?0,?1,?0?};
????int?k?=?1;
????int?result?=?minKBitFlips(nums,?k);
????cout?<<?"Result:?"?<<?result?<<?endl;
????return?0;
}
c語言完整代碼如下：
int?minKBitFlips(int*?nums,?int?numsSize,?int?k)?{
????int*?queue?=?(int*)malloc(numsSize?*?sizeof(int));
????int?l?=?0,?r?=?0,?ans?=?0;
????for?(int?i?=?0;?i?<?numsSize;?i++)?{
????????if?(l?!=?r?&&?i?-?queue[l]?==?k)?{
????????????l++;
????????}
????????if?(((r?-?l)?&?1)?==?nums[i])?{
????????????queue[r++]?=?i;
????????????ans++;
????????}
????}
????free(queue);
????return?(l?!=?r?&&?queue[r?-?1]?+?k?>?numsSize)???-1?:?ans;
}
int?main()?{
????int?nums[]?=?{?0,?1,?0?};
????int?numsSize?=?sizeof(nums)?/?sizeof(nums[0]);
????int?k?=?1;
????int?result?=?minKBitFlips(nums,?numsSize,?k);
????printf("Result:?%d\n",?result);
????return?0;
}
