济宁住房和城乡建设厅网站,靖州建设局网站,微网站移交,网络推广竞价外包题目链接 Leetcode.995 K 连续位的最小翻转次数 rating : 1835 题目描述
给定一个二进制数组 n u m s nums nums 和一个整数 k k k 。 k k k位翻转 就是从 n u m s nums nums 中选择一个长度为 k k k 的 子数组 #xff0c;同时把子数组中的每一个 0 0 0 都改成 1 1 1 …题目链接 Leetcode.995 K 连续位的最小翻转次数 rating : 1835 题目描述
给定一个二进制数组 n u m s nums nums 和一个整数 k k k 。 k k k位翻转 就是从 n u m s nums nums 中选择一个长度为 k k k 的 子数组 同时把子数组中的每一个 0 0 0 都改成 1 1 1 把子数组中的每一个 1 1 1 都改成 0 0 0 。
返回数组中不存在 0 0 0 所需的最小 k k k位翻转 次数。如果不可能则返回 − 1 -1 −1 。
子数组 是数组的 连续 部分。
示例 1 输入nums [0,1,0], K 1 输出2 解释先翻转 A[0]然后翻转 A[2]。 示例 2 输入nums [1,1,0], K 2 输出-1 解释无论我们怎样翻转大小为 2 的子数组我们都不能使数组变为 [1,1,1]。 示例 3 输入nums [0,0,0,1,0,1,1,0], K 3 输出3 解释 翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0] 翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0] 翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1] 提示 1 ≤ n u m s . l e n g t h ≤ 1 0 5 1 \leq nums.length \leq 10^5 1≤nums.length≤105 1 ≤ k ≤ n u m s . l e n g t h 1 \leq k \leq nums.length 1≤k≤nums.length
解法贪心 差分
假设前 i − 1 i - 1 i−1 个元素已经是全为 1 1 1 了第 i i i 个元素是 0 0 0。我们要想翻转这个元素就要翻转 [ i , i k − 1 ] [i,i k - 1] [i,ik−1] 整个区间的元素。并且这也是翻转第 i i i 位元素最少的操作次数对于每一个元素都是如此。
需要注意的是对于一个需要翻转的元素它的反转次数必须是奇数如果是偶数的话就相当于没有翻转。
我们可以使用差分数组来优化翻转的过程比如要翻转区间 [ i , i k − 1 ] [i , i k - 1] [i,ik−1]我们只需要让 [ i , i k − 1 ] [i , i k - 1] [i,ik−1] 中每一个元素的翻转次数 1 1 1即 d i f f [ i ] , d i f f [ i k ] − − diff[i] , diff[i k]-- diff[i],diff[ik]−− d i f f diff diff 就是差分数组。
时间复杂度 O ( n ) O(n) O(n)
C代码
class Solution {
public:int minKBitFlips(vectorint nums, int k) {int n nums.size();vectorint diff(n 1);int cnt 0 , ans 0;for(int i 0;i n;i){cnt diff[i];//默认初始每一个元素都是 0//nums[i] cnt 即元素 nums[i] 的翻转次数//如果翻转次数为偶数 说明当前元素还是0需要翻转if((nums[i] cnt) % 2 0){diff[i 1];//此时 i k n 说明无法翻转了直接返回 -1if(i k n) return -1;diff[i k]--;ans;}}return ans;}
};
