LeetCode每日一题-8:重塑矩阵
题目描述:
在仅包含 0 和 1 的数组 A 中,一次 K 位翻转包括选择一个长度为 K 的(连续)子数组,同时将子数组中的每个 0 更改为 1,而每个 1 更改为 0。
返回所需的 K 位翻转的最小次数,以便数组没有值为 0 的元素。如果不可能,返回 -1。
示例 1:
输入:A = [0,1,0], K = 1 输出:2 解释:先翻转 A[0],然后翻转 A[2]。
示例 2:
输入:A = [1,1,0], K = 2 输出:-1 解释:无论我们怎样翻转大小为 2 的子数组,我们都不能使数组变为 [1,1,1]。
示例 3:
输入:A = [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]
思路分析:
题目大意:每次翻转长度为 K 的子数组,求最少的翻转次数使数组中所有的 0 都更改为 1。如果不能实现,则返回 -1.
- 结论 1:后面区间的翻转,不会影响前面的元素。因此可以使用贪心策略,从左到右遍历,遇到每个 0 都把它和后面的 K 个数进行翻转。
- 结论 2:A[i] 翻转偶数次的结果是 A[i];翻转奇数次的结果是 A[i] ^ 1。
上面方法超时的主要原因是我们真实地进行了翻转。根据结论二,位置 i 现在的状态,和它被前面 K - 1个元素翻转的次数(奇偶性)有关。
我们使用队列模拟滑动窗口,该滑动窗口的含义是前面 K - 1个元素中,以哪些位置起始的 子区间进行了翻转。该滑动窗口从左向右滑动,如果当前位置 i 需要翻转,则把该位置存储到队列中。遍历到新位置 j (j < i + K)时,队列中元素的个数代表了 i被前面 K - 1个元素翻转的次数。
当 i 位置被翻转了偶数次,如果 A[i]为 0,那么翻转后仍是 0,当前元素需要翻转; 当 i 位置被翻转了奇数次,如果 A[i]为 1,那么翻转后是 0,当前元素需要翻转。 综合上面两点,我们得到一个结论,如果 len(que) % 2 == A[i] 时,当前元素需要翻转。
当 i + K > N 时,说明需要翻转大小为 K 的子区间,但是后面剩余的元素不到 K 个了,所以返回 -1。
Python实现
class Solution(object):
def minKBitFlips(self, A, K):
"""
:type A: List[int]
:type K: int
:rtype: int
"""
N = len(A)
que = collections.deque()
res = 0
for i in range(N):
if que and i >= que[0] + K:
que.popleft()
if len(que) % 2 == A[i]:
if i + K > N: return -1
que.append(i)
res += 1
return res
作者:fuxuemingzhu
链接:https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/solution/hua-dong-chuang-kou-shi-ben-ti-zui-rong-z403l/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
java实现
class Solution {
public int minKBitFlips(int[] A, int K) {
int len=A.length;
int res=0;
Deque<Integer> deque=new LinkedList<>();
for(int i=0;i<len;i++){
if(deque.size()>0 && i>deque.peek()+K-1){
deque.removeFirst();
}
if(deque.size()%2==A[i]){
if(i+K>len){
return -1;
}
deque.add(i);
res=res+1;
}
}
return res;
}
}
相关文章
- LeetCode每日一题-1:反转链表
- LeetCode每日一题-3:回文链表
- ☆打卡算法☆LeetCode 206. 反转链表 算法解析
- 两数相加(leetcode 2)
- 老梁你居然说刷LeetCode Easy找不到工作,你一定没做过Java
- LeetCode周赛300,没能AK,刚拿到的勋章要没了……
- Leetcode题目037-解数独
- LeetCode(Weekly Contest 187)题解
- LeetCode笔记:Weekly Contest 314
- 【day08】LeetCode(力扣)每日一刷[409. 最长回文串 ][144. 二叉树的前序遍历][589. N 叉树的前序遍历 ]
- LeetCode周赛331,思维题训练场
- 19道leetcode二分查找算法
- 用javascript分类刷leetcode--双指针(图文视频讲解)
- 每日一道leetcode:1. 两数之和
- 【Leetcode-滑动窗口问题】
- 每日一道leetcode:8. 字符串转换整数 (atoi)
- 每日一道leetcode:6. N 字形变换
- LeetCode每日一题:合并两个有序数组
- leetcode每日一练:旋转数组
- leetcode每日一题:字符串中的第一个唯一字符
- leetcode每日一题:数组的相对排序
- leetcode每日一练:将句子排序
- leetcode: 二叉树的层序遍历
- LeetCode 知识点集成