LeetCode如何解决重塑矩阵问题

发布时间:2021-12-15 10:53:54 作者:小新
来源:亿速云 阅读:158

这篇文章给大家分享的是有关LeetCode如何解决重塑矩阵问题的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。

题目描述:

在仅包含 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.

上面方法超时的主要原因是我们真实地进行了翻转。根据结论二,位置 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如何解决翻转图像问题
  2. leetcode如何实现转置矩阵

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

leetcode

上一篇:SparkStreaming与Kafka的整合是怎么样的

下一篇:LeetCode如何实现最大正方形

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》