算法基础算法

滑动窗口 | 按位单独处理 | 字符计数

字数统计: 989字   |   阅读时长: 4分
, , , ,

摘要:

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，今天我们来看一个综合题，在滑动窗口中维护各个二进制位对应的计数，这种计数有点像字符串上滑动窗口时的字符计数，也有点像是按位单独处理的技巧，可以理解为将两种思想结合了一下。

按位单独处理，以及在滑动窗口内维护字符计数这两种思想上周都有文章解决过各自的问题，可以参考：

题目

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空子数组的长度，如果特别子数组不存在，那么返回 -1 。

示例 1：
输入：nums = [1,2,3], k = 2
输出：1
解释：
子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。

示例 2：
输入：nums = [2,1,8], k = 10
输出：3
解释：
子数组 [2,1,8] 的按位 OR 值为 11 ，所以我们返回 3 。

示例 3：
输入：nums = [1,2], k = 0
输出：1
解释：
子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。

提示：

1
2
3
1 <= nums.length <= 2e5
0 <= nums[i] <= 1e9
0 <= k <= 1e9

题解

算法: 滑动窗口

由按位或的性质，x | y >= x，因此当固定子数组左端点 l 时，随着右端点 r 推进，按位或的结果是单调递增的。因此当 r 推进到某个位置，按位或的结果首次不小于 k，此时的窗口长度 r - l + 1 就对应了左端点为 l 时的最短的满足条件的窗口。由此我们可以设计以滑动窗口为基础的算法。

在推进滑动窗口时，始终维护一个类似于字符计数的信息 cnt[i] 表示第 i 位为 1 的个数，对于给定的数据范围，有 0 <= i < 32。在判定窗口合法性时，把 cnt[i] 中计数大于 0 的位都置 1，即可得到窗口的按位或的结果，大致的代码如下：

1
2
3
4
5
6
7
8
s = 0
b = 1
for i in range(32):
    if cnt[i] > 0:
        s += b
    b *= 2
if s >= k:
    # 窗口合法

至此我们可以给出最终算法：

1
2
3
4
5
6
7
8
l = 0, r = -1
一个单位一个单位地推进 l：
    若窗口内按位或的结果 s < k，就推进 r:
        r += 1
        若 r < n 则更新字符计数 cnt，否则 break
    若 r < n，则以 r - l + 1 更新答案
    l += 1
    更新字符计数 cnt

l 和 r 都只向右推进一轮，每推进一步需要遍历一次字符计数，因此总时间复杂度为 $O(nU)$，$U$ 为元素的二进制位数。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def check(cnt, k):
    s = 0
    b = 1
    for i in range(len(cnt)):
        if cnt[i] > 0:
            s += b
        b *= 2
    return s >= k

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        INF = int(1e9)
        n = len(nums)
        cnt = [0] * 32
        l = 0
        r = -1
        ans = INF
        while l < n and r < n:
            while r < l or not check(cnt, k):
                r += 1
                if r == n:
                    break
                # 推进 r 后更新字符计数
                x = nums[r]
                i = 0
                while x > 0:
                    if x & 1 == 1:
                        cnt[i] += 1
                    x >>= 1
                    i += 1
            if r < n:
                ans = min(ans, r - l + 1)
            # 更新字符计数后推进 l
            y = nums[l]
            j = 0
            while y > 0:
                if y & 1 == 1:
                    cnt[j] -= 1
                y >>= 1
                j += 1
            l += 1
        return ans if ans <= n else -1
Share