アルゴリズムとデータ構造の基礎-ハッシュテーブル(Hash Table)
7527 ワード
Hash Table基礎
ハッシュ・テーブル(Hash Table)は、一般的なデータ構造であり、ハッシュ関数を用いてマッピングを実現し、内部はオープン・アドレス・ファスナー法などを用いてハッシュ・衝突を解決し、読み書き時間の複雑さが平均的にO(1)となるようにする.
HashMap(std:unordeded mumap)とHashSet(std:unordedededed duet)の原理はHash Tableと同じで、用途が広く、使い方も柔軟で、次にそれらの応用を紹介することに重点を置いています.
関連するLeetCodeの問題:
706. Design HashMap 問題を解く
705. Design HashSet 問題を解く
集合する
要素があるセットに存在するかどうかを判断するだけであれば、構造HashSet(std:unordededededgeust)を使用することができます.例えば、LeetCodeのテーマ 349. Intersection of Two Arays:
関連するLeetCodeの問題:
349. Intersection of Two Arays 問題を解く
771. Jewers and Stors 問題を解く
202. Happy Number 問題を解く
166. Fraction to Recurring Decimal 問題を解く
720. Longest Word in Dictionary 問題を解く
970. パワフルIntegers 問題を解く
204. Count Primes 問題を解く
36. Valid Sudoku 問題を解く
数をかぞえる
要素を計数する必要があるなら、構造HashMap(std:unordedededumap)を使用してもいいです.元素は取得範囲が固定されているなら、Aray(std:vector)を使ってもいいです.例えば、LeetCodeのテーマです. 217. Contins Duplicate:
関連するLeetCodeの問題:
217. Contins Duplicate 問題を解く
811. Subdomain Visit Count 問題を解く
1002. Find Common Chracters 問題を解く
266. Palindrome Permutation 問題を解く
242. Valid Anagram 問題を解く
748. Shotest Copleting Word 問題を解く
1072. Flip Columns For Maximumber of Equal Rows 問題を解く
451. Sort Charcters By Frequency 問題を解く
347. Top K Frequent Elements 問題を解く
454. 4 Sum II 問題を解く
781. Rabbits in Forest 問題を解く
30. Substring with Concation of All Words 問題を解く
スライドウィンドウアルゴリズムでは、HashMapカウントがよく使われています.スライドウィンドウアルゴリズムについては、アルゴリズムとデータ構造ベースのスライドウィンドウ(Sliding Window)をご参照ください.
Key-Val
さらに、HashMapはKey−Val(またはID−属性)関係を表し、ここでValはカウント、アンダースコア(index)などとすることができる.
関連するLeetCodeの問題:
1. Two Sum 問題を解く
219. Contins Duplicate II 問題を解く
953. Verifying an Alien Dictionary 問題を解く
359. ロガーRate Limiter 問題を解く
1086. High Five 問題を解く
690. Employee Importance 問題を解く
981. Time Based Key-Value Store 問題を解く
325. Maximm Size Subarray Sum Equals k 問題を解く
244. Shotest Word Distance II 問題を解く
355. Design Twitter 問題を解く
336. Palindrome Pairs 問題を解く
マップ
より一般的には、HashMapは、O(1)時間の複雑さがA＞Bによるマッピングを完了することを意味するマッピング関係を表している.
関連するLeetCodeの問題:
246. Strobogrammatic Number 問題を解く
205. Isomorphic Strings 問題を解く
49. Group Anagrams 問題を解く
249. Group Shiftd Strings 問題を解く
290. Word Pattern 問題を解く
138. Copy List with Random Pointer 問題を解く
535. Encode and Decode Tiny URL 問題を解く
710. Random Pick with Blacklist 問題を解く
HashMapとPrefix sum
HashMapとPrefix sumを利用して、私達はO(n)時間の複雑さでサブシーケンスの求めと問題の種類を解くことができます.ここでHashMapは、例えばLeetCodeのテーマのようなカウントに用いられます. 560. Subarray Sum Equals K:
関連するLeetCodeの問題:
560. Subarray Sum Equals K 問題を解く
525. Contitous Aray 問題を解く
930. Binary Subarrays With Sum 問題を解く
325. Maximm Size Subarray Sum Equals k 問題を解く
554. Brick Wall 問題を解く
HashMapと図形の問題
HashMapは、二次元図形に適用されるいくつかの問題を解いて、Oul距離、傾き、x/y座標などをkeyとして、カウント、x/y座標をvalとします.図の問題の中でHashMapのマッピング関係はそんなに直観的ではなく、個々にkeyを計算し、マッピング関係を慎重に識別する必要があります.
関連するLeetCodeの問題:
447. Number of Boomerangs 問題を解く
939. Minimum Area Rectangle 問題を解く
149. Max Points on a Line 問題を解く
356. Line Reflection 問題を解く
HashMapとvector/list/stackが結合しています.
HashMapとvector、list、stackなどのデータ構造を結合して複合データ構造にすることができます.hashMap O(1)の利点を使うだけでなく、vectorで下付き操作をサポートし、list添削ノードが速く、stackが先進的に出てくる特徴もあります.例えば、LeetCodeのテーマ 380. Insert Delete Get Random O(1):
関連するLeetCodeの問題:
380. Insert Delete Get Random O(1) 問題を解く
381. Insert Delete GetRandom O(1)-Dupliccates allowed 問題を解く
895. Maximum Frequency Stock 問題を解く
146. LRU Cache 問題を解く
ハッシュ・テーブル(Hash Table)は、一般的なデータ構造であり、ハッシュ関数を用いてマッピングを実現し、内部はオープン・アドレス・ファスナー法などを用いてハッシュ・衝突を解決し、読み書き時間の複雑さが平均的にO(1)となるようにする.
HashMap(std:unordeded mumap)とHashSet(std:unordedededed duet)の原理はHash Tableと同じで、用途が広く、使い方も柔軟で、次にそれらの応用を紹介することに重点を置いています.
関連するLeetCodeの問題:
706. Design HashMap 問題を解く
705. Design HashSet 問題を解く
集合する
要素があるセットに存在するかどうかを判断するだけであれば、構造HashSet(std:unordededededgeust)を使用することができます.例えば、LeetCodeのテーマ 349. Intersection of Two Arays:
// 349. Intersection of Two Arrays
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> s1(nums1.begin(),nums1.end());
unordered_set<int> s2(nums2.begin(),nums2.end());
vector<int> res;
for(auto& a:s1)
if(s2.count(a)) res.push_back(a);
return res;
}関連するLeetCodeの問題:
349. Intersection of Two Arays 問題を解く
771. Jewers and Stors 問題を解く
202. Happy Number 問題を解く
166. Fraction to Recurring Decimal 問題を解く
720. Longest Word in Dictionary 問題を解く
970. パワフルIntegers 問題を解く
204. Count Primes 問題を解く
36. Valid Sudoku 問題を解く
数をかぞえる
要素を計数する必要があるなら、構造HashMap(std:unordedededumap)を使用してもいいです.元素は取得範囲が固定されているなら、Aray(std:vector)を使ってもいいです.例えば、LeetCodeのテーマです. 217. Contins Duplicate:
// 217. Contains Duplicate
bool containsDuplicate(vector<int>& nums) {
unordered_map<int,int> m;
for(int x:nums) if(m[x]++==1) return true;
return false;
}関連するLeetCodeの問題:
217. Contins Duplicate 問題を解く
811. Subdomain Visit Count 問題を解く
1002. Find Common Chracters 問題を解く
266. Palindrome Permutation 問題を解く
242. Valid Anagram 問題を解く
748. Shotest Copleting Word 問題を解く
1072. Flip Columns For Maximumber of Equal Rows 問題を解く
451. Sort Charcters By Frequency 問題を解く
347. Top K Frequent Elements 問題を解く
454. 4 Sum II 問題を解く
781. Rabbits in Forest 問題を解く
30. Substring with Concation of All Words 問題を解く
スライドウィンドウアルゴリズムでは、HashMapカウントがよく使われています.スライドウィンドウアルゴリズムについては、アルゴリズムとデータ構造ベースのスライドウィンドウ(Sliding Window)をご参照ください.
Key-Val
さらに、HashMapはKey−Val(またはID−属性)関係を表し、ここでValはカウント、アンダースコア(index)などとすることができる.
関連するLeetCodeの問題:
1. Two Sum 問題を解く
219. Contins Duplicate II 問題を解く
953. Verifying an Alien Dictionary 問題を解く
359. ロガーRate Limiter 問題を解く
1086. High Five 問題を解く
690. Employee Importance 問題を解く
981. Time Based Key-Value Store 問題を解く
325. Maximm Size Subarray Sum Equals k 問題を解く
244. Shotest Word Distance II 問題を解く
355. Design Twitter 問題を解く
336. Palindrome Pairs 問題を解く
マップ
より一般的には、HashMapは、O(1)時間の複雑さがA＞Bによるマッピングを完了することを意味するマッピング関係を表している.
関連するLeetCodeの問題:
246. Strobogrammatic Number 問題を解く
205. Isomorphic Strings 問題を解く
49. Group Anagrams 問題を解く
249. Group Shiftd Strings 問題を解く
290. Word Pattern 問題を解く
138. Copy List with Random Pointer 問題を解く
535. Encode and Decode Tiny URL 問題を解く
710. Random Pick with Blacklist 問題を解く
HashMapとPrefix sum
HashMapとPrefix sumを利用して、私達はO(n)時間の複雑さでサブシーケンスの求めと問題の種類を解くことができます.ここでHashMapは、例えばLeetCodeのテーマのようなカウントに用いられます. 560. Subarray Sum Equals K:
// 560. Subarray Sum Equals K
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> m;
m[0]=1;
int sum=0,res=0;
for(auto& a:nums){
sum+=a;
res+=m[sum-k];
m[sum]++;
}
return res;
}関連するLeetCodeの問題:
560. Subarray Sum Equals K 問題を解く
525. Contitous Aray 問題を解く
930. Binary Subarrays With Sum 問題を解く
325. Maximm Size Subarray Sum Equals k 問題を解く
554. Brick Wall 問題を解く
HashMapと図形の問題
HashMapは、二次元図形に適用されるいくつかの問題を解いて、Oul距離、傾き、x/y座標などをkeyとして、カウント、x/y座標をvalとします.図の問題の中でHashMapのマッピング関係はそんなに直観的ではなく、個々にkeyを計算し、マッピング関係を慎重に識別する必要があります.
関連するLeetCodeの問題:
447. Number of Boomerangs 問題を解く
939. Minimum Area Rectangle 問題を解く
149. Max Points on a Line 問題を解く
356. Line Reflection 問題を解く
HashMapとvector/list/stackが結合しています.
HashMapとvector、list、stackなどのデータ構造を結合して複合データ構造にすることができます.hashMap O(1)の利点を使うだけでなく、vectorで下付き操作をサポートし、list添削ノードが速く、stackが先進的に出てくる特徴もあります.例えば、LeetCodeのテーマ 380. Insert Delete Get Random O(1):
// 380. Insert Delete GetRandom O(1)
vector<int> v;
unordered_map<int,int> m;関連するLeetCodeの問題:
380. Insert Delete Get Random O(1) 問題を解く
381. Insert Delete GetRandom O(1)-Dupliccates allowed 問題を解く
895. Maximum Frequency Stock 問題を解く
146. LRU Cache 問題を解く