Java数据结构和算法(代码版)-3

Hash算法

package com.lzlg.study.algorithm.new2023.hash;

import cn.hutool.core.lang.hash.MurmurHash;

import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

/
 * 自定义Hash表
 *
 * @author lzlg
 * 2023/8/2 11:46
 */
public class MyHashTable {
    // hash表数组
    Entry[] table;
    // 元素数量
    int size;
    // 扩容的阈值
    int threshold;

    public MyHashTable() {
        // 初始化数组长度为16,为2的n次幂
        this.table = new Entry[16];
        this.size = 0;
        // 阈值是0.75(3/4)
        this.threshold = table.length * 3 / 4;
    }

    /
     * 根据key查找值value
     *
     * @param key 关键字key
     * @return 值value
     */
    public Object get(Object key) {
        int hash = hash(key);
        return get(hash, key);
    }

    /
     * 根据key放置value
     *
     * @param key   关键字key
     * @param value 值value
     */
    public void put(Object key, Object value) {
        int hash = hash(key);
        put(hash, key, value);
    }

    /
     * 根据key删除value
     *
     * @param key 关键字key
     * @return 被删除的值value
     */
    public Object remove(Object key) {
        int hash = hash(key);
        return remove(hash, key);
    }

    /
     * hash函数
     *
     * @param key 关键字
     * @return hash值
     */
    private int hash(Object key) {
        if (key instanceof String) {
            String k = (String) key;
//            int hash = 0;
//            for (int i = 0; i < k.length(); i++) {
//                hash = hash * 31 + k.charAt(i);
//            }
//            return hash;
            return MurmurHash.hash32(k);
        }
        // JDK自带实现的hash函数
        return key.hashCode();
    }

    /
     * 根据hash和key查找value
     *
     * @param hash hash值
     * @param key  关键字key
     * @return 值value
     */
    Object get(int hash, Object key) {
        // 相当于hash%table.length,前提是table.length必须是2的n次幂
        int idx = hash & (table.length - 1);
        // 如果指定下标没有元素,直接返回null
        if (table[idx] == null) {
            return null;
        }
        // 如果有,则遍历链表进行查找
        Entry p = table[idx];
        while (p != null) {
            // 找到和key一致的节点,然后返回节点的值
            if (p.key.equals(key)) {
                return p.value;
            }
            p = p.next;
        }
        return null;
    }

    /
     * 根据hash和key放置value
     *
     * @param hash  hash值
     * @param key   关键字key
     * @param value 值value
     */
    void put(int hash, Object key, Object value) {
        // 相当于hash%table.length,前提是table.length必须是2的n次幂
        int idx = hash & (table.length - 1);
        // 如果下标对应的元素为null,则直接赋值
        if (table[idx] == null) {
            table[idx] = new Entry(hash, key, value);
            size++;
            return;
        }
        // 如果该下标已有元素
        // 1.没有查找到,则添加到链表中
        // 2.查找到,则进行更新
        Entry p = table[idx];
        // 开始循环
        while (true) {
            // 如果找到和key相同的,则进行更新
            if (p.key.equals(key)) {
                p.value = value;
                return;
            }
            // 当在链表最后一个节点时退出循环
            if (p.next == null) {
                break;
            }
            p = p.next;
        }

        // 如果没找到,则添加到链表中
        p.next = new Entry(hash, key, value);
        size++;

        // 如果元素数量大于阈值,则进行扩容
        if (size > threshold) {
            resize();
        }
    }

    /
     * 扩容
     * 规律:按 hash & table.length 是否等于0划分链表
     * 1.如果等于0,则还是留在和原下标一样
     * 2.如果不等于0,则留在原下标+原数组长度的下标
     * <p>
     * 原因:因为数组长度是2的n次幂
     * 因此 hash & table.length 是0的一定是小于数组长度的hash
     * 且hash的二进制的后n+1位在扩容(扩容后数组长度变为2的n+1次幂)后
     * 仍然保持和扩容前一致,因此留在原下标
     * <p>
     * 若数组长度为16,扩容到32,如果hash值有11和21两个
     * 原数组(长度为16即2的4次幂)时:
     * 16--0001 0000
     * 11--0000 1011   下标为11(看后4位)
     * 21--0001 0101   下标为5(看后4位)
     * 扩容后数组(长度为32即2的5次幂)时:
     * 32--001 00000
     * 11--000 01011   下标为11(看后5位)--保持不变
     * 21--000 10101   下标为21(看后5位)--原下标+原数组长度
     * <p>
     * 而不是0的,在数组扩容后的hash的二进制后n+1和扩容前不一致,且相差一个数组长度
     * 因此留在原下标+原数组长度的下标
     */
    private void resize() {
        // 容量为原数组的长度的2倍
        Entry[] newTable = new Entry[table.length << 1];
        // 转移旧数组元素到新数组中
        for (int i = 0; i < table.length; i++) {
            // 元素节点
            Entry p = table[i];
            // 不为空的才进行处理
            if (p != null) {
                // 规律:按 hash & table.length 是否等于0划分链表
                // 保留在原下标的链表指针
                Entry stay = null;
                // 保留在原下标的链表头指针
                Entry stayHead = null;

                // 转移到新下标的链表指针
                Entry trans = null;
                // 转移到新下标的链表头指针
                Entry transHead = null;

                // 开始循环链表
                while (p != null) {
                    // 如果等于0,则还是留在和原下标一样
                    if ((p.hash & table.length) == 0) {
                        // 如果不为空,则stay的next是p
                        if (stay != null) {
                            stay.next = p;
                        } else {// 头节点赋值

                            stayHead = p;
                        }
                        // 将节点转移到新链表上,且移动stay指针到末尾
                        stay = p;

                    } else { // 如果不等于0,则留在原下标+table.length的下标
                        // 如果不为空,则trans的next是p
                        if (trans != null) {
                            trans.next = p;
                        } else {// 头节点赋值
                            transHead = p;
                        }
                        // 将节点转移到新链表上,且移动trans指针到末尾
                        trans = p;
                    }
                    p = p.next;
                }

                // 循环退出后,开始赋值
                if (stay != null) {
                    // 断开和原链表的关联
                    stay.next = null;
                    // 保留在原下标的
                    newTable[i] = stayHead;
                }
                if (trans != null) {
                    // 断开和原链表的关联
                    trans.next = null;
                    // 保留在原下标+原数组长度的
                    newTable[i + table.length] = transHead;
                }
            }
        }

        // 新数组赋值给table
        table = newTable;
        // 更新阈值
        threshold = table.length * 3 / 4;
    }

    /
     * 根据hash和key删除value
     *
     * @param hash hash值
     * @param key  关键字key
     * @return 被删除的值value
     */
    Object remove(int hash, Object key) {
        // 相当于hash%table.length,前提是table.length必须是2的n次幂
        int idx = hash & (table.length - 1);
        // 如果指定下标的数组元素为null,则直接返回null
        if (table[idx] == null) {
            return null;
        }
        // 遍历链表
        Entry p = table[idx];
        // 记录前一个节点,方便删除
        Entry prev = null;
        while (p != null) {
            // 如果找到了,则直接删除
            if (p.key.equals(key)) {
                // 如果前一个节点为null,则删除的是链表头部
                if (prev == null) {
                    // 链表头部改为p的next
                    table[idx] = p.next;
                } else {
                    // 上一个节点的next是待删除节点的next
                    prev.next = p.next;
                }
                // 元素数量-1
                size--;
                return p.value;
            }
            prev = p;
            p = p.next;
        }
        // 如果p为null,则没找到,返回null
        return null;
    }

    /
     * 节点类
     */
    static class Entry {
        // 节点的hash值
        int hash;
        // 节点的key
        Object key;
        // 节点的value
        Object value;
        // 节点的下个节点
        Entry next;

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    /
     * 打印当前hash表的冲突情况,统计每个下标里的元素数量
     * 然后根据元素数量进行分组汇总
     */
    public void testConflict() {
        int[] sum = new int[table.length];
        for (int i = 0; i < table.length; i++) {
            int iSum = 0;
            // 统计链表长度
            Entry p = table[i];
            while (p != null) {
                iSum++;
                p = p.next;
            }
            sum[i] = iSum;
        }
        Map<Integer, Long> collect = Arrays.stream(sum)
                .boxed()
                .collect(Collectors.groupingBy(s -> s, Collectors.counting()));
        System.out.println(collect);
    }

    public static void main(String[] args) {
        MyHashTable table = new MyHashTable();
        String s1 = "abc";
        String s2 = new String("abc");
        // String类型的hashCode方法被重写了
        // 是每个字符的int值*31,如abc的hash计算为
        // ((a + 0*31)*31 + b)*31) + c
        System.out.println(s1.hashCode());
        System.out.println(s2.hashCode());
        System.out.println(table.hash(s1));

        System.out.println("=============================");

//        for (int i = 0; i < 20_0000; i++) {
//            Object obj = new Object();
//            table.put(obj, obj);
//        }
//
//        table.testConflict();

        // MurmurHash
        System.out.println(MurmurHash.hash32(s1));

        // 1.上面的HashTable实现用的是尾插入法,可使用头插入法
        // 但是头插入法在HashMap1.7版本使用,但是在多线程环境下会造成死循环的bug

        // 2.JDK的HashMap采用了将对象的hashCode高低位相互异或的方式减少冲突
        // hash ^ (hash >>> 16)

        // 3.也可以不用2的n次幂作为hash表中数组的容量,如JDK的Hashtable(使用的是质数)

        // 4.JDK8的HashMap在链表过长时转化为红黑树,防止多个冲突的hash造成链表过长导致的性能急剧下降
    }
}

package com.lzlg.study.algorithm.new2023.hash.quiz;

import java.util.HashMap;
import java.util.Map;

/
 * 从字符串中找到第一个不重复的字符,返回下标
 * 字符串只有小写字母
 *
 * @author lzlg
 * 2023/8/4 11:08
 */
public class FindFirstUniqueChar {
    /
     * 从字符串中找到第一个不重复的字符,返回下标
     * 方法1:使用HashMap
     *
     * @param s 字符串
     * @return 字符的下标, 找不到返回-1
     */
    public static int findFistUniqueChar(String s) {
        // 使用HashMap,key是字符,value是字符出现的次数
        Map<Character, Integer> map = new HashMap<>();
        // 遍历字符串的字符数组,并统计字符出现的次数
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            if (map.containsKey(ch)) {
                int count = map.get(ch);
                count++;
                map.put(ch, count);
            } else {
                map.put(ch, 1);
            }
        }
        // 重新遍历一次字符数组,找到第一个不重复的字符下标
        for (int i = 0; i < chars.length; i++) {
            // 如果该字符的出现次数为1,则是第一个不重复的字符
            if (map.get(chars[i]) == 1) {
                // 返回下标
                return i;
            }
        }
        // 找不到返回-1
        return -1;
    }

    /
     * 从字符串中找到第一个不重复的字符,返回下标
     * 方法1:使用26长度的int数组
     *
     * @param s 字符串
     * @return 字符的下标, 找不到返回-1
     */
    public static int findFistUniqueCharArray(String s) {
        // 创建统计字符出现次数的长度为26的int数组
        int[] array = new int[26];
        // 遍历字符串的字符数组,并统计字符出现的次数
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            array[ch - 97]++;
        }
        // 重新遍历一次字符数组,找到第一个不重复的字符下标
        for (int i = 0; i < chars.length; i++) {
            // 如果该字符的出现次数为1,则是第一个不重复的字符
            if (array[chars[i] - 97] == 1) {
                // 返回下标
                return i;
            }
        }
        // 找不到返回-1
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(findFistUniqueChar("leetcodel"));
        System.out.println(findFistUniqueCharArray("leetcodel"));
    }
}

package com.lzlg.study.algorithm.new2023.hash.quiz;

import java.util.HashSet;

/
 * 找到不重复的数字
 * 给定一个数组,重复的数字只有两个,不重复的只有一个
 * 找到不重复的数字
 *
 * @author lzlg
 * 2023/8/3 16:42
 */
public class FindNotRepeatNumber {
    /
     * 方法1:使用HashSet
     * 使用HashSet的add方法添加元素,如果添加成功,则返回true
     * 如果是替换,则返回false,此时需要把元素从HashSet中移出
     *
     * @param nums 数组
     * @return 不重复的元素
     */
    public static int findNotRepeatNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        // 遍历数组
        for (int num : nums) {
            // 如果添加不成功,则删除该元素
            if (!set.add(num)) {
                set.remove(num);
            }
        }
        // 遗留下来的元素(只有一个)返回
        return set.toArray(new Integer[0])[0];
    }

    /
     * 方法2:使用异或
     * 两个相同的数字的异或结果为0
     * 而0与任何一个数字的异或结果是该数字
     *
     * @param nums 数组
     * @return 不重复的元素
     */
    public static int findNotRepeatNumber2(int[] nums) {
        int num = nums[0];
        for (int i = 1; i < nums.length; i++) {
            num = num ^ nums[i];
        }
        return num;
    }


    public static void main(String[] args) {
        System.out.println(findNotRepeatNumber2(new int[]{1, 2, 3, 2, 3}));
        System.out.println(findNotRepeatNumber2(new int[]{4, 1, 2, 1, 2}));
    }
}

package com.lzlg.study.algorithm.new2023.hash.quiz;

import java.util.HashMap;
import java.util.Map;

/
 * 判断是否有重复的元素
 *
 * @author lzlg
 * 2023/8/3 15:58
 */
public class FindRepeatNumber {
    /
     * 判断是否有重复的元素
     *
     * @param nums 数组
     * @return 结果, 有返回true
     */
    public static boolean findRepeat(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                return true;
            }
            map.put(num, num);
        }
        return false;
    }

    /
     * 判断是否有重复的元素,更快速
     *
     * @param nums 数组
     * @return 结果, 有返回true
     */
    public static boolean fastFindRepeat(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        final Integer value = 1;
        for (int num : nums) {
            // 因为map的put方法如果是新增的话是返回null,如果是替换的话,返回原来的值
            // 这样写比上面的少了一个containsKey的判断,更加快速
            if (map.put(num, value) != null) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(fastFindRepeat(new int[]{1, 2, 3, 1}));
        System.out.println(fastFindRepeat(new int[]{1, 2, 3, 4}));
    }
}

package com.lzlg.study.algorithm.new2023.hash.quiz;

import java.util.*;

/
 * 分组字母异位词,如abc和cba是一组字母异位词
 * 给定的字符串都是小写字母
 *
 * @author lzlg
 * 2023/8/3 15:28
 */
public class GroupAnagrams {

    /
     * 通过给定的字符串数字,把此数组按照字母异位词进行分组
     * 方式1:通过排序和HashMap来解决
     * 方式2:因为只有小写字母,可使用长度为26的int数组作为HashMap的key,需重写equals和hashCode方法
     * 方式3:因为只有小写字母,将这些小写字母的int值之和,作为HashMap的key
     *
     * @param strings 字符串数组
     * @return 分组结果
     */
    public static List<List<String>> groupAnagrams1(String[] strings) {
        // HashMap表
        Map<String, List<String>> map = new HashMap<>();
        // 遍历字符串数组
        for (String str : strings) {
            // 获取字符串的字符数组
            char[] chars = str.toCharArray();
            // 进行排序
            Arrays.sort(chars);
            // 排序后的新字符串作为key
            String key = new String(chars);
            // 放入map中
            List<String> list = map.computeIfAbsent(key, s -> new ArrayList<>());
            // 添加原字符串到list中
            list.add(str);
        }
        return new ArrayList<>(map.values());
    }

    /
     * 方式2,使用长度为26的int数组存储
     *
     * @param strings 字符串数组
     * @return 分组结果
     */
    public static List<List<String>> groupAnagrams2(String[] strings) {
        // HashMap表
        Map<ArrayKey, List<String>> map = new HashMap<>();
        // 遍历字符串数组
        for (String str : strings) {
            // 创建ArrayKey
            ArrayKey key = new ArrayKey(str);
            // 放入map中
            List<String> list = map.computeIfAbsent(key, s -> new ArrayList<>());
            // 添加原字符串到list中
            list.add(str);
        }
        return new ArrayList<>(map.values());
    }

    /
     * 方式2的key,因此需要重写equals和hashCode方法
     */
    static class ArrayKey {

        int[] chars;

        public ArrayKey(String str) {
            this.chars = new int[26];
            for (int i = 0; i < str.length(); i++) {
                // 因为都是小写字母,而字符a的int值为97,因此下标为ch-97
                char ch = str.charAt(i);
                chars[ch - 97]++;
            }
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ArrayKey arrayKey = (ArrayKey) o;
            return Arrays.equals(chars, arrayKey.chars);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(chars);
        }
    }

    public static void main(String[] args) {
        String[] strings = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(groupAnagrams2(strings));
    }
}

package com.lzlg.study.algorithm.new2023.hash.quiz;

import java.util.Arrays;

/
 * 判断是否是字母异位词
 * 字符串都是由小写字母组成
 *
 * @author lzlg
 * 2023/8/4 10:50
 */
public class JudgeIsAnagrams {
    /
     * 判断两个字符串是否是字母异位词
     * 方法1:把字符串的字符数组排序后比较
     *
     * @param s 字符串s
     * @param t 字符串t
     * @return 结果, 是返回true
     */
    public static boolean isAnagrams(String s, String t) {
        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }
        // 转化为字符数组
        char[] sChars = s.toCharArray();
        // 排序
        Arrays.sort(sChars);

        // 转化为字符数组
        char[] tChars = t.toCharArray();
        // 排序
        Arrays.sort(tChars);

        // 开始比较,可使用Arrays.equals的API
        for (int i = 0; i < sChars.length; i++) {
            // 如果有一个字符不相等,则返回false
            if (sChars[i] != tChars[i]) {
                return false;
            }
        }
        // 循环过后,则是字母异位词
        return true;
    }

    /
     * 判断两个字符串是否是字母异位词
     * 方法2:因为只有小写字母,可通过创建长度为26的int数组来比较
     *
     * @param s 字符串s
     * @param t 字符串t
     * @return 结果, 是返回true
     */
    public static boolean isAnagramsArray(String s, String t) {
        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }
        // 数组长度为26
        final int LEN = 26;

        // 创建字符串s对应的int数组
        int[] sa = new int[LEN];
        // 字符串s转化为字符数组
        char[] sChars = s.toCharArray();
        // 遍历字符数组
        for (char ch : sChars) {
            // 将相应的下标增加
            sa[ch - 97]++;
        }

        // 创建字符串t对应的int数组
        int[] ta = new int[LEN];
        // 字符串t转化为字符数组
        char[] tChars = t.toCharArray();
        // 遍历字符数组
        for (char ch : tChars) {
            // 将相应的下标增加
            ta[ch - 97]++;
        }

        // 最后比较两个int数组
        for (int i = 0; i < LEN; i++) {
            if (sa[i] != ta[i]) {
                return false;
            }
        }
        // 可使用Arrays.equals的API
        return true;
    }

    public static void main(String[] args) {
        String s = "anagram";
        String t = "nagrama";
        System.out.println(isAnagrams(s, t));
        System.out.println(isAnagramsArray(s, t));
    }
}

package com.lzlg.study.algorithm.new2023.hash.quiz;

import java.util.HashMap;
import java.util.Map;

/
 * 最长无重复字符子串的长度
 * 如字符串是: abcabcca
 * 则最长的没有重复字符的子串是: abc, bca, cab
 *
 * @author lzlg
 * 2023/8/3 12:09
 */
public class LongestSubString {

    /
     * 获取字符串的最长无重复字符子串的长度
     * 使用HashMap和两个指针
     * 一个begin指针指向不重复字符的最大下标
     * 一个end指针遍历字符串的字符
     *
     * @param str 字符串
     * @return 长度
     */
    public static int lengthLongestSubString(String str) {
        // 使用HashMap,key是字符,value是字符所在字符串的最大位置下标
        Map<Character, Integer> map = new HashMap<>();
        // 返回的最大子串长度
        int maxLength = 0;
        // 开始指针,当遇到重复的时候移动
        int begin = 0;
        // 结束指针,遍历字符串字符使用
        for (int end = 0; end < str.length(); end++) {
            // 字符串中单个字符
            char ch = str.charAt(end);
            // 如果map中有此字符,则更新begin,且更新此字符的最新下标
            if (map.containsKey(ch)) {
                // 记录begin的最大下标,防止往回走
                begin = Integer.max(begin, map.get(ch) + 1);
                // 更新此字符的最新下标
                map.put(ch, end);
            } else {
                // 如果map中没有,则放入
                map.put(ch, end);
            }
            // 打印无重复字符的子串
            System.out.println(str.substring(begin, end + 1));
            // 记录最大的子串长度
            maxLength = Integer.max(maxLength, end - begin + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String str = "abcabcca";
        System.out.println(lengthLongestSubString(str));
    }
}

package com.lzlg.study.algorithm.new2023.hash.quiz;

import java.util.*;

/
 * 找到一段文字中出现次数最多的单词
 * 题目只有一个唯一答案
 *
 * @author lzlg
 * 2023/8/4 11:29
 */
public class MostCommonWord {
    /
     * 找到一段文字中出现次数最多的单词
     *
     * @param paragraph 段落
     * @param banned    禁用词
     * @return 单词, 没有返回null
     */
    public static String findMostCommonWord(String paragraph, String[] banned) {
        // 根据不是字母的进行切分为单词字符串数组
        String[] words = paragraph.toLowerCase().split("[^a-z]+");
        // 使用Set封装禁用词词组
        Set<String> banSet = new HashSet<>(Arrays.asList(banned));
        // 使用HashMap统计单词的出现次数,key是单词,value是单词的出现次数
        Map<String, Integer> map = new HashMap<>();
        // 使用HashMap统计单词的出现次数
        for (String word : words) {
            // 禁用词里不包括该单词,才加入到map中
            if (!banSet.contains(word)) {
                // 使用word作为key,如果v值为null,则v值为1,否则为更新v值为原来的v值+1
                map.compute(word, (k, v) -> v == null ? 1 : v + 1);
            }

        }
        // 找出出现次数最多的单词
        // 根据value值比较找到最大的Map.Entry
        Optional<Map.Entry<String, Integer>> optional = map.entrySet().stream().max(Map.Entry.comparingByValue());
        // 从optional中获取entry的key,如果没有则返回null
        return optional.map(Map.Entry::getKey).orElse(null);
    }

    /
     * 找到一段文字中出现次数最多的单词,效率高的版本
     *
     * @param paragraph 段落
     * @param banned    禁用词
     * @return 单词, 没有返回null
     */
    public static String fastFindMostCommonWord(String paragraph, String[] banned) {
        // 自己遍历段落的字符,拼接为单词并加入到map集合中
        char[] chars = paragraph.trim().toLowerCase().toCharArray();
        // 使用Set封装禁用词词组
        Set<String> banSet = new HashSet<>(Arrays.asList(banned));
        // 使用HashMap统计单词的出现次数,key是单词,value是单词的出现次数
        Map<String, Integer> map = new HashMap<>();

        // 拼接单词使用的
        StringBuilder sb = new StringBuilder();
        // 遍历字符数组
        for (char ch : chars) {
            // 如果是小写字母范围的,则进行拼接
            if (ch >= 'a' && ch <= 'z') {
                sb.append(ch);
            } else {
                // 如果遇到不是小写字母的,则将以前拼接的转化为单词
                String key = sb.toString();
                if (!banSet.contains(key)) {
                    map.compute(key, (k, v) -> v == null ? 1 : v + 1);
                }
                // 重置拼接字符使用的sb的长度
                sb.setLength(0);
            }
        }
        // 防止段落只有一个单词造成的问题
        if (sb.length() > 0) {
            // 把最后一个单词放入map中
            String key = sb.toString();
            if (!banSet.contains(key)) {
                map.compute(key, (k, v) -> v == null ? 1 : v + 1);
            }
        }

        // 统计完成后,自己实现找到出现次数最多的单词
        // 找到次数最多的
        int max = 0;
        // 找到次数最多的key
        String maxKey = null;
        // 遍历map集合
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            int value = entry.getValue();
            // 如果有比max大的,则进行记录
            if (value > max) {
                max = value;
                maxKey = entry.getKey();
            }
        }
        return maxKey;
    }

    public static void main(String[] args) {
        // 段落
        String paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.";
        // 禁用词
        String[] banned = {"hit"};
        System.out.println(findMostCommonWord(paragraph, banned));

        paragraph = "Bob";
        System.out.println(findMostCommonWord(paragraph, banned));
    }
}

package com.lzlg.study.algorithm.new2023.hash.quiz;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/
 * 两数之和
 * <p>
 * 给定一个数组和一个目标值
 * 找到数组中两个数字之和等于目标值的下标数组,如
 * 数组: [3, 2, 6, 7, 1]
 * 目标值: 8
 * 返回结果是: [1, 2]
 * 给定的数据必定有一个结果
 *
 * @author lzlg
 * 2023/8/3 11:41
 */
public class TwoNumberSum {

    /
     * 两数之和
     *
     * @param nums   数组
     * @param target 目标值
     * @return 两个数下标的数组
     */
    public static int[] twoNumberSum(int[] nums, int target) {
        // 使用HashMap解决,key是数组中数字,value是下标
        Map<Integer, Integer> map = new HashMap<>();
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 数组中的数字
            int x = nums[i];
            // 目标值和数字的相差值
            int y = target - x;
            // 如果map中有相应的相差值,则找到了,直接返回
            if (map.containsKey(y)) {
                // 返回的是下标
                return new int[]{map.get(y), i};
            } else {
                // 如果没有找到,则继续添加到map中
                map.put(x, i);
            }
        }
        return null;
    }


    public static void main(String[] args) {
        int[] nums = {3, 2, 6, 7, 1};
        int target = 9;
        System.out.println(Arrays.toString(twoNumberSum(nums, target)));
    }
}