【leetcode刷题之路】面试经典150题（3）——哈希表+区间

5 哈希表

5.1 【哈希表】赎金信

题目地址：https://leetcode.cn/problems/ransom-note/description/?envType=study-plan-v2&envId=top-interview-150

  分别计算两个字符串中字母的出现次数，然后比较$ransomNote$中字母出现次数在$magazine$中是否一样。

class Solution:def canConstruct(self, ransomNote: str, magazine: str) -> bool:r_dict = {}m_dict = {}# hashtablefor c in ransomNote:if c in r_dict:r_dict[c] += 1else:r_dict[c] = 0for c in magazine:if c in m_dict:m_dict[c] += 1else:m_dict[c] = 0# comparafor c in r_dict:if c not in m_dict or r_dict[c] > m_dict[c]:return Falsereturn True

5.2 【数学】同构字符串

题目地址：https://leetcode.cn/problems/isomorphic-strings/description/?envType=study-plan-v2&envId=top-interview-150

  如果映射是唯一的，那么每对有映射关系的s和t中对应的字母在各自的字符串中，首次出现的小标索引也是一致的，通过这个规则来判断是否为同构字符串。

class Solution:def isIsomorphic(self, s: str, t: str) -> bool:for i in range(len(s)):if s.index(s[i]) != t.index(t[i]):return Falsereturn True

5.3 【数学】单词规律

题目地址：https://leetcode.cn/problems/word-pattern/description/?envType=study-plan-v2&envId=top-interview-150

  同上一题，映射关系为字母与单词一一对应。

class Solution:def wordPattern(self, pattern: str, s: str) -> bool:s_new = s.split(" ")if len(pattern) != len(s_new):return Falsefor i in range(len(pattern)):if pattern.index(pattern[i]) != s_new.index(s_new[i]):return Falsereturn True

5.4 【哈希表】有效的字母异位词

题目地址：https://leetcode.cn/problems/valid-anagram/description/?envType=study-plan-v2&envId=top-interview-150

  分别计算字符串$s$和$t$中字母出现次数，比较是否一致即可。

class Solution:def isAnagram(self, s: str, t: str) -> bool:s_dict = {}t_dict = {}# hashtable_buildfor c in s:if c in s_dict:s_dict[c] += 1else:s_dict[c] = 0for c in t:if c in t_dict:t_dict[c] += 1else:t_dict[c] = 0# judge_stringif len(s_dict) != len(t_dict):return Falsefor c in s_dict:if c not in t_dict or s_dict[c] != t_dict[c]:return Falsereturn True

5.5 【哈希表】字母异位词分组

题目地址：https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-interview-150

  方法一：分别计算每个单词的字母出现次数，将一样的单词分为一组。

  方法二：每组异位词经过词内排序后，都会是同一个单词，根据这个规则构建哈希表。

# 方法一
class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:strs_dict = [{} for _ in range(len(strs))]strs_visited = [0]*len(strs)# hashtable_buildfor i in range(len(strs)):for c in strs[i]:if c in strs_dict[i]:strs_dict[i][c] += 1else:strs_dict[i][c] = 1# divideans = []for i in range(len(strs)):tmp = []if strs_visited[i] == 0:tmp.append(strs[i])strs_visited[i] = 1for j in range(i+1,len(strs)):if strs_dict[j] == strs_dict[i] and strs_visited[j] == 0:tmp.append(strs[j])strs_visited[j] = 1ans.append(tmp)return ans
# 方法二
class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:hash_table = {}for s in strs:tmp = "".join(sorted(s))if tmp in hash_table:hash_table[tmp].append(s)else:hash_table[tmp] = [s]return list(hash_table.values())

5.6 【双指针】两数之和

题目地址：https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-interview-150

  详见代码。

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:tmp = nums.copy()tmp.sort()left,right = 0,len(nums)-1while left<right:if tmp[left]+tmp[right] == target:index_a = nums.index(tmp[left])nums[index_a] = pow(10,9)+1index_b = nums.index(tmp[right])return [index_a,index_b]elif tmp[left]+tmp[right] < target:left += 1else:right -= 1 

5.7 【数学】快乐数

题目地址：https://leetcode.cn/problems/happy-number/?envType=study-plan-v2&envId=top-interview-150

  结果为$1$就是快乐数，出现循环就不是快乐数。

class Solution:def isHappy(self, n: int) -> bool:cir_num = []while True:if n == 1:return Trueif n in cir_num:return Falsecir_num.append(n)str_num = str(n)n = sum(int(c)**2 for c in str_num)

5.8 【哈希表】219. 存在重复元素 II

题目地址：https://leetcode.cn/problems/contains-duplicate-ii/description/?envType=study-plan-v2&envId=top-interview-150

  详见代码。

class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:idx_dict = {}for i in range(len(nums)):if nums[i] in idx_dict:if i-idx_dict[nums[i]] <= k:return Trueidx_dict[nums[i]] = ireturn False

5.9 【数学】最长连续序列

题目地址：https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-interview-150

  排序后逐一比较即可，并更新最长长度。

class Solution:def longestConsecutive(self, nums: List[int]) -> int:if len(nums) == 0:return 0nums = list(set(nums))nums.sort()max_long,tmp_long = 1,1for i in range(1,len(nums)):if nums[i]-nums[i-1] == 1:tmp_long += 1else:max_long = max(max_long,tmp_long)tmp_long = 1return max(max_long,tmp_long)

6 区间

6.1 【数学】汇总区间

题目地址：https://leetcode.cn/problems/summary-ranges/description/?envType=study-plan-v2&envId=top-interview-150

  逐一比较相邻元素差值是否为$1$，把差值为$1$的元素合并到一个区间，剩下的单独一个区间。

class Solution:def summaryRanges(self, nums: List[int]) -> List[str]:ans = []# array_len == 0if len(nums) == 0:return ans# array_len != 0range_l,range_r = nums[0],nums[0]for i in range(1,len(nums)):if nums[i] - nums[i-1] == 1:range_r = nums[i]else:rg = str(range_l) + "->" + str(range_r) if range_l != range_r else str(range_l)ans.append(rg)range_l = range_r = nums[i]rg = str(range_l) + "->" + str(range_r) if range_l != range_r else str(range_l)if rg not in ans:ans.append(rg)return ans

6.2 【区间】合并区间

题目地址：https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-interview-150

  根据区间的第一个元素进行排序，然后依次比较区间的收尾元素进行合并。

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort()l,r = intervals[0][0],intervals[0][1]ans = []for i in range(1,len(intervals)):if intervals[i][0] <= r:r = max(intervals[i][1],r)else:ans.append([l,r])l,r = intervals[i][0],intervals[i][1]if [l,r] not in ans:ans.append([l,r])return ans

6.3 【区间】插入区间

题目地址：https://leetcode.cn/problems/insert-interval/description/?envType=study-plan-v2&envId=top-interview-150

  将新区间插入列表中，然后进行排序再合并。

class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:intervals.append(newInterval)intervals.sort()l,r = intervals[0][0],intervals[0][1]ans = []for i in range(1,len(intervals)):if intervals[i][0] <= r:r = max(intervals[i][1],r)else:ans.append([l,r])l,r = intervals[i][0],intervals[i][1]if [l,r] not in ans:ans.append([l,r])return ans

6.4 【区间】用最少数量的箭引爆气球

题目地址：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/?envType=study-plan-v2&envId=top-interview-150

  按照每个区间的第二个元素进行排序，如果区间有交叉元素，则需要一支箭，循环时记录当前的最末尾位置，如果遍历超过了这个最末尾位置，则需要一支箭。

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort(key = lambda x:x[1])end = points[0][1]ans = 1for i in range(1,len(points)):if points[i][0] > end:ans += 1end = points[i][1]return ans