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

本文主要是介绍Leetcod面试经典150题刷题记录 —— 哈希表篇，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 赎金信

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

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

from collections import Counterclass 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_tt2s[ch_t] = ch_sreturn 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_tt2s[ch_t] = ch_sreturn 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 Falsep2S = 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 Falsep2S[ch_p] = word_SS2p[word_S] = ch_preturn True

4. 有效的字母异位词

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

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

from collections import Counterclass 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 = 0while n > 0:digit = n%10total += digit**2n = int(n/10)return totalclass 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 = 0while n > 0:digit = n%10total += digit**2n = int(n/10)return totalclass Solution:def isHappy(self, n: int) -> bool:slow_p = nfast_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 stepreturn fast_p == 1 # 走到了终点吗?

数学+仿真(待完成)

class Solution:# 在没有确定循环数字前，模拟的思路是错误的def squareSum(self, num: int) -> int:ans = 0while num != 0:x = num % 10ans += x**2num = int(num/10)return ansdef 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) <= khash_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) <= kfor 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 Truereturn 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 Truepos[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 Truewindow.add(num)return False

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

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

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

class Solution:def longestConsecutive(self, nums: List[int]) -> int:longest_streak = 0num_set = set(nums) #去重，时间复杂度O(n)，想到用set()是非常关键的for num in num_set:if num - 1 not in num_set: # 若存在前驱数，则跳过。判断的时间复杂度是O(1)current_num = numcurrent_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 += 1current_streak += 1longest_streak = max(longest_streak, current_streak)return longest_streak

这篇关于Leetcod面试经典150题刷题记录 —— 哈希表篇的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---