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中文網其他相關文章！
