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 * 104 将对 inc、dec、getMaxKey 和 getMinKey 进行调用。
解决方案：
我们需要实现一个数据结构，允许在恒定时间 (O(1)) 内递增、递减和检索具有最小和最大计数的键。
主要见解：
哈希表（用于字符串计数）:
我们需要一个哈希表（计数）将每个字符串（键）映射到其计数。这允许在递增或递减计数时进行 O(1) 访问。
双向链表（用于计数）:
为了跟踪最小和最大计数，我们可以使用双向链表，其中每个节点代表一个唯一的计数。该节点会将具有该计数的所有字符串存储在一个集合中。链表将有助于通过跟踪头（最小）和尾（最大）节点来在恒定时间内检索最小和最大计数。
-
两个哈希映射:
- 哈希映射（key_to_node）会将每个字符串（key）映射到双向链表中存储其计数的节点。这允许我们在递增或递减计数时，在 O(1) 时间内将键从一个计数节点移动到另一个计数节点。
- 另一个哈希映射（计数）会将每个计数映射到双向链表中对应的节点，确保我们可以在 O(1) 时间内找到任意计数的节点。
计划：
让我们用 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"
?>
登录后复制
解释：
-
数据结构:
-
key_to_node：将每个键映射到双向链表中对应的节点。
-
counts：将每个计数映射到双向链表中对应的节点。
-
head 和 tail：虚拟头节点和尾节点，以便更轻松地操作双向链表。
-
方法：
-
inc($key)：如果该键存在，则会增加其计数并将其移动到列表中适当的节点。如果没有，则插入计数为 1 的值。
-
dec($key)：减少键的计数并将其删除或移动到适当的节点。
-
getMaxKey()：从双向链表尾部节点返回键（最大计数）。
-
getMinKey()：返回双向链表头部节点的键（最小计数）。
复杂：
- 所有操作均设计为以 O(1) 平均时间复杂度运行。
如果您需要进一步说明，请告诉我！
联系链接
如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！
如果您想要更多类似的有用内容，请随时关注我：
以上是。所有 O`one 数据结构的详细内容。更多信息请关注PHP中文网其他相关文章！
