Leetcode 898. Bitwise ORs of Subarrays

文章作者：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)

Reference

1. https://leetcode.com/problems/bitwise-ors-of-subarrays/