898. Bitwise ORs of Subarrays

LeetCode medium оригинал: C# #array #bit-manipulation #csharp #hash-table #leetcode #medium

LeetCode Static

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

Пример:

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++ решение

auto-draft, проверить перед отправкой

#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

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

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

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

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

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.