오늘 우리는 3월 수업이 끝난 도전의 일곱 번째 문제를 해결할 것이다.

문제 진술

내장된 해시 라이브러리를 사용하지 않고 해시도를 설계합니다.
구체적으로 다음과 같은 기능이 설계에 포함되어야 합니다.

put(key,value):HashMap에 (key,value) 쌍을 삽입합니다.HashMap에 이 값이 이미 있는 경우 해당 값을 업데이트합니다.

get(key): 지정한 키가 비치는 값을 되돌려줍니다. 이 비치는 키가 포함되지 않으면 -1을 되돌려줍니다.

제거(키): 이 맵에 키의 맵이 포함되어 있으면 값 키의 맵을 제거합니다.

예:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);          // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found)

참고:

모든 키와 값은 [01000000] 범위에 있습니다.

작업의 수량은 [11000]의 범위 내에 있을 것이다.

내장형 HashMap 라이브러리는 사용하지 마십시오.

솔루션

그래서 이 문제에서 우리는 라이브러리 함수를 사용하지 않고HashMap을 설계해야 한다는 요구를 받았다.여기서 우리는 이 문제를 해결하는 두 가지 방법을 토론할 것이다.
방법1-수조: 이런 방법을 사용하면 우리는 -1로 특정 크기의 수조를 초기화할 것이다.우리는 주어진 키를 수조의 인덱스로 사용하고, 주어진 값을 이 인덱스를 가진 수조에 저장할 것이다.우리는 키가 항상 바르기 때문에 이런 방법을 사용할 수 있다.이것은 매우 직접적인 코드다.

시간 복잡도: O(1), get,put,remove 방법

공간 복잡도: O(1), 수조는 1000001개의 공간을 차지합니다

** 방법 2 -LinkedList:* 키 값이 마이너스가 아니기 때문에 이전의 해결 방안을 받아들인다.그러나 전반적으로 상황은 그렇지 않다.따라서, 우리는 해결 방안을 개선하여, 산열 인덱스 값을 찾아, 그것을 수조에 저장할 것이다.HashMap 배후의 핵심 개념과 그 내부 실현을 이해하려면 이 놀라운 유튜브 재생 목록을 보십시오.( ).

따라서 영상을 보면 서로 다른 키에 대해 우리는 같은 해시 인덱스(충돌이라고 부른다)를 얻을 수 있다는 것을 이해할 수 있다.이 문제를 해결하기 위해LinkedList를 사용합니다

전체 알고리즘을 한 번 검사합시다

1. ListNode 클래스를 만듭니다.LinkedList의 노드입니다.키 및 값 쌍을 저장합니다

2. ListNode 유형의 명명 노드 배열을 만듭니다.기본적으로 HashMap처럼 작동합니다

3. 구조 함수에서 수조 초기화

4. put 방법: 우선 주어진 키의 산열 값을 찾습니다.이 위치에 다른 값이 저장되어 있는지 확인하십시오.없으면 키 값 쌍이 있는 ListNode를 만들고 nodes 배열에 저장합니다.존재하면 노드에 대한 인용 (prev) 을 가져옵니다.저번에next는null이고 키 값을 사용하여 새로운ListNode를 만듭니다.그렇지 않으면 이전 값을 바꿉니다.다음 노드

5. get 방법: 산열 값을 반복해서 찾고ListNode(prev)에 대한 인용을 가져오는 과정입니다.저번에next는null이고 -1을 되돌려줍니다. 그렇지 않으면prev를 되돌려줍니다.다음.가치관

6. remove 방법: 산열 값을 반복해서 찾고ListNode(prev)에 대한 인용을 가져오는 과정입니다.그룹에서 이 키 값 쌍을 삭제하려면prev를 실행하십시오.다음다음.다음.(LinkedList에서 노드 삭제)

아래에 상세한 코드와 주석이 있습니다

시간 복잡성: 평균 O(1), 최악의 경우 O(n)

공간 복잡도: O(1), 항목 수는 고정

코드는 여기서 찾을 수 있습니다

2021년 3월 LeetCoding 챌린지 전 질문 보기

1. March LeetCoding Challenge — Day 1 — Distribute Candies

2. March LeetCoding Challenge — Day 2 — Set Mismatch

3. March LeetCoding Challenge — Day 3 — Missing Number

4. March LeetCoding Challenge — Day 4 — Intersection of Two Linked Lists

5. March LeetCoding Challenge — Day 5 — Average of Levels in Binary Tree

6. March LeetCoding Challenge — Day 6— Short Encoding of Words