哈希表-set/数组
在C++中，set 和 map 分別提供以下三種數據結構，其底層實現以及優劣如下表所示
參考：https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E5%93%88%E5%B8%8C%E5%87%BD%E6%95%B0
242. 有效的字母異位詞
給定兩個字符串 s 和 t ，編寫一個函數來判斷 t 是否是 s 的字母異位詞。
注意：若 s 和 t 中每個字符出現的次數都相同，則稱 s 和 t 互為字母異位詞。
示例 1:
輸入: s = “anagram”, t = “nagaram” 輸出: true
示例 2:
輸入: s = “rat”, t = “car” 輸出: false
class Solution:def isAnagram(self, s: str, t: str) -> bool:count = collections.Counter()for x in s:count[x] +=1for x in t:count[x] -=1# 如果count有數量不為0 說明s和t中有多余的元素for x in count.values():if x != 0:return Falsereturn True''' s = "rat", t = "car" sss Counter({'r': 1, 'a': 1, 't': 1}) ttt Counter({'t': 1, 'r': 0, 'a': 0, 'c': -1}) '''349. 兩個數組的交集
給定兩個數組 nums1 和 nums2 ，返回 它們的交集 。輸出結果中的每個元素一定是 唯一 的。我們可以 不考慮輸出結果的順序 。
示例 1：
輸入：nums1 = [1,2,2,1], nums2 = [2,2] 輸出：[2]
示例 2：
輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 輸出：[9,4] 解釋：[4,9] 也是可通過的
class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:res=[]#去重 nums1=set(nums1)nums2=set(nums2)# 比較nums1 nums2for x in nums1:if x in nums2:res.append(x)return res利用python求交集
class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:s1=set(nums1)s2=set(nums2)return list(s1&s2)利用Counter
from collections import Counterclass Solution:def intersect(self, nums1, nums2):print(list(Counter(nums1).elements()))print(Counter(nums1))print(Counter(nums2))print((Counter(nums1)&Counter(nums2)))print(list((Counter(nums1) & Counter(nums2)).elements()))return sorted((Counter(nums1)&Counter(nums2)).elements())ss=Solution() # elements() 按照counter的計數，重復返回元素 '''>>> c = Counter(a=4, b=2, c=0, d=-2) >>> list(c.elements()) ['a', 'a', 'a', 'a', 'b', 'b'] ''' # list直接按照Counter中key的順序生成 # sort將element某個key的value從小到大排序 nums1 = [2,2,9,5,4] nums2 = [9,4,9,8,4] print(ss.intersect(nums1, nums2)) ''' [2, 9, 5, 4] Counter({2: 1, 9: 1, 5: 1, 4: 1}) Counter({9: 2, 4: 2, 8: 1}) Counter({9: 1, 4: 1}) [9, 4] [4, 9]'''首先排序倆個數組 然后分別設置倆個指針i和j指向倆數組的開頭 如果i和j指向數組元素不相等 比較他們的大小
小的元素的指針向前移一位 如果相等的話就存進ans中
202. 快樂數
編寫一個算法來判斷一個數 n 是不是快樂數。
「快樂數」 定義為：
對于一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
然后重復這個過程直到這個數變為 1，也可能是 無限循環 但始終變不到 1。
如果這個過程 結果為 1，那么這個數就是快樂數。
如果 n 是 快樂數 就返回 true ；不是，則返回 false 。
383. 贖金信
給你兩個字符串：ransomNote 和 magazine ，判斷 ransomNote 能不能由 magazine 里面的字符構成。
如果可以，返回 true ；否則返回 false 。
magazine 中的每個字符只能在 ransomNote 中使用一次。
示例 1：
輸入：ransomNote = “a”, magazine = “b” 輸出：false 示例 2：
輸入：ransomNote = “aa”, magazine = “ab” 輸出：false 示例 3：
輸入：ransomNote = “aa”, magazine = “aab” 輸出：true
class Solution:def canConstruct(self, ransomNote: str, magazine: str) -> bool:'''利用Counter類統計各字符個數：- 如果前者出現的某字符后者沒有- 或者前者出現的某字符個數大于后者該字符出現的個數則返回False'''c1 = Counter(ransomNote)c2 = Counter(magazine)for i in c1:if i not in c2 or c1[i]>c2[i]:return Falsereturn True class Solution(object):def canConstruct(self, ransomNote, magazine):""":type ransomNote: str:type magazine: str:rtype: bool"""if len(ransomNote) > len(magazine):return Falsec1 = Counter(ransomNote)c2 = Counter(magazine)# 如果c1比c2有多的部分 則說明c2不能完全覆蓋c1 此時c不空 所以False# 如果c2可以完全覆蓋c1 比如aa和bbaaa 則c=c1-c2為空 Counter()c = c1 - c2return not Counter(ransomNote) - Counter(magazine)49. 字母異位詞分組
給你一個字符串數組，請你將 字母異位詞 組合在一起。可以按任意順序返回結果列表。
字母異位詞 是由重新排列源單詞的字母得到的一個新單詞，所有源單詞中的字母通常恰好只用一次。
示例 1:
輸入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 輸出:
[[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
輸入: strs = [“”] 輸出: [[“”]]
示例 3:
輸入: strs = [“a”] 輸出: [[“a”]]
法一：排序，利用defaultdict(list)
class Solution(object):def groupAnagrams(self, strs):""":type strs: List[str]:rtype: List[List[str]]"""map = collections.defaultdict(list) # 指定沒有key時 返回的是list 即[], {key:[]}for s in strs:# 如果相同字母次數的話則出現的 則sort后結果相同 如 aett和ttae ['a', 'e', 't', 't']key = sorted(s)key = ''.join(sorted(s))map[key].append(s)return list(map.values()) class Solution(object):def groupAnagrams(self, strs):""":type strs: List[str]:rtype: List[List[str]]"""map = {} for s in strs:# 如果相同字母次數的話則出現的 則sort后結果相同 如 aett和ttae ['a', 'e', 't', 't']key = ''.join(sorted(s))# 如果key不在字典 賦值if key not in map:map[key] = [s]# key在字典 else:map[key].append(s)return list (map.values())法二：計數
比如將 [b,a,a,a,b,c] 編碼成 a3b2c1，使用編碼后的字符串作為 HashMap 的 Key 進行聚合。或出現的字母數字來作為key
438. 找到字符串中所有字母異位詞
給定兩個字符串 s 和 p，找到 s 中所有 p 的 異位詞 的子串，返回這些子串的起始索引。不考慮答案輸出的順序。
異位詞 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
輸入: s = “cbaebabacd”, p = “abc” 輸出: [0,6] 解釋: 起始索引等于 0 的子串是 “cba”, 它是
“abc” 的異位詞。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的異位詞。
示例 2:
輸入: s = “abab”, p = “ab” 輸出: [0,1,2] 解釋: 起始索引等于 0 的子串是 “ab”, 它是 “ab” 的異位詞。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的異位詞。 起始索引等于 2 的子串是 “ab”, 它是 "ab"的異位詞。
- 因為字符串中的字符全是小寫字母，可以用長度為26的數組記錄字母出現的次數
- 設n = len(s), m = len§。記錄p字符串的字母頻次p_cnt，和s字符串前m個字母頻次s_cnt
- 若p_cnt和s_cnt相等，則找到第一個異位詞索引 0
- 繼續遍歷s字符串索引為[m, n)的字母，在s_cnt中每次增加一個新字母，去除一個舊字母
- 判斷p_cnt和s_cnt是否相等，相等則在返回值res中新增異位詞索引 i - m + 1
作者：edelweisskoko
鏈接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/438-zhao-dao-zi-fu-chuan-zhong-suo-you-z-nx6b/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
總結
在349. 兩個數組的交集 (opens new window)需要用set。這道題目沒有限制數值的大小，就無法使用數組來做哈希表了。
本題和242.有效的字母異位詞 (opens new window)很像，242.有效的字母異位詞 (opens new window)是求 字符串a 和 字符串b 是否可以相互組成，在383.贖金信 (opens new window)中是求字符串a能否組成字符串b，而不用管字符串b 能不能組成字符串a。要求只有小寫字母，暗示用數組
總結
以上是生活随笔為你收集整理的哈希表-set/数组的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： LSTM股票价格预测
- 下一篇： 06 矩阵计算【动手学深度学习v2】