哈希表基礎(chǔ)
一般哈希表都是用來快速判斷一個(gè)元素是否出現(xiàn)集合里。
當(dāng)我們想使用哈希法來解決問題的時(shí)候，我們一般會(huì)選擇如下三種數(shù)據(jù)結(jié)構(gòu)。
- 數(shù)組
- set (集合)
- map(映射)
242 有效的字母異位詞 Valid Anagram
要點(diǎn)
學(xué)習(xí)哈希表解題。哈希值比較小且范圍比較可控的時(shí)候，選擇使用數(shù)組解決。數(shù)值很大的時(shí)候，一般使用 set。k v 的時(shí)候使用 map。
此題中，字母均為小寫字母，總共 26 個(gè)，可以開辟一個(gè)長為 26 的數(shù)組。數(shù)組的每一個(gè)位置儲(chǔ)存對(duì)應(yīng)字母在字符串中出現(xiàn)的個(gè)數(shù)。遍歷第一個(gè)字符串，把每個(gè)位置的字符存進(jìn)數(shù)組（使用 hash[s[i] - 'a'] 的方式獲取 ASCII 碼）
代碼
時(shí)間復(fù)雜度 O(N) 空間復(fù)雜度 O(1)
Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# if length not equal, cannot be anagram
if len(s) != len(t):
return False
# use list to store alphabet
hash_list = [0 for _ in range(26)]
for i in range(len(s)):
hash_list[ord(s[i]) - ord('a')] += 1
hash_list[ord(t[i]) - ord('a')] -= 1
for i in range(26):
if hash_list[i] != 0:
return False
return True
C++
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
//int hash_array[26] = {0};
vector<int> hash_array(26);
for (int i = 0; i < s.size(); i++) {
hash_array[s[i] - 'a']++;
hash_array[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (hash_array[i] != 0) return false;
}
return true;
}
};
349 兩個(gè)數(shù)組的交集 Intersection of Two Arrays
要點(diǎn)
- 此題里，數(shù)組的取值范圍比字母表的略大一些?？梢钥紤]使用 set 來做哈希表，由于限制在了 1000 以內(nèi)，所以數(shù)組依舊可以做。兩種方法都可以選取。
-
unordered_set::find()返回一個(gè)指向目標(biāo)的指針；若未找到，則返回末尾指針unordered_set.end();
代碼
set / unordered_map
時(shí)間復(fù)雜度 O(MN) (每次在set里查找需要M，總共N輪) 空間復(fù)雜度 O(N)
Python
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1_set = set(nums1)
res_set = set()
for num in nums2:
if num in nums1_set:
res_set.add(num)
return list(res_set)
C++
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> nums1_set(nums1.begin(), nums1.end());
unordered_set<int> res_set;
for (int num : nums2) {
if (nums1_set.find(num) != nums1_set.end()) {
res_set.insert(num);
}
}
return vector<int>(res_set.begin(), res_set.end());
}
};
array / list
由于數(shù)值限制范圍，所以使用數(shù)組時(shí)間復(fù)雜度更低。
時(shí)間復(fù)雜度 O(M+N) 空間復(fù)雜度 O(N) (給 set 的空間)
C++
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
int nums1_hash[1001] = {0}; // to store 0 ~ 1000
unordered_set<int> res_set;
for (int num : nums1) {
nums1_hash[num] = 1;
}
for (int num : nums2) {
if (nums1_hash[num] == 1) {
res_set.insert(num);
}
}
return vector<int>(res_set.begin(), res_set.end());
}
};
Python
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1_list = [0 for _ in range(1001)]
res_set = set()
for num in nums1:
nums1_list[num] = 1
for num in nums2:
if nums1_list[num] == 1:
res_set.add(num)
return list(res_set)
202 快樂數(shù) Happy Number
要點(diǎn)
- 注意使用輔助函數(shù)的時(shí)候，按位處理數(shù)字的辦法：對(duì) 10 取模，再更新
n。 - 題意里提示
while True循環(huán)。關(guān)注if, else if, else對(duì)應(yīng)的情況：如果n等于一，則直接為True，如果n不等于一，要看它是否在集合內(nèi)，如果在，退出循環(huán)return False，若不在，則把它加入集合，再使用輔助函數(shù)更新一次n。
代碼
時(shí)間復(fù)雜度 O(logN) 空間復(fù)雜度 O(logN)
Python
class Solution:
def isHappy(self, n: int) -> bool:
tmp_set = set()
while True:
if n == 1:
return True
elif n in tmp_set:
return False
else:
tmp_set.add(n)
n = self.getSum(n)
def getSum(self, n: int) -> int:
n_sum = 0
while n > 0:
n_sum += (n % 10) * (n % 10)
n //= 10
return n_sum
C++
class Solution:
def isHappy(self, n: int) -> bool:
tmp_set = set()
while True:
if n == 1:
return True
elif n in tmp_set:
return False
else:
tmp_set.add(n)
n = self.getSum(n)
def getSum(self, n: int) -> int:
n_sum = 0
while n > 0:
n_sum += (n % 10) * (n % 10)
n //= 10
return n_sum
1 兩數(shù)之和 Two Sum
要點(diǎn)
- 使用
unordered_map，保存 k v 對(duì)。其中注意思考 k v 分別是什么：k 是 數(shù)組中的值，v 是對(duì)應(yīng)的下標(biāo)。 - 注意別忘了如果找不到，在最后返回一個(gè)空數(shù)組
return {}。
代碼
時(shí)間復(fù)雜度 O(N) 遍歷一次數(shù)組 空間復(fù)雜度 O(N) map 存儲(chǔ)
C++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> nums_map;
for (int i = 0; i < nums.size(); i++) {
int tmp = target - nums[i];
auto iter = nums_map.find(tmp);
if (iter != nums_map.end()) { // found it
return vector<int> {iter->second, i};
} else { // cannot find it, store in map
nums_map.insert(pair<int, int>(nums[i], i));
}
}
return {};
}
};
Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_dict = {}
for i in range(len(nums)):
tmp = target - nums[i]
if tmp in nums_dict.keys():
return [nums_dict[tmp], i]
else:
nums_dict[nums[i]] = i
return []
