算法leetcode

【搜索难题】力扣898-子数组按位或操作

字数统计: 656字   |   阅读时长: 2分
, ,

摘要: 等效性剪枝

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

本文看一个搜索问题，涉及到了记忆化，以及等效性剪枝。

$1 题目

我们有一个非负整数数组 A。

对于每个（连续的）子数组 B = [A[i], A[i+1], …, A[j]] （ i <= j），我们对 B 中的每个元素进行按位或操作，获得结果 A[i] | A[i+1] | … | A[j]。

返回可能结果的数量。 （多次出现的结果在最终答案中仅计算一次。）

提示：

1
2
1 <= A.length <= 50000
0 <= A[i] <= 10^9

示例 1：

输入：[0]
输出：1
解释：
只有一个可能的结果 0 。
示例 2：

输入：[1,1,2]
输出：3
解释：
可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
产生的结果为 1，1，2，1，3，3 。
有三个唯一值，所以答案是 3 。
示例 3：

输入：[1,2,4]
输出：6
解释：
可能的结果是 1，2，3，4，6，以及 7 。

$2 题解

算法: 搜索

(1) 基础搜索

搜索所有子串：

先枚举终点 $j$，再枚举起点 $i$，求 [i,j] 范围的按位或，插入到哈希表(哈希表自带去重)。

(2) 记忆化

1
2
dp[i][j] := [i..j] 上的按位或结果
dp[i][j] = dp[i][j - 1] | A[j]

后期可以将 dp 的空间优化掉一维，然后直接在原数组 A 上做。

(3) 等效性剪枝

固定 j (此时 A[j] 可能会提供一些新的贡献)，向前推 i 的时候，某一时刻如果出现 (dp[i][j - 1] | A[j]) == dp[i][j - 1]

说明 A[j] 为 1 的位置，dp[i][j - 1] 已经为 1，i 可以不用往前推了。

因为当前的 dp[i][j - 1] 都把 A[j] 中的 1 都包含了，继续往前推 i ，dp[i - 1][j - 1] 更把 A[j] 中的 1 都包含了。

代码 (C++)

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
class Solution {
public:
    int subarrayBitwiseORs(vector<int>& A) {
        if(A.empty()) return 0;
        int n = A.size();
        if(n == 1) return 1;
        unordered_set<int> setting;
        for(int j = 0; j < n; ++j)
        {
            setting.insert(A[j]);
            for(int i = j - 1; i >= 0; --i)
            {
                // A[i..j] 以 j 结尾可以得到的结果
                if((A[j] | A[i]) == A[i])
                {
                    // A[j] 为 1 的位置，A[i] (即 dp[i][j-1]) 已经为 1
                    break;
                }
                // 更新 dp
                A[i] |= A[j];
                setting.insert(A[i]);
            }
        }
        return setting.size();
    }
};
Share