[Swift]LeetCode898.子数组按位或操作|BitwiseORsofSubarrays

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10607099.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

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

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

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

示例 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 。

提示：

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

Runtime: 1244 ms

Memory Usage: 26.6 MB

 1 class Solution {
 2     func subarrayBitwiseORs(_ A: [Int]) -> Int {
 3         var res:Set<Int> = Set<Int>()
 4         var cur:Set<Int> = Set<Int>()        
 5         for i in A
 6         {
 7             var cur2:Set<Int> = Set<Int>()
 8             cur2.insert(i)
 9             res.insert(i)
10             for j in cur
11             {
12                 cur2.insert(i|j)
13                 res.insert(i|j)
14             }
15             cur = cur2
16         }
17         return res.count
18     }
19 }

1312ms

 1 class Solution {
 2     func subarrayBitwiseORs(_ A: [Int]) -> Int {
 3         if A.count == 0 {
 4             return 0
 5         }
 6         
 7         if A.count == 1 {
 8             return 1
 9         }
10         var total = Set<Int>()
11         var one: Set = [A[0]]
12         total.insert(A[0])
13         for i in 1..<A.count {
14             var next = Set<Int>()
15             one.insert(0)
16             for item in one {
17                 let t = item|A[i]
18                 next.insert(t)
19                 total.insert(t)
20             }
21             one = next
22         }
23         return total.count
24     }
25 }

1756ms

 1 class Solution {
 2     func subarrayBitwiseORs(_ A: [Int]) -> Int {
 3         var res = [Int]()
 4         var current = Set<Int>()
 5         var temp = Set<Int>()        
 6         for num in A {
 7             temp.removeAll()
 8             for x in current {
 9                 temp.insert(num | x)
10             }
11             temp.insert(num)
12             current = temp
13             res.append(contentsOf: current)
14         } 
15         return Set(res).count
16     }
17 }

1784ms

 1 class Solution {
 2     func subarrayBitwiseORs(_ A: [Int]) -> Int {
 3         var res = Set<Int>(), last = Set<Int>(), cur = Set<Int>()
 4         for i in A {
 5             cur = Set<Int>([i])
 6             for j in last {
 7                 cur.insert(i|j)
 8             }
 9             last = cur
10             res.formUnion(cur)
11         }
12         return res.count
13     }
14 }