Hash Table

242. Valid Anagram Anagram 有一個特性就是只要是 Anagram 每個字元的字數都會一樣多，因此一個解法是先計算出一個單字每個字元所出現的次數，接著是再見去另外一個單字，有出現的字元的字數。 如果中間有發現其他的字元，就代表不是 Anagram 。 最後還要再記得檢查，有沒有哪個字元有在第一個單字有出現，但是第二個單字沒有出現。 {% tabs %} {% tab title="Python" %} class Solution: def isAnagram(self, s: str, t: str) -> bool: table = defaultdict(int) for char in s: table[char] += 1 for char in t: if table[char] > 0: table[

1010. Pairs of Songs With Total Durations Divisible by 60 這一個題目的核心比較偏向數學，首先要先推導出以下這個關係。 $$ (a+b) \bmod 60 = 0 \ \rightarrow ((a \bmod 60) + (b \bmod 60)) \bmod 60 =0 \ \rightarrow \begin{equation} \begin{cases} a \bmod 60 = 0 \text{ and }  b \bmod 60 = 0 \ a \bmod 60 + b \bmod 60 = 60 \end{

187. Repeated DNA Sequences 1. 使用 Hash Table 的特性來判斷是否有重複出現的 sequence 2. 滑動窗口的方式來找 class Solution: def findRepeatedDnaSequences(self, s: str) -> List[str]: table = defaultdict(int) for i in range(len(s) - 9): table[s[i:i+10]] += 1 ans = [] for key, val in table.items(): if val >= 2: ans.

560. Subarray Sum Equals K 給定一個陣列，要找一個子陣列的總和為 K 。 暴力法 我想到的方法是我先算出每個位置的 prefix sum ，之後我就看如果當前這個位置的 prefix sum 減掉前面某一個位置的 prefix sum ，如果說當好等於 k ，就代表這兩個位置之間的總和是 k ，也就是說前一個位置到當前這個位置的子陣列的總和是 k 。 有一個邊角情況要考慮，那就是第一個元素可能剛好就是 k ，所以我們的 prefix_sum 陣列前面要多放一個零的元素。這樣剛好第一個元素就是一個子陣列滿足總和是 k 。 先從 [1..l] 算出 prefix sum 。 接著從 [i..l-1] 開始，設定起始位置，然後看看從 [i+1..l] 是不是有兩個位置之間的差剛好是 k

49. Group Anagrams Anagram 的特性就是裡面的每個字元出現的頻率相同，如果經過排序的話，只要是 Anagram 就一定會一樣。 利用這個特性，我們將每個詞都排序過，當作 key ，在 Hash table 裡面去把每個 anagram 加到那個 arrary 裡面。 class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: table = defaultdict(list) for s in strs: table[tuple(sorted(s))].append(s) return table.values()

1170. Compare Strings by Frequency of the Smallest Character class Solution: def f(self, word): lexicalOrder = sorted(word) counter = collections.Counter(lexicalOrder) return counter[lexicalOrder[0]] def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]: queryFreqs = [self.f(query) for query in queries] wordFreqs = [self.f(word)