一些理論知識
哈希函數是一種映射關系，根據關鍵詞key，經過一定函數關系得到元素的位置。
常見的哈希函數構造方法
-
直接定址法
-
除留余數法
-
疊加法
-
隨機數法
哈希沖突
不同關鍵字通過相同哈希函數計算出相同的哈希地址，該種現象稱為哈希沖突或者哈希碰撞
--------
熟練掌握幾種常見的STL。
一、有效的字母異位詞
知識點
-
統計字母個數操作技巧 record[s[i] - 'a']++;
-
數組也是哈希表哦~
題目
給定兩個字符串 *s* 和 *t* ，編寫一個函數來判斷 *t* 是否是 *s* 的字母異位詞。
注意：若 *s* 和 *t* 中每個字符出現的次數都相同，則稱 *s* 和 *t* 互為字母異位詞。
242. 有效的字母異位詞 - 力扣（LeetCode）
題解
class Solution {
public:bool isAnagram(string s, string t) {vector<int> record(26, 0);// 統計s中字母個數for(int i = 0; i < s.size(); i++){record[s[i] - 'a']++;}for(int j = 0; j < t.size(); j++){record[t[j] - 'a']--;}for(int k = 0; k < record.size(); k++){if(record[k] != 0){return false;}}return true;}
};
二、兩個數組的交集
知識點
-
unordered_set無序集合；存儲唯一元素；與set不同，unordered_set不會對元素進行排序，而是使用哈希表來實現快速的查找和插入操作。unordered_set使用哈希表來實現，這使得查找、插入和刪除操作的平均時間復雜度為常數級別（O(1)）。 -
find如果找到了，find返回指向該元素的迭代器，否則返回nums1_set.end()，表示未找到。
題目
給定兩個數組 nums1 和 nums2 ，返回 它們的交集 。輸出結果中的每個元素一定是 唯一 的。我們可以 不考慮輸出結果的順序 。
349. 兩個數組的交集 - 力扣（LeetCode）
題解
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result_set;unordered_set<int> nums1_set(nums1.begin(), nums1.end());
?for (int i = 0; i < nums2.size(); i++){if(nums1_set.find(nums2[i]) != nums1_set.end()){result_set.insert(nums2[i]);}}
?return vector<int> (result_set.begin(), result_set.end());}
};
三、快樂數
知識點
-
停止條件的設置
在計算每個位置上的數字的平方和時，如果出現了之前已經計算過的結果，就會形成一個循環。這是因為每個數字的平方和可能會有限個，而如果在計算的過程中遇到了之前的結果，就會陷入一個循環，不斷重復。
題目
編寫一個算法來判斷一個數 n 是不是快樂數。
「快樂數」 定義為：
-
對于一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
-
然后重復這個過程直到這個數變為 1，也可能是 無限循環 但始終變不到 1。
-
如果這個過程 結果為 1，那么這個數就是快樂數。
如果 n 是 快樂數 就返回 true ；不是，則返回 false 。
202. 快樂數 - 力扣（LeetCode）
題解
class Solution {
public:int get_sum(int n){int sum = 0;while(n){sum += (n % 10) * (n % 10);n /= 10;}return sum;}
?bool isHappy(int n) {unordered_set<int> result_sum;while(1){int sum = get_sum(n);if(sum == 1) return true;if(result_sum.find(sum) == result_sum.end()){result_sum.insert(sum);}else{return false;}n = sum;}}
};
四、兩數之和
知識點
學會 unordered_map 的用法
| 映射 | 底層實現 | 是否有序 | 數值是否可以重復 | 能否更改數值 | 查詢效率 | 增刪效率 |
|---|---|---|---|---|---|---|
| std::map | 紅黑樹 | key有序 | key不可重復 | key不可修改 | O(log n) | O(log n) |
| std::multimap | 紅黑樹 | key有序 | key可重復 | key不可修改 | O(log n) | O(log n) |
| std::unordered_map | 哈希表 | key無序 | key不可重復 | key不可修改 | O(1) | O(1) |
題目
給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那 兩個 整數，并返回它們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現。
你可以按任意順序返回答案。
1. 兩數之和 - 力扣（LeetCode）
題解
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 goal = nums_map.find(tmp);if(goal != nums_map.end()){return {goal->second, i};}nums_map.insert(pair<int,int>(nums[i], i));}return {};}
};
五、四數相加 II
知識點
-
時間復雜度； 不需要考慮去重；哈希表
題目
給你四個整數數組 nums1、nums2、nums3 和 nums4 ，數組長度都是 n ，請你計算有多少個元組 (i, j, k, l) 能滿足：
-
0 <= i, j, k, l < n -
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
454. 四數相加 II - 力扣（LeetCode）
題解
class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int,int> Map;
?for (int i : nums1){for(int j : nums2){Map[i + j]++; }}
?int count = 0;for (int i : nums3){for(int j : nums4){if(Map.find(-(i + j)) != Map.end()){count += Map[-(i + j)];}}}return count;}
};
六、贖金信
題目
給你兩個字符串：ransomNote 和 magazine ，判斷 ransomNote 能不能由 magazine 里面的字符構成。
如果可以，返回 true ；否則返回 false 。
magazine 中的每個字符只能在 ransomNote 中使用一次。
383. 贖金信 - 力扣（LeetCode）
題解
解法類似于 ‘有效的字母異位詞’
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int record[26] = {0};for(int i = 0; i < magazine.size(); i++){record[magazine[i] - 'a']++;}
?for(int j = 0; j < ransomNote.size(); j++){record[ransomNote[j] - 'a']--;}
?for(int k = 0; k < 26; k++){if(record[k] < 0){return false;}}return true;}
};
)
