LeetCode 898. Bitwise ORs of Subarrays 子数组按位或操作_importsys的博客-程序员宅基地

技术标签： Set 子数组按位或操作 Bitwise ORs of Subarrays leetcode LeetCode 898.

LeetCode 898. Bitwise ORs of Subarrays 子数组按位或操作

- 898. Bitwise ORs of Subarrays
- - 题目描述
  - 示例:
  - 解答
  - 代码

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.)

Note:

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

示例:

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.

解答

从前向后扫描一边数组，每遇到一个新的值，把这个值和之前所有可能的结果bitwise or一遍。

然后bitwise or的结果插入到res数组中。

最后返回res数组的长度。

代码


class Solution {
    
public:
    int subarrayBitwiseORs(vector<int>& A) {
    
        unordered_set<int> res;
        unordered_set<int> prev;
        for (auto &a : A) {
    
            unordered_set<int> curr;
            curr =  {
    a};
            for (auto &p : prev) {
    
                curr.insert(p | a);
            }
            prev = curr;
            res.insert(prev.begin(), prev.end());
        }
        return res.size();
    }
};

本文链接：https://blog.csdn.net/qq_31027515/article/details/94966792

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

查看mac的串口_mac 查看串口_阿锤是个靓仔的博客-程序员宅基地

在终端中输入：cd /dev/ls -al tty 就可以找到了。如果在程序中使用，在port处填/dev/这里填串口

html 瀑布流_weixin_33895016的博客-程序员宅基地

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"><html lang="en"><head><meta http-equiv="Content-Type" content="text/html;ch...

springboot+thymeleaf+ajax局部刷新_CGSX的博客-程序员宅基地

springboot+thymeleaf+ajax局部刷新

RedHat Linux Perl的安装_redhat安装perl_zhangqifeng92的博客-程序员宅基地

重新安装了新版本的 Perl，过程记录如下： 1、在官方网站下载新版本的源码包：http://www.perl.org/get.html，版本自己选择，我下载的是perl-5.12.2.tar.gz2、解压/usr/local/src下的perl-5.12.2.tar.gz # tar zxvf perl-5.12.2.tar.gz3、建立文件目录，以供安装时使用

arcgis地理配准_花舞月咏潭的博客-程序员宅基地

1打开地理文档，加载地理配准工具条2点击内容列表缩放到图层，在点击地理配准适应显示范围3.点击地理配准----变换--一次多项式（仿射）4.更新地理配准5点击地理配准纠正----纠正另存为...

关于AsyncHttpClient的cz.msebera.android.httpclient.Header_cz.msebera.android:httpclient_Sammy爱学习的博客-程序员宅基地

android-async-http-1.4.9使用时cz.msebera.android.httpclient.Header会出现Header[] headers找不到的错误网上查询到解决方法是：dependencies {compile 'cz.msebera.android:httpclient:4.3.6'}