3個月用python刷完leetcode600題!-hash table簡單題（一）

07-23

來自專欄 Python程序員128 人贊了文章

作者：石曉文 Python愛好者社區專欄作者
個人公眾號：小小挖掘機
博客專欄:wenwen

十五天的時間，刷完了所有的簡單題，避免遺忘，所以開始簡單題的二刷，第一遍刷題的時候過得速度比較快，因為我覺得基礎不好的我，不要硬著頭皮去想最優的方法，而是應該盡量去學一些演算法思想，所以每道題只給自己5-10分鐘的時間想，想不出來的就去找相關的答案，所以刷的比較快。二刷的時候按照leetcode官方給出的題目分類展開，同時，將解題思路記錄於簡書加深印象。

想要一起刷題的小夥伴，我們一起加油吧！

我的github連接：https://github.com/princewen/leetcode_python

1、Two Sum

同 http://www.jianshu.com/p/b71fc7307e42

136. Single Number

Single Number

"""

這道題雖然放在了hashtable里，但其實用二進位的演算法更容易求解

兩個相同數的二進位異或為0，所以遍歷一邊數組，出現兩次的異或值變為0，那麼剩下的數就是出現一次的數

"""

class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ res = 0 for i in nums: res = res ^ i return res

202. Happy Number

Happy Number

"""解法1，用列表保存出現過的數，當出現重複的數字的時候，說明出現了循環，循環有兩種情況，一種不是hayyp數，循環的數必不是1，如果是happy數，那麼會出現1的不斷循環"""

class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ c = set() while not n in c: c.add(n) n = sum([int(x) ** 2 for x in str(n)]) return n==1

"""解法2，使用追趕法，快的指針每次前進兩步，慢的指針每次只前進一步，當快的指針追上慢的指針即二者數字相同時，同樣說明出現了循環，情況同上"""

class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ slow = n quick = sum([int(x) ** 2 for x in str(n)]) while quick != slow: quick = sum([int(x) ** 2 for x in str(quick)]) quick = sum([int(x) ** 2 for x in str(quick)]) slow = sum([int(x) ** 2 for x in str(slow)]) return slow == 1

204. Count Primes

Count Primes

統計比n小的質數有多少，首先設置一個數組，全部質為true，然後遍歷2-sqrt（n）的數，把他們的倍數所在的數組位置

置為True這裡為了避免重複，從ii的位置開始，而不是從i2的位置開始，因為i2，i3，i*n-1其實已經置為false了.

class Solution(object): def countPrimes(self, n): """ :type n: int :rtype: int """ if n < 3: return 0 res = [True] * n res[0] = res[1] = False for i in range(2,int(math.sqrt(n)) + 1): res[i*i:n:i] = [False] * len(res[i*i:n:i]) return sum(res)

205. Isomorphic Strings

Isomorphic Strings

一開始我的解法是這樣的，但是這是不對的，如下面的情況s=ab,t=aa 就會出現錯誤

class Solution(object): def isIsomorphic(self, s, t): """ :type s: str :type t: str :rtype: bool """ if len(s) != len(t): return False dic = dict() for i in range(len(s)): if s[i] in dic and dic[s[i]] != t[i]: return False else: dic[s[i]] = t[i] return True

所以用兩個dict分別對應保存兩個字元串對應位置的對方字元，只要其中一個不滿足條件，則返回錯誤

class Solution(object): def isIsomorphic(self, s, t): """ :type s: str :type t: str :rtype: bool """ if len(s) != len(t): return False dic1 = dict() dic2 = dict() for i in range(len(s)): if (s[i] in dic1 and dic1[s[i]] != t[i]) or (t[i] in dic2 and dic2[t[i]] != s[i]): return False else: dic1[s[i]] = t[i] dic2[t[i]] = s[i] return True

其實，還有更簡單的解法,使用zip將兩個數組對應位置元素相連，再利用set不能有重複元素的特性，判斷三者的長度是否相同即可

class Solution(object): def isIsomorphic(self, s, t): """ :type s: str :type t: str :rtype: bool """ return len(set(zip(s,t))) == len(set(s)) == len(set(t))

217、Contains Duplicate

219、Contains Duplicate||

這兩題參見http://www.jianshu.com/p/217cb8cc5d08

242. Valid Anagram

Valid Anagram

用兩個字典保存字元出現的情況，判斷兩個字典是否相同即可

class Solution(object): def isAnagram(self, s, t): """ :type s: str :type t: str :rtype: bool """ dic1 = {} dic2 = {} for i in s: dic1[i] = dic1.get(i,0)+1 for i in t: dic2[i] = dic2.get(i,0)+1 return dic1 == dic2

290. Word Pattern

Word Pattern

將str 用split分開之後，解法類似於205題

class Solution(object): def wordPattern(self, pattern, str): """ :type pattern: str :type str: str :rtype: bool """ return len(pattern) == len(str.split( )) and len(set(zip(pattern, str.split( )))) == len( set(pattern)) == len(set(str.split( )))

349. Intersection of Two Arrays

Intersection of Two Arrays

可以使用hash table保存下數組1的出現的元素，然後判斷數組2中的各元素是否在數組1中出現過，但直接使用set更簡單

class Solution(object): def intersection(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ nums1 = set(nums1) return [x for x in set(nums2) if x in nums1]

350. Intersection of Two Arrays II

Intersection of Two Arrays II

使用兩個字典記錄下兩個數組中元素出現的次數

class Solution(object): def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ dic1,dic2 = dict(),dict() for num in nums1: dic1[num] = dic1.get(num,0) + 1 for num in nums2: dic2[num] = dic2.get(num,0) + 1 return [x for x in dic2 for j in range(min(dic1.get(x,0),dic2.get(x,0)))]

但是python內置了Counter類型數組，可以方便實現計數功能

import collectionsclass Solution(object): def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ c1,c2 = collections.Counter(nums1),collections.Counter(nums2) return [i for i in c1.keys() for j in range(min([c1[i], c2[i]]))]