算法题刷题笔记-哈希

1. 两数之和（LC1）

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i,num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target-num], i]
            hashtable[nums[i]] = i
        return []
  • 因为返回数组下标，所以建立哈希表（字典）时以值为索引，以索引为值
  • 求目标数target减去当前数num是否在哈希字典中

2. 最长连续序列（LC128）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest = 0
        num_set = set(nums)

        for num in num_set:
            if num-1 not in num_set:
                current_num = num
                current = 1

                while current_num + 1 in num_set:
                    current_num += 1
                    current += 1
                
                longest = max(longest, current)
        return longest
  • 使用set()去重，得到num_set
  • 先遍历出一个没有前置数字的初始数字current_num
  • 从current_num开始依次+1，检测是否在num_set中，
  • 循环直到最后，记录最长序列长度

3. 字母移位词分组（LC49）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = list()
        res_index = dict()
        for str_ in strs:
            counts = [0] * 26
            for word in str_:
                counts[ord(word) - ord("a")] += 1
            counts = tuple(counts)
            if counts not in res:
                res.append(counts)
                res_index[res.index(counts)] = [str_]
            else:
                res_index[res.index(counts)].append(str_)
        return list(res_index.values())
  • 自己的实现，用得哈希法计数，折腾字典折腾了一段时间
  • 主要思路就是建立一个类似词向量的东西counts，把每个单词扩展成26个字母的一维向量
  • 如果判断词向量相等，则判定他们是一组字母移位词（eat和ate）加入到向量列表res中
  • 单词分组结果设置为字典res_index，索引是当前词向量在res中的索引.
  • 如果索引存在则append当前单词str_；不存在则先将词向量counts加入向量列表res，再按照索引将当前单词str_加入单词分组res_index
  • 最后时间和空间的代价都很高
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution:
        def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

            table = dict()

            for str_ in strs:
                key = "".join(sorted(str_))
                if(key not in table):
                    table[key] = []
                table[key].append(str_)

            return list(table.values())
  • 题解给了排序法，将每个单词排序后直接作为字典键。
  • 如果存在则将当前单词str_加入该键对应值列表；不存在则加入新的键值对
  • 时间空间代价很低