• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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. 1 <= A.length <= 50000
  2. 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. 1 <= A.length <= 50000
  2. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift添加webview发布时间:2022-07-13
下一篇:
[Swift开发]使用闭包传值(typealias)发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap