898. Bitwise ORs of Subarrays

LeetCode medium original: C# #array #bit-manipulation #csharp #hash-table #leetcode #medium

题目文本会按所选界面语言从俄语翻译；代码保持不变。

LeetCode Static

Если задан 整数数组 arr, return количество различных побитовых ИЛИ всех непустых под数组ов arr. Побитовое ИЛИ под数组а - это побитовое ИЛИ каждого целого числа в под数组е. Побитовым ИЛИ под数组а одного целого числа является это 整数. Под数组 - это непрерывная непустая последовательность elementов в 数组е.

示例:

Input: arr = [0]

Output: 1

C# 解法

匹配/原始

using System;
using System.Collections.Generic;
public class Solution {
    public int SubarrayBitwiseORs(int[] arr) {
        HashSet<int> result = new HashSet<int>();
        HashSet<int> current = new HashSet<int>();
        foreach (int num in arr) {
            HashSet<int> next = new HashSet<int> { num };
            foreach (int x in current) {
                next.Add(x | num);
            }
            current = next;
            result.UnionWith(current);
        }
        return result.Count;
    }
}

C++ 解法

自动草稿，提交前请检查

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SubarrayBitwiseORs(vector<int>& arr) {
        HashSet<int> result = new HashSet<int>();
        HashSet<int> current = new HashSet<int>();
        foreach (int num in arr) {
            HashSet<int> next = new HashSet<int> { num };
            foreach (int x in current) {
                next.push_back(x | num);
            }
            current = next;
            result.UnionWith(current);
        }
        return result.size();
    }
}

Java 解法

匹配/原始

import java.util.*;

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> result = new HashSet<>();
        Set<Integer> current = new HashSet<>();
        for (int num : arr) {
            Set<Integer> next = new HashSet<>();
            for (int x : current) {
                next.add(x | num);
            }
            next.add(num);
            current = next;
            result.addAll(current);
        }
        return result.size();
    }
}

JavaScript 解法

匹配/原始

var subarrayBitwiseORs = function(arr) {
    let result = new Set();
    let current = new Set();
    for (let num of arr) {
        let next = new Set();
        for (let x of current) {
            next.add(x | num);
        }
        next.add(num);
        current = next;
        for (let x of current) {
            result.add(x);
        }
    }
    return result.size;
};

Python 解法

匹配/原始

def subarrayBitwiseORs(arr):
    result = set()
    current = set()
    for num in arr:
        current = {num | x for x in current} | {num}
        result.update(current)
    return len(result)

Go 解法

匹配/原始

package main

func subarrayBitwiseORs(arr []int) int {
    result := make(map[int]struct{})
    current := make(map[int]struct{})
    for _, num := range arr {
        next := make(map[int]struct{})
        next[num] = struct{}{}
        for x := range current {
            next[x|num] = struct{}{}
        }
        current = next
        for x := range current {
            result[x] = struct{}{}
        }
    }
    return len(result)
}

Algorithm

Создать множество для хранения уникальных результатов побитового ИЛИ.

Для каждого elementа 数组а, вычислить побитовое ИЛИ всех под数组ов, начинающихся с этого elementа.

Добавить результат каждого вычисления в множество.

Вернуть размер множества.

😎

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。