Mari kita lihat masalah ketiga dari kontes dua mingguan Leetcode 98 . Anda dapat menemukan solusi dari masalah yang berbeda dari kontes lain di sini .

Masalah Minimal Tidak Mungkin ATAU

Anda diberi array integer 0-diindeksnums .

Kami mengatakan bahwa bilangan bulat x dapat diekspresikan dari numsjika ada beberapa bilangan bulat 0 <= index1 < index2 < ... < indexk < nums.lengthyang nums[index1] | nums[index2] | ... | nums[indexk] = x. Dengan kata lain, sebuah integer dapat diekspresikan jika dapat ditulis sebagai bitwise OR dari beberapa subsequence dari nums.

Mengembalikan bilangan bulat bukan nol positif minimum yang tidak dapat diungkapkan dari .nums

Larutan

Untuk memahami solusi dari masalah ini, mari pertimbangkan angka dari 0 hingga 8, dan bagaimana angka tersebut dapat direpresentasikan dalam format biner dan dibentuk menggunakan operasi OR.

Bisakah kita membentuk 1 ? Tidak. Kami tidak dapat mengubah 1 dalam indeks tertentu menjadi 0 menggunakan operasi ATAU. Tidak ada angka yang lebih besar dari 1 yang semuanya nol kecuali yang pertama di semua bit kecuali yang pertama. Bisakah kita membentuk 2 ? Tidak. Sama seperti untuk 1 tetapi logika yang sama diterapkan pada bit kedua. Bisakah kita membentuk 3? Ya. 3 dapat dibentuk menjadi 1 ATAU 2. Bisakah kita membentuk 4 ? Tidak. Sama seperti untuk 1 tetapi logika diterapkan pada bit ketiga. Bisakah kita membentuk 5 ? Ya. 5 dapat dibentuk sebagai 4 ATAU 1. 6 adalah 4 ATAU 2. 7 adalah 4 ATAU 2 ATAU 1. 8 tidak dapat dibentuk. Sama seperti untuk 1 tetapi logika diterapkan pada bit keempat. Jika kita menggeneralisasi menemukan subsequence:

• Kami tidak dapat membentuk kekuatan 2 dari angka lain dengan operasi ATAU.
• Jika kita memiliki pangkat 2 hingga N, kita dapat membentuk semua bilangan lainnya hingga 2^N-1

Mendekati

Kami memindahkan semua angka dari array awal ke HashSet. Kami akan menghasilkan kekuatan 2 sampai pertama tidak disajikan ke dalam array.

Inilah solusi 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;
    }
}

Kompleksitas waktu: O(N)

Kompleksitas ruang: O(N)

PS

Inilah solusi saya di Leetcode .