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<Character, Integer> 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<String,Integer> map = new HashMap();//因为需要用到contains()方法所以需要转换为set集合Set<String> 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<Map.Entry<String, Integer>> 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<String,Integer> map = new HashMap();//因为需要用到contains()方法所以需要转换为set集合Set<String> 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<Map.Entry<String, Integer>> 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<String, Integer> map = new HashMap<>();Set<String> 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;}