内容简介:In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.Return the minimum number of K-bit flips required so t
In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.
Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.
Example 1:
Input: A = [0,1,0], K = 1 Output: 2 Explanation: Flip A[0], then flip A[2].
Example 2:
Input: A = [1,1,0], K = 2 Output: -1 Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].
Example 3:
Input: A = [0,0,0,1,0,1,1,0], K = 3 Output: 3 Explanation: Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0] Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0] Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]
Note:
1 <= A.length <= 30000
1 <= K <= A.length
难度:Hard
题目:在一个只包含0和1的数组中,每次可以翻转K个元素,其中所有的0翻转成1,1翻转成0. 返回其最小的翻转次数。如果不存在则返回-1.
思路:贪心算法,每次找到第1个0后翻转从该元素开始的K个元素。
Runtime: 171 ms, faster than 57.70% of Java online submissions for Minimum Number of K Consecutive Bit Flips.
Memory Usage: 48.9 MB, less than 5.03% of Java online submissions for Minimum Number of K Consecutive Bit Flips.
class Solution { public int minKBitFlips(int[] A, int K) { int i = 0, count = 0; while (i <= A.length - 1) { if (1 == A[i]) { i++; continue; } if (i + K > A.length) { return -1; } count++; for (int t = i; t < i + K; t++) { A[t] = (A[t] + 1) & 1; } } return count; } }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Docker从入门到实战
黄靖钧 / 机械工业出版社 / 2017-6 / 69.00元
本书从Docker的相关概念与基础知识讲起,结合实际应用,通过不同开发环境的实战例子,详细介绍了Docker的基础知识与进阶实战的相关内容,以引领读者快速入门并提高。 本书共19章,分3篇。第1篇容器技术与Docker概念,涵盖的内容有容器技术、Docker简介、安装Docker等。第2篇Docker基础知识,涵盖的内容有Docker基础、Docker镜像、Dockerfile文件、Dock......一起来看看 《Docker从入门到实战》 这本书的介绍吧!