算法总结-哈希表

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) {
        // 存储结果的map
        Map<String, List<String>> map = new HashMap<>();
        // 一次遍历，将每个元素都排序之后作为key放到map中
        for (String str : strs) {
            // 转换为数组
            char[] charArray = str.toCharArray();
            // 排序
            Arrays.sort(charArray);
            // 作为key
            String 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为index
        Map<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 {
                // 如果不满足条件，就将当前元素加入map
                map.put(nums[i], i);
            }
        }
        // do nothing
        return 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来统计，如果重复出现一次，就是返回false
        Set<Integer> set = new HashSet<>();
        // 只要 1 != n
        while (1 != n) {
            // 计算平方和
            int num = getNum(n);
            // 如果已经包含了，就直接返回false
            if (set.contains(num)) {
                return false;
            }
            // 没有包含再放到set中
            set.add(num);
            // 更新这个n
            n = 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中，一趟遍历，只要当前元素的前一个元素不在数组中，那么就说明是一个起点，就可以寻找连续序列的长度