898. Bitwise ORs of Subarrays

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

Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.

LeetCode Static

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

Esempio:

Input: arr = [0]

Output: 1

C# soluzione

abbinato/originale

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++ soluzione

bozza automatica, rivedere prima dell'invio

#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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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а arrayа, вычислить побитовое ИЛИ всех подarrayов, начинающихся с этого elementа.

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

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

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte

Non ci sono ancora offerte attive.