chapter13-hashTable-algorithm

Posted on | In | | Visitors: ℃
Words count in article: 762 | Reading time ≈ 3

chapter13-hashTable-algorithm

[TOC]

哈希表算法
1. 数组中两个数的和为给定值

Leetcode / 力扣

1
2
3
4
5
6
7
8
def twoSum(nums, target):
    nd = dict()
    for idx, n in enumerate(nums):
        if target - n in nd:
            return [idx, nd[target-n]]
        else:
            nd[n] = idx
    return []
2. 判断数组是否含有重复元素

Leetcode / 力扣

1
2
def containsDuplicate(nums) :
    return len(nums) != len(set(nums))
3. 最长和谐序列

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def findLHS(nums) -> int:
    # 又题意可知
    # 相差为1的两个数，即为和谐序列，
    # 因此，满足差为1，两个数的统计数之和即为最长和谐序列
    # 直接一个for训练，在遍历的同时，同时字典存储当前数的个数，和找出最大累计值
    # 注意前后同时更新即可
    # 上诉为优化，人懒，直接函数搞定
    # 逻辑代码如下：
    def solve1():
        from collections import Counter
        nd = Counter(nums)
        maxv = 0
        for n in nums:
            if n+1 in nd:
                maxv = max(maxv, nd[n] + nd[n+1])

        return maxv

    def solue2(): # cuod
        result, lengths = 1, {key: 0 for key in nums}
        for i in nums:
            if lengths[i] == 0:
                lengths[i] = 1
                left, right = lengths.get(i - 1, 0), lengths.get(i + 1, 0)
                length = 1 + left + right
                result, lengths[i - left], lengths[i + right] = max(result, length), length, length
        return result
4. 最长连续序列

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

def longestConsecutive( nums) -> int:
    # you题意可知
    # 统计最长连续序列
    # 坑点：
    # 1. 相同元素只算一种
    # 2. hash后，计数需要累积
    # 因为他要O(n)，意味着不让你排序
    # 所以就让你hash
    # 优化主要在你hash后如何去找是连续序列
    # 我这里使用临时存储去存储已经遍历得到的值，后面去不用去遍历了，防止每一个元素都要查找的，人称剪枝
    if not nums:
        return 0
    from collections import Counter
    nd = Counter(set(nums))
    maxv = float('-inf')

    dp = {}
    def forward(k ,nd):
        if k not in nd:
            return 0
        k += 1
        return forward(k, nd) + 1

    for k, v in nd.items():
        if k not in dp:
            v = forward(k, nd)
            maxv = max(maxv,v)
            dp[k] = v
            dp[k+1] = v-1
            dp[k-1] = v + 1
        else:
            maxv = max(maxv, dp[k])
            dp[k+1] = dp[k]-1
            dp[k-1] = dp[k] + 1
    return maxv
5. 设计哈希集合

力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class ListNode(object):
    def __init__(self, key, val):
        self.val = val
        self.key = key
        self.next = None
        self.prev = None


class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def insert(self, node):
        node.next, node.prev = None, None  # avoid dirty node
        if self.head is None:
            self.head = node
        else:
            self.tail.next = node
            node.prev = self.tail
        self.tail = node

    def delete(self, node):
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        node.next, node.prev = None, None  # make node clean

    def find(self, key):
        curr = self.head
        while curr:
            if curr.key == key:
                break
            curr = curr.next
        return curr


class MyHashSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.__data = [LinkedList() for _ in range(10000)]

    def add(self, key):
        """
        :type key: int
        :rtype: void
        """
        l = self.__data[key % len(self.__data)]
        node = l.find(key)
        if not node:
            l.insert(ListNode(key, 0))

    def remove(self, key):
        """
        :type key: int
        :rtype: void
        """
        l = self.__data[key % len(self.__data)]
        node = l.find(key)
        if node:
            l.delete(node)

    def contains(self, key):
        """
        Returns true if this set did not already contain the specified element
        :type key: int
        :rtype: bool
        """
        l = self.__data[key % len(self.__data)]
        node = l.find(key)
        return node is not None


# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)