【LeetCode】Day96-第一个唯一字符＆赎金信＆字母异位词

1.字符串中的第一个唯一字符

387. 字符串中的第一个唯一字符【简单】

题解

使用哈希表存储频数，这里哈希表用HashMap

class Solution {
    
    public int firstUniqChar(String s) {
    
        Map<Character,Integer>hashMap=new HashMap<>();
        for(int i=0;i<s.length();i++){
    
            char c=s.charAt(i);
            if(hashMap.containsKey(c)){
    
                int count=hashMap.get(c);
                hashMap.put(c,count+1);
            }
            else
                hashMap.put(c,1);
        }
        for(int i=0;i<s.length();i++){
    
            if(hashMap.get(s.charAt(i))==1)
                return i;
        }
        return -1;
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(\mid \Sigma \mid )$，其中 $\Sigma$ 是字符集

2.赎金信

383. 赎金信【简单】

题解

使用哈希表存储频数，这里哈希表用数组，运行时间更短

class Solution {
    
    public boolean canConstruct(String ransomNote, String magazine) {
    
        int[] cnt=new int[26];
        for(int i=0;i<magazine.length();i++){
    
            cnt[magazine.charAt(i)-'a']++;
        }
            
        for(int i=0;i<ransomNote.length();i++){
    
            char c=ransomNote.charAt(i);
            if(cnt[c-'a']<=0)
                return false;
            cnt[c-'a']--;
        }
        return true;
    }
}

时间复杂度：$O(m+n)$

空间复杂度：$O(\mid \Sigma \mid )$，其中 $\Sigma$ 是字符集

3.有效的字母异位词

242. 有效的字母异位词【简单】

题解

哈希表

class Solution {
    
    public boolean isAnagram(String s, String t) {
    
        int m=s.length(),n=t.length();
        if(m!=n)
            return false;
        int[] snt=new int[26];
        for(int i=0;i<m;i++)
            snt[s.charAt(i)-'a']++;
        for(int i=0;i<n;i++){
    
            snt[t.charAt(i)-'a']--;
            if(snt[t.charAt(i)-'a']<0)
                return false;   
        }
        return true;
    }
}

注意：在进阶中提到“如果输入字符串包含 unicode 字符怎么办”？
这种情况就不可以用数组表示哈希表了，而只能用HashMap！

时间复杂度：$O(n)$

空间复杂度：$O(\mid \Sigma \mid )$，其中 $\Sigma$ 是字符集

排序

t 是 s 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 s 和 t 分别排序，看排序后的字符串是否相等即可判断。

重点记一下字符串转数组、排序、判等的操作API

class Solution {
    
    public boolean isAnagram(String s, String t) {
    
        int m=s.length(),n=t.length();
        if(m!=n)
            return false;
        char[] str1=s.toCharArray();
        char[] str2=t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1,str2);
    }
}

时间复杂度：$O(nlogn)$，排序所需

空间复杂度：$O(logn)$，排序所需