資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中 K 個連續位元翻轉的最小次數
假設我們有一個數組 A。它只包含 0 和 1，這裡 K 位翻轉包括選擇一個長度為 K 的（連續）子陣列，並同時反轉子陣列中的位。我們必須找到所需的最小 K 位翻轉次數，以便陣列中沒有 0。如果沒有這樣的可能性，則返回 -1。
因此，如果輸入類似於 [0,0,0,1,0,1,1,0] 且 K = 3，則輸出將為 3，因為我們需要執行三次操作，在第一次嘗試中翻轉 A[0] 到 A[3]，陣列將為 [1,1,1,1,0,1,1,0]，在第二次執行中翻轉 A[4] 到 A[6]，陣列將為 [1,1,1,1,1,0,0,0]，在第 3 次移動中更改 A[5] 到 A[7]，陣列將為 [1,1,1,1,1,1,1,1]。
為了解決這個問題，我們將遵循以下步驟：
n := A 的大小
定義一個大小為 n 的陣列 moves
counter := 0
for 初始化 i := 0，當 i + K <= n 時，更新（i 增加 1），執行：
如果 i > 0，則：
moves[i] := moves[i] + moves[i - 1]
如果 (moves[i] mod 2) + A[i] 的模 2 不為零，則：
moves[i] := moves[i] + 1
如果 i + K < n，則：
moves[i + K] - = 1
（counter 增加 1）
for i < n，更新（i 增加 1），執行：
如果 i > 0，則：
moves[i] := moves[i] + moves[i - 1]
如果 (moves[i] mod 2) + A[i] 的模 2 不為零，則：
返回 -1
返回 counter
讓我們看看下面的實現以獲得更好的理解：
輸出
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minKBitFlips(vector<int>& A, int K){
int n = A.size();
vector<int> moves(n);
int i;
int counter = 0;
for (i = 0; i + K <= n; i++) {
if (i > 0)
moves[i] += moves[i - 1];
if (!(((moves[i] % 2) + A[i]) % 2)) {
moves[i] += 1;
if (i + K < n)
moves[i + K] -= 1;
counter++;
}
}
for (; i < n; i++) {
if (i > 0)
moves[i] += moves[i - 1];
if (!(((moves[i] % 2) + A[i]) % 2))
return -1;
}
return counter;
}
};
main(){
Solution ob;
vector<int> v = {0,0,0,1,0,1,1,0};
cout << (ob.minKBitFlips(v, 3));
}輸入
{0,0,0,1,0,1,1,0}, 3輸出
3
更新於： 2020年6月4日
190 次瀏覽
廣告