Day05代码随想录2 | 哈希表理论&&有效的字母异位词&&两个数组的交集&&快乐数&&赎金信

哈希表理论基础

哈希表

根据关键码的值而进行直接访问的数据结构

哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。

一般哈希表都是用来快速判断一个元素是否出现在集合里。

哈希函数

哈希函数，将学生的姓名直接映射味哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数，通过hashcode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转换为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

如果hashCode得到的数值大于哈希表的大小，我们将会再次对数值做一个取模的操作，这样我们就保证了学生姓名一定可以映射到哈希表上。

为了避免多个hashCode映射到哈希表同一个索引下标的位置，我们需要哈希碰撞。

哈希碰撞

拉链法

索引1的位置发生了冲突，发生冲突的元素都被存储在链表中，这样我们就可以通过索引找到了。

拉链法：要选择 适当的哈希表的大小，这样既不会因为数组控制而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

一定要保证tableSize大于dataSize，我们需要依靠哈希表中的空位来解决碰撞问题

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。

常见的三种哈希结构

• 数组
• set集合
• map映射

---

242.有效的字母异位词

文章：3. 两个数组的交集

题目：242. 有效的字母异位词

【思路】

关键：res[s.charAt(i) - ‘a’]++;

• Java

class Solution {
    public boolean isAnagram(String s, String t) {
       if(s.length() != t.length()){
           return false;
       }
       int[]res = new int[27];
       for(int i = 0;i < s.length();i++){
           res[s.charAt(i) - 'a']++;
       }
        for(int i = 0;i < t.length();i++){
           res[t.charAt(i) - 'a']--;
       }
       for(int i : res){
           if(i != 0){
               return false;
           }
       }
       return true;
    }
}

• Go

unicode解法：rune函数转换为unicode类型

func isAnagram(s string, t string) bool {
    record := [26]int{}
    for _,s := range s{
        record[s-rune('a')]++
    }
    for _,s := range t{
        record[s-rune('a')]--
    }
    return record == [26]int{}
}

---

349.两个数组的交集

文章：3. 两个数组的交集

题目：349. 两个数组的交集

【思路】

忘记set转换成int数组的函数了、、

res.stream().mapToInt(x -> x).toArray();

• Java

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set = new HashSet<>();
        HashSet<Integer> res = new HashSet<>();
        for(int i : nums1){
            if(!set.contains(i)){
                set.add(i);
            }
        }
        for(int i : nums2){
            if(set.contains(i)){
                res.add(i);
            }
        }
        return res.stream().mapToInt(x -> x).toArray();
    }
}

• Go

Struct{}{}:表示创建一个空结构体类型和使用该类型的字面量、这样的语法表示我们创建了一个空结构体的实例

func intersection(nums1 []int, nums2 []int) []int {
    set := make(map[int]struct{},0)
    res:= make([]int,0)
    for _,i:= range nums1{
        if _,ok := set[i];!ok{
            set[i] = struct{}{}
        }
    }
    for _,i:=range nums2{
        if _,ok := set[i]; ok{
            res = append(res,i)
            delete(set,i)
        }
    }
    return res
}

---

202.快乐数

文章：4. 快乐数

题目：202. 快乐数

【思路】

• Java

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer>set = new HashSet<>();
        while(n !=1 && !set.contains(n)){
            set.add(n);
            n = cal(n);
            //调换一下顺序，不调换的话少了一个数
        }   
        return n ==1 ;
    }
    public int cal(int n){
        int res = 0;
        while(n > 0){
                int i = n %10;
                res += i*i;
                n = n/10;           
        }
        return res;
    }
}

• Go

func isHappy(n int) bool {
    m := make(map[int]bool,0)
    for n != 1 && !m[n]{
       n,m[n]= cal(n),true//好简洁的写法！！ 
    }
    return n==1
}
func cal(n int)int{
    res := 0
    for n >0{
        i:= n%10
        res += i*i
        n = n/10
    }
    return  res 
}

---

383.赎金信

文章：7. 赎金信

题目：383. 赎金信

【思路】

和上边一样的

• Java

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
//用数组
        int[]arr = new int[26];
        for(char c : magazine.toCharArray()){
            arr[c - 'a']++;
        }
        for(char c : ransomNote.toCharArray()){
            arr[c - 'a']--;
        }
        for(int i : arr){
            if(i <0)return false;
        }
        return true;
    }
}

• Go

func canConstruct(ransomNote string, magazine string) bool {
    res :=make([]int,26)
    for _,i := range magazine{
        res[ i - 'a' ]++
    }
    for _,i := range ransomNote{
        res[ i - 'a']--
    }
    for _,i := range res{
        if i < 0 {
            return false
        }
    }
    return true
}

---