LeetCode刷题记录（哈希表篇）

LeetCode刷题记录（哈希表篇），个人向。
为了锻炼代码能力，会交替使用不同编程语言完成答案。

[242] Valid Anagram

难度：Easy
语言：C++

题目描述。
题目限定了字符串里字符只能是小写英文字符，因此可以使用长度为26的数组直接当哈希表。若字符串可能包含Unicode字符，则把数组替换成unordered_map使用即可。
若大多数是短字符串，则s一个循环，t一个循环同时检查table[t[i]]是否小于0应该开销更小（两个次数为size的循环）。若大多数是长字符串，那么如下所示的一个循环写table，一个循环检查table应该开销更小（一个次数为size的循环和一个次数为26的循环）。虽然实际上长度超过26的单词应该非常稀有，但作为LeetCode题目，反而应该长字符串的测试用例比较多。

  bool isAnagram(string s, string t) {
    int table[26] = {0};
    int size = s.size();
    if (t.size() != size) {
      return false;
    }
    for (int i = 0; i < size; ++i) {
      table[s[i] - 'a']++;
      table[t[i] - 'a']--;
    }
    for (int i = 0; i < 26; ++i) {
      if (table[i] != 0) {
        return false;
      }
    }
    return true;
  }

[1002] Find Common Characters

难度：Easy
语言：Python

题目描述。
“Easy”题并不Easy。
这道题的特殊点在于字符在结果中是可以重复的。一开始想到的是用一个multimap来做，但是感觉代码会比较麻烦，而且寻思Python也没有multimap的方便替代，于是好奇网上是怎么写的。关键点是为每个word都统计一个hash table，然后再取这些hash table之间的最小值。
用多个hash table取交集（取最小值）的想法确实不容易想到，如果思维被局限于只使用一个hash table，估计会被困扰很久。

    def commonChars(self, words: List[str]) -> List[str]:
        min_count = [0] * 26
        for c in words[0]:
            min_count[ord(c) - ord("a")] += 1

        for word in words[1:]:
            count = [0] * 26
            for c in word:
                count[ord(c) - ord("a")] += 1
            for i, cur in enumerate(min_count):
                min_count[i] = min(cur, count[i])

        ret = []
        for i, num in enumerate(min_count):
            for _ in range(num):
                ret.append(chr(ord("a") + i))
        return ret

[349] Intersection of Two Arrays

难度：Easy
语言：Rust

题目描述。
把第一个array先做成hash set，再把第二个array对着第一个array做成的hash set来查，查完插入返回结果的hash set即可。基本没有难度。

use std::collections::HashSet;

impl Solution {
    pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let mut ret_set: HashSet<i32> = HashSet::with_capacity(1000);
        let mut set1: HashSet<i32> = nums1.into_iter().collect();

        nums2
            .iter()
            .filter(|num| set1.contains(num))
            .for_each(|&num| {
                ret_set.insert(num);
            });

        ret_set.into_iter().collect()
    }
}

AllenY's blog