[Leetcode][第1002题][JAVA][查找常用字符][计数][HashMap]

爱被打了一巴掌 2022-12-15 02:24 102阅读 0赞

#### 【问题描述】\[简单\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

###### 计数法 ######

##### 1. minfreq存放最终重复字母的个数 freq存放每次遍历字符串的字母个数 #####

##### 2. minfreq初始化最大值，每遍历一个字符串后，比较minfreq\[i\]、freq\[i\]的大小，minfreq\[i\]更新为两者的最小值。 #####

##### 3. 根据minfreq，输出答案 #####

**时间复杂度：O(N^2) 空间复杂度：O(N)**

class Solution { 
        public List<String> commonChars(String[] A) { 
            int[] minfreq = new int[26];
            Arrays.fill(minfreq, Integer.MAX_VALUE);
            for (String word: A) { 
                int[] freq = new int[26];
                int length = word.length();
                for (int i = 0; i < length; ++i) { 
                    char ch = word.charAt(i);
                    ++freq[ch - 'a'];
                }
                for (int i = 0; i < 26; ++i) { 
                    minfreq[i] = Math.min(minfreq[i], freq[i]);
                }
            }
    
            List<String> ans = new ArrayList<String>();
            for (int i = 0; i < 26; ++i) { 
                for (int j = 0; j < minfreq[i]; ++j) { 
                    ans.add(String.valueOf((char) (i + 'a')));
                }
            }
            return ans;
        }
    }

###### HashMap思路 ######

public List<String> commonChars(String[] A) { 
            Map<Character, Integer> map = new HashMap<>();
            if (A.length == 0)
                return null;
            for (Character c : A[0].toCharArray())
                map.put(c, map.getOrDefault(c, 0) + 1);
            for (int i = 1; i < A.length; i++) { 
                String str = A[i];
                Map<Character, Integer> map2 = new HashMap<>();
                for (Character c : str.toCharArray()) { 
                    if (map.containsKey(c)) { 
                        map2.put(c, Math.min(map2.getOrDefault(c, 0) + 1, map.get(c)));
                    }
                }
                map = map2;
            }
            List<String> ans = new ArrayList<>();
            for (Character c : map.keySet()) { 
                int num = map.get(c);
                for (int i = 0; i < num; i++) { 
                    ans.add(String.valueOf(c));
                }
            }
            return ans;

#### 【总结】 ####

###### 1. Java字母题目细节 ######

**数组赋值相同的值**  
Arrays.fill(minfreq, Integer.MAX\_VALUE);  
**char int 互转**  
char转 int ch - ‘a’  
int 转char (char) (i + ‘a’)  
**int 转char转String**  
String.valueOf((char) (i + ‘a’))；

###### 2.简单题一点都不简单 ，细节决定成败 ######

参考链接：https://leetcode-cn.com/problems/find-common-characters/solution/cha-zhao-chang-yong-zi-fu-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b48eb1975c5a41fd83238d14b0a179f7.png