脚撕LeetCode(1002)Easy
题目地址：https://leetcode-cn.com/problems/find-common-characters/
给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。 例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。 你可以按任意顺序返回答案。 示例 1： 输入：["bella","label","roller"] 输出：["e","l","l"] 示例 2： 输入：["cool","lock","cook"] 输出：["c","o"] 提示：1 <= A.length <= 100 1 <= A[i].length <= 100 A[i][j] 是小写字母 https://leetcode-cn.com/problems/find-common-characters/
这道题主要思路是找出重复的字符
一、爆破法
根据以往的规律，我想到了用数组，但后来转念一想用数组的话会不会有空间浪费，毕竟如果我一个单词类似于cat只有三个单词，但是直接创造26的元素的length的数组未免太过于浪费，于是我想到了用hashmap，每一个字符占用一个k，每个v是一个数组标识每个单词中该k的出现次数，执行结果如下：
83 / 83 个通过测试用例
状态：通过
执行用时: 16 ms
内存消耗: 39.2 MB
public int getMin(int[] arr) {
int result = Integer.MAX_VALUE;
for (int i : arr) {
if (result > i)
result = i;
}
return result;
}
public List<String> commonCharsMy(String[] words) {
Map<String, int[]> map = new HashMap<>();
String word;
int[] arr;
String str;
for (int i = 0; i < words.length; i++) {
word = words[i];
for (int j = 0; j < word.length(); j++) {
str = String.valueOf(word.charAt(j));
if (null == (arr = map.get(str)) || arr.length < 1) {
map.put(str, new int[words.length]);
}
map.get(str)[i]++;
}
}
List<String> result = new ArrayList<>(map.size());
map.forEach((k, v) -> {
for (int i = 0; i < getMin(v); i++) {
result.add(k);
}
});
return result;
}但是看了一下执行结果不是很满意，我在想是不是用数组才是最好的解法？
果然还是我太年轻了，数组远远没有我想象的那么占空间，反倒是map比较占空间。
二、数组记录法
评论区大佬的解法，先为每个单词创造一个数组，长度26，代表着26个字母。
然后从每个数组中筛选出同一下标下的最小值，执行结果如下：
83 / 83 个通过测试用例
状态：通过
执行用时: 3 ms
内存消耗: 38.6 MB
static final int CAPACIY = 26;
public List<String> commonChars(String[] words) {
int[] minArr = new int[CAPACIY];
Arrays.fill(minArr, Integer.MAX_VALUE);
for (String word : words) {
int[] myResultArr = new int[CAPACIY];
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
myResultArr[c - 'a']++;
}
for (int i = 0; i < CAPACIY; i++) {
minArr[i] = Math.min(minArr[i], myResultArr[i]);
}
}
List<String> result = new ArrayList<>();
for (int i = 0; i < CAPACIY; i++) {
for (int j = 0; j < minArr[i]; j++) {
result.add(String.valueOf((char) (i + 'a')));
}
}
return result;
}总的来说，不得不承认map虽然用的很爽，但是里面涉及到寻址和对象。而数组则是简单的数组，只需要存储一个int而不像map一样要存储一个Node（Entry）在空间上就拉一条街了，再加上寻址的时候数组的随机寻址比map要快上些许，果然我以为的还是知识我以为啊。爆破法内存上多了1m多快2m，时间上也多了13ms，实在是不应该。
腾讯云开发者
