242. 有效的字母异位词

• 思路
  • example
  • hash: 数组, size: 26
    • ord('a)
    • 遍历完t后, 再检查一遍table_s,全部为0说明匹配。
• 复杂度. 时间：O(m+n), 空间: O(1) = O(26)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        table_s = [0] * 26
        for ch in s:
            table_s[ord(ch)-ord('a')] += 1
        for ch in t:
            table_s[ord(ch)-ord('a')] -= 1
        for i in range(26):
            if table_s[i] != 0:
                return False 
        return True

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        table = collections.defaultdict(int)   
        for ch in s:
            table[ch] += 1
        for ch in t:
            table[ch] -= 1 
            if table[ch] < 0:
                return False
        for key, val in table.items():
            if table[key] != 0:
                return False     
        return True  

• Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
• 对于进阶问题，Unicode 是为了解决传统字符编码的局限性而产生的方案，它为每个语言中的字符规定了一个唯一的二进制编码。而 Unicode 中可能存在一个字符对应多个字节的问题，为了让计算机知道多少字节表示一个字符，面向传输的编码方式的 UTF−8 和 UTF−16 也随之诞生逐渐广泛使用，具体相关的知识读者可以继续查阅相关资料拓展视野，这里不再展开。
  回到本题，进阶问题的核心点在于「字符是离散未知的」，因此我们用哈希表维护对应字符的频次即可。同时读者需要注意 Unicode 一个字符可能对应多个字节的问题，不同语言对于字符串读取处理的方式是不同的。
• hash: 字典

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        table_s = collections.defaultdict(int)  
        table_t = collections.defaultdict(int)  
        for ch in s:
            table_s[ch] += 1
        for ch in t:
            table_t[ch] += 1
        return table_s == table_t

349. 两个数组的交集

• 思路
  • example
  • hash: set （两个）
    • set1
    • result set
• 复杂度. 时间：O(m+n), 空间: O(m+n)

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set()   
        for num in nums1:
            set1.add(num)   
        res = set()  
        for num in nums2:
            if num in set1 and num not in res:
                res.add(num)  
        return list(res)   

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        res = set()
        for num in nums1:
            if num in set1 and num in set2:
                res.add(num)
        return list(res) 

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set()  
        for num in nums1:
            set1.add(num)  
        set2 = set()
        for num in nums2:
            if num in set1:
               set2.add(num) 
        return list(set2) 

202. 快乐数

• 思路
  • example
  • hash: set

用set来处理cycle

• 复杂度.

class Solution:
    def isHappy(self, n: int) -> bool:
        def compute_sum(num):
            sum_ = 0
            while num:
                rem = num % 10
                sum_ += rem ** 2
                num //= 10
            return sum_ 
        used = set()
        while True:
            n = compute_sum(n)
            if n == 1:
                return True  
            if n in used:
                return False 
            used.add(n)

class Solution:
    def isHappy(self, n: int) -> bool:
        def sumOfSquare(n):
            res = 0 
            while n:
                res += (n % 10) ** 2
                n //= 10
            return res 
        if n == 1:
            return True
        path = set()
        path.add(n)
        while n != 1:
            n = sumOfSquare(n)
            if n in path:
                return False 
            else:
                path.add(n)
        return True 

1. 两数之和

• 思路
  • example
  • hash: dict
    • record[nums[i]] = i
• 复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums) 
        hash_map = collections.defaultdict(int)  
        for i in range(n):
            if target - nums[i] in hash_map:
                return [hash_map[target-nums[i]], i] 
            hash_map[nums[i]] = i  

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums) 
        record = collections.defaultdict(int)   
        for i in range(n):
            if nums[i] in record:
                return [record[nums[i]], i] 
            record[target-nums[i]] = i