算法总结-哈希表

1.赎金信

1.答案

package com.sunxiansheng.arithmetic.day14;/*** Description: 383. 赎金信** @Author sun* @Create 2025/1/22 11:10* @Version 1.0*/
public class t383 {public static boolean canConstruct(String ransomNote, String magazine) {// 字符频率数组int[] frequency = new int[26];// 将magazine的字符频率统计一下for (char c : magazine.toCharArray()) {frequency[c - 'a']++;}// 遍历一下ransomNote，看看够不够减for (char c : ransomNote.toCharArray()) {if (--frequency[c - 'a'] < 0) {return false;}}return true;}
}

2.思路

就是利用一个字母减去’a’的范围是在0到25的，来统计一下字符的频率数组，之后再看一下够不够减即可

2.字母异位词分组

1.答案

package com.sunxiansheng.arithmetic.day14;import java.util.*;/*** Description: 49. 字母异位词分组** @Author sun* @Create 2025/1/22 13:30* @Version 1.0*/
public class t49 {public static List<List<String>> groupAnagrams(String[] strs) {// 存储结果的mapMap<String, List<String>> map = new HashMap<>();// 一次遍历，将每个元素都排序之后作为key放到map中for (String str : strs) {// 转换为数组char[] charArray = str.toCharArray();// 排序Arrays.sort(charArray);// 作为keyString key = new String(charArray);// 如果map中包含了就加入，不包含就创建一个if (!map.containsKey(key)) {List<String> list = new ArrayList<>();list.add(str);map.put(key, list);} else {map.get(key).add(str);}}return new ArrayList<>(map.values());}
}

2.思路

一次遍历，将每个元素都排序之后作为key放到map中，如果map中包含了就加入，不包含就创建一个

3.两数之和

1.答案

package com.sunxiansheng.arithmetic.day14;import java.util.HashMap;
import java.util.Map;/*** Description: 1. 两数之和** @Author sun* @Create 2025/1/22 13:41* @Version 1.0*/
public class t1 {public static int[] twoSum(int[] nums, int target) {// key为nums的元素，value为indexMap<Integer, Integer> map = new HashMap<>();// 一次遍历，如果当前元素跟map中的元素可以满足条件，就返回结果for (int i = 0; i < nums.length; i++) {if (map.containsKey(target - nums[i])) {return new int[]{map.get(target - nums[i]), i};} else {// 如果不满足条件，就将当前元素加入mapmap.put(nums[i], i);}}// do nothingreturn null;}
}

2.思路

一个map，key为nums的元素，value为index，一次遍历，如果当前元素跟map中的元素可以满足条件，就返回结果，如果不满足条件，就将当前元素加入map

4.快乐数

1.答案

package com.sunxiansheng.arithmetic.day14;import java.util.HashSet;
import java.util.Set;/*** Description: 202. 快乐数** @Author sun* @Create 2025/1/22 13:50* @Version 1.0*/
public class t202 {public static boolean isHappy(int n) {// 使用一个set来统计，如果重复出现一次，就是返回falseSet<Integer> set = new HashSet<>();// 只要 1 != nwhile (1 != n) {// 计算平方和int num = getNum(n);// 如果已经包含了，就直接返回falseif (set.contains(num)) {return false;}// 没有包含再放到set中set.add(num);// 更新这个nn = num;}return true;}/*** 拿到数字的每个位数的平方和** @param n* @return*/private static int getNum(int n) {int sum = 0;while (n > 0) {// 拿出第一位int num = n % 10;sum += (num) * num;// 将n去掉一位n = n / 10;}return sum;}
}

2.思路

先编写一个方法，拿到数字的每个位数的平方和，然后使用一个set来统计平方和，如果重复出现一次，就是返回false

5.最长连续序列

1.答案

package com.sunxiansheng.arithmetic.day14;import java.util.HashSet;
import java.util.Set;/*** Description: 128. 最长连续序列** @Author sun* @Create 2025/1/22 14:16* @Version 1.0*/
public class t128 {public static int longestConsecutive(int[] nums) {if (nums == null || nums.length == 0) {return 0;}// 将数组去重并放到set中Set<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);}// 一趟遍历，只要当前元素的前一个元素不在数组中，那么就说明是一个起点，就可以寻找连续序列的长度int max = 1;for (Integer num : set) {// 统计长度int length = 1;if (!set.contains(num - 1)) {// 当前元素是起点int temp = num;// 只要包含了下一个元素，长度就加一while (set.contains(temp + 1)) {length++;temp++;}}// 更新最大值max = Math.max(max, length);}return max;}
}

2.思路

先将数组去重并放到set中，一趟遍历，只要当前元素的前一个元素不在数组中，那么就说明是一个起点，就可以寻找连续序列的长度