。所有 O`one 資料結構

432。所有 O`one 数据结构

难度：难

主题：哈希表、链表、设计、双向链表

设计一个数据结构来存储字符串的计数，并能够返回具有最小和最大计数的字符串。

实现 AllOne 类：

• AllOne() 初始化数据结构的对象。
• inc(String key) 将字符串 key 的计数加 1。如果数据结构中不存在 key，则将其插入，计数为 1。
• dec(String key) 将字符串 key 的计数减 1。如果递减后 key 的计数为 0，则将其从数据结构中删除。保证递减之前数据结构中存在 key。
• getMaxKey() 返回具有最大计数的键之一。如果不存在元素，则返回空字符串“”。
• getMinKey() 返回具有最小计数的键之一。如果不存在元素，则返回空字符串“”。

注意每个函数必须以 O(1) 平均时间复杂度运行。

示例1：

• 输入： [“AllOne”，“inc”，“inc”，“getMaxKey”，“getMinKey”，“inc”，“getMaxKey”，“getMinKey”] [[]、[“你好”]、[“你好”]、[]、[]、[“利特”]、[]、[]]
• 输出： [空，空，空，“你好”，“你好”，空，“你好”，“利特”]
• 说明： AllOne allOne = new AllOne(); allOne.inc(“你好”); allOne.inc(“你好”); allOne.getMaxKey(); // 返回“你好” allOne.getMinKey(); // 返回“你好” allOne.inc(“利特”); allOne.getMaxKey(); // 返回“你好” allOne.getMinKey(); // 返回“利特”

约束：

• 1
• key 由小写英文字母组成。
• 保证每次调用 dec 时，数据结构中都存在 key。
• 最多 5 * 10⁴ 将对 inc、dec、getMaxKey 和 getMinKey 进行调用。

解决方案：

我们需要实现一个数据结构，允许在恒定时间 (O(1)) 内递增、递减和检索具有最小和最大计数的键。

主要见解：

1. 哈希表（用于字符串计数）:
   我们需要一个哈希表（计数）将每个字符串（键）映射到其计数。这允许在递增或递减计数时进行 O(1) 访问。

2. 双向链表（用于计数）:
   为了跟踪最小和最大计数，我们可以使用双向链表，其中每个节点代表一个唯一的计数。该节点会将具有该计数的所有字符串存储在一个集合中。链表将有助于通过跟踪头（最小）和尾（最大）节点来在恒定时间内检索最小和最大计数。

3. 两个哈希映射:

   • 哈希映射（key_to_node）会将每个字符串（key）映射到双向链表中存储其计数的节点。这允许我们在递增或递减计数时，在 O(1) 时间内将键从一个计数节点移动到另一个计数节点。
   • 另一个哈希映射（计数）会将每个计数映射到双向链表中对应的节点，确保我们可以在 O(1) 时间内找到任意计数的节点。

计划：

• inc(key):

  • 如果该键存在，则将其计数增加 1 并将其移动到下一个节点（如果需要，创建一个新节点）。
  • 如果键不存在，则创建一个计数为1的新节点并将其插入。

• dec(key):

  • 将键的数量减 1。
  • 如果计数变为零，则从数据结构中删除该键。

• getMaxKey() 和 getMinKey():

  • 在常数时间内返回尾节点（最大计数）或头节点（最小计数）的第一个键。

让我们用 PHP 实现这个解决方案：432。所有 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"
?>

解释：

1. 数据结构:

   • key_to_node：将每个键映射到双向链表中对应的节点。
   • counts：将每个计数映射到双向链表中对应的节点。
   • head 和 tail：虚拟头节点和尾节点，以便更轻松地操作双向链表。

2. 方法：

   • inc($key)：如果該鍵存在，則會增加其計數並將其移至清單中適當的節點。如果沒有，則插入計數為 1 的值。
   • dec($key)：減少鍵的計數並將其刪除或移動到適當的節點。
   • getMaxKey()：從雙向鍊錶尾部節點返回鍵（最大計數）。
   • getMinKey()：傳回雙向鍊錶頭部節點的鍵（最小計數）。

複雜：

• 所有操作均設計為以 O(1) 平均時間複雜度運作。

如果您需要進一步說明，請告訴我！

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。所有 O`one 資料結構的詳細內容。更多資訊請關注PHP中文網其他相關文章！