Leetcode 898. Bitwise ORs of Subarrays

Tyan

发布于 2021-07-08 15:53:17

3100

发布于 2021-07-08 15:53:17

文章被收录于专栏：SnailTyan

文章作者：Tyan 博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

**解析：**Version 1、Version 2都超时，Version 3、Version 4可以通过，Version 4效率高于Version 3。

Version 1

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        result = set()
        n = len(arr)
        for i in range(n):
            for j in range(i, n):
                temp = 0
                for k in range(i, j + 1):
                    temp = temp | arr[k]
                result.add(temp)
        return len(result)

Version 2

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        result = set()
        n = len(arr)
        sub = []
        for i in range(n):
            pre = arr[i]
            result.add(pre)
            for j in range(i + 1, n):
                temp = pre | arr[j]
                pre = temp
                result.add(pre)
        return len(result)

Version 3

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        result = set(arr)
        pre = set()
        for num in arr:
            current = set()
            current.add(num)
            for val in pre:
                temp = val | num
                current.add(temp)
                result.add(temp)
            pre = current
        return len(result)

Version 4

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        result = set(arr)
        pre = set()
        for num in arr:
            current = {num | val for val in pre}
            current.add(num)
            result |= current
            pre = current
        return len(result)