. 올오원 데이터 구조

432. 올오원 데이터 구조

난이도:어려움

주제: 해시 테이블, 연결 목록, 디자인, 이중 연결 목록

최소 및 최대 개수로 문자열을 반환하는 기능을 사용하여 문자열 개수를 저장하는 데이터 구조를 설계합니다.

AllOne 클래스 구현:

• AllOne() 데이터 구조의 객체를 초기화합니다.
• inc(String key) 문자열 key의 개수를 1씩 증가시킵니다. 데이터 구조에 key가 없으면 개수를 1로 삽입합니다.
• dec(String key) 문자열 키의 개수를 1만큼 감소시킵니다. 감소 후 키의 개수가 0이면 데이터 구조에서 이를 제거합니다. 감소하기 전에 데이터 구조에 키가 존재하는 것이 보장됩니다.
• getMaxKey() 최대 개수를 가진 키 중 하나를 반환합니다. 요소가 없으면 빈 문자열 ""을 반환합니다.
• getMinKey() 최소 개수를 가진 키 중 하나를 반환합니다. 요소가 없으면 빈 문자열 ""을 반환합니다.

참고 각 함수는 O(1) 평균 시간 복잡도에서 실행되어야 합니다.

예 1:

• 입력: ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["안녕하세요"], ["안녕하세요"], [], [], ["leet"], [], []]
• 출력: [null, null, null, "안녕하세요", "안녕하세요", null, "안녕하세요", "leet"]
• 설명: AllOne allOne = new AllOne(); allOne.inc("안녕하세요"); allOne.inc("안녕하세요"); allOne.getMaxKey(); // "안녕하세요"를 반환합니다. allOne.getMinKey(); // "안녕하세요"를 반환합니다. allOne.inc("leet"); allOne.getMaxKey(); // "안녕하세요"를 반환합니다. allOne.getMinKey(); // "leet"를 반환합니다.

제약조건:

• 1
• 키는 영문소문자로 구성됩니다.
• dec를 호출할 때마다 키가 데이터 구조에 존재하는 것이 보장됩니다.
• inc, dec, getMaxKey 및 getMinKey에 대해 최대 5 * 10⁴ 호출이 이루어집니다.

해결책:

상수 시간(O(1))에서 최소 및 최대 개수로 키를 증가, 감소 및 검색할 수 있는 데이터 구조를 구현해야 합니다.

주요 통찰력:

1. 해시 테이블(문자열 개수용):
   각 문자열(키)을 해당 개수에 매핑하는 해시 테이블(개수)이 필요합니다. 이를 통해 개수를 늘리거나 줄일 때 O(1) 액세스가 가능합니다.

2. 이중 연결 목록(개수용):
   최소 및 최대 개수를 추적하기 위해 각 노드가 고유한 개수를 나타내는 이중 연결 목록을 사용할 수 있습니다. 노드는 해당 개수의 모든 문자열을 세트에 저장합니다. 연결된 목록은 헤드(최소) 및 테일(최대) 노드를 추적하여 일정한 시간에 최소 및 최대 개수를 검색하는 데 도움이 됩니다.

3. 두 개의 해시 맵:

   • 해시 맵(key_to_node)은 각 문자열(키)을 개수를 저장하는 이중 연결 목록의 노드에 매핑합니다. 이를 통해 카운트를 늘리거나 줄일 때 O(1) 시간 내에 한 카운트 노드에서 다른 카운트 노드로 키를 이동할 수 있습니다.
   • 또 다른 해시 맵(개수)은 각 개수를 이중 연결 목록의 해당 노드에 매핑하여 O(1) 시간 내에 모든 개수에 대한 노드를 찾을 수 있도록 합니다.

계획:

• inc(키):

  • 키가 존재하는 경우 개수를 1 증가시키고 다음 노드로 이동합니다(필요한 경우 새 노드 생성).
  • 키가 존재하지 않으면 개수가 1인 새 노드를 생성하여 삽입하세요.

• dec(키):

  • 키 개수를 1씩 줄입니다.
  • 개수가 0이 되면 데이터 구조에서 키를 제거하세요.

• getMaxKey() 및 getMinKey():

  • 테일 노드(최대 개수) 또는 헤드 노드(최소 개수)에서 첫 번째 키를 상수 시간에 반환합니다.

이 솔루션을 PHP로 구현해 보겠습니다. 432. 올오원 데이터 구조

<?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: 각 개수를 이중 연결 목록의 해당 노드에 매핑합니다.
   • 머리와 꼬리: 이중 연결 목록을 더 쉽게 조작하기 위한 더미 머리와 꼬리 노드.

2. 방법:

   • inc($key): 키가 존재하면 개수를 증가시키고 목록의 적절한 노드로 이동합니다. 그렇지 않은 경우 1번째로 삽입합니다.
   • dec($key): 키 개수를 줄이고 키를 제거하거나 적절한 노드로 이동합니다.
   • getMaxKey(): 이중 연결 목록(최대 개수)의 끝 부분에 있는 노드에서 키를 반환합니다.
   • getMinKey(): 이중 연결 리스트(최소 개수)의 선두에 있는 노드에서 키를 반환합니다.

복잡성:

• 모든 작업은 O(1) 평균 시간 복잡도에서 실행되도록 설계되었습니다.

추가 설명이 필요하면 알려주세요!

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 . 올오원 데이터 구조의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!