算法训练营（day06）

哈希表理论基础

  • 哈希表是根据关键码的值而直接进行访问的数据结构
  • 直白来讲其实数组就是一张哈希表。哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。
哈希表1
  • 一般哈希表都是用来快速判断一个元素是否出现在集合里

哈希表需要了解的知识点主要是 哈希函数、哈希碰撞 以及 哈希结构：

1.哈希函数

哈希函数主要是将元素映射到哈希表的索引，通过查询索引能快速查询元素是否存在。

举个例子，判断学生是否是该学校的，可以把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里

哈希表2

这里会出现一个问题，如果哈希表的长度不足以容纳所有的元素，会发生什么情况呢？

答案是：会出现多个元素指向同一个索引下标的情况，也就是常说的 哈希碰撞（哈希冲突）

2.哈希冲突（哈希碰撞）

举个例子，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞

哈希表3

解决哈希冲突一般使用两种解决方法：

  • 拉链法：

​ 上面说到，小李和小王在索引1的位置发生了冲突，那我们可以将发生冲突的元素存储在链表中。 这样我们仍可以通过索引找到小李和小王

哈希表4

​ 使用拉链法，需要根据数据规模(dataSize)定义好哈希表的大小(tableSize)。防止因为数组空值而浪费大量内存，以及因为链表太长而在查找上浪费太多时间。这里就引申到哈希表的扩容机制了：https://blog.csdn.net/java_wxid/article/details/121599499

  • 线性探测法:

​ 使用线性探测法，一定要保证tableSize(哈希表的大小)大于dataSize(数据规模)。 我们需要依靠哈希表中的空位来解决碰撞问题。

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

哈希表5

3.哈希结构

当使用哈希法解决问题时，一般使用三种数据结构：

  • 数组
  • map
  • set

242.有效的字母异位词

题目链接：https://leetcode.cn/problems/valid-anagram/description/

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

解题思路

解题过程：

  1. 如果 s 字符串长度和 t 字符串长度不等，直接返回 false

  2. 判断 t 是否是 s 的字母异位词，可以考虑使用数组遍历

    • 将 s 字符串 遍历成数组char
    • 用 t 字符串 遍历数组char
    • 如果匹配到相同的字母，则数组中除去这个元素

  3. t 字符串遍历结束后，判断数组 char 长度

    • 如果为0， 则说明 t 字符串是 s 的字母异位词，返回 true
    • 否则返回 false

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        char[] res = new char[26];
        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 count : res){
            if(count != 0){
                return false;
            }
        }
        return true;
    }
}

349.两个数组的交集

题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/description/

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

解题思路

解题过程：

  1. 看到了唯一且无序，可以考虑使用 set 进行解题

  2. 首先判定一下 两个数组的状态（null / length == 0）

  3. 将 nums1 内的元素保存进 set 中

  4. 定义一个 resSet 存放 交集

    • 遍历 nums2
    • 如果 nums2 的元素 在 set 中能找到
    • 则将这个元素保存在 resSet 中

  5. 将 resSet 转换成数组输出

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0){
            return new int[0];
        }
        Set<Integer> nums1Set = new HashSet<>();
        Set<Integer> res = new HashSet<>();

        for(int num : nums1){
            nums1Set.add(num);
        }
        for(int num : nums2){
            if(nums1Set.contains(num)){
                res.add(num);
            }
        }
        return res.stream().mapToInt(x -> x).toArray();
    }
}

202.快乐数

题目链接：https://leetcode.cn/problems/happy-number/description/

编写一个算法来判断一个数 n 是不是快乐数。「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；否则返回 false 。

解题思路

解题过程：

  1. 反向理解快乐数：如果不是快乐数，就会 无限循环 且 始终变不到 1

  2. 根据题意，可以将遍历条件以及判定结果写出

    • 遍历条件：!= 1 && 不循环
    • 判定结果 return n == 1

  3. 不循环这个条件，可以拆解成没有重复出现平方和，就可以用 set.contains() 来解决

  4. 平方和的循环

    • 通过 取余 的方式，得到每一位上的值
    • 将 平方和的值 赋值给 n
    • 用 set 保存每一个 n

  5. 当 n 出现重复时，跳出循环，进行判定

详细代码

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

1.两数之和

题目链接：https://leetcode.cn/problems/two-sum/description/

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

解题思路

思路一：暴力遍历

解题过程：

  1. 定义两个for循环，如果存在 nums[i] + nums[j] == target，则返回数组[i，j]
  2. 否则返回 new int[]{}

思路二：哈希法

解题过程：

  1. 既要找到数组中的数(key)，又要返回下标(value)，可以考虑使用 map 来解题
  2. 题目要求的返回两个整数的下标，实际就是返回 nums[i] 和 target - nums[i] 的值(value)
  3. 用 map 保存数组中的每个值和其下标，再用 map.containsKey() 判断是否存在，即可判断答案是否存在
    • 存在，则返回 new int[]{map.get(target - nums[i]), i}
    • 不存在，则返回 new int[]{}

详细代码

解法一：暴力遍历

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{};
    }
}

解法二：哈希法

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

解法二优化：

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