哈希算法

1. 两数之和

两数之和

class Solution:
    def twoSum(self, nums, target):
        temp = dict()
        for i, num in enumerate(nums):
            if target - num in temp:
                return [temp[target - num], i]
            temp[nums[i]] = i
        return []

202. 快乐数

202. 快乐数

# 「快乐数」 定义为：
# 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
# 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
# 如果这个过程 结果为 1，那么这个数就是快乐数。


class Solution:
    def isHappy(self, n: int) -> bool:
        def cal(num):
            res = 0
            while num:
                res += (num % 10)**2
                num = num // 10
            return res

        record = set()
        while True:
            n = cal(n)
            if n == 1:
                return True
            # 如果中间结果重复出现，说明陷入死循环了，该数不是快乐数
            if n in record:
                return False
            else:
                record.add(n)

242. 有效的字母异位词

242. 有效的字母异位词

s = "rat"
t = "car"


class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        temp = [0] * 26
        for i in s:
            temp[ord(i) - ord("a")] += 1
        for i in t:
            temp[ord(i) - ord("a")] -= 1

        for i in range(26):
            if temp[i] != 0:
                return False
        return True

349. 两个数组的交集

349. 两个数组的交集

# nums1 = [4, 9, 5]
# nums2 = [9, 4, 9, 8, 4]

# print(list(set(nums1) & set(nums2)))

class Solution:
    def intersection(self, nums1, nums2):
        return list(set(nums1) & set(nums2))

    def intersection2(self, nums1, nums2):
        ans = []
        temp_dict = {}
        for i in nums1:
            temp_dict[i] = 1

        for i in nums2:
            if i in temp_dict.keys() and temp_dict[i] == 1:
                ans.append(i)
                temp_dict[i] = 0

        return ans

454. 四数相加 II

454. 四数相加 II

class Solution:
    def fourSumCount(self, nums1, nums2, nums3, nums4) -> int:
        hashmap = dict()
        for n1 in nums1:
            for n2 in nums2:
                if n1 + n2 in hashmap:
                    hashmap[n1 + n2] += 1
                else:
                    hashmap[n1 + n2] = 1
        count = 0
        for n3 in nums3:
            for n4 in nums4:
                key = - n3 - n4
                if key in hashmap:
                    count += hashmap[key]
        return count

1002. 查找共用字符

1002. 查找共用字符

class Solution:
    def commonChars(self, words):
        min_count = [float("inf")] * 26
        for word in words:
            temp = [0] * 26
            for i in word:
                temp[ord(i) - ord("a")] += 1
            for i in range(26):
                min_count[i] = min(min_count[i], temp[i])

        res = []
        for i in range(26):
            res.extend([chr(i + ord("a"))] * min_count[i])
        return res