Dwutygodniowy konkurs Leetcode 98 trudny problem
Przyjrzyjmy się trzeciemu problemowi z konkursu dwutygodnika Leetcode 98 . Rozwiązania różnych problemów z innych konkursów można znaleźć tutaj .
Problem Minimum Niemożliwe LUB
Otrzymujesz tablicę liczb całkowitych z indeksem 0nums .
Mówimy, że liczba całkowita x jest wyrażalna , jeśli numsistnieją liczby całkowite, 0 <= index1 < index2 < ... < indexk < nums.lengthdla których nums[index1] | nums[index2] | ... | nums[indexk] = x. Innymi słowy, liczba całkowita jest wyrażalna, jeśli można ją zapisać jako bitowe LUB jakiegoś podsekwencji nums.
Zwróć minimalną dodatnią liczbę całkowitą różną od zera , której nie da się wyrazić znums .
Rozwiązanie
Aby zrozumieć rozwiązanie tego problemu, rozważmy liczby od 0 do 8 oraz sposób, w jaki można je przedstawić w formacie binarnym i utworzyć za pomocą operacji OR.
Czy możemy utworzyć 1 ? Nie. Nie możemy zmienić 1 w określonym indeksie na 0 za pomocą operacji OR. Nie ma liczby większej niż 1, która ma wszystkie zera oprócz pierwszego we wszystkich bitach oprócz pierwszego. Czy możemy utworzyć 2 ? Nie. Tak samo jak dla 1, ale ta sama logika jest stosowana do drugiego bitu. Czy możemy utworzyć 3? Tak. 3 można utworzyć jako 1 LUB 2. Czy możemy utworzyć 4 ? Nie. Tak samo jak dla 1, ale logika jest stosowana do trzeciego bitu. Czy możemy utworzyć 5 ? Tak. 5 można utworzyć jako 4 LUB 1. 6 to 4 LUB 2. 7 to 4 LUB 2 LUB 1. 8 nie może zostać utworzone. Tak samo jak dla 1, ale logika jest stosowana do czwartego bitu. Jeśli uogólnimy znaleziony podciąg:
- Nie możemy utworzyć potęgi 2 z żadnych innych liczb za pomocą operacji LUB.
- Jeśli mamy potęgi od 2 do N, możemy utworzyć wszystkie inne liczby do 2^N-1
Zbliżać się
Przenosimy wszystkie liczby z początkowej tablicy do HashSet. Będziemy generować potęgi 2, dopóki pierwszy nie zostanie przedstawiony w tablicy.
Oto rozwiązanie JavaScript:
var minImpossibleOR = function(nums) {
let set = new Set(nums);
for (let i = 0; i <= 32; i++){
let num = Math.pow(2, i)
if(!set.has(num)){
return num
}
}
return -1;
};
impl Solution {
pub fn min_impossible_or(nums: Vec<i32>) -> i32 {
let mut set = std::collections::HashSet::new();
for num in nums.iter() {
set.insert(num);
}
for n in 0..=32 {
let num:i32 = 2i32.pow(n);
if(!set.contains(&num)){
return num;
}
}
return -1;
}
}
Złożoność czasowa: O(N)
Złożoność przestrzeni: O(N)
PS
Oto moje rozwiązanie na Leetcode .

![Czym w ogóle jest lista połączona? [Część 1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)



































