0


【LeetCode】 哈希表的使用

坚持啊!给自己自由!

当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法

但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。

请添加图片描述

242. 有效的字母异位词

在这里插入图片描述

因为string 只包含小写字母 ,所以可以创建数组来存储各个字母,再循环判断

classSolution{publicbooleanisAnagram(String s,String t){int[]num1 =newint[128];int[]num2 =newint[128];for(int i  =0; i <s.length(); i++){char c= s.charAt(i);
            num1[c]++;}for(int i =0; i< t.length(); i++){char c = t.charAt(i);
            num2[c]++;}for(int i =0; i<128;i++){if(num1[i]!= num2[i])returnfalse;}returntrue;}

383. 赎金信

在这里插入图片描述
改进版,只用一个数组,通过对这一个数组加减判断
小写字母是128以内的数字,主要magazine里字母存在,就让相应的下标的值加一,
在到ransomNote匹配,只要是ransomNote里的字母,就让相应下标的值减一,只要存在
哪个下标的值大于0,说明magazine里存在ransomNote没有的字母,那就return false

classSolution{publicbooleancanConstruct(String ransomNote,String magazine){int num[]=newint[128];for(char  i : ransomNote.toCharArray()){
            num[i]++;}for(char i : magazine.toCharArray()){
            num[i]--;}for(int i : num ){if(i >0)returnfalse;}returntrue;}}

在这里插入图片描述

49. 字母异位词分组

在这里插入图片描述

方法一:字母排序

理解字母异位词,具有相同的字母特征,所以可以利用散列表map来存储,键为一组异位字母词的标志, 值为一组字母异位词列表

1.首先,遍历每一个的string,得到每一个字符串所在组的字母异位词的标志

2将当前字符串加入该组字母异位词的列表中,遍历全部字符串之后,哈希表中的每一键值对即为一组字母异位词
这道题运用了好多集合的API,首先是定义上的套娃,map<String,List>

再着是运用字符串的toCharArray();,toCharArray() 方法将字符串转换为字符数组。

再使用Arrays.sort(),排序 是Arrays 不是Array,(这里我踩了坑,呜呜呜)

接着是,再将排序好的字符数组 创建成 字符串

下一步是,运用map.getOrDefault 获取 map的值 也就是List

说明一下map.getOrDefault方法:

Java中map.getOrDefault()方法的使用

Map.getOrDefault(Object key, V defaultValue)方法的作用是:

当Map集合中有这个key时,就使用这个key值;

如果没有就使用默认值defaultValue。

HashMap<String,String> map =newHashMap<>();
    map.put("name","cookie");
    map.put("age","18");
    map.put("sex","女");String name = map.getOrDefault("name","random");System.out.println(name);// cookie,map中存在name,获得name对应的valueint score = map.getOrDefault("score",80);System.out.println(score);// 80,map中不存在score,使用默认值80

了解了map.getOrDefault()后,我们就知道我们得到了 一个List ,这个List有两种情况,一种是map 里已经有key存在,那么直接获取key所对应的value值,不然就直接返回 新的ArrayList ,泛型为String。

接着,把一开始没有排序过的字符串加入List里,运用了List,add()的api

再把List放进map里,用的是map.put()的API;

最后一步是,退出循环后,返回ArrayList<List>(map.values());,这句话的意思是 创建ArrayList数组,类型是List,他的值为map.values值,map.values()取出来的值就是value,没有key.

classSolution{publicList<List<String>>groupAnagrams(String[] strs){Map<String,List<String>>   map =newHashMap<String,List<String>>();for(String str: strs){char[] c = str.toCharArray();Arrays.sort(c);String key =newString(c);//构造单词的字符排序,作为键List<String>List= map.getOrDefault(key,newArrayList<String>());List.add(str);
            map.put(key,List);//将单词加入散列表中}returnnewArrayList<List<String>>(map.values());}}

第二种方法:

改变map的key值,由字母和字母出现的次数组成

classSolution{publicList<List<String>>groupAnagrams(String[] strs){Map<String,List<String>> map =newHashMap<String,List<String>>();for(String str :strs){int[]num =newint[26];for(int i =0; i< str.length();i++){//统计字符出现次数
                num[str.charAt(i)-'a']++;}StringBuffer stringBuffer =newStringBuffer();for(int i =0; i <26;i++){if(num[i]>0){
                    stringBuffer.append((char)('a'+i));
                    stringBuffer.append(num[i]);//创建键值}}String s =newString(stringBuffer);List<String> list = map.getOrDefault(s,newArrayList<String>());
            list.add(str);//将具有相同特征的字母放在一起
            map.put(s,list);}returnnewArrayList<List<String>>(map.values());}}

438. 找到字符串中所有字母异位词

在这里插入图片描述
呜呜呜,超时了!
在这里插入图片描述

快慢指针法:

如果遇到没有的字符,high原地等待;low++遍历到这个字符后(即low比high多1后),下一次high也会消耗掉这个没有的字符

classSolution{publicList<Integer>findAnagrams(String s,String p){int num1[]=newint[128];List<Integer> list =newArrayList<>();for(char i: p.toCharArray()) num1[i]++;int low =0,high =0;while(high <s.length()){if(num1[s.charAt(high)]>0){
                     num1[s.charAt(high++)]--;if(high -low == p.length())  list.add(low);}else{
                     num1[s.charAt(low++)]++;}}return list;}}

请添加图片描述

标签: leetcode 散列表 java

本文转载自: https://blog.csdn.net/weixin_61203642/article/details/124916796
版权归原作者 七仔Ace 所有, 如有侵权,请联系我们删除。

“【LeetCode】 哈希表的使用”的评论:

还没有评论