第五天 break day
代码随想录算法训练六天 链表完结开启哈希表
今日任务
● 哈希表理论基础
● 242.有效的字母异位词
● 349. 两个数组的交集
● 202. 快乐数
● 1. 两数之和
哈希表理论基础
了解哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set 和map。
哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。通过哈希函数hashcode()将元素存储于hashtable中
这样原本要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。
如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法
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 哈希碰撞
多个元素被映射到同一下标
解决方法
- 拉链法 发生冲突的元素都被存储在链表中
其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。
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.
定义一个数组叫用来上记录字符串s里字符出现的次数。
需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。
再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。
那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。
最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。
class Solution {
public boolean isAnagram(String s, String t) {
//把字符映射到数组也就是哈希表的索引下标上
//字符a映射为下标0，相应的字符z映射为下标25
int[] dic = new int[26];
//记录字符在s中出现次数
for(int i = 0; i < s.length(); i++){
dic[s.charAt(i) - 'a']++;
}
//相应字符减去在t中出现的次数
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)
空间复杂度： 一个常量大小的辅助数组, O(1)
349. 两个数组的交集
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. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 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判断当前之和是否已经出现过， 一旦出现循环， 则不是happy number。一旦出现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) 得到的链是一个隐式的链表。隐式意味着我们没有实际的链表节点和指针，但数据仍然形成链表结构。起始数字是链表的头 “节点”，链中的所有其他数字都是节点。next 指针是通过调用 getNext(n) 函数获得。
意识到我们实际有个链表，那么这个问题就可以转换为检测一个链表是否有环
的问题。（即成为142题. 环形链表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， 只需要常数额外空间
- Two Sum 两数之和
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)
