字符串中第一個唯一字符

題目地址：387. 字符串中的第一個唯一字符 - 力扣（LeetCode） (leetcode-cn.com)

WhfGHs.png

思路：

• 使用哈希表存儲值，遍歷字符數組，如果找到最先相同的字母，就返回索引即可
• 這個方法比較占空間，第二種方法使用數組！

哈希表

class Solution {
    public int firstUniqChar(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            map.put(ch,map.getOrDefault(ch,0)+1);
        }
        for (int i = 0; i < chars.length; i++) {
            if(map.get(chars[i])==1){
                return i;
            }
        }
        return -1;
    }
}

復雜度分析

• 時間復雜度：O(n)O(n)，其中 nn 是字符串s的長度。我們需要進行兩次遍歷。

• 空間復雜度：O(∣Σ∣)，其中 Σ 是字符集，在本題中 s只包含小寫字母，因此26∣Σ∣≤26。我們需要 O(∣Σ∣) 的空間存儲哈希映射

數組

能用數組就用數組，這樣更快，學到了！

class Solution {
    public int firstUniqChar(String s) {
         int[] arr=new int[26];
        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i)-'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if(arr[s.charAt(i)-'a']==1){
                return i;
            }
        }
        return -1;
    }
}

贖金信

題目地址：383. 贖金信 - 力扣（LeetCode） (leetcode-cn.com)

WhTlvV.png

思路

• 記錄雜志出現的字符串
• 在贖金信中查找字符串，找到就減1，找不到就返回false

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 首先記錄雜志出現的字符串
        int[] arr=new int[26];
        int r=ransomNote.length();
        int m=magazine.length();
        for(int i=0;i<m;i++){
            arr[magazine.charAt(i)-'a']++;
        }
        // 在贖金信中查找字符串，找到減1，找不到就返回false
        for(int i=0;i<r;i++){
            if(arr[ransomNote.charAt(i)-'a']>0){
                arr[ransomNote.charAt(i)-'a']--;
            }else{
                return false;
            }
        }
        return true;
    }
}

復雜度分析

• 空間復雜度O(n²)
• 時間復雜度O(1)

同樣可以采用數組法！

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] chars = new char[26];
        for (char c : magazine.toCharArray()) {
            chars[c-'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            if(chars[c-'a']--==0){
                return false;
            }
        }
        return true;
    }
}

查找常用字符

題目地址：1002. 查找常用字符 - 力扣（LeetCode） (leetcode-cn.com)

W45Zod.png

思路：

• 這題是參考大神的方法查找常用字符 (qq.com)
• 題目看了半天和評論才看懂

就是26個小寫字符中有字符 在所有字符串里都出現的話，就輸出，重復的也算

• 特此記錄下大神代碼，見到與大神的差距，還是要多寫，多練??????

class Solution {
    public List<String> commonChars(String[] words) {
        ArrayList<String> result = new ArrayList<>();
        if (words.length == 0) {
            return result;
        }
        // 統計所有字符串里字符出現的最小頻率
        int[] hash = new int[26];
        for (int i = 0; i < words[0].length(); i++) {
            hash[words[0].charAt(i) - 'a']++;
        }
        // 統計除第一個字符串外字符出現的頻率
        for (int i = 0; i < words.length; i++) {
            int[] hashOtherStr = new int[26];
            for (int j = 0; j < words[i].length(); j++) {
                hashOtherStr[words[i].charAt(j) - 'a']++;
            }
            // 更新hash，保證hash里統計26個字符在所有字符串里出現的最小次數
            for (int k = 0; k < 26; k++) {
                hash[k] = Math.min(hash[k], hashOtherStr[k]);
            }
        }
        // 將hash統計的字符次數，轉成輸出形式
        for (int i = 0; i < 26; i++) {
            while (hash[i] != 0) {
                //多個重復的字符
                char c = (char) (i + 'a');
                result.add(String.valueOf(c));
                hash[i]--;
            }
        }
        return result;
    }
}

代碼均由力扣編譯器，提交通過，描述編寫不當地方還請大家評論區(qū)指出??！