力扣刷题日记——哈希

有效的字母异位词

定义一个数组叫做record用来上记录字符串s里字符出现的次数。遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，遍历字符串t的时候 只需要-1操作即可，那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

class Solution {
    public boolean isAnagram(String s, String t) {
    int[] recond=new int [26];
    for(char c : s.toCharArray()){
        recond[c-'a']+=1;
    } 
    for(char d : t.toCharArray()){
        recond[d-'a']-=1;
    
    }
    for(int i : recond){
        if(i!=0){
            return false;
        }
    }                    
    return true;                                                   
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

赎金信

这题与上一题差不多因为题目所只有小写字母，那可以采用空间换取时间的哈希策略， 用一个长度为26的数组还记录magazine里字母出现的次数。然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。
依然是数组在哈希法中的应用。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
            int[] recond=new int [26];

            for(char c : magazine.toCharArray()){
                recond[c-'a']+=1;
            }
            for( char c: ransomNote.toCharArray()){
                recond[c-'a']-=1;
            }
          
            for(int i: recond){
             if(i<0){
                 return false;
             }
             
            }
            return true;
         
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

字母异位词分组

用哈希表的方法来做，用map来存储字母相同的字符串。
用每一个单词排序后的结果来作为key值，然后将相同字母的单词放入同一key中。
toCharArray（）是将字符串转换为字符串数组，即把字符串存到数组中
String.valueOf()把括号中的类型转换为string型

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, ArrayList<String>> map = new HashMap<>();//哈希表存
        for (int i = 0; i < strs.length ; i++) {
            char[] chars = strs[i].toCharArray();//将strs转换为字符串数组
            Arrays.sort(chars);//按a-z的顺序进行排序
            String key = String.valueOf(chars);//将char型转换为string型
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());//用排序后的结果来作为key值，因为相同字母排序后结果相同
            }
            map.get(key).add(strs[i]);//.get（）方法是获取key值对应的value 然后再add当前字符串
        }
        return new ArrayList<>(map.values());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

这题可以用滑动窗口的思想，首先把p字符串转换为字符串数组，统计字母出现次数，
然后创一个list来存答案，然后这个滑动窗口的长度就对应了p字符串的长度，然后当长度相同时就进行判断，若两个数组相同则返回l的下标（即数组起始下标）。
charAt(i)就是返回当前字符串的第i个字符
stringbuffer就是有操作方法的字符串

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
            int []s1=new int [26];
            int []p1=new int [26];
            for(int i=0;i<p.length();i++){
                p1[p.charAt(i)-'a']+=1;
            }
            List<Integer> res = new ArrayList<>();
            for(int l=0,r=0;r<s.length();r++){
                s1[s.charAt(r)-'a']+=1;
                if(r-l+1>p.length())s1[s.charAt(l++)-'a']--;
                if(r-l+1==p.length()){
                    if(isSame(s1,p1)){
                    res.add(l);
                    }
                }
            }
            return res;
    }
  boolean isSame(int[]a,int[]b){
      for(int i=0;i<a.length;i++){
          if(a[i]!=b[i]){
              return false;
          }
      }
      return true;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28