. 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:

• AllOne() Memulakan objek struktur data.
• inc(Kunci rentetan) Menambah kiraan kunci rentetan sebanyak 1. Jika kunci tidak wujud dalam struktur data, masukkannya dengan kiraan 1.
• dec(Kunci rentetan) Mengurangkan kiraan kunci rentetan sebanyak 1. Jika kiraan kunci ialah 0 selepas pengurangan, keluarkannya daripada struktur data. Ia dijamin bahawa kunci wujud dalam struktur data sebelum penyusutan.
• getMaxKey() Mengembalikan salah satu kunci dengan kiraan maksimum. Jika tiada unsur wujud, kembalikan rentetan kosong "".
• getMinKey() Mengembalikan salah satu kunci dengan kiraan minimum. Jika tiada unsur wujud, kembalikan rentetan kosong "".

Perhatikan bahawa setiap fungsi mesti dijalankan dalam O(1) purata kerumitan masa.

Contoh 1:

• Input: ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []]
• Output: [null, null, null, "hello", "hello", null, "hello", "leet"]
• Penjelasan: AllOne allOne = AllOne baru(); allOne.inc("hello"); allOne.inc("hello"); allOne.getMaxKey(); // kembalikan "hello" allOne.getMinKey(); // kembalikan "hello" allOne.inc("leet"); allOne.getMaxKey(); // kembalikan "hello" allOne.getMinKey(); // kembalikan "leet"

Kekangan:

• 1
• kunci terdiri daripada huruf kecil Inggeris.
• Adalah dijamin bahawa untuk setiap panggilan ke Disember, kunci wujud dalam struktur data.
• Maksimum 5 * 10⁴ panggilan akan dibuat kepada inc, dec, getMaxKey dan getMinKey.

Penyelesaian:

Kami perlu melaksanakan struktur data yang membenarkan penambahan, pengurangan dan pengambilan kunci dengan kiraan minimum dan maksimum dalam masa tetap (O(1)).

Wawasan Utama:

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.

2. 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).

3. Dua Peta Hash:

   • Peta cincang (key_to_node) akan memetakan setiap rentetan (kunci) ke nod dalam senarai terpaut dua kali yang menyimpan kiraannya. Ini membolehkan kami mengalihkan kunci dari satu nod kiraan ke nod kiraan yang lain dalam masa O(1) apabila kami menambah atau mengurangkan kiraan.
   • Peta cincang (kiraan) lain akan memetakan setiap kiraan kepada nod yang sepadan dalam senarai berganda, memastikan kami dapat mengesan nod untuk sebarang kiraan dalam masa O(1).

Pelan:

• inc(kunci):

  • Jika kunci wujud, tambahkan kiraannya sebanyak 1 dan alihkannya ke nod seterusnya (buat nod baharu jika perlu).
  • Jika kunci tidak wujud, buat nod baharu dengan kiraan 1 dan masukkannya.

• dec(kunci):

  • Kurangkan kiraan kunci sebanyak 1.
  • Jika kiraan menjadi sifar, keluarkan kunci daripada struktur data.

• getMaxKey() dan getMinKey():

  • Kembalikan kunci pertama daripada nod ekor (kiraan maks) atau nod kepala (kiraan min) dalam masa tetap.

Mari laksanakan penyelesaian ini dalam PHP: 432. Semua Struktur Data O`one

<?php class Node {
    /**
     * @var
     */
    public $count;
    /**
     * @var array
     */
    public $keys;
    /**
     * @var null
     */
    public $prev;
    /**
     * @var null
     */
    public $next;

    /**
     * @param $count
     */
    public function __construct($count) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

class AllOne {
    /**
     * @var array
     */
    private $key_to_node;
    /**
     * @var array
     */
    private $counts;
    /**
     * @var Node
     */
    private $head;
    /**
     * @var Node
     */
    private $tail;

    /**
     */
    function __construct() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Insert a new node after a given node
     *
     * @param $newNode
     * @param $prevNode
     * @return void
     */
    private function insertAfter($newNode, $prevNode) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Remove a node from the linked list
     *
     * @param $node
     * @return void
     */
    private function removeNode($node) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Increments the count of a key
     *
     * @param String $key
     * @return NULL
     */
    function inc($key) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Decrements the count of a key
     *
     * @param String $key
     * @return NULL
     */
    function dec($key) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Returns one of the keys with the maximum count
     *
     * @return String
     */
    function getMaxKey() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Returns one of the keys with the minimum count
     *
     * @return String
     */
    function getMinKey() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

/**
 * Your AllOne object will be instantiated and called as such:
 * $obj = AllOne();
 * $obj->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:

1. 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.

2. 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:

• Semua operasi direka bentuk untuk dijalankan dalam O(1) purata kerumitan masa.

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:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci . Semua Struktur Data O`one. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!