关于hash表的一些练习题

1.前言

我在前文已经讲述了,HashTable的代码实现,这次来讲讲如何实现hash算法来写一些练习题吧

对于hash表存在的优点就是:快速搜索,高效插入和删除和快速搜索

2.习题练习

2.1返回不重复子串的最大长度

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子字符串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

输入: s = ""
输出: 0

1.思路分析:

1.使用双指针实现,定义一个begin表示最大索引的起始位置，end记录结束位置

2.创建一个hash表键存数据,值存数据的索引

3.取出end下标的元素来判断hash表有没有,没有的话连同它的索引添加进去,如果遇到重复的调整begin为重复元素第一次出现的位置 + 1,然后重复元素的索引更新

4.在你end每走一次都取出substring(start,end + 1)这个就是每一个子串,获取出他们的最大长度即可

2.代码实现

 public int lengthOfLongSubstring(String s) {
        HashMap map = new HashMap<>();
        int begin = 0;//记录起始位置
        int maxLength = 0;//最大长度
        for (int end = 0; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (map.containsKey(ch)) {//重新调整begin
                //防止begin往后走(begin前面的元素与其重复不处理  )
                begin = Math.max(map.get(ch) + 1,begin);
            }
            //重复更新   不重复添加
            map.put(ch, end);
            maxLength = Math.max(maxLength, end - begin + 1);
        }
        return maxLength;
    }

 2.2 出现单词次数最多的单词

注意本题的要求: 1 . 答案是唯一的   2.并且存在禁入词

1.思路分析 

    1.将大串进行切割成为多个单词

    2.将单词添加到map集合中，本身是key，出现次数是value,并且避免禁用词加入

    3.在map集合找到value最大的,返回它对应的key即可

    4.在每次添加到hash表的时候,判断是否为禁用词,即可舍弃禁用词

 2.代码实现

        1.普通代码

public String mostCommonWord(String s, String[] banned){
        String[] s1 = s.toLowerCase().split("[^a-zA-Z]+");//排除单词字符就是分隔符
        HashMap map = new HashMap();
 
        //因为需要用到contains()方法所以需要转换为set集合
        Set set = Arrays.stream(banned).collect(Collectors.toSet());
          for (String s2 : s1) {
                if (map.containsKey(s2)){
                    map.put(s2,1);
                }else {
                    Integer value = map.get(s2);
                    value++;
                    map.put(s2,value);
                }
            }
        Optional> max = map.entrySet().stream()
                .max(Map.Entry.comparingByValue());
        return max.map(Map.Entry::getKey).orElse(null);
        //这样也可以
 //            Integer value = map.get(s2);
//            if (value == null){
//                value = 0;
//            }
//            map.put(s2,value + 1);

        2.stream流进行优化

public String mostCommonWord(String s, String[] banned){
        String[] s1 = s.toLowerCase().split("[^a-zA-Z]+");//排除单词字符就是分隔符
        HashMap map = new HashMap();
 
        //因为需要用到contains()方法所以需要转换为set集合
        Set set = Arrays.stream(banned).collect(Collectors.toSet());
        for (String s2 : s1) {
 
//            //lambda表达式实现
            if (!set.contains(s2)) map.compute(s2, ( k, v ) -> v == null ? 1 : v + 1);
        }
 
        Optional> max = map.entrySet().stream()
                .max(Map.Entry.comparingByValue());
        return max.map(Map.Entry::getKey).orElse(null);

        3.优化分析

stream流和正则表达式会时间复杂度高

这个实现不使用 Stream 流和正则表达式，而是逐个字符检查输入字符串 s 的每个字符。

一旦遇到非字母字符，我们将当前的单词（由连续的字母字符组成）检查是否在 bannedSet 中，

如果不在，则更新该单词的出现次数并比较是否为最常见的单词。

通过避免使用正则表达式的 split() 方法以及通过字符级别的处理，可以降低时间复杂度。

 然而，这种实现方式可能会稍微增加代码的复杂性和可读性，因此在具体情况下需要根据实际需求进行权衡。

 public String mostCommonWord2(String s, String[] banned) {
        s = s.toLowerCase();
        StringBuilder word = new StringBuilder();
        HashMap map = new HashMap<>();
 
        Set bannedSet = new HashSet<>(Arrays.asList(banned));
 
        int maxCount = 0;
        String mostCommonWord = "";
 
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isLetter(c)) {
                word.append(c);
                if (i != s.length() - 1) {
                    continue;
                }
            }
 
            if (word.length() > 0) {
                String currentWord = word.toString();
                if (!bannedSet.contains(currentWord)) {
                    int count = map.getOrDefault(currentWord, 0) + 1;
                    map.put(currentWord, count);
                    if (count > maxCount) {
                        maxCount = count;
                        mostCommonWord = currentWord;
                    }
                }
                word = new StringBuilder();//也可以不重新创建  用word.setLength(0)来清空
            }
        }
 
        return mostCommonWord;
    }