在僅包含 0 和 1 的數組 A 中，一次 K 位翻轉包括選擇一個長度為 K 的（連續）子數組，同時將子數組中的每個 0 更改為 1，而每個 1 更改為 0。

返回所需的 K 位翻轉的最小次數，以便數組沒有值為 0 的元素。如果不可能，返回 -1。

示例 1：

輸入：A = [0,1,0], K = 1
輸出：2
解釋：先翻轉 A[0]，然后翻轉 A[2]。

解題思路

貪心思路：遍歷每個0元素，對其進行翻轉，使用隊列維護翻轉的子數組的首位下標

代碼

class Solution {public int minKBitFlips(int[] A, int K) {int res=0;LinkedList<Integer> queue=new LinkedList<>();for (int i = 0; i < A.length; i++) {if(!queue.isEmpty()&&i-K+1>queue.getFirst()) //當前位置不在隊頭翻轉的子數組范圍內，所以移除隊頭元素queue.removeFirst(); //剩余隊列中的元素個數，代表當前位置被多少個已經翻轉的子數組覆蓋，即當前位置的翻轉次數，偶數次翻轉是本身，奇數次翻轉是相反數，以此判定當前位置的元素是否為0if(queue.size()%2==A[i]){if(i+K>A.length) return -1;//不能恰好被k長度子數組覆蓋res++;queue.addLast(i);}}return res;} }

總結

以上是生活随笔為你收集整理的leetcode 995. K 连续位的最小翻转次数（贪心算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。