代码随想录算法训练营第六天 | 哈希表算法题

哈希表是什么？

哈希表是通过关键码直接进行访问的数据结构；其实哈希表就是数组，关键码就是数组下标；区别在于数据存进数组前，要先通过元素的hash值算出要存放的数组位置下标；

242.有效的字母异位词

力扣题目链接

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

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
示例 2: 输入: s = “rat”, t = “car” 输出: false

说明: 你可以假设字符串只包含小写字母。

解法：定义数组 hash[] 当作哈希表使，数组长度为26，对应26个英文小写字母；然后遍历第一个字符串，通过表达式： 字符 - ‘a’ 计算出字符存放的位置，但不存字符值，而是进行+1操作，比如字符串中 ‘c’ 出现了5次，则hash[‘c’ - ‘a’] 的值为5; 第一个字符串遍历结束后开始遍历第二个字符串，和第一个字符的遍历逻辑类似，区别在于这次采取-1操作； 最后，如果数组的每一个位置都是0，则满足字母异位词；

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        // 存放26个字母出现次数, 每个位置默认值是0
        int[] records = new int[26];
        for (int i = 0; i < s.length(); i++) {
            // s.charAt(i)是遍历字符串，- 'a'是获得字母对应的数组下标，参考ASCII表
            records[s.charAt(i) - 'a']++;
        } 

        for (int i = 0; i < t.length(); i++) {
            records[t.charAt(i) - 'a']--;
            // 如果不是字母异位词，则循环中有个位置一定会小于0
            if ( records[t.charAt(i) - 'a'] < 0) {
                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

349. 两个数组的交集

力扣题目链接

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

解法：最直观的思路就是，把nums1存入hashSet中，再遍历nums2，有相交的存入另一个hashSet中，然后转化为数组返回;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length <= 0 || nums2 == null || nums2.length <= 0) {
            return new int[0];
        }
        Set<Integer> setA = new HashSet<Integer>();
        Set<Integer> resultSet = new HashSet<Integer>();
        for (Integer i: nums1) {
            setA.add(i);
        }
        for (Integer i: nums2) {
            if (setA.contains(i)) {
                resultSet.add(i);
            }
        }
        return resultSet.stream().mapToInt(x -> x).toArray();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

202. 快乐数

[力扣题目链接](202. 快乐数 - 力扣（Leetcode）)

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

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false

解法：两个要点 1. 如何计算每个位置上的数字的平方和 2. 如何判断可能是无限循环(定义一个set存放n，如果set出现过，则会无限循环，直接return false);

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

1. 两数之和

[力扣题目链接](1. 两数之和 - 力扣（Leetcode）)

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

思路：由于只存在一种结果，所以入参数组必然不可能有重复元素； 判断某个元素是否存在的最快方式当然是数组了，但是这个题目要求返回下标，所以我们选择hashMap，元素值作为key，下标作为value，如果map中存在 target - num[i] 的元素，则满足条件；否则，将元素插入map中

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