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