2023-09-30：用go語(yǔ)言，給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 。 nums 僅包含 0 和 1，
2023-09-30：用go語(yǔ)言，給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 。 nums 僅包含 0 和 1，
每一次移動(dòng)，你可以選擇 相鄰 兩個(gè)數(shù)字并將它們交換。
請(qǐng)你返回使 nums 中包含 k 個(gè) 連續(xù) 1 的 最少 交換次數(shù)。
輸入：nums = [1,0,0,1,0,1], k = 2。
輸出：1。
來(lái)自左程云。
答案2023-09-30：
步驟描述：
1.定義一個(gè)函數(shù) minMoves(nums []int, k int)，傳入一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k。
2.如果 k 等于 1，直接返回 0。
3.獲取數(shù)組 nums 的長(zhǎng)度 n。
4.計(jì)算目標(biāo)窗口中索引和的左半部分，即 (k - 1)/2 個(gè)索引的和，賦值給 leftAimIndiesSum。
5.計(jì)算目標(biāo)窗口中索引和的右半部分，即 (k-1)*k/2 - leftAimIndiesSum，賦值給 rightAimIndiesSum。
6.初始化一個(gè)變量 ans，并將其賦值為最大整數(shù)。
7.初始化左邊窗口的起始索引 l 為 0，中間位置索引 m 為 (k - 1)/2，右邊窗口的結(jié)束索引 r 為 k - 1。
8.計(jì)算左邊窗口需要的 1 的個(gè)數(shù) leftNeedOnes 為 (k - 1)/2 + 1。
9.初始化左邊窗口的起始索引 leftWindowL 為 0，左邊窗口的 1 的個(gè)數(shù) leftWindowOnes 為 0，左邊窗口中索引和的總和 leftWindowOnesIndiesSum 為 0。
10.遍歷數(shù)組 nums，i 從 0 到 m-1，進(jìn)行如下操作：
10.1.如果 nums[i] 等于 1，將 leftWindowOnes 加一，leftWindowOnesIndiesSum 加上 i。
11.計(jì)算右邊窗口需要的 1 的個(gè)數(shù) rightNeedOnes 為 k - leftNeedOnes。
12.初始化右邊窗口的結(jié)束索引 rightWindowR 為 m，右邊窗口的 1 的個(gè)數(shù) rightWindowOnes 為 nums[m]，右邊窗口中索引和的總和 rightWindowOnesIndiesSum 為 0。
13.如果 nums[m] 等于 1，將 rightWindowOnesIndiesSum 賦值為 m。
14.對(duì)于 l、m、r 從初始狀態(tài)開(kāi)始，進(jìn)行如下操作：
14.1.如果 nums[m] 等于 1，將 leftWindowOnes 加一，leftWindowOnesIndiesSum 加上 m，rightWindowOnes 減一，rightWindowOnesIndiesSum 減去 m。
14.2.當(dāng) leftWindowOnes 大于 leftNeedOnes 時(shí)，如果 nums[leftWindowL] 等于 1，則將 leftWindowOnes 減一，leftWindowOnesIndiesSum 減去 leftWindowL，左窗口的起始索引 leftWindowL 加一。
14.3.當(dāng) rightWindowOnes 小于 rightNeedOnes 且 rightWindowR+1 小于 n 時(shí)，如果 nums[rightWindowR+1] 等于 1，則將 rightWindowOnes 加一，rightWindowOnesIndiesSum 加上 rightWindowR+1，右窗口的結(jié)束索引 rightWindowR 加一。
14.4.如果左窗口的 1 的個(gè)數(shù)等于 leftNeedOnes，右窗口的 1 的個(gè)數(shù)等于 rightNeedOnes，說(shuō)明找到了滿足要求的窗口。將 ans 更新為 leftAimIndiesSum 減去 leftWindowOnesIndiesSum，再加上 rightWindowOnesIndiesSum 減去 rightAimIndiesSum 和 ans 中的較小值。
14.5.更新 leftAimIndiesSum 為 m+1-l，更新 rightAimIndiesSum 為 r-m。
14.6.將 l 加一，m 加一，r 加一。
15.返回 ans。
總的時(shí)間復(fù)雜度：根據(jù)代碼逐行分析，其中的遍歷是線性時(shí)間復(fù)雜度 O(n)，其余操作的時(shí)間復(fù)雜度均為常數(shù)時(shí)間復(fù)雜度。所以總的時(shí)間復(fù)雜度為 O(n)。
總的額外空間復(fù)雜度：除了函數(shù)調(diào)用棧外，代碼中沒(méi)有使用額外空間，所以額外空間復(fù)雜度為 O(1)。
go完整代碼如下：
package?main
import?(
????"fmt"
)
func?minMoves(nums?[]int,?k?int)?int?{
????if?k?==?1?{
????????return?0
????}
????n?:=?len(nums)
????x?:=?(k?-?1)?/?2
????leftAimIndiesSum?:=?x?*?(x?+?1)?/?2
????rightAimIndiesSum?:=?int((k-1)*k/2?-?leftAimIndiesSum)
????ans?:=?int(^uint(0)?>>?1)
????l?:=?0
????m?:=?(k?-?1)?/?2
????r?:=?k?-?1
????leftNeedOnes?:=?m?+?1
????leftWindowL?:=?0
????leftWindowOnes?:=?0
????leftWindowOnesIndiesSum?:=?0
????for?i?:=?0;?i?<?m;?i++?{
????????if?nums[i]?==?1?{
????????????leftWindowOnes++
????????????leftWindowOnesIndiesSum?+=?i
????????}
????}
????rightNeedOnes?:=?k?-?leftNeedOnes
????rightWindowR?:=?m
????rightWindowOnes?:=?nums[m]
????rightWindowOnesIndiesSum?:=?0
????if?nums[m]?==?1?{
????????rightWindowOnesIndiesSum?=?m
????}
????for?;?r?<?n;?l,?m,?r?=?l+1,?m+1,?r+1?{
????????if?nums[m]?==?1?{
????????????leftWindowOnes++
????????????leftWindowOnesIndiesSum?+=?m
????????????rightWindowOnes--
????????????rightWindowOnesIndiesSum?-=?m
????????}
????????for?leftWindowOnes?>?leftNeedOnes?{
????????????if?nums[leftWindowL]?==?1?{
????????????????leftWindowOnes--
????????????????leftWindowOnesIndiesSum?-=?leftWindowL
????????????}
????????????leftWindowL++
????????}
????????for?rightWindowOnes?<?rightNeedOnes?&&?rightWindowR+1?<?n?{
????????????if?nums[rightWindowR+1]?==?1?{
????????????????rightWindowOnes++
????????????????rightWindowOnesIndiesSum?+=?rightWindowR?+?1
????????????}
????????????rightWindowR++
????????}
????????if?leftWindowOnes?==?leftNeedOnes?&&?rightWindowOnes?==?rightNeedOnes?{
????????????ans?=?min(ans,?leftAimIndiesSum-leftWindowOnesIndiesSum+rightWindowOnesIndiesSum-rightAimIndiesSum)
????????}
????????leftAimIndiesSum?+=?m?+?1?-?l
????????rightAimIndiesSum?+=?r?-?m
????}
????return?ans
}
func?min(a,?b?int)?int?{
????if?a?<?b?{
????????return?a
????}
????return?b
}
func?main()?{
????nums?:=?[]int{1,?0,?0,?1,?0,?1}
????k?:=?2
????result?:=?minMoves(nums,?k)
????fmt.Println(result)
}
rust完整代碼如下：
fn?min_moves(nums:?Vec<i32>,?k:?i32)?->?i32?{
????if?k?==?1?{
????????return?0;
????}
????let?n?=?nums.len()?as?i32;
????let?x?=?(k?-?1)?/?2;
????let?mut?left_aim_indices_sum?=?x?*?(x?+?1)?/?2;
????let?mut?right_aim_indices_sum?=?(k?-?1)?*?k?/?2?-?left_aim_indices_sum;
????let?mut?ans?=?std::i32::MAX;
????let?(mut?l,?mut?m,?mut?r)?=?(0,?(k?-?1)?/?2,?k?-?1);
????let?left_need_ones?=?m?+?1;
????let?(mut?left_window_l,?mut?left_window_ones,?mut?left_window_ones_indices_sum)?=?(0,?0,?0);
????for?i?in?0..m?{
????????if?nums[i?as?usize]?==?1?{
????????????left_window_ones?+=?1;
????????????left_window_ones_indices_sum?+=?i?as?i32;
????????}
????}
????let?right_need_ones?=?k?-?left_need_ones;
????let?(mut?right_window_r,?mut?right_window_ones,?mut?right_window_ones_indices_sum)?=?(
????????m,
????????nums[m?as?usize],
????????if?nums[m?as?usize]?==?1?{?m?as?i32?}?else?{?0?},
????);
????while?r?<?n?{
????????if?nums[m?as?usize]?==?1?{
????????????left_window_ones?+=?1;
????????????left_window_ones_indices_sum?+=?m?as?i32;
????????????right_window_ones?-=?1;
????????????right_window_ones_indices_sum?-=?m?as?i32;
????????}
????????while?left_window_ones?>?left_need_ones?{
????????????if?nums[left_window_l]?==?1?{
????????????????left_window_ones?-=?1;
????????????????left_window_ones_indices_sum?-=?left_window_l?as?i32;
????????????}
????????????left_window_l?+=?1;
????????}
????????while?right_window_ones?<?right_need_ones?&&?right_window_r?+?1?<?n?{
????????????if?nums[(right_window_r?+?1)?as?usize]?==?1?{
????????????????right_window_ones?+=?1;
????????????????right_window_ones_indices_sum?+=?(right_window_r?+?1)?as?i32;
????????????}
????????????right_window_r?+=?1;
????????}
????????if?left_window_ones?==?left_need_ones?&&?right_window_ones?==?right_need_ones?{
????????????ans?=?ans.min(
????????????????left_aim_indices_sum?-?left_window_ones_indices_sum?+?right_window_ones_indices_sum
????????????????????-?right_aim_indices_sum,
????????????);
????????}
????????left_aim_indices_sum?+=?(m?+?1?-?l)?as?i32;
????????right_aim_indices_sum?+=?(r?-?m)?as?i32;
????????l?+=?1;
????????m?+=?1;
????????r?+=?1;
????}
????ans
}
fn?main()?{
????let?nums?=?vec![1,?0,?0,?1,?0,?1];
????let?k?=?2;
????let?result?=?min_moves(nums,?k);
????println!("{}",?result);
}
c++完整代碼如下：
using?namespace?std;
int?minMoves(vector<int>&?nums,?int?k)?{
????if?(k?==?1)?{
????????return?0;
????}
????int?n?=?nums.size();
????int?x?=?(k?-?1)?/?2;
????int?leftAimIndiesSum?=?x?*?(x?+?1)?/?2;
????int?rightAimIndiesSum?=?(k?-?1)?*?k?/?2?-?leftAimIndiesSum;
????int?ans?=?INT_MAX;
????int?l?=?0;
????int?m?=?(k?-?1)?/?2;
????int?r?=?k?-?1;
????int?leftNeedOnes?=?m?+?1;
????int?leftWindowL?=?0;
????int?leftWindowOnes?=?0;
????int?leftWindowOnesIndiesSum?=?0;
????for?(int?i?=?0;?i?<?m;?i++)?{
????????if?(nums[i]?==?1)?{
????????????leftWindowOnes++;
????????????leftWindowOnesIndiesSum?+=?i;
????????}
????}
????int?rightNeedOnes?=?k?-?leftNeedOnes;
????int?rightWindowR?=?m;
????int?rightWindowOnes?=?nums[m];
????int?rightWindowOnesIndiesSum?=?nums[m]?==?1???m?:?0;
????for?(;?r?<?n;?l++,?m++,?r++)?{
????????if?(nums[m]?==?1)?{
????????????leftWindowOnes++;
????????????leftWindowOnesIndiesSum?+=?m;
????????????rightWindowOnes--;
????????????rightWindowOnesIndiesSum?-=?m;
????????}
????????while?(leftWindowOnes?>?leftNeedOnes)?{
????????????if?(nums[leftWindowL]?==?1)?{
????????????????leftWindowOnes--;
????????????????leftWindowOnesIndiesSum?-=?leftWindowL;
????????????}
????????????leftWindowL++;
????????}
????????while?(rightWindowOnes?<?rightNeedOnes?&&?rightWindowR?+?1?<?n)?{
????????????if?(nums[rightWindowR?+?1]?==?1)?{
????????????????rightWindowOnes++;
????????????????rightWindowOnesIndiesSum?+=?rightWindowR?+?1;
????????????}
????????????rightWindowR++;
????????}
????????if?(leftWindowOnes?==?leftNeedOnes?&&?rightWindowOnes?==?rightNeedOnes)?{
????????????ans?=?min(ans,
????????????????leftAimIndiesSum?-?leftWindowOnesIndiesSum?+?rightWindowOnesIndiesSum?-?rightAimIndiesSum);
????????}
????????leftAimIndiesSum?+=?m?+?1?-?l;
????????rightAimIndiesSum?+=?r?-?m;
????}
????return?ans;
}
int?main()?{
????vector<int>?nums?=?{?1,?0,?0,?1,?0,?1?};
????int?k?=?2;
????int?result?=?minMoves(nums,?k);
????cout?<<?result?<<?endl;
????return?0;
}
c完整代碼如下：
int?minMoves(int*?nums,?int?numsSize,?int?k)?{
????if?(k?==?1)?{
????????return?0;
????}
????int?x?=?(k?-?1)?/?2;
????int?leftAimIndiesSum?=?x?*?(x?+?1)?/?2;
????int?rightAimIndiesSum?=?((k?-?1)?*?k?/?2?-?leftAimIndiesSum);
????int?ans?=?INT_MAX;
????int?l?=?0;
????int?m?=?(k?-?1)?/?2;
????int?r?=?k?-?1;
????int?leftNeedOnes?=?m?+?1;
????int?leftWindowL?=?0;
????int?leftWindowOnes?=?0;
????int?leftWindowOnesIndiesSum?=?0;
????for?(int?i?=?0;?i?<?m;?i++)?{
????????if?(nums[i]?==?1)?{
????????????leftWindowOnes++;
????????????leftWindowOnesIndiesSum?+=?i;
????????}
????}
????int?rightNeedOnes?=?k?-?leftNeedOnes;
????int?rightWindowR?=?m;
????int?rightWindowOnes?=?nums[m];
????int?rightWindowOnesIndiesSum?=?nums[m]?==?1???m?:?0;
????for?(;?r?<?numsSize;?l++,?m++,?r++)?{
????????if?(nums[m]?==?1)?{
????????????leftWindowOnes++;
????????????leftWindowOnesIndiesSum?+=?m;
????????????rightWindowOnes--;
????????????rightWindowOnesIndiesSum?-=?m;
????????}
????????while?(leftWindowOnes?>?leftNeedOnes)?{
????????????if?(nums[leftWindowL]?==?1)?{
????????????????leftWindowOnes--;
????????????????leftWindowOnesIndiesSum?-=?leftWindowL;
????????????}
????????????leftWindowL++;
????????}
????????while?(rightWindowOnes?<?rightNeedOnes?&&?rightWindowR?+?1?<?numsSize)?{
????????????if?(nums[rightWindowR?+?1]?==?1)?{
????????????????rightWindowOnes++;
????????????????rightWindowOnesIndiesSum?+=?rightWindowR?+?1;
????????????}
????????????rightWindowR++;
????????}
????????if?(leftWindowOnes?==?leftNeedOnes?&&?rightWindowOnes?==?rightNeedOnes)?{
????????????ans?=?min(ans,?leftAimIndiesSum?-?leftWindowOnesIndiesSum?+?rightWindowOnesIndiesSum?-?rightAimIndiesSum);
????????}
????????leftAimIndiesSum?+=?m?+?1?-?l;
????????rightAimIndiesSum?+=?r?-?m;
????}
????return?ans;
}
int?main()?{
????int?nums[]?=?{?1,?0,?0,?1,?0,?1?};
????int?k?=?2;
????int?numsSize?=?sizeof(nums)?/?sizeof(nums[0]);
????int?result?=?minMoves(nums,?numsSize,?k);
????printf("%d\n",?result);
????return?0;
}
