Bitmask sebagai Set Kecil
Merepresentasikan subset sebagai bilangan bulat
Bitmask sebagai Set Kecil adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Bilangan Bulat sebagai Himpunan
Satu bilangan bulat dapat mewakili seluruh himpunan: bit i yang bernilai 1 berarti elemen i ada di dalamnya. Dengan cara ini, subhimpunan dapat dikemas menjadi satu nilai kecil yang cepat. 🎒
Himpunan Kosong dan Penuh
Bilangan 0 adalah himpunan kosong, sedangkan nilai dengan n bit paling rendah semuanya aktif berarti setiap elemen ada di dalamnya.
empty = 0
full = (1 << 4) - 1 # 0b1111, four elementsMenambahkan Elemen
Untuk menambahkan elemen i ke dalam himpunan, aktifkan bitnya dengan OR. Ini persis seperti operasi mengaktifkan bit, tetapi sekarang dipahami sebagai gabungan dengan satu elemen.
s = 0
s |= (1 << 2) # add element 2Menghapus Elemen
Untuk menghapus elemen i, lakukan AND dengan bit yang dibalik. Elemen tersebut keluar dari himpunan, sementara elemen lainnya tetap. Ini adalah selisih himpunan dengan satu elemen.
s &= ~(1 << 2) # remove element 2Menguji Keanggotaan
Periksa apakah elemen i termasuk di dalamnya dengan melakukan AND pada bitnya. Hasil bukan nol berarti elemen tersebut adalah anggota himpunan.
if s & (1 << 2):
print('2 is in the set')Gabungan dan Irisan
Lakukan OR pada dua masker untuk mendapatkan gabungan; lakukan AND untuk mendapatkan irisannya. Operasi pada seluruh himpunan menjadi satu instruksi mesin masing-masing.
union = a | b
inter = a & bUkuran Himpunan adalah Jumlah Bit 1
Jumlah elemen dalam masker bit hanyalah jumlah bit 1 yang aktif. Gunakan bit_count untuk mendapatkan ukurannya seketika.
size = mask.bit_count()Melakukan Perulangan pada Semua Subhimpunan
Untuk n elemen, bilangan bulat dari 0 hingga 2^n - 1 mencantumkan setiap subhimpunan. Satu perulangan rentang sederhana dapat mencakup semuanya.
for mask in range(1 << n):
pass # mask is one subsetMelakukan Iterasi pada Masker Bagian dengan Cepat
Untuk mengunjungi hanya subhimpunan dari masker tertentu, gunakan perulangan klasik masker bagian. Perulangan ini melewati setiap subhimpunan dalam urutan menurun.
sub = mask
while sub:
sub = (sub - 1) & maskDP Masker Bit Digunakan di Sini
Masker bit menjadi keadaan untuk banyak soal DP, seperti masalah pedagang keliling, ketika masker melacak simpul yang sudah Anda kunjungi.
Pertahankan n Tetap Kecil
Karena ada 2^n subhimpunan, trik ini hanya praktis untuk n yang kecil, biasanya hingga sekitar 20. Setelah itu, jumlahnya meningkat drastis. ⚠️
Pemeriksaan Singkat
Satu pertanyaan terakhir tentang himpunan sebagai masker.
Ringkasan: Himpunan Masker Bit
Anda dapat menyimpan sebuah himpunan dalam satu bilangan bulat, menambah dan menghapus elemen dengan masker, serta melakukan perulangan pada setiap subhimpunan. Ini membuka penggunaan DP masker bit yang cepat. 🎉
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Bitmask sebagai Set Kecil” gratis?
Ya — teks lengkap “Bitmask sebagai Set Kecil” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Bitmask sebagai Set Kecil”?
Merepresentasikan subset sebagai bilangan bulat Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Bitmask sebagai Set Kecil” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- AND, OR, XOR & Pergeseran
- Mengatur, Menghapus & Membalik Bit
- Menghitung Bit dan Bit Set Terendah
- Bitmask sebagai Set Kecil