您好,登录后才能下订单哦!
这篇文章给大家分享的是有关LeetCode如何解决重塑矩阵问题的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
在仅包含 0 和 1 的数组 A 中,一次 K 位翻转包括选择一个长度为 K 的(连续)子数组,同时将子数组中的每个 0 更改为 1,而每个 1 更改为 0。
返回所需的 K 位翻转的最小次数,以便数组没有值为 0 的元素。如果不可能,返回 -1。
输入:A = [0,1,0], K = 1
输出:2
解释:先翻转 A[0],然后翻转 A[2]。
输入:A = [1,1,0], K = 2
输出:-1
解释:无论我们怎样翻转大小为 2 的子数组,我们都不能使数组变为 [1,1,1]。
输入: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.
上面方法超时的主要原因是我们真实地进行了翻转。根据结论二,位置 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。
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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
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如何解决重塑矩阵问题”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。