Leetcod面试经典150题刷题记录 —— 哈希表篇

1. 赎金信

题目链接：赎金信 - leetcode
题目描述：
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。
题目归纳：
统计字符频率并比较即可

解题思路：
(1) 解法： 赎金信 - leetcode官方题解

from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # magzine的字符词频绝对 >= ransomNote即可啊
        r_counter = Counter(ransomNote)
        m_counter = Counter(magazine)
        return m_counter >= r_counter

2. 同构字符串(按逻辑完整性，分次书写代码)

题目链接：同构字符串 - leetcode
题目描述：
给定两个字符串 s 和 t ，判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
题目归纳：
s[i]与t[i]是否互相是一一映射

解题思路：
(1) 解法： 同构字符串 - leetcode官方题解

这里值得说一点的是，写代码不一定是遵守代码完整性，从上到下完整书写，应遵循逻辑完整的原则，这一点也是我写了这么久代码的一点小心得，人做一切事情都是会遵循逻辑和规律，不能是碎片化的，例如这里，应该按这样的顺序写：

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # 两个字典
        s2t = dict()
        t2s = dict()
        s_len = len(s)

        for i in range(s_len):
            # 先构建映射
            ch_s = s[i]
            ch_t = t[i]          
            s2t[ch_s] = ch_t
            t2s[ch_t] = ch_s

        return True

再添加判断逻辑，将上面的代码块变成下面的

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # 两个字典
        s2t = dict()
        t2s = dict()
        s_len = len(s)

        for i in range(s_len):
            ch_s = s[i]
            ch_t = t[i]       
            # 再添加映射失败的判断逻辑
            if (ch_s in s2t and s2t[ch_s] != ch_t) or (ch_t in t2s and t2s[ch_t] != ch_s):
                return False     
            s2t[ch_s] = ch_t
            t2s[ch_t] = ch_s

        return True

3. 单词规律

题目链接：单词规律 - leetcode
题目描述：
给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
题目归纳：
先把s按' '进行split()，得到分词数组S，就回归到了上一题：同构字符串

解题思路：
(1) 解法： 单词规律- leetcode官方题解

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        # 先把s按空格进行split就回归到上一题：同构字符串
        S = s.split()
        S_len = len(S)
        p_len = len(pattern)
        if S_len != p_len:
            return False

        p2S = dict()
        S2p = dict()

        for i in range(p_len):
            ch_p = pattern[i]
            word_S = S[i]
            if (ch_p in p2S and p2S[ch_p] != word_S) or (word_S in S2p and S2p[word_S] != ch_p):
                return False
            
            p2S[ch_p] = word_S
            S2p[word_S] = ch_p
        
        return True

4. 有效的字母异位词

题目链接：有效的字母异位词 - leetcode
题目描述：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
题目归纳：
字符频率相同即可

解题思路：
(1) 解法： 有效的字母异位词 - leetcode官方题解

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t) # 字符频率相同即可

4.1 进阶: 输入字符串包含 unicode 字符

5. 字母异位词分组

题目链接：字母异位词分组 - leetcode
题目描述：
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

题目归纳：
相同字符频率的字符串放一起作为value，那么key就是其对应的字典序母串

解题思路：
(1) 解法： 字母异位词分组 - leetcode官方题解

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 字符频率一致的放一起
        sortedS_dysWords = dict() # 变量命名法:key_value dystopia n. 异位；非理想化的地方，糟透的社会；地狱般的处境
        n = len(strs)
        
        for S in strs:
            key = "".join(sorted(S))
            if key in sortedS_dysWords: # 该str经排序后，存在于hash表中，说明其字符频率出现过
                sortedS_dysWords[key].append(S)
            else:
                sortedS_dysWords[key] = [S]
        
        ans = []
        for key in sortedS_dysWords:
            value = sortedS_dysWords[key]
            ans.append(value)
        return ans

6. 两数之和

题目链接：两数之和 - leetcode
题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

示例 1:
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

题目归纳：
解题思路：数组的索引方式是由下标index --> 元素值value，可以用一个hash表反向存储，由元素值value --> 下标index

解题思路：
(1) 解法： 两数之和 - leetcode官方题解

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_table = dict() # key:val = index:nums[index],相当于反向存储数组
        for i, num in enumerate(nums): # 一次遍历即可
            if target - num in hash_table:
                return [i, hash_table[target-num]]
            else: # 数组是key:value = 下标:元素值，这里是key:value=元素值:下标
                hash_table[num] = i 
        return []

7. 快乐数

题目链接：快乐数 - leetcode
题目描述：
编写一个算法来判断一个数 n 是不是快乐数。「快乐数」 定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1，那么这个数就是快乐数。如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：
输入：n = 19
输出：true
解释：
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1
提示
1 <= n <= 2³¹ - 1，即 1 <= n <= 2147483647，换算成十进制，n最高也只有10位数字。

题目归纳：
看上去可以用仿真法，但是由于图灵停机问题：“给定一段算法和输入组成程序A，你找不到一段通用程序B，去判断程序A是否会陷入无限循环”，所以这道题你没有一个通用的判定方法，来判断是否会无限循环，除非你能找到那些会陷入无限循环的数字，官方题解在之后就给出了这样的一个无限循环，在 1 <= n <= 2³¹ - 1 的情况下，这样的循环有且只有一个。

解题思路：
解法： 快乐数 - leetcode官方题解
(1) 用hash集合检测循环。
(2) 隐式链表+快慢指针（又称为弗洛伊德循环查找算法）检测循环。
(3) 数学法确定循环数字 + 仿真。
这道题的关键点在于死循环数字的检测上。

hash集合检测循环

def get_next(n):
    total = 0
    while n > 0:
        digit = n%10
        total += digit**2
        n = int(n/10)
    return total

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()
        while n != 1 and n not in seen: # 不在seen集合中，就是不在循环中
            seen.add(n)
            n = get_next(n)
        return n == 1

隐式链表+快慢指针（弗洛伊德循环查找算法）

def get_next(n):
    total = 0
    while n > 0:
        digit = n%10
        total += digit**2
        n = int(n/10)
    return total

class Solution:
    def isHappy(self, n: int) -> bool:
        slow_p = n
        fast_p = get_next(n)
        while fast_p != 1 and slow_p != fast_p : # fast指针没到终点，并且slow没追上fast，游戏就没结束
            slow_p = get_next(slow_p) # 1 step 
            fast_p = get_next(get_next(fast_p)) # 2 step
        return fast_p == 1 # 走到了终点吗?

数学+仿真(待完成)

class Solution:
    # 在没有确定循环数字前，模拟的思路是错误的
    def squareSum(self, num: int) -> int:
        ans = 0
        while num != 0:
            x = num % 10
            ans += x**2
            num = int(num/10)
        return ans

    def isHappy(self, n: int) -> bool:
        while n != 1:
            n = self.squareSum(n)
        return True

8. 存在重复元素 II

题目链接：存在重复元素 II - leetcode
题目描述：
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
题目归纳：
(1)我一开始的解法是遍历数组+遍历hash表
(2)最大下标解法。
(3)滑动窗口法。

解题思路：
解法： 存在重复元素 II - leetcode官方题解

8.1 我的原始解法(遍历数组+遍历hash表)

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 相同value，其下标index_i添加到hash表中
        # 建立hash表 key:val = value:[index_1, ...]
        # 遍历hash表的下标数组，查找是否存在 abs(i-j) <= k
        hash_table = dict()
        
        # (1)遍历数组，并添加元素至hash表中
        for i,num in enumerate(nums):
            if num in hash_table:
                hash_table[num].append(i)
            else: # 建立数组
                hash_table[num] = [i]

        print(hash_table)
        # (2)遍历hash表，查找是否有index满足 abs(i-j) <= k
        for value in hash_table:
            indices = hash_table[value]
            for i in indices:
                for j in indices:
                    if i != j and abs(i-j)<=k: # 必须是不同的索引
                        return True

        return False

8.2 记录最大下标解法

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        pos = dict()
        for i,num in enumerate(nums):
            if num in pos and i - pos[num] <= k: # i 一直比当前的pos[num]大
                return True
            pos[num] = i # 记录最大的下标
        return False

8.3 滑动窗口法

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 滑动窗口法
        # (1)nums中，每个长度不超过k+1的滑动窗口，其任意两个下标i,j，一定满足abs(i-j)<=k
        # (2)若存在一个滑动窗口，其中有重复元素，则一定存在两个不同的下标i,j，满足nums[i] = nums[j] and abs(i-j) <= k
        # (3)若该滑动窗口没有重复元素，则不符合要求，继续遍历滑动窗口
        # (4)若一个滑动窗口的结束下标是i，则开始下标是max(0,i-k)
        # (5)使用哈希集合，存储滑动窗口中的元素，从左至右遍历数组nums
        # (6)若 i > k，则i-(k+1)处的元素被移出滑动窗口，即s.remove(nums[i-k-1])
        # (7)若nums[i]在哈希集合中，则在同一个滑动窗口中有重复元素，不在哈希集合中则将其加入集合。

        window = set()
        for i, num in enumerate(nums):
            if i > k: # (1)维持窗口大小
                window.remove(nums[i-(k+1)])
            if num in window: # (2)判断窗口是否出现相同元素
                return True
            window.add(num)
        return False

9. 最长连续序列(有个语法问题，待解决)

题目链接：最长连续序列 - leetcode
题目描述：
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
题目归纳：

解题思路：
解法： 最长连续序列 - leetcode官方题解

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest_streak = 0
        num_set = set(nums) #去重，时间复杂度O(n)，想到用set()是非常关键的

        for num in num_set:
            if num - 1 not in num_set: # 若存在前驱数，则跳过。判断的时间复杂度是O(1)
                current_num = num
                current_streak = 1

                # next_num = num + 1 # ？？？不能用next_num? 离大谱了！！
                # while next_num in num_set: # 这行搭配上面这行会超时，实在离谱
                while current_num+1 in num_set: # 判断的时间复杂度是O(1)
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak