哈希表篇
刷题路线来自: 代码随想录
1. map的遍历方式
方式一： 在for-each循环中遍历keys或values。
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//遍历map中的键
for (Integer key : map.keySet()) {
}
//遍历map中的值
for (Integer value : map.values()) {
}
方式二： 把所有的键值对装入迭代器中，然后遍历迭代器
Iterator<Map.Entry<Integer,String>> it = map.entrySet().iterator();
while(it.hasNext()){
Map.Entry<Integer,String> entry=it.next();
System.out.println("Key = " + entry.getKey() + ", Value = " +
entry.getValue());
}
方法三： 在for-each循环中使用entries来遍历
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println("Key = " + entry.getKey() + ", Value = " +
entry.getValue());
}
2. map 作为哈希表
242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
题解：
先遍历记录单词 s 记录字符出现的次数，然后遍历字符串 t，减去 map 中对应的次数，若是变位词，最后 map 中一定所有字符出现次数为 0
class Solution {
public boolean isAnagram(String s, String t) {
Map<Character, Integer> map = new HashMap<>();
// 遍历单词 t，记录字符出现的次数
for (char ch : s.toCharArray()) {
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
// 遍历单词 s，减去 map 中对应的次数
for (char ch : t.toCharArray()) {
map.put(ch, map.getOrDefault(ch, 0) - 1);
}
// 遍历map
for (char key : map.keySet()) {
if (map.get(key) != 0) return false;
}
return true;
}
}
方式二：
使用数组代替 hashMap
class Solution {
public boolean isAnagram(String s, String t) {
int[] table = new int[26];
for (char ch : s.toCharArray()) {
table[ch - 'a']++;
}
for (char ch : t.toCharArray()) {
table[ch - 'a']--;
}
for (int count : table) {
if (count != 0) return false;
}
return true;
}
}
383. 赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = “a”, magazine = “b”
输出：false
示例 2：
输入：ransomNote = “aa”, magazine = “ab”
输出：false
示例 3：
输入：ransomNote = “aa”, magazine = “aab”
输出：true
题解：
思路同上题，ransomNote 中的字符 magazine 中必须有，而 magazine 中的字符 ransomNote 中不一定有
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] table = new int[26];
for (char ch : magazine.toCharArray()) {
table[ch - 'a']++;
}
for (char ch : ransomNote.toCharArray()) {
if (table[ch - 'a'] != 0) {
table[ch - 'a']--;
} else {
return false;
}
}
return true;
}
}
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
题解：
使用 map 记录数组中出现的数字和对应下标，在遍历 num 时判断 map 中是否存在 target - num
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i ++) {
// 是否存在 target - num，
if (map.containsKey(target - nums[i])) {
// 存在说明两数和为 0
return new int[] {i, map.get(target - nums[i])};
}
// 不存在，map中添加，继续遍历
map.put(nums[i], i);
}
return new int[0];
}
}
3. set 作为哈希表
349. 两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
题解：
使用 set 记录和判断数组中的数字，再使一个 set 用来保存两个数组的交集
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Set<Integer> res = new HashSet<>();
// 遍历 nums1，记录nums1 中出现的数字
for (int num : nums1) {
set.add(num);
}
// 遍历 nums2，判断nums2 中的数字是否在 nums1 中
for (int num : nums2) {
if (set.contains(num)) {
// 保存交集数字
res.add(num);
}
}
// 返回值数组
int[] resArr = new int[res.size()];
int i = 0;
for (int num : res) {
resArr[i++] = num;
}
return resArr;
}
}
202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
题解： 如果是快乐数最后会等于1，如果不是就会陷入死循环，使用 set 记录可判断是否陷入死循环。同 环形链表 这道题，也可以使用快慢指针判断是否陷入循环
class Solution {
// 计算并返回下一个数
public int nextNum(int num) {
int res = 0;
while (num > 0) {
int temp = num % 10;
num /= 10;
res += temp * temp;
}
return res;
}
public boolean isHappy(int n) {
// 记录出现过的数
Set<Integer> set = new HashSet<>();
set.add(n);
while (n != 1) {
// 得到下一个数
n = nextNum(n);
// 如果出现过说明已经陷入循环
if (set.contains(n)) {
// 已死循环，返回 false
return false;
}
// 第一次出现，添加到 set里
set.add(n);
}
// 此时n = 1，是快乐数
return true;
}
}