。所有 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中文网其他相关文章！