Rumah >pembangunan bahagian belakang >tutorial php >. Semua Struktur Data O`one
432. Semua Struktur Data O`one
Kesukaran: Sukar
Topik: Jadual Hash, Senarai Terpaut, Reka Bentuk, Senarai Berganda Berkaitan
Reka bentuk struktur data untuk menyimpan kiraan rentetan dengan keupayaan untuk mengembalikan rentetan dengan kiraan minimum dan maksimum.
Melaksanakan kelas AllOne:
Perhatikan bahawa setiap fungsi mesti dijalankan dalam O(1) purata kerumitan masa.
Contoh 1:
Kekangan:
Penyelesaian:
Kami perlu melaksanakan struktur data yang membenarkan penambahan, pengurangan dan pengambilan kunci dengan kiraan minimum dan maksimum dalam masa tetap (O(1)).
Jadual Hash (untuk Kiraan Rentetan):
Kami memerlukan jadual cincang (kiraan) yang memetakan setiap rentetan (kunci) kepada kiraannya. Ini membenarkan akses O(1) apabila menambah atau mengurangkan kiraan.
Senarai Berganda Berpaut (untuk Kiraan):
Untuk menjejaki kiraan minimum dan maksimum, kita boleh menggunakan senarai terpaut dua kali di mana setiap nod mewakili kiraan unik. Nod akan menyimpan semua rentetan dengan kiraan itu dalam satu set. Senarai terpaut akan membantu dalam mendapatkan kiraan min dan maks dalam masa yang tetap dengan menjejaki nod kepala (min) dan ekor (maks).
Dua Peta Hash:
inc(kunci):
dec(kunci):
getMaxKey() dan getMinKey():
Mari laksanakan penyelesaian ini dalam PHP: 432. Semua Struktur Data O`one
inc($key); * $obj->dec($key); * $ret_3 = $obj->getMaxKey(); * $ret_4 = $obj->getMinKey(); */ // Example usage $allOne = new AllOne(); $allOne->inc("hello"); $allOne->inc("hello"); echo $allOne->getMaxKey(); // returns "hello" echo $allOne->getMinKey(); // returns "hello" $allOne->inc("leet"); echo $allOne->getMaxKey(); // returns "hello" echo $allOne->getMinKey(); // returns "leet" ?>Penjelasan:
Struktur Data:
- key_to_node: Petakan setiap kunci ke nod yang sepadan dalam senarai terpaut dua kali.
- kiraan: Peta setiap mengira ke nod yang sepadan dalam senarai terpaut dua kali.
- kepala dan ekor: Nod kepala dan ekor tiruan untuk manipulasi senarai berganda yang lebih mudah.
Kaedah:
- inc($key): Jika kunci wujud, ia menambah kiraannya dan mengalihkannya ke nod yang sesuai dalam senarai. Jika tidak, ia memasukkannya dengan kiraan 1.
- dec($key): Mengurangkan kiraan kunci dan sama ada mengeluarkannya atau mengalihkannya ke nod yang sesuai.
- getMaxKey(): Mengembalikan kunci daripada nod di bahagian ekor senarai berganda (kiraan maks).
- getMinKey(): Mengembalikan kunci daripada nod di kepala senarai berganda (kiraan min).
Kerumitan:
Beri tahu saya jika anda memerlukan penjelasan lanjut!
Pautan Kenalan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!
Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:
Atas ialah kandungan terperinci . Semua Struktur Data O`one. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!