首页 > 编程知识 正文

与的符号表达式,常用符号怎么旋转

时间:2023-05-03 13:19:10 阅读:264615 作者:27

K 连续位的最小翻转次数

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

解题思路

题中用到了子数组,所以使用滑动窗口(双指针):left 指针和 right 指针来解决该问题。
滑动窗口的大小 = K(长度为K的连续子数组) = right - left + 1

(1) 若滑动窗口的开头是 1,则一定不能翻转(若翻转,则开头的 1 变为 0,无论后面怎么变都变不回来了)。

此时,应该使 left 指针右移一位,并判断当前 left 指针指向的元素的值是否为 0。right 指针同样也向右移动一位即可(要保证窗口的大小始终为 K)。若 right 指针移动完后超出了数组范围,则直接到第 3 步进行最后的判断。

(2) 若滑动窗口的开头是 0,则可以进行翻转,并且count 值加 1(count 用来记录翻转的次数)。

此时,将窗口中的 0 改为 1,1 改为 0(用 A[i] ^= 1,这样修改不会超时。若先判断再赋值修改则会超时),修改完后要在保证窗口大小不变的情况下将窗口整体右移一个单位,继续判断当前窗口的开头是否是 1,以及 right 指针是否超出了数组的范围(超出了,则直接到第三步进行最后的判断)。

(3) 全部翻转完了,检查翻转后的数组中的元素是否全为 1,若是返回 count,否则返回 -1。

提示:其中的 A[i] ^= 1 中的符号 ^ 为异或运算符,异或是一个数学运算符,它应用于逻辑运算。
其运算法则为:a⊕b = (¬a ∧ b) ∨ (a ∧¬b)。如果 a、b 两个值不相同,则异或结果为 1,如果 a、b 两个值相同,异或结果为 0。

A[i] ^= 1窗口中的当前元素值与 1 相比,若 A[i] == 0 则与 1 的值不相同,异或结果为 1(相当于是将 0 翻转成了 1)。

代码 class Solution { public int minKBitFlips(int[] A, int K) { int n = A.length; int left = 0, right = K - 1; int count = 0; for (right=K-1;right<n;right++) { if (right - left + 1 == K) { if (A[left] == 1) { left++; } else { if (left == right) { A[left] = 1; } else { for (int i=left;i<=right;i++) { A[i] ^= 1;//异或运算符 } } count++; left++; } } } for (int i=0;i<n;i++) { if (A[i] == 0) { return -1; } } return count; }}

时间复杂度:有 for 循环的嵌套,所以复杂度为O(n²)
空间复杂度:因为没有开辟新的空间,所以复杂度为O(1)

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。