?LeetCode刷題實戰(zhàn)49：字母異位詞分組
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?字母異位詞分組，我們先來看題面：
https://leetcode-cn.com/problems/group-anagrams/
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
題意
樣例
輸入: ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出:
[
??["ate","eat","tea"],
??["nat","tan"],
??["bat"]
]
說明：
所有輸入均為小寫字母。
不考慮答案輸出的順序。
解題
https://www.cnblogs.com/techflow/p/12693828.html
暴力
def?splitStr(s):
????d?=?defaultdict(int)
????for?c?in?s:
????????d[c]?+=?1
????ret?=?''
????#?將dict中內(nèi)容排序
????for?k,v?in?sorted(d.items()):
????????ret?+=?(str(k)?+?str(v))
????return?ret
from?collections?import?defaultdict
class?Solution:
????def?splitStr(self,?s):
????????d?=?defaultdict(int)
????????#?拆分字符串中元素
????????for?c?in?s:
????????????d[c]?+=?1
????????ret?=?''
????????#?將dict中內(nèi)容排序
????????for?k,v?in?sorted(d.items()):
????????????ret?+=?(str(k)?+?str(v))
????????return?ret
????
????def?groupAnagrams(self,?strs:?List[str])?->?List[List[str]]:
????????groups?=?defaultdict(list)
????????for?s?in?strs:
????????????#?拿到拆分之后的字符串作為key進行分組
????????????key?=?self.splitStr(s)
????????????groups[key].append(s)
????????????
????????ret?=?[]
????????for?_,?v?in?groups.items():
????????????ret.append(v)
????????return?ret
????????
hash
def?hash(dict):
????ret?=?0
????prime?=?23
????#?k代表字符，v表示出現(xiàn)次數(shù)
????for?k,?v?in?dict:
????????ret?+=?v?*?pow(23,?ord(k)?-?ord('a'))
????????#?對2^32取模，控制返回值在32個bit內(nèi)
????????ret?%=?(1?<32)
????return?ret
，單個b的hash值也很好算，是23。請問23個a的hash值是多少？算一下就知道，也是23。因為雖然我們用的冪不同，但是它們的底數(shù)是一樣的，我們可以用前面的系數(shù)來彌補指數(shù)的差。這種不同的對象hash結(jié)果一樣的情況叫做hash碰撞，這種是不符合我們預(yù)期的。但是可以肯定的是，大多數(shù)情況下hash碰撞幾乎是不可避免的。因為我們hash的目的就是為了用一個簡單的數(shù)字或者字符串代替原本復(fù)雜龐大的數(shù)據(jù)，就好像拍照一樣，兩個不同的人，也可能拍出來看起來很像。
from?collections?import?defaultdict
import?math
class?Solution:
????def?splitStr(self,?s):
????????hashtable?=?[0?for?_?in?range(30)]
????????ret?=?0
????????for?c?in?s:
????????????hashtable[ord(c)?-?ord('a')]?+=?1
????????????
????????#?hash算法
????????for?i?in?range(26):
????????????ret?=?ret?*?23?+?hashtable[i]
????????????#?控制返回值在32個bit內(nèi)
????????????ret?%=?(1?<32)
????????return?ret
????
????def?groupAnagrams(self,?strs:?List[str])?->?List[List[str]]:
????????groups?=?defaultdict(list)
????????for?s?in?strs:
????????????key?=?self.splitStr(s)
????????????groups[key].append(s)
????????
????????????
????????ret?=?[]
????????for?_,?v?in?groups.items():
????????????ret.append(v)
????????return?ret
????????
上期推文：
評論
圖片
表情