LeetCode攀登之旅(2)

2019 年 10 月 5 日
筆記

LeetCode攀登之旅(2)

0.本節思想

1.兩數之和

2.無重複字符的最長子串

3.作者的話

0.本節思想

數據結構：哈希表形式：(key,value)

1.兩數之和

給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。你可以假設每個輸入只對應一種答案，且同樣的元素不能被重複利用。

示例:

給定 nums = [2, 7, 11, 15], target = 9  因為 nums[0] + nums[1] = 2 + 7 = 9  所以返回 [0, 1]

暴力解決本題就是雙重for循環，此法效率太低，這裡採用O(n)的時間複雜度算法，哈希思想算法。

首先給定nums=[2,7,11,15],利用這個數組去構造key，value。

nums[i]即為裏面的value,key即為index。

那如果換成nums[i]為value,key為index呢，如果採用這個方法，在去遍歷的時候，很不方便，因為我們是直接找對應的差值是否在這個哈希表中，如果nums[i]換成了value，則直接查找不到了！

以下給出Python實現代碼：

新建一個hash表
通過enumerate循環可以直接獲取key與value
然後根據key得到其中一個數，再根據此數從哈希表中尋找另外一個數
一開始哈希表為空，另外一個數肯定不存在哈希表中，那麼我們每次給哈希表賦值，key為number,value為index
最終返回的兩個數的順序為哈希表中的index與當前遍歷的index。或者直接sorted排序即可！

【哈希code】

class Solution:      def twoSum(self,nums,target):          nums_hash = {}          for index,number in enumerate(nums):              one_num = nums[index]              other_num = target-one_num              if other_num in nums_hash:                  return [nums_hash[other_num],index]              nums_hash[number] = index          return []

手動推演：

nums = [2,6,8,9] target=10

當one_num = 2(index=0)時,other_num=8,此時這個數不在哈希表中，先將當前數加入哈希表中，得到nums_hash = {2:0}

當one_num=6(index=1)時候，other_num=4，繼續重複上述操作，得到nums_hash={2:0,6:1}

當one_num=8(index=2)時，other_num=2，此時此數在哈希表中，直接返回[nums_hash[other_num],index] ，循環結束，退出程序。

2.無重複字符的最長子串

給定一個字符串，找出不含有重複字符的最長子串的長度。 示例 1:

輸入: "abcabcbb"  輸出: 3  解釋: 無重複字符的最長子串是 "abc"，其長度為 3。

示例 2:

輸入: "bbbbb"  輸出: 1  解釋: 無重複字符的最長子串是 "b"，其長度為 1。

示例 3:

輸入: "pwwkew"  輸出: 3  解釋: 無重複字符的最長子串是 "wke"，其長度為 3。       請注意，答案必須是一個子串，"pwke" 是一個子序列 而不是子串。

暴力解法： 【解題思想】首先想到遍歷整個字符，然後對遍歷到的每個字符後的字符處理，即判斷它是否是重複元素，這個判別可以通過list/dict/str解決，如果檢查的字符不在這個判別list/dict/str裏面，則加入進去，並記錄本次長度，在最外面定義一個最大長度標記，將每次的長度與最大長度對比，取最大即為最終結果！【暴力code】

def lengthOfLongestSubstring(self, s):      """      :type s: str      :rtype: int      """      MaxLength = 0      for i in range(len(s)):          st = ''          count = 0          for j in s[i:]:              if j not in st:                  st += j                  count += 1                  if (MaxLength<count):                      MaxLength=count              else:                  break      return MaxLength

手動推演：

給定字符s="pwwkew"，首先得到s的總長6，接着對其做6次循環。  當i=0時：count=0，此時的j的範圍為"pwwkew"  內部過程如下：  st='p' count=1 MaxLength=1 st='pw' count=2 MaxLength=2  w in st中，直接退出本次循環  跳至外部循環如下：  當i=1時：count=0，此時的j的範圍為"wwkew"  內部過程如下：  st='w' count=1 MaxLength=1  w in st中，直接退出本次循環  跳至外部循環如下：  當i=2時：count=0，此時的j的範圍為"wkew"  內部過程如下：  st='w' count=1 MaxLength=2 st='wk' count=2 MaxLength=2  st='wke' count=3 MaxLength=3  w in st中，直接退出本次循環  跳至外部循環如下：  當i=3、4、5，依此重複上述過程，最終返回MaxLength

哈希解法： 注意到上述的手動推演了？可以看到在下次查找重複元素時，實際上白做了這麼一段過程，比如：i=0可直接跳到i=2情況下，那麼此時效率肯定會高很多，也就是當i=1時是沒有用的，因為去掉一個元素後，不可能比之前的元素長度還長！以下分別為i=0,i=1,i=2的情況

p w w k e w  i      j  hash_str = pw

p w w k e w    i      j  hash_str = w

p w w k e w      i      j  hash_str = w

【解題思想】於是乎新思想出來了，我們跳過i=1的過程，直接從兩個相等情況入手，而存儲的j位字符為上述的哈希表，沒錯，我們仿照上述兩數之和的哈希思想去解決這個問題，會變得非常簡單，從原先的O(n^2)變為現在的O(n)複雜度！這裡有一點注意，最大長度是根據index與start位置變化，所以這裡是index-start+1

實質：例如：字符串為"pswkwabc"，原先按照暴力解法，直接循環每一個元素，  那麼用哈希跟跳過重複元素解決則為，從  p     s w k w a b c  start  直接指向了重複元素w的後一個元素k，剛好跳過重複元素  p s w   k   w a b c        start

【哈希code】看下面代碼跟上述兩數之和，及其相似，一個是找到元素就退出，一個是等對比完，找出最大長度，才退出！

def lengthOfLongestSubstring(self, s):      """      :type s: str      :rtype: int      """      start = MaxLength = 0      hash_str = {}      for index,char in enumerate(s):          if char in hash_str and start<=hash_str[char]:              start = hash_str[char]+1          else:              if(MaxLength<(index-start+1)):                  MaxLength=index-start+1          hash_str[char] = index        return MaxLength

手動推演： 以pwwkew為例:

-------------------------  start = MaxLength = 0   hash_str = {}  index = 0, char= 'p' 此時char不在hash_str中，進入else裏面  MaxLength=1 退出判斷， hash_str={'p':0}  -------------------------  index = 1, char= 'w' 此時char不在hash_str中，進入else裏面  MaxLength=2 退出判斷， hash_str={'p':0,'w':1}  -------------------------  index = 2, char= 'w' 此時char在hash_str中，並且start=0<hash_str['w']=1，進入if裏面  start=2 退出判斷， hash_str={'p':0,'w':1,'w':2}  -------------------------  index = 3, char= 'k' 此時char不在hash_str中，進入else裏面  MaxLength=2 退出判斷， hash_str={'p':0,'w':1,'w':2,'k':3}  -------------------------  index = 4, char= 'e' 此時char不在hash_str中，進入else裏面  MaxLength=3 退出判斷， hash_str={'p':0,'w':1,'w':2,'k':3}  -------------------------  index = 4, char= 'e' 此時char在hash_str中，並且start=2=hash_str['w']=2，進入if裏面  start=3 退出判斷， hash_str={'p':0,'w':1,'w':2,'k':3，'w':4}  -------------------------  return MaxLength=3

【效率對比】

暴力解法圖

哈希解法圖

3.作者的話

最後，您如果覺得本公眾號對您有幫助，歡迎您多多支持，轉發，謝謝！更多刷題，請關注本公眾號算法系列！