Leetcode刷题day6|242.有效的字母异位词 ,349. 两个数组的交集, 202. 快乐数,1. 两数之和

一、哈希表理论基础

1. 哈希作用

​ 作用：用来在一个集合中快速查找一个元素,看是不是出现过、看出现过多少次。

2. 哈希表

​ 定义：哈希表，英文名字叫做hashtable，也叫作散列表，可以通过哈希表中的关键码快速定位一个元素。

3. 哈希函数

简单来说，就是哈希的规则。

但是实际开发中，因为需要处理的数据非常多，我们很难保证每次哈希得到的位置都是不相同的。这里就涉及到另一个重要概念——哈希碰撞。

4. 哈希碰撞

   哈希碰撞就是不同的数据通过相同的哈希函数得到相同的结果的现象。

   处理方案：分为开散列处理法和闭散列处理法。其中闭散列中使用的比较多的是线性探测法、开散列用的比较多的是开链/哈希桶法。

5. 常用的哈希结构

   • 数组
   • set(集合)
   • map(映射)

   一般而言，数组用于数据范围比较集中，数据量比较小的场景；set、map用于数据范围比较分散，数据量比较大的场景。但这并不是绝对的，我们还需要根据他们的底层实现、和其他细节决定到底用哪个。

   能用数组用数组，否则用set、map。

二、有效的字母异位词

题目链接

思路

这道题的题意其实很好理解，就是判断这两个单词是不是“同分异构体”或者是不是完全相同。

显然，我们需要判断这两个字符串中所含的字母种类是不是相同，以及对应字母出现的次数是不是相同。

尝试

尝试用两个map，然后分别放进去，然后通过entrySet函数都转成set并对较长/大的进行遍历，遍历看另外一个是不是存在并且次数相同，一旦不同，就返回false。

在尝试这种思路的过程中，遇到了一些问题，通过查资料和debug找到了对应的解决方案。

1. 包装类型/引用类型数据的比较问题：在进行比较一个set1的key是不是与set2中出现的是否相同的时候，需要用equals进行比较。

2. map中判断**是否存在：

   1. 判断key：containsKey(key)
   2. 判断value:contains(value)

3. map中通过一个数据获取另外一个

   1. 通过key得到value: map.get(key)
   2. 通过key得到value，没有返回默认值x：map.getOrDefault(key,x)

4. map获得集合的方式

   1. entrySet——k-v[Set>]
   2. keySet——k[Set]
   3. values——v[Collection]

5. 字符串和整数的转换

   1. 字符串–》整数：Integer.parseInt(s)
   2. 整数–》字符串：String.valuesOf(num)

   简而言之，就是前边是什么包装类，返回的就是对应的类型的对象

AC代码

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character,Integer> map1=new HashMap<>();
        Map<Character,Integer> map2=new HashMap<>();
        char[] str1=s.toCharArray();
        char[] str2=t.toCharArray();
        for(int i=0;i<str1.length;i++){
            int cnt=map1.getOrDefault(str1[i],0);
            if(cnt==0){
                map1.put(str1[i],1);
            }else{
                map1.put(str1[i],cnt+1);
            }
        }
        for(int i=0;i<str2.length;i++){
            int cnt=map2.getOrDefault(str2[i],0);
            if(cnt==0){
                map2.put(str2[i],1);
            }else{
                map2.put(str2[i],cnt+1);
            }
        }
        Set<Map.Entry<Character,Integer>> set1=map1.entrySet();
        Set<Map.Entry<Character,Integer>> set2=map2.entrySet();
        if(set1.size()>=set2.size()){
            for(Map.Entry<Character,Integer> x:set1){
                if(!Objects.equals(map2.getOrDefault(x.getKey(), 0), x.getValue())){
                    return false;
                }
            }
        }else{
            for(Map.Entry<Character,Integer> x:set2){
                if(map1.getOrDefault(x.getKey(),0)!=x.getValue()){
                    return false;
                }
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

但是这种思路相较于下边这种方法而言，确实显得有点low……

优化的思路

因为这里题目已经说明，字符集中在a–>z，一共有26个字符，并且对应的ASCII码非常集中，此时我们就可以采用数组作为哈希结构。

1. 数组大小开辟成26，初始值均设置成0
2. 遍历字符串1，将字符-‘a’作为索引，对应数组对应的值加加
3. 遍历字符串2，将字符-‘a’，对应数组对应值减减
4. 最后判断数组元素是不是都是0，是的话就是字母异位词，反之不是。

AC代码

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] hash=new int[26];
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            hash[ch-'a']++;
        }
        for(int i=0;i<t.length();i++){
            char ch=t.charAt(i);
            hash[ch-'a']--;
        }
        for(int x:hash){
            if(x!=0){
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

三、两个数组的交集

题目链接

思路

一开始这么想的，但是感觉结果集的获得很麻烦，最后果断放弃。

1. 定义两个set
2. 分别遍历两个数组，把对应的数组元素加入到set中。
3. 最后任选一个set，遍历

AC思路

1. 定义两个set，一个用来遍历，一个用来存放结果集
2. 其中一个数组都放到第一个set，之后再遍历第二个数组，判断第一个集合中是不是包含，包含的话放进第二个结果集中去
3. 由于集合不能直接转成数组返回，所以再开辟结果集大小相等的一个数组
4. 遍历结果集，分别放到数组中，返回

AC代码

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set=new HashSet<>();
        Set<Integer> retSet=new HashSet<>();
        for(int x:nums1){
            set.add(x);
        }
        for(int x:nums2){
            if(set.contains(x)){
                retSet.add(x);
            }
        }
        int[] arr=new int[retSet.size()];
        int k=0;
        for(int x:retSet){
            arr[k++]=x;
        }
        return arr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

四、快乐数

题目链接

思路

一开始想把n转成字符串，在操作，结果发现这样绕的太远了……

1. 定义一个set集合，将每次处理的n都加入set里，定义一个子函数，得到下次循环处理的数

2. 一旦重复==》循环，直接返回false

3. 显然这个问题，需要循环处理

4. 循环的条件是，不是1（结果不明朗，还需要处理），或者没有在set中出现过（没有死循环）

5. 循环体内，加入set集合，并且调用子函数，用于得到一次操作后新的n

AC代码

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set=new HashSet<>();
        while(n!=1&&!set.contains(n)){
            set.add(n);
            n=getNextNum(n);
        }
        return n==1;
    }
    private int getNextNum(int n){
        int ret=0;
        while(n>0){
            int tmp=n%10;
            ret+=tmp*tmp;
            n/=10;
        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

五、两数之和

题目链接

思路

1. 因为此题要求我们返回下标，并且符合使用哈希的条件，所以我们这里使用map
2. 遍历数组，如果看target-当前的数是不是在数组中存在，若存在直接赋值给结果数组；不存在放进map集合
3. 注意遍历的范围是1到nums.length

AC代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        int[] ret=new int[2];
        map.put(nums[0],0);
        for(int i=1;i<nums.length;i++){
            int tmp=target-nums[i];
            if(map.containsKey(tmp)){
                ret[0]=map.get(tmp);
                ret[1]=i;
                break;
            }else{
                map.put(nums[i],i);
            }
        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

六、总结

1. 什么时候使用哈希——快速查找元素

2. 用好哈希——掌握好map和set的几个得到数值和查找是否存在的方法

3. 字符串的查找——一般是以字符为基本单位处理

   这里有两个处理思路：转成字符数组toCharArray()，直接取对应下标的字符，放进集合中。