专栏首页Bingo的深度学习杂货店【DP】898. Bitwise ORs of Subarrays

【DP】898. Bitwise ORs of Subarrays

题目描述:

We have an array A of non-negative integers.

For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]] (with i <= j), we take the bitwise OR of all the elements in B, obtaining a result A[i] | A[i+1] | ... | A[j].

Return the number of possible results. (Results that occur more than once are only counted once in the final answer.)

Example 1:
Input: [0]
Output: 1
Explanation: 
There is only one possible result: 0.
Example 2:
Input: [1,1,2]
Output: 3
Explanation: 
The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.
Example 3:
Input: [1,2,4]
Output: 6
Explanation: 
The possible results are 1, 2, 3, 4, 6, and 7.

Note:

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

解题思路:

这道题很好理解,但是时间复杂度要求很高,就连普通DP都会超时,容我慢慢道来。

1、直接暴力(TLE):

  • 尝试所有可能的子数组 n^2;
  • 对每个子数组计算 Or 操作。

这样,时间复杂度 O(n^3),空间复杂度 O(1),肯定不行,想都不用想先pass。

2、普通DP(我使用的方法,但是很可惜还是 TLE 了):

  • 用 dp[i][j] 记录子串 i~j 之间的 Or 操作结果,即 dp[i][j] = A[i] | A[i+1] | ... | A[j],其中 i >= j;
  • 容易找到转移方程 dp[i][j] = dp[i][j-1] + A[j]
  • 结果为 ans = len(set(dp))

这样,时间复杂度 O(n^2),空间复杂度 O(n^2),还是超时了......

3、高级DP(AC):

  • dp[i] 表示以 A[i] 结尾的所有子数组的 Or 结果,其实是个 set。
  • 转移方程式:dp[i] = [(b | A[i]) for b in dp[i-1]] + A[i],即以 A[i] 结尾的所有子数组 Or 结果等于以 A[i-1] 结尾的所有子数组 Or 结果,和当前的 A[i] 进行 Or 操作,再加上 A[i] 这个结果。注意: len(dp) <= 32,后面会给出证明。
  • ans = len(set(dp))

这时,时间复杂度 O(32*n),空间复杂度 O(32*n),接受。

证明:为什么方法 3 中的 len(dp) <= 32 ? dp[i] = { A[i], A[i]|A[i-1], A[i]|A[i-1]|A[i-2], … , A[i]|A[i-1]|…|A[0] },这个序列单调递增,通过把 A[i] 中的 0 变成 1。A[i] 最多有 32 个 0,所以这个集合的大小 <= 32。 举例:最坏情况 A = [8, 4, 2, 1, 0],都是 2^k。 A[5] = 0,dp[5] = { 0, 0|1, 0|1|2, 0|1|2|4, 0|1|2|4| } = { 0, 1, 3, 7, 15 }.

Python3 实现:

方法2(TLE):
class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        lens = len(A)
        dp = [[0] * lens for _ in range(lens)]
        res = set()
        for i in range(lens):
            dp[i][i] = A[i]
            res.add(dp[i][i])
            for j in range(i+1, lens):
                dp[i][j] = dp[i][j-1] | A[j]
                res.add(dp[i][j])
        return len(res)
方法3(AC):
class Solution(object):
    def subarrayBitwiseORs(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        res = set()
        cur = set()  # 保存上一次的结果
        for a in A:
            cur = {n | a for n in cur} | {a} 
            res |= cur  # 更新结果
        return len(res)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode【712、746、877】

    读完题目后发现:把两个字符串中多余的字符删除后,最后留下的字符串是两个字符串的最长公共子序列。因此这道题可以像最长公共子序列一样,采用动态规划的思想解决:常考的...

    echobingo
  • 【DP】338. Counting Bits

    Given a non negative integer number num. For every numbers i in the range 0 ≤ i ...

    echobingo
  • 【DP】64. Minimum Path Sum

    Given a m x n grid filled with non-negative numbers, find a path from top left t...

    echobingo
  • LeetCode 123. 买卖股票的最佳时机 III(动态规划)

    Michael阿明
  • 漫画:BAT必考题目 (如何压缩状态完成不同路径题目)

    不同路径:一个机器人位于一个 m x n 网格的左上角,起始点在下图中标记为“Start”。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角,在下...

    程序员小浩
  • 最长公共子串

    动态规划是大厂的热门考点,其中最长公共子串与最长公共子序列这两道题出现得尤其频繁,这两道题其实有挺多变种,很适合考察侯选人对动态规划的掌握情况,今天我们就先来看...

    kunge
  • 动态规划此一篇就够了 万字总结

    动态规划,一直以来听着就是一种很高深莫测的算法思想。尤其是上学时候算法的第一堂课,老师巴拉巴拉列了一大堆的算法核心思想,贪心、回溯、动态规划... ...,开始...

    计算广告生态
  • 打卡群刷题总结0801——解码方法

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 巧解动态规划问题

    前言:最近在力扣刷题,但是之前从没有接触过算法题,有的看答案都看不懂,后来做的题做多了发现有好多类似的题目,所以我打算总结一下规律。

    wsuo
  • LeetCode 357. 计算各个位数不同的数字个数(DP)

    给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券