leetcode-哈希表

哈希表（Hash Table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。哈希表通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。

目录

1. 两数之和

 3. 无重复字符的最长子串

12. 整数转罗马数字

17. 电话号码的字母组合

 30. 串联所有单词的子串

41. 缺失的第一个正数

49. 字母异位词分组

73. 矩阵置零

76. 最小覆盖子串

105. 从前序与中序遍历序列构造二叉树

126. 单词接龙

127. 单词接龙

128. 最长连续序列

138. 复制带随机指针的列表

139. 单词拆分

140. 单词拆分Ⅱ

141. 环形链表

142. 环形链表Ⅱ

 149. 直线上最多的点数

160. 相交链表

 166. 分数到小数

187. 重复的DNA序列

 202. 快乐数

205. 同构字符串

229. 求众数

242. 有效的字母异位词

264. 丑数

313. 超级丑数

---

1. 两数之和

 运行过程中hashtable如下所示，键key为nums中的元素值，值value为nums中的下标。

 hashtable[nums[i]] = i 中， hashtable[key] = value

 3. 无重复字符的最长子串

 因此随着子串的起始位置递增，子串的结束位置也是递增的。可以使用滑动窗口解决问题。

 如果用暴力解法，时间复杂度为O(n^2)，相当于两层遍历。使用哈希表（代码中设置的集合存储不重复元素）只需要遍历一次。

12. 整数转罗马数字

理论上是没错的不知道为什么在线结果和离线结果不一样，另一种能通过的解法：

17. 电话号码的字母组合

 30. 串联所有单词的子串

41. 缺失的第一个正数

 哈希表的优势在于：哈希表是一个可以支持快速查找的数据结构：给定一个元素，我们可以在 O(1) 的时间查找该元素是否在哈希表中。

1. 假设列表中的数为[1,n]，只检验[1,n]范围内是否有缺失的正整数，因此将负数标记为n 1不干扰最后结果；

2. 遍历列表，当元素在[1,n]范围内时，将nums对应位置更改为负数，起到标记作用（当nums[i]为负数时，说明存在i 1）；

3. 返回列表中第一个为正整数的下标 1，如果全都为负数（全都被标记）则返回n 1。

49. 字母异位词分组

 或者用collections库函数defaultdict排序：

73. 矩阵置零

 用矩阵中的第一行和第一列标记该行/列是否有0

76. 最小覆盖子串

利用一个滑动窗口记录子串情况，right负责向右延申，left负责向右缩进，将子串中元素情况记录在哈希表need中。代码中need = collections.defaultdict(int)与need = {} 的区别在于，可以直接使用need[val] = 1

Python中通过Key访问字典，当Key不存在时，会引发‘KeyError’异常。为了避免这种情况的发生，可以使用collections类中的defaultdict()方法来为字典提供默认值。

105. 从前序与中序遍历序列构造二叉树

没太看明白，做到二叉树的时候再看一遍吧。

126. 单词接龙

 第一种方法：建立邻接图，找到所有相邻的点

第二种方法：优化的BFS（广度优先搜索）

1. 把每个单词看作可以hash成c个值，c代表单词长度，比如单词'hit'，可以hash成'*it','h*t','hi*'这3个值，如果2个单词的hash值有重合，说明这2个单词是可以通过改1个字母变成另外一个；

2. 双向BFS：分别从beginWord和endWord开始遍历，当哪边的节点少就遍历哪边，当两边的节点存在交集时，遍历结束。如果一直没交集，任何一头走到末尾就可以结束，代表全部节点都遍历完成。

1.  
   import collections
2.  
    
3.  
    
4.  
   class Solution:
5.  
   def findLadders(self, beginWord, endWord, wordList):
6.  
   if endWord not in wordList:
7.  
   return []
8.  
   hashtable = collections.defaultdict(list)
9.  
   # hashtable存储格式符合要求的单词(h*t:[hot])
10.  
    for word in wordList:
11.  
    for i in range(len(word)):
12.  
    hashtable[word[:i] "*" word[i 1:]].append(word)
13.  
     
14.  
    def findNeighbor(word):
15.  
    for i in range(len(word)):
16.  
    # 遍历符合格式条件的单词（符合格式条件说明newWord是word的neighbor）
17.  
    for newWord in hashtable[word[:i] '*' word[i 1:]]:
18.  
    if newWord not in visited:
19.  
    yield newWord
20.  
     
21.  
    def findPath(end):
22.  
    res = []
23.  
    for curr in end:
24.  
    # key存放右面的word，value存放左面的word，已知右面的word找它左面所有word
25.  
    for parent in path[curr[0]]:
26.  
    res.append([parent] curr)
27.  
    return res
28.  
     
29.  
    visited = set()
30.  
    path = collections.defaultdict(set)
31.  
    begin = {beginWord} # 记录最后一层所有节点（上一次循环的visited_add）
32.  
    end = {endWord}
33.  
    forward = True # forward为True时从begin开始遍历，False从end开始遍历
34.  
    while begin and end:
35.  
    if len(begin) > len(end):
36.  
    # 从节点少的一端开始遍历，begin一端节点多时头尾互换
37.  
    begin, end = end, begin
38.  
    forward = not forward
39.  
    visited_add = set() # 该层的访问过的集合
40.  
    for word in begin:
41.  
    visited.add(word)
42.  
    # 先把begin一端所有节点添加到visited防止重复遍历
43.  
    for word in begin:
44.  
    for next_word in findNeighbor(word):
45.  
    visited_add.add(next_word)
46.  
    if forward:
47.  
    # 如果从begin一端开始遍历的，key存放右面的word，value存放左面的word
48.  
    path[next_word].add(word)
49.  
    else:
50.  
    # 如果从end一端开始遍历的，key存放右面的word，value存放左面的word
51.  
    path[word].add(next_word)
52.  
    begin = visited_add
53.  
    if begin & end: # 当begin和end存在交集
54.  
    res = [[endWord]]
55.  
    while res[0][0] != beginWord:
56.  
    res = findPath(res)
57.  
    return res
58.  
    return []

127. 单词接龙

1.  
   import collections
2.  
   class Solution:
3.  
   def ladderLength(self, beginWord, endWord, wordList):
4.  
   wordSet = set(wordList) # 将wordList转为set格式会快很多
5.  
   if endWord not in wordSet:
6.  
   return 0
7.  
    
8.  
   l_queue = [beginWord]
9.  
   r_queue = [endWord]
10.  
    l_visited = {beginWord} # 初始化为集合set
11.  
    r_visited = {endWord}
12.  
    depth = 1
13.  
     
14.  
    neighbors = collections.defaultdict(list)
15.  
    for word in wordSet:
16.  
    for i in range(len(word)):
17.  
    neighbors[word[:i] '*' word[i 1:]].append(word)
18.  
     
19.  
    while l_queue and r_queue:
20.  
    if len(l_queue) > len(r_queue):
21.  
    # 每次都走节点少的一端
22.  
    l_queue, r_queue = r_queue, l_queue
23.  
    l_visited, r_visited = r_visited, l_visited
24.  
    for _ in range(len(l_queue)): # 每层开始遍历
25.  
    cur = l_queue.pop(0)
26.  
    if cur in r_visited: # 当前节点在另一端遍历过
27.  
    return depth
28.  
    for i in range(len(beginWord)):
29.  
    for nextWord in neighbors[cur[:i] '*' cur[i 1:]]:
30.  
    if nextWord not in l_visited:
31.  
    l_queue.append(nextWord)
32.  
    l_visited.add(nextWord)
33.  
    depth = 1
34.  
    return 0

128. 最长连续序列

right记录在num右边还有几个连续的数，left记录num左边还有几个连续的数，每个num循环结束更新两边端点的currentlength值，记录当前最长长度。

dict.get(key, n) 返回字典中key对应的value，如果不存在则返回n。

或者第二种思路：

 当num-1不在字典中时（即num为一串连续数的开始）检查该串连续数的长度，其中cnts是记录nums中元素种类和个数的字典。

138. 复制带随机指针的列表

1.  
   class Node:
2.  
   def __init__(self, x, next=None, random=None):
3.  
   self.val = int(x)
4.  
   self.next = next
5.  
   self.random = random
6.  
    
7.  
    
8.  
   class Solution(object):
9.  
   def copyRandomList(self, head):
10.  
    """
11.  
    :type head: Node
12.  
    :rtype: Node
13.  
    """
14.  
    if not head:
15.  
    return None
16.  
    # 创建一个哈希表，key是原节点，value是新节点
17.  
    hashtable = dict()
18.  
    p = head
19.  
    while p:
20.  
    new_node = Node(p.val, None, None)
21.  
    hashtable[p] = new_node
22.  
    p = p.next
23.  
    p = head
24.  
    while p:
25.  
    if p.next:
26.  
    hashtable[p].next = hashtable[p.next]
27.  
    if p.random:
28.  
    hashtable[p].random = hashtable[p.random]
29.  
    p = p.next
30.  
    return hashtable[head]

139. 单词拆分

另外一种方法采用回溯思想：

 在如下样例中存在大量重复计算情况下可能会超时：

使用一个数组存储计算结果，数组索引为指针位置（以该指针作为起始位置的计算结果），值为计算的结果，下次遇到相同的子问题直接返回数组中的缓存值：

140. 单词拆分Ⅱ

 动态规划：

1.  
   from functools import lru_cache
2.  
   class Solution(object):
3.  
   def wordBreak(self, s, wordDict):
4.  
   """
5.  
   :type s: str
6.  
   :type wordDict: List[str]
7.  
   :rtype: List[str]
8.  
   """
9.  
    
10.  
    @lru_cache(None)
11.  
    def backtrack(index) :
12.  
    if index == len(s):
13.  
    return [[]]
14.  
    ans = list()
15.  
    for i in range(index 1, len(s) 1):
16.  
    word = s[index:i]
17.  
    if word in wordSet:
18.  
    nextWordBreaks = backtrack(i)
19.  
    for nextWordBreak in nextWordBreaks:
20.  
    ans.append(nextWordBreak.copy() [word])
21.  
    return ans
22.  
     
23.  
    wordSet = set(wordDict)
24.  
    breakList = backtrack(0)
25.  
    return [" ".join(words[::-1]) for words in breakList]

@Iru_cache(None) 在第二次调用函数时不进行计算直接返回缓存结果。

第二种方法，使用memo[i:]代表s[i:]这个字符串能否被分割，如果不能停止后续遍历。（其实和第一种是一样的但是第一种在python3里运行）

1.  
   class Solution:
2.  
   # 带备忘录的记忆化搜索
3.  
   def wordBreak(self, s, wordDict):
4.  
   res = []
5.  
   memo = [1] * (len(s) 1)
6.  
   wordDict = set(wordDict)
7.  
    
8.  
   def dfs(wordDict, temp, pos):
9.  
   num = len(res) # 回溯前先记下答案中有多少个元素
10.  
    if pos == len(s):
11.  
    res.append(" ".join(temp))
12.  
    return
13.  
    for i in range(pos, len(s) 1):
14.  
    if memo[i] and s[pos:i] in wordDict: # 添加备忘录的判断条件
15.  
    temp.append(s[pos:i])
16.  
    dfs(wordDict, temp, i)
17.  
    temp.pop()
18.  
    # 答案中的元素没有增加，说明s[pos:]不能分割，修改备忘录
19.  
    memo[pos] = 1 if len(res) > num else 0
20.  
     
21.  
    dfs(wordDict, [], 0)
22.  
    return res

141. 环形链表

142. 环形链表Ⅱ

1.  
   # Definition for singly-linked list.
2.  
   # class ListNode(object):
3.  
   # def __init__(self, x):
4.  
   # self.val = x
5.  
   # self.next = None
6.  
    
7.  
   class Solution(object):
8.  
   def detectCycle(self, head):
9.  
   """
10.  
    :type head: ListNode
11.  
    :rtype: ListNode
12.  
    """
13.  
    fast, slow = head, head
14.  
    while True:
15.  
    if not (fast and fast.next): return
16.  
    fast, slow = fast.next.next, slow.next
17.  
    if fast == slow: break
18.  
    fast = head
19.  
    while fast != slow:
20.  
    fast, slow = fast.next, slow.next
21.  
    return fast

构建两次相遇：

 149. 直线上最多的点数

1.  
   class Solution(object):
2.  
   def maxPoints(self, points):
3.  
   """
4.  
   :type points: List[List[int]]
5.  
   :rtype: int
6.  
   """
7.  
   n = len(points)
8.  
   if n <= 2:
9.  
   return n
10.  
    res = 2
11.  
    for i in range(n):
12.  
    x1, y1 = points[i][0], points[i][1]
13.  
    has = {}
14.  
    for j in range(i 1, n):
15.  
    x2, y2 = points[j][0], points[j][1]
16.  
    if x1 == x2:
17.  
    a, b, c = 1, 0, -x1
18.  
    elif y1 == y2:
19.  
    a, b, c = 0, 1, -y1
20.  
    else:
21.  
    a = 1.0
22.  
    b = 1.0 * (x1 - x2) / (y2 - y1)
23.  
    c = 1.0 * (x1 * y2 - x2 * y1) / (y1 - y2)
24.  
    if (a,b,c) in has.keys():
25.  
    has[(a,b,c)] =1
26.  
    res = max(res,has[(a,b,c)])
27.  
    else:
28.  
    has[(a,b,c)] = 2
29.  
    return res

 字典中的key可以使用任意不可变数据（整数、实数、复数、字符串、元组等可散列数据），不能使用可变类型（列表、集合、字典）。

160. 相交链表

1.  
   # Definition for singly-linked list.
2.  
   # class ListNode(object):
3.  
   # def __init__(self, x):
4.  
   # self.val = x
5.  
   # self.next = None
6.  
    
7.  
   class Solution(object):
8.  
   def getIntersectionNode(self, headA, headB):
9.  
   """
10.  
    :type head1, head1: ListNode
11.  
    :rtype: ListNode
12.  
    """
13.  
    nowA, nowB = headA, headB
14.  
    while nowA != nowB:
15.  
    nowA = nowA.next if nowA else headB
16.  
    nowB = nowB.next if nowB else headA
17.  
    return nowA

两个指针分别从两个链表的head开始遍历，当其中一个遍历完之后从另一个链表的head继续遍历。

 166. 分数到小数

1.  
   import collections
2.  
   class Solution(object):
3.  
   def fractionToDecimal(self, numerator, denominator):
4.  
   """
5.  
   :type numerator: int
6.  
   :type denominator: int
7.  
   :rtype: str
8.  
   """
9.  
   ans = []
10.  
    flag = True # 标记结果的正负
11.  
    if numerator == 0:
12.  
    return '0'
13.  
    if (numerator < 0 and denominator > 0) or (numerator > 0 and denominator < 0):
14.  
    # if (numerator < 0) != (denominator < 0):
15.  
    flag = False
16.  
    numerator = abs(numerator)
17.  
    denominator = abs(denominator)
18.  
    if not flag:
19.  
    ans.append('-')
20.  
     
21.  
    # 整数部分
22.  
    tmp = numerator // denominator
23.  
    ans.append('%d' % tmp)
24.  
    # ans.append(str(tmp))
25.  
    remainder = numerator % denominator
26.  
    if remainder == 0:
27.  
    return ''.join(ans)
28.  
    ans.append('.')
29.  
     
30.  
    # 小数部分
31.  
    hashtable = collections.defaultdict(int) # 记录余数第一次出现的下标
32.  
    while remainder and remainder not in hashtable:
33.  
    hashtable[remainder] = len(ans)
34.  
    remainder *= 10
35.  
    ans.append('%d' % (remainder // denominator))
36.  
    remainder %= denominator
37.  
    if remainder:
38.  
    start = hashtable[remainder]
39.  
    ans.insert(start, '(')
40.  
    ans.append(')')
41.  
     
42.  
    return ''.join(ans)

187. 重复的DNA序列

1.  
   import collections
2.  
   class Solution(object):
3.  
   def findRepeatedDnaSequences(self, s):
4.  
   """
5.  
   :type s: str
6.  
   :rtype: List[str]
7.  
   """
8.  
   hashtable = collections.defaultdict(int)
9.  
   if len(s) < 10:
10.  
    return []
11.  
    for left in range(len(s)-9):
12.  
    dna = s[left:left 10]
13.  
    hashtable[str(dna)] = 1
14.  
    ans = []
15.  
    for key in hashtable:
16.  
    if hashtable[key] > 1:
17.  
    ans.append(key)
18.  
    return ans

 202. 快乐数

1.  
   class Solution(object):
2.  
   def isHappy(self, n):
3.  
   """
4.  
   :type n: int
5.  
   :rtype: bool
6.  
   """
7.  
   hashtable = set()
8.  
   tmp = n
9.  
   while tmp not in hashtable and tmp != 1:
10.  
    hashtable.add(tmp)
11.  
    num = []
12.  
    count = len(str(tmp)) # 数字位数
13.  
    for i in range(count-1, -1, -1):
14.  
    num.append(tmp // (10 ** i))
15.  
    tmp = tmp % (10 ** i)
16.  
    tmp = 0
17.  
    for i in range(len(num)):
18.  
    tmp = num[i] ** 2
19.  
     
20.  
    if tmp != 1:
21.  
    return False
22.  
    else:
23.  
    return True

或者使用快慢指针，指针相遇时返回False

205. 同构字符串

1.  
   import collections
2.  
   class Solution(object):
3.  
   def isIsomorphic(self, s, t):
4.  
   """
5.  
   :type s: str
6.  
   :type t: str
7.  
   :rtype: bool
8.  
   """
9.  
   hashtable_st = collections.defaultdict(str) # 记录s到t的映射关系
10.  
    hashtable_ts = set() # 检验是否有相同两个字符映射到同一字符
11.  
     
12.  
    for i, letter in enumerate(s):
13.  
    if letter not in hashtable_st:
14.  
    if t[i] not in hashtable_ts:
15.  
    hashtable_st[letter] = t[i]
16.  
    hashtable_ts.add(t[i])
17.  
    else:
18.  
    return False
19.  
    else:
20.  
    if hashtable_st[letter] != t[i]:
21.  
    return False
22.  
    return True

229. 求众数

1.  
   import collections
2.  
   class Solution(object):
3.  
   def majorityElement(self, nums):
4.  
   """
5.  
   :type nums: List[int]
6.  
   :rtype: List[int]
7.  
   """
8.  
   hashtable = collections.defaultdict(int)
9.  
   ans = []
10.  
    for num in nums:
11.  
    hashtable[num] = 1
12.  
    for num in hashtable:
13.  
    if hashtable[num] > len(nums) // 3:
14.  
    ans.append(num)
15.  
    return ans

242. 有效的字母异位词

1.  
   class Solution(object):
2.  
   def isAnagram(self, s, t):
3.  
   """
4.  
   :type s: str
5.  
   :type t: str
6.  
   :rtype: bool
7.  
   """
8.  
   hashtable_s = collections.defaultdict(int)
9.  
   hashtable_t = collections.defaultdict(int)
10.  
     
11.  
    for letter in s:
12.  
    hashtable_s[letter] = 1
13.  
    for letter in t:
14.  
    hashtable_t[letter] = 1
15.  
    return hashtable_s == hashtable_t

264. 丑数

1.  
   import heapq
2.  
   class Solution(object):
3.  
   def nthUglyNumber(self, n):
4.  
   """
5.  
   :type n: int
6.  
   :rtype: int
7.  
   """
8.  
   factors = [2, 3, 5]
9.  
   visited = {1} # 遍历过的丑数集合
10.  
    heap = [1] # 堆顶
11.  
     
12.  
    for i in range(n - 1):
13.  
    curr = heapq.heappop(heap) # 从堆中弹出最小值
14.  
    for factor in factors:
15.  
    if (curr * factor) not in visited:
16.  
    nxt = curr * factor
17.  
    visited.add(nxt)
18.  
    heapq.heappush(heap, nxt) # 往堆中插入新的值
19.  
     
20.  
    return heapq.heappop(heap)

heapq常见应用：

heap = []   #创建了一个空堆
heappush(heap,item)   # 往堆中插入一条新的值
item = heappop(heap)   # 从堆中弹出最小值
item = heap[0]   # 查看堆中最小值，不弹出
heapify(x)   # 以线性时间将一个列表转化为堆
item = heapreplace(heap,item)   # 弹出并返回最小值，然后将item的值插入到堆中，堆的整体结构不会发生改变。

堆的方法比较慢，也可以采用动态规划的方法：

设置三个指针p2，p3，p5，dp[i]=min(dp[p2]×2,dp[p3]×3,dp[p5]×5)，并将对应指针加一。

1.  
   class Solution(object):
2.  
   def nthUglyNumber(self, n):
3.  
   """
4.  
   :type n: int
5.  
   :rtype: int
6.  
   """
7.  
   ans = [0, 1]
8.  
   p2 = p3 = p5 = 1
9.  
    
10.  
    for i in range(2, n 1):
11.  
    ans.append(min(ans[p2] * 2, ans[p3] * 3, ans[p5] * 5))
12.  
    if ans[i] == ans[p2] * 2:
13.  
    p2 = 1
14.  
    if ans[i] == ans[p3] * 3:
15.  
    p3 = 1
16.  
    if ans[i] == ans[p5] * 5:
17.  
    p5 = 1
18.  
     
19.  
    return ans

313. 超级丑数

1.  
   class Solution(object):
2.  
   def nthSuperUglyNumber(self, n, primes):
3.  
   """
4.  
   :type n: int
5.  
   :type primes: List[int]
6.  
   :rtype: int
7.  
   """
8.  
   len_primes = len(primes)
9.  
   pointers = [1] * (len_primes)
10.  
    num = [0] * (len_primes)
11.  
    ans = [0, 1]
12.  
     
13.  
    for i in range(2, n 1):
14.  
    for j in range(len_primes):
15.  
    num[j] = ans[pointers[j]] * primes[j]
16.  
    next = min(num)
17.  
    for j in range(len_primes):
18.  
    if num[j] == next:
19.  
    pointers[j] = 1
20.  
    ans.append(next)
21.  
     
22.  
    return ans[n]

这种方法超出时间限制了，可以通过以下方法优化（减少一个for循环）：

1.  
   class Solution(object):
2.  
   def nthSuperUglyNumber(self, n, primes):
3.  
   """
4.  
   :type n: int
5.  
   :type primes: List[int]
6.  
   :rtype: int
7.  
   """
8.  
   ans = [0] * (n 1)
9.  
   m = len(primes)
10.  
    pointers = [0] * m
11.  
    num = [1] * m
12.  
     
13.  
    for i in range(1, n 1):
14.  
    next = min(num)
15.  
    ans[i] = next
16.  
    for j in range(m):
17.  
    if num[j] == next:
18.  
    pointers[j] = 1
19.  
    num[j] = ans[pointers[j]] * primes[j]
20.  
    return ans[n]

或者采用堆排序：

1.  
   import heapq
2.  
    
3.  
    
4.  
   class Solution(object):
5.  
   def nthSuperUglyNumber(self, n, primes):
6.  
   """
7.  
   :type n: int
8.  
   :type primes: List[int]
9.  
   :rtype: int
10.  
    """
11.  
    # ans[i] 代表第i 1个丑数
12.  
    ans = [1] * n
13.  
    # 丑数, 刚刚乘过的丑数的坐标, 质因数
14.  
    pq = [(p, 0, i) for i, p in enumerate(primes)]
15.  
     
16.  
    for i in range(1, n):
17.  
    # 目前最新的最小的丑数
18.  
    ans[i] = pq[0][0]
19.  
    # 所有等于这个值的要全部出队列，并根据该乘的丑数重新加入队列
20.  
    while pq and pq[0][0] == ans[i]:
21.  
    _, idx, p = heapq.heappop(pq)
22.  
    heapq.heappush(pq, (ans[idx 1] * primes[p], idx 1, p))
23.  
    return ans[-1]

这篇好文章是转载于：学新通技术网