第五天 break day
代碼隨想錄算法訓練六天 鏈表完結開啟哈希表
今日任務
● 哈希表理論基礎
● 242.有效的字母異位詞
● 349. 兩個數(shù)組的交集
● 202. 快樂數(shù)
● 1. 兩數(shù)之和
哈希表理論基礎
了解哈希表的內部實現(xiàn)原理，哈希函數(shù)，哈希碰撞，以及常見哈希表的區(qū)別，數(shù)組，set 和map。
哈希表中關鍵碼就是數(shù)組的索引下標，然后通過下標直接訪問數(shù)組中的元素。通過哈希函數(shù)hashcode()將元素存儲于hashtable中
這樣原本要枚舉的話時間復雜度是O(n)，但如果使用哈希表的話， 只需要O(1)就可以做到
當我們遇到了要快速判斷一個元素是否出現(xiàn)集合里的時候，就要考慮哈希法。
但是哈希法也是犧牲了空間換取了時間，因為我們要使用額外的數(shù)組，set或者是map來存放數(shù)據(jù)，才能實現(xiàn)快速的查找。
如果在做面試題目的時候遇到需要判斷一個元素是否出現(xiàn)過的場景也應該第一時間想到哈希法
An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor.
The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially.
The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
Hash collision 哈希碰撞
多個元素被映射到同一下標
解決方法
- 拉鏈法 發(fā)生沖突的元素都被存儲在鏈表中
其實拉鏈法就是要選擇適當?shù)墓１淼拇笮?，這樣既不會因為數(shù)組空值而浪費大量內存，也不會因為鏈表太長而在查找上浪費太多時間。
2.線性探測法
一定要保證tableSize大于dataSize。 我們需要依靠哈希表中的空位存儲沖突元素來解決碰撞問題
242. 有效的字母異位詞
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
定義一個數(shù)組叫用來上記錄字符串s里字符出現(xiàn)的次數(shù)。
需要把字符映射到數(shù)組也就是哈希表的索引下標上，因為字符a到字符z的ASCII是26個連續(xù)的數(shù)值，所以字符a映射為下標0，相應的字符z映射為下標25。
再遍歷 字符串s的時候，只需要將 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要記住字符a的ASCII，只要求出一個相對數(shù)值就可以了。 這樣就將字符串s中字符出現(xiàn)的次數(shù)，統(tǒng)計出來了。
那看一下如何檢查字符串t中是否出現(xiàn)了這些字符，同樣在遍歷字符串t的時候，對t中出現(xiàn)的字符映射哈希表索引上的數(shù)值再做-1的操作。
最后如果record數(shù)組所有元素都為零0，說明字符串s和t是字母異位詞，return true。
class Solution {
public boolean isAnagram(String s, String t) {
//把字符映射到數(shù)組也就是哈希表的索引下標上
//字符a映射為下標0，相應的字符z映射為下標25
int[] dic = new int[26];
//記錄字符在s中出現(xiàn)次數(shù)
for(int i = 0; i < s.length(); i++){
dic[s.charAt(i) - 'a']++;
}
//相應字符減去在t中出現(xiàn)的次數(shù)
for(int i = 0; i < t.length(); i++){
dic[t.charAt(i) - 'a']--;
}
for(int i = 0; i < dic.length; i++){
if(dic[i] != 0) return false;
}
return true;
}
}
時間復雜度： O(n)
空間復雜度： 一個常量大小的輔助數(shù)組, O(1)
349. 兩個數(shù)組的交集
Set 操作， 很直觀
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> records = new HashSet<Integer>();
Set<Integer> resSet = new HashSet<Integer>();
//for(int num: nums1){
for(int i = 0; i < nums1.length; i++){
records.add(nums1[i]);
}
for(int i = 0; i < nums2.length; i++){
if(records.contains(nums2[i])){
resSet.add(nums2[i]);
}
}
int[] intersection = new int[resSet.size()];
int index = 0;
for(int s: resSet){
intersection[index] = s;
index++;
}
return intersection;
}
}
時間復雜度： O（m + n）
空間復雜度： O(m + n)
202. 快樂數(shù)
編寫一個算法來判斷一個數(shù) n 是不是快樂數(shù)。
「快樂數(shù)」定義為：對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和，然后重復這個過程直到這個數(shù)變?yōu)?1，也可能是 無限循環(huán) 但始終變不到 1。如果 可以變?yōu)? 1，那么這個數(shù)就是快樂數(shù)。
如果 n 是快樂數(shù)就返回 True ；不是，則返回 False 。
示例：
輸入：19
輸出：true
解釋：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
思路
題目給出判斷條件： Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1
所以可以用set判斷當前之和是否已經出現(xiàn)過， 一旦出現(xiàn)循環(huán)， 則不是happy number。一旦出現(xiàn)1，為happy number.
class Solution {
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<Integer>();
while(n != 1 && !seen.contains(n)){
seen.add(n);
n = getNextNumber(n);
}
return n == 1;
}
private int getNextNumber(int n){
int sum = 0;
//對于每個digit進行平方，并相加
while(n > 0){
int d = n % 10;
n = n / 10;
sum += d * d;
}
return sum;
}
}
時間復雜度: getNextNumber()的復雜度 O(logN)
空間復雜度： O(logN)
方法二：快慢指針法
思路：
通過反復調用 getNext(n) 得到的鏈是一個隱式的鏈表。隱式意味著我們沒有實際的鏈表節(jié)點和指針，但數(shù)據(jù)仍然形成鏈表結構。起始數(shù)字是鏈表的頭 “節(jié)點”，鏈中的所有其他數(shù)字都是節(jié)點。next 指針是通過調用 getNext(n) 函數(shù)獲得。
意識到我們實際有個鏈表，那么這個問題就可以轉換為檢測一個鏈表是否有環(huán)
的問題。（即成為142題. 環(huán)形鏈表II）
class Solution {
public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
int slowRunner = n;
int fastRunner = getNext(n);
while (fastRunner != 1 && slowRunner != fastRunner) {
slowRunner = getNext(slowRunner);
fastRunner = getNext(getNext(fastRunner));
}
return fastRunner == 1;
}
}
//作者：LeetCode-Solution
//鏈接：https://leetcode.cn/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/
時間復雜度：O(logn)
空間復雜度： O（1）不需要hashSet， 只需要常數(shù)額外空間
- Two Sum 兩數(shù)之和
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> targetTable = new HashMap<Integer, Integer> ();
//因為要返回下標，所以將下標存為map 的value, target-nums[i] 存為key
for(int i = 0; i < nums.length; i++){
if(targetTable.containsKey(nums[i])){
return new int[]{targetTable.get(nums[i]), i};
}
targetTable.put(target - nums[i], i);
}
return new int[0];
}
}
時間復雜度 O(N)
空間復雜度 O(N)
