LeetCode算法题整理（设计篇）Design

Posted on   |   Updated on | In | | Visitors

155. Min Stack

设计一个栈，要求在常数时间复杂度取出最小值。原题

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.
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
class MinStack:

    def __init__(self):
        self._stack = []
        
    def push(self, x: int) -> None:
        cur_min = self.getMin()
        if x < cur_min:
            cur_min = x
        self._stack.append((x, cur_min))
        
    def pop(self) -> None:
        self._stack.pop()

    def top(self) -> int:
        if not self._stack:
            return None
        else:
            return self._stack[-1][0]

    def getMin(self) -> int:
        if not self._stack:
            return float('inf')
        else:
            return self._stack[-1][1]

232. Implement Queue using Stacks

使用两个栈实现一个队列。原题

1
2
3
4
5
6
7
MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

方法一：push-O(1), pop-O(N). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MyQueue:

    def __init__(self):
        self.in_stack, self.out_stack = [], []
        
    def push(self, x: int) -> None:
        self.in_stack.append(x)
        
    def move(self) -> None:
        if self.out_stack == []:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

    def pop(self) -> int:
        self.move()
        return self.out_stack.pop()
        
    def peek(self) -> int:
        self.move()
        return self.out_stack[-1]
        
    def empty(self) -> bool:
        return self.in_stack==self.out_stack==[]

方法二：push-O(N), pop-O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MyQueue:

    def __init__(self):
        self.s1 = []
        self.s2 = []
        
    def push(self, x: int) -> None:
        while self.s1:
            self.s2.append(self.s1.pop())
        self.s1.append(x)
        while self.s2:
            self.s1.append(self.s2.pop())
        
    def pop(self) -> int:
        return self.s1.pop()
        
    def peek(self) -> int:
        return self.s1[-1]
        
    def empty(self) -> bool:
        return self.s1 == []

225. Implement Stack using Queues

使用队列实现栈。原题

方法一：两个队列，push-O(1), pop/top O(n). 思想在于q2就是一个临时队列，无论是是top还是pop都是保持q1剩一个元素，然后再交换q1, q2.

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
class MyStack:
    
    def __init__(self):
        from collections import deque
        self.q1, self.q2 = deque(), deque()
        
    def push(self, x: int) -> None:
        self.q1.append(x)
        
    def pop(self) -> int:
        while len(self.q1) != 1:
            self.q2.append(self.q1.popleft())
        pop_val = self.q1.popleft()
        self.q1, self.q2 = self.q2, self.q1
        return pop_val
        
    def top(self) -> int:
        while len(self.q1) != 1:
            self.q2.append(self.q1.popleft())
        val = self.q1[0]
        self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1
        return val
       
    def empty(self) -> bool:
        return not self.q1
方法二：两个队列，push-O(n), pop/top-O(1). 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MyStack:

    def __init__(self):
        from collections import deque
        self.q1, self.q2 = deque(), deque()

    def push(self, x: int) -> None:
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        return self.q1.popleft()

    def top(self) -> int:
        return self.q1[0]
        
    def empty(self) -> bool:
        return not self.q1
方法三：一个队列旋转。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MyStack:

    def __init__(self):
        from collections import deque
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        # self.q.rotate(1)  这里是用了双端队列的特性
        # self.q.rotate(1-len(self.q))  这里和下面循环是一样的效果
        for _ in range(len(self.q)-1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]
        
    def empty(self) -> bool:
        return not self.q

295. Find Median from Data Stream

找出数据流中的中位数。原题

思路：使用两个堆，最大堆存储较小的数据，最小堆存储较大的数据。添加数字时，先添加到最大堆，然后最大堆返回一个最大的数字给最小堆，最后为了平衡，可能需要最小堆还给最大堆一个最小值，以保证最大堆的长度>=最小堆的长度。由于headpq是最小堆，所以使用取反实现最大堆。添加数字：Time-O(logn)，取出中位数：Time-O(1)。

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
Adding number 41
MaxHeap lo: [41]           // MaxHeap stores the largest value at the top (index 0)
MinHeap hi: []             // MinHeap stores the smallest value at the top (index 0)
Median is 41
=======================
Adding number 35
MaxHeap lo: [35]
MinHeap hi: [41]
Median is 38
=======================
Adding number 62
MaxHeap lo: [41, 35]
MinHeap hi: [62]
Median is 41
=======================
Adding number 4
MaxHeap lo: [35, 4]
MinHeap hi: [41, 62]
Median is 38
=======================
Adding number 97
MaxHeap lo: [41, 35, 4]
MinHeap hi: [62, 97]
Median is 41
=======================
Adding number 108
MaxHeap lo: [41, 35, 4]
MinHeap hi: [62, 97, 108]
Median is 51.5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import heapq as hq

class MedianFinder:

    def __init__(self):
        self.lo, self.hi = [], []  # lo is max_heap, hi is min_heap
        
    def addNum(self, num):
        hq.heappush(self.lo, -num)
        hq.heappush(self.hi, -hq.heappop(self.lo))
        
        if len(self.lo) < len(self.hi):
            hq.heappush(self.lo, -hq.heappop(self.hi))       

    def findMedian(self):
        if len(self.lo) == len(self.hi):
            return (-self.lo[0]+self.hi[0]) / 2.0
        else:
            return float(-self.lo[0])

480. Sliding Window Median

滑动窗口中的中位数。这题基于295的思想，但是要比其难处理的多。

1
2
3
4
5
6
7
8
Window position                Median
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6

方法一：我自己的思路是到了最大堆最小堆，不知道如何删除左侧窗口废弃的元素。看了讨论区知道了，要把索引加进去，但是当一个废弃的索引， 不在堆首无法将其剔除时，就是影响两个堆的长度，那么从而影响中位数的判断。这是这段代码的核心。首先，不能够像295那样，通过两个堆的长度来平衡，因为堆中可能含有废弃的元素，这里使用的是懒删除。然后尽量保证hi 即最小堆的长度较大，当要删除一个数时，判断这个数是在最大堆还是最小堆。如果是在lo中，则从hi补齐一个元素到lo中，因为平衡两个堆时不考虑将来要被删除的元素。20~27行是这段代码能正常运作的核心。

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
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
    lo, hi  = [], [(n, i) for i, n in enumerate(nums[:k])]  # lo is maxheap, hi is minheap
    heapq.heapify(hi)
    ans = []
    
    def get_med(odd=True):
        if odd:
            return hi[0][0]
        else:
            return (-lo[0][0] + hi[0][0]) / 2
        
    def move(h1, h2):
        x, i = heapq.heappop(h1)
        heapq.heappush(h2, (-x, i))
    for _ in range(k//2): 
        move(hi, lo)
    # print(lo, hi)
    ans.append(get_med(k&1))
    for i, n in enumerate(nums[k:], k):
        if n >= hi[0][0]:
            heapq.heappush(hi, (n, i))
            if nums[i-k] <= hi[0][0]:
                move(hi, lo)
        else:
            heapq.heappush(lo, (-n, i))
            if nums[i-k] >= hi[0][0]:
                move(lo, hi)
        while lo and lo[0][1] <= i-k:
            heapq.heappop(lo)
        while hi and hi[0][1] <= i-k:
            heapq.heappop(hi)
        # print(lo, hi)
        ans.append(get_med(k&1))
        
    return ans

方法二：还是stefan的方法好，比赛能做出来起码。

1
2
3
4
5
6
7
8
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
    window = sorted(nums[:k])
    ans = []
    for a, b in zip(nums, nums[k:] + [0]):
        ans.append((window[k//2]+window[~k//2]) / 2)
        window.remove(a)
        bisect.insort(window, b)
    return ans
方法三：bisect.insort的时间复杂度为O(n)。这里使用SortedList可以优化到O(logn)。 
1
2
3
4
5
6
7
8
9
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
    from sortedcontainers import SortedList
    window = SortedList(nums[:k])
    res = []
    for a, b in zip(nums, nums[k:]+[0]):
        res.append((window[k//2]+window[~k//2]) / 2)
        window.remove(a)
        window.add(b)
    return res

535. Encode and Decode TinyURL

设计一个短链接。原题

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
class Codec:
    
    BASE = 62
    UPPERCASE_OFFSET = 55
    LOWERCASE_OFFSET = 61
    DIGIT_OFFSET = 48
    num_sender = 0
    url = {}

    def encode(self, longUrl):
        """Encodes a URL to a shortened URL.
        
        :type longUrl: str
        :rtype: str
        """
        
        if Codec.num_sender == 0:
            Codec.url[Codec.num_sender] = longUrl
            return '0'
        s_url = ''
        while Codec.num_sender > 0:
            tail = Codec.num_sender % Codec.BASE
            s_url = self.parse_chr(tail) + s_url
            Codec.num_sender //= Codec.BASE
        
        Codec.url[Codec.num_sender] = longUrl
        Codec.num_sender += 1
        return s_url
        
    def decode(self, shortUrl):
        """Decodes a shortened URL to its original URL.
        
        :type shortUrl: str
        :rtype: str
        """
        num = 0
        for i, char in enumerate(reversed(shortUrl)):
            num += self.parse_ord(char) * (Codec.BASE**i)
        return Codec.url[num]
    
    def parse_ord(self, char):
        if char.isdigit():
            return ord(char) - Codec.DIGIT_OFFSET
        elif char.islower():
            return ord(char) - Codec.LOWERCASE_OFFSET
        elif char.isupper():
            return ord(char) - Codec.UPPERCASE_OFFSET
        else:
            raise ValueError('%s is not a valid character' % char)
            
    def parse_chr(self, integer):
        if integer < 10:
            return chr(integer + DIGIT_OFFSET)
        elif 10 <= integer <= 35:
            return chr(integer + UPPERCASE_OFFSET)
        elif 36 <= integer < 62:
            return chr(integer + LOWERCASE_OFFSET)
        else:
            raise ValueError('%d is not a valid integer in the range of base %d' % (integer, Codec.BASE))

方法二：使用字典保存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Codec:
    BASE = 62
    num_sender = 0
    ALNUM = string.ascii_letters + '0123456789'
    d_map = {c: i for i, c in enumerate(ALNUM)}
    url = {}

    def encode(self, longUrl):
        pk = Codec.num_sender
        s_url = ''
        while pk > 0:
            pk, tail = divmod(pk, Codec.BASE)
            s_url = Codec.ALNUM[tail] + s_url

        Codec.url[pk] = longUrl
        Codec.num_sender += 1
        if pk == 0:
            s_url = Codec.ALNUM[0]
        return s_url 

    def decode(self, shortUrl):
        pk = sum(Codec.d_map[c]*Codec.BASE**i 
                 for i, c in enumerate(reversed(shortUrl)))
        return Codec.url[pk]

707. Design Linked List

设计一个链表。原题

1
2
3
4
5
6
7
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2);  // linked list becomes 1->2->3
linkedList.get(1);            // returns 2
linkedList.deleteAtIndex(1);  // now the linked list is 1->3
linkedList.get(1);            // returns 3
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
class ListNode:
    
    def __init__(self, val):
        self.val = val
        self.next = None
    
class MyLinkedList:

    def __init__(self):
        self.head = None
        self.size = 0

    def get(self, index: 'int') -> 'int':
        if index < 0 or index >= self.size or \
            self.head is None:
            return -1
        return self.findIndex(index).val
        
    def addAtHead(self, val: 'int') -> 'None':
        self.addAtIndex(0, val)
        
    def addAtTail(self, val: 'int') -> 'None':
        self.addAtIndex(self.size, val)
        
    def addAtIndex(self, index: 'int', val: 'int') -> 'None':
        if index > self.size:
            return -1
        elif index == 0:
            head = ListNode(val)
            head.next, self.head = self.head, head
        else:
            pre = self.findIndex(index-1)
            cur = ListNode(val)
            cur.next, pre.next = pre.next, cur
        self.size += 1
        
    def deleteAtIndex(self, index: 'int') -> 'None':
        if index < 0 or index >= self.size:
            return -1
        cur = self.findIndex(index-1)
        cur.next = cur.next.next
        self.size -= 1
        
    def findIndex(self, index: 'int') -> 'None':
        cur = self.head
        for _ in range(index):
            cur = cur.next
        return cur

146. LRU Cache

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4
方法一：使用OrderedDict.

开始有两个testcase没过，一个是{2: 3, 1: 1}更新2时，和{1: 1, 2: 3}更新2时，二者都可以使用先pop再更新的方式。remain的方式是从discuss学来的，之前还用len或额外的size来保存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class LRUCache:
    def __init__(self, capacity: 'int'):
        self.cache = collections.OrderedDict()
        self.remain = capacity

    def get(self, key: 'int') -> 'int':
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache.get(key)

    def put(self, key: 'int', value: 'int') -> 'None':
        if key not in self.cache:
            if self.remain > 0:
                self.remain -= 1
            else:
                self.cache.popitem(last=False)
        else:
            self.cache.pop(key)
        self.cache[key] = value

方法二：不使用OrderedDict

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
class DLinkedNode:
    
    def __init__(self, key=0, value=0):
        self.key = key
        self.val = value
        self.next = None
        self.prev = None
        
#     def __repr__(self):
#         return '<DLinkedNode: ({}, {})>'.format(self.key, self.val)
        

class DLinkedList:
    
    def __init__(self):
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next, self.tail.prev = self.tail, self.head
        
    def add_node(self, node):
        node.prev, node.next = self.head, self.head.next
        node.next.prev, node.prev.next = node, node
        
    def remove_node(self, node):
        node.prev.next, node.next.prev = node.next, node.prev
        return node.key
        
    def remove_tail(self):
        key = self.tail.prev.key
        return self.remove_node(self.tail.prev)
        
    def move_to_head(self, node):
        self.remove_node(node)
        self.add_node(node)
        
    # def __repr__(self):
    #     ans = []
    #     h = self.head
    #     while h:
    #         ans.append(str(h.val))
    #         h = h.next
    #     return '<DLinkedList: {}>'.format('->'.join(ans))
        
    
class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes = {}
        self.cache = DLinkedList()

    def get(self, key: int) -> int:
        node = self.nodes.get(key, None)
        if node:
            self.cache.move_to_head(node)
            return node.val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        node = self.nodes.get(key, None)
        if not node:
            if self.capacity > 0:
                self.capacity -= 1
            else:
                rm_key = self.cache.remove_tail()
                self.nodes.pop(rm_key)
            new_node = DLinkedNode(key, value)
            self.nodes[key] = new_node
            self.cache.add_node(new_node)
        else:
            self.cache.move_to_head(node)
            node.val = value

460. LFU Cache

设计一个LFU缓存。

方法一：简单地看了一下题解后，写了半个下午。需要考虑的地方确实很多。其它的地方都还好，关于min_freq的更新处踩了一个坑，就是必须得是当前最小的空了以后，再更新它。为了兼容capacity为0的情况，在DLinkedList中添加了count变量。

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
class DLinkedNode:
    
    def __init__(self, key=0, value=0, freq=1):
        self.key = key
        self.val = value
        self.freq = freq
        self.next = None
        self.prev = None


class DLinkedList:

    def __init__(self):
        self.count = 0
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next, self.tail.prev = self.tail, self.head

    def add_node(self, node):
        self.count += 1
        node.prev, node.next = self.head, self.head.next
        node.next.prev, self.head.next = node, node

    def remove_node(self, node):
        if self.count > 0:
            self.count -= 1
            node.prev.next = node.next
            node.next.prev = node.prev

    def remove_tail(self):
        key = self.tail.prev.key
        self.remove_node(self.tail.prev)
        return key

    def is_empty(self):
        return self.count == 0


class LFUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 1
        self.freq_map = defaultdict(DLinkedList)
        self.key_map = {}
        self.is_empty = capacity==0

    def get(self, key: int) -> int:
        if self.is_empty: return -1
        node = self.key_map.get(key, None)
        if node:
            self.increase_freq(node)
            return node.val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if self.is_empty: return 
        node = self.key_map.get(key, None)
        if not node:
            if self.capacity > 0:
                self.capacity -= 1
            else:
                r_key = self.freq_map[self.min_freq].remove_tail()
                self.key_map.pop(r_key, -1)
                
            new_node = DLinkedNode(key, value)
            self.freq_map[1].add_node(new_node)
            self.min_freq = 1
            self.key_map[key] = new_node
        else:
            node.val = value
            self.increase_freq(node)
    
    def increase_freq(self, node):
        freq = node.freq
        self.freq_map[freq].remove_node(node)
        freq += 1
        if self.freq_map[freq-1].is_empty():
            if self.min_freq == freq - 1:
                self.min_freq = freq
        node.freq = freq
        self.freq_map[freq].add_node(node)

1381. Design a Stack With Increment Operation

设计一个栈，实现一个将k个栈底元素全部增加val的方法。原题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack customStack = new CustomStack(3); // Stack is Empty []
customStack.push(1);                          // stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.push(3);                          // stack becomes [1, 2, 3]
customStack.push(4);                          // stack still [1, 2, 3], Don't add another elements as size is 4
customStack.increment(5, 100);                // stack becomes [101, 102, 103]
customStack.increment(2, 100);                // stack becomes [201, 202, 103]
customStack.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
customStack.pop();                            // return 202 --> Return top of the stack 102, stack becomes [201]
customStack.pop();                            // return 201 --> Return top of the stack 101, stack becomes []
customStack.pop();                            // return -1 --> Stack is empty return -1.

方法一：普通的方法不记录了，这里学到一个延迟增加的方法。因为值的增加只有在pop的时候才会体现，所以维护了一个inc用来累加增加的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class CustomStack:

    def __init__(self, maxSize: int):
        self.stack = []
        self.max_size = maxSize
        self.inc = []

    def push(self, x: int) -> None:
        if len(self.stack) < self.max_size:
            self.stack.append(x)
            self.inc.append(0)

    def pop(self) -> int:
        if not self.stack: return -1
        if len(self.inc) > 1:
            self.inc[-2] += self.inc[-1]
        return self.inc.pop() + self.stack.pop()

    def increment(self, k: int, val: int) -> None:
        if self.inc:
            self.inc[min(k, len(self.inc))-1] += val

208. Implement Trie (Prefix Tree)

实现一个单词查找树。原题

1
2
3
4
5
6
7
8
Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

方法一：我的常规节点方法。

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
class TrieNode:
    
    def __init__(self):
        self.child = collections.defaultdict(TrieNode)
        self.is_word = False

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        cur = self.root
        for letter in word:
            cur = cur.child[letter]
        cur.is_word = True

    def search(self, word: str) -> bool:
        cur = self.root
        for letter in word:
            cur = cur.child.get(letter)
            if not cur:
                return False
        return cur.is_word

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for letter in prefix:
            cur = cur.child.get(letter)
            if not cur:
                return False
        return True

方法二：reduce的妙用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Trie(object):

    def __init__(self):
        T = lambda: collections.defaultdict(T)
        self.root = T()

    def insert(self, word):
        reduce(dict.__getitem__, word, self.root)['#'] = True

    def search(self, word):
        return '#' in reduce(lambda cur, c: cur.get(c, {}), word, self.root)

    def startsWith(self, prefix):
        return bool(reduce(lambda cur, c: cur.get(c, {}), prefix, self.root))

380. Insert Delete GetRandom O(1)

设计一个类，插入删除，随机都是O(1)。原题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

方法一：解法的思想有点像删除链表，是一种覆盖的思想。主要是删除时用最后的元素将其覆盖，然后再将末尾的元素删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class RandomizedSet:

    def __init__(self):
        self.nums, self.pos = [], {}

    def insert(self, val: int) -> bool:
        if val not in self.pos:
            self.nums.append(val)
            self.pos[val] = len(self.nums)-1
            return True
        return False
        
    def remove(self, val: int) -> bool:
        if val in self.pos:
            idx, last = self.pos[val], self.nums[-1]
            self.nums[idx], self.pos[last] = last, idx
            self.nums.pop()
            self.pos.pop(val)
            return True
        return False

    def getRandom(self) -> int:
        return random.choice(self.nums)

341. Flatten Nested List Iterator

扁平化一个嵌套的List迭代器，NestedInteger是一个类。原题

1
2
3
4
Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,1,2,1,1].

方法一：这里设计时考虑了，next之前可能不会调用hasNext。因为正常来说一个生成器就是这样的。

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
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        
        def flatten(items):
            for x in items:
                if x.getInteger() is not None:
                    yield x.getInteger()
                else:
                    yield from flatten(x.getList())
                    
        self.g = flatten(nestedList)
        self.buff = None
    
    def next(self) -> int:
        if self.buff is not None:
            ans = self.buff
            self.buff = None
            return ans
        else:
            return next(self.g)
    
    def hasNext(self) -> bool:
        if self.buff is not None: return True
        try:
            self.buff = next(self.g)
            return True
        except StopIteration:
            return False

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

5525. 皇位继承顺序

啰里啰嗦一大堆，实际上就是让见一个家族图谱，然后先序遍历。

方法一：比赛的时候想到了N叉树，但是设计上没想好怎么通过family节点融合。所以直接用的defaultdict做的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class ThroneInheritance:

    def __init__(self, kingName: str):
        self.g = defaultdict(list)
        self.king = kingName
        self.d = set()

    def birth(self, parentName: str, childName: str) -> None:
        self.g[parentName].append(childName)

    def death(self, name: str) -> None:
        self.d.add(name)

    def getInheritanceOrder(self) -> List[str]:
        ans = []
        
        def dfs(p):
            if p not in self.d:
                ans.append(p)
            for children in self.g[p]:
                dfs(children)
        dfs(self.king)
        return ans

方法二：使用多叉树模拟。

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
class Person:

    def __init__(self, name):
        self.name = name
        self.children = []
        self.alive = True
    

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.root = Person(kingName)
        self.family = {kingName: self.root}

    def birth(self, parentName: str, childName: str) -> None:
        child = Person(childName)
        self.family[parentName].children.append(child)
        self.family[childName] = child

    def death(self, name: str) -> None:
        self.family[name].alive = False

    def getInheritanceOrder(self) -> List[str]:
        
        def dfs(node):
            if node:
                if node.alive:
                    yield node.name
                for child in node.children:
                    yield from dfs(child)

        return list(dfs(self.root))

432. All O`one Data Structure

实现一个数据结构使所有的操作在O(1)时间复杂度。某个Key计数+1或者-1，返回最多、最少的key其中的一个。

方法一：这道题有难度而且实现很复杂，我开始的时候想着以LFU的形式来解，写到最后发现一个问题就是，当一个key的计数变为0的时候，我没法维护一个min_freq来记录最小的计数。对我来说此题首先要打破常规，之前总是认为Node节点就装node，其实这里可以装上一整个key的集合。整体上实现一个双链表，每一个单节点里对应了某些key的集合。节点按照计数顺序增序排列，使用node_freq字典来定位每个频率的节点。

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
class DLinkedNode:

    def __init__(self):
        self.keys = set()
        self.next = None
        self.prev = None

    def add_key(self, key):
        self.keys.add(key)

    def remove_key(self, key):
        self.keys.remove(key)

    def get_any_key(self):
        if self.keys:
            key = self.keys.pop()
            self.keys.add(key)
            return key
        else:
            return None

    def __len__(self):
        return len(self.keys)

    def is_empty(self):
        return len(self) == 0


class DLinkedList:

    def __init__(self):
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next, self.tail.prev = self.tail, self.head

    def insert_after(self, x):
        node = DLinkedNode()
        node.prev, node.next = x, x.next
        node.next.prev, node.prev.next = node, node
        return node
   
    def insert_before(self, x):
        return self.insert_after(x.prev)

    def remove(self, x):
        x.prev.next, x.next.prev = x.next, x.prev

    def get_head(self):
        return self.head.next
    
    def get_tail(self):
        return self.tail.prev

    def get_sentinel_head(self):
        return self.head

    def get_sentinel_tail(self):
        return self.tail


class AllOne:

    def __init__(self):
        self.dll, self.key_counter = DLinkedList(), defaultdict(int)
        self.node_freq = {0: self.dll.get_sentinel_head()}

    def _rmv_key_pf_node(self, pf, key):
        node = self.node_freq[pf]
        node.remove_key(key)
        if node.is_empty():
            self.dll.remove(node)
            self.node_freq.pop(pf)

    def inc(self, key: str) -> None:
        self.key_counter[key] += 1
        cf, pf = self.key_counter[key], self.key_counter[key]-1
        if cf not in self.node_freq:
            # No need to test if pf = 0 since frequency zero points to sentinel node
            self.node_freq[cf] = self.dll.insert_after(self.node_freq[pf])
        self.node_freq[cf].add_key(key)
        if pf > 0:
            self._rmv_key_pf_node(pf, key)

    def dec(self, key: str) -> None:
        if key in self.key_counter:
            self.key_counter[key] -= 1
            cf, pf = self.key_counter[key], self.key_counter[key]+1
            if self.key_counter[key] == 0:
                self.key_counter.pop(key)
            if cf != 0:
                if cf not in self.node_freq:
                    self.node_freq[cf] = self.dll.insert_before(self.node_freq[pf])
                self.node_freq[cf].add_key(key)
            self._rmv_key_pf_node(pf, key)
       
    def getMaxKey(self) -> str:
        return self.dll.get_tail().get_any_key() if len(self.dll.get_tail()) > 0 else ""

    def getMinKey(self) -> str:
        return self.dll.get_head().get_any_key() if len(self.dll.get_tail()) > 0 else ""

1670. Design Front Middle Back Queue

设计一个可以从中间入队出队的队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input:
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
Output:
[null, null, null, null, null, 1, 3, 4, 2, -1]

Explanation:
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1);   // [1]
q.pushBack(2);    // [1, 2]
q.pushMiddle(3);  // [1, 3, 2]
q.pushMiddle(4);  // [1, 4, 3, 2]
q.popFront();     // return 1 -> [4, 3, 2]
q.popMiddle();    // return 3 -> [4, 2]
q.popMiddle();    // return 4 -> [2]
q.popBack();      // return 2 -> []
q.popFront();     // return -1 -> [] (The queue is empty)

方法一：比赛时用的双端队列，一开始想的3个，后来想2个就够了。

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
class FrontMiddleBackQueue:

    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()
    
    def pushFront(self, val: int) -> None:
        self.q1.appendleft(val)
        if len(self.q1) > len(self.q2) + 1:
            self.q2.appendleft(self.q1.pop())

    def pushMiddle(self, val: int) -> None:
        if len(self.q1) > len(self.q2):
            self.q2.appendleft(self.q1.pop())
        self.q1.append(val)

    def pushBack(self, val: int) -> None:
        self.q2.append(val)
        if len(self.q2) > len(self.q1):
            self.q1.append(self.q2.popleft())

    def popFront(self) -> int:
        if not self.q1:
            return -1
        ans = self.q1.popleft()
        if len(self.q2) > len(self.q1):
            self.q1.append(self.q2.popleft())
        return ans
        
    def popMiddle(self) -> int:
        if not self.q1:
            return -1
        ans = self.q1.pop()
        if len(self.q2) > len(self.q1):
            self.q1.append(self.q2.popleft())
        return ans

    def popBack(self) -> int:
        if not self.q2:
            if not self.q1:
                return -1
            self.q2.appendleft(self.q1.pop())
    
        ans = self.q2.pop()
        if len(self.q1) > len(self.q2) + 1:
            self.q2.appendleft(self.q1.pop())
        return ans

方法二：整理一下方法一。

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
class FrontMiddleBackQueue:

    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()
    
    def pushFront(self, val: int) -> None:
        self.q1.appendleft(val)
        self.balance()

    def pushMiddle(self, val: int) -> None:
        if len(self.q1) > len(self.q2):
            self.q2.appendleft(self.q1.pop())
        self.q1.append(val)

    def pushBack(self, val: int) -> None:
        self.q2.append(val)
        self.balance()

    def popFront(self) -> int:
        if not self.q1:
            return -1
        ans = self.q1.popleft()
        self.balance()
        return ans
        
    def popMiddle(self) -> int:
        if not self.q1:
            return -1
        ans = self.q1.pop()
        self.balance()
        return ans

    def popBack(self) -> int:
        if not self.q2:
            if not self.q1:
                return -1
            self.q2.appendleft(self.q1.pop())
    
        ans = self.q2.pop()
        self.balance()
        return ans

    def balance(self):
        if len(self.q1) > len(self.q2) + 1:
            self.q2.appendleft(self.q1.pop())
        elif len(self.q2) > len(self.q1):
            self.q1.append(self.q2.popleft())

方法三：竞赛中直接使用复杂度较高的方法也能过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class FrontMiddleBackQueue:

    def __init__(self):
        self.q = []

    def pushFront(self, val: int) -> None:
        self.q.insert(0, val)

    def pushMiddle(self, val: int) -> None:
        self.q.insert(len(self.q)//2, val)

    def pushBack(self, val: int) -> None:
        self.q.append(val)

    def popFront(self) -> int:
        return self.q.pop(0) if self.q else -1

    def popMiddle(self) -> int:
        return self.q.pop((len(self.q)-1)//2) if self.q else -1

    def popBack(self) -> int:
        return self.q.pop() if self.q else -1

1825. Finding MK Average

找到M滑动窗口数据流中去除前后K个最大最小值的平均数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]
[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]
Output
[null, null, null, -1, null, 3, null, null, null, 5]

Explanation
MKAverage obj = new MKAverage(3, 1); 
obj.addElement(3);        // current elements are [3]
obj.addElement(1);        // current elements are [3,1]
obj.calculateMKAverage(); // return -1, because m = 3 and only 2 elements exist.
obj.addElement(10);       // current elements are [3,1,10]
obj.calculateMKAverage(); // The last 3 elements are [3,1,10].
                          // After removing smallest and largest 1 element the container will be [3].
                          // The average of [3] equals 3/1 = 3, return 3
obj.addElement(5);        // current elements are [3,1,10,5]
obj.addElement(5);        // current elements are [3,1,10,5,5]
obj.addElement(5);        // current elements are [3,1,10,5,5,5]
obj.calculateMKAverage(); // The last 3 elements are [5,5,5].
                          // After removing smallest and largest 1 element the container will be [5].
                          // The average of [5] equals 5/1 = 5, return 5

方法一：这题暴力居然过了。。10**5的数据集，暴力排序就过了。实际上比赛的时候想到了数据流中的中位数，想着用队列和堆来解决。但是堆不好解决删除的问题。此题应该用SortedList。这里不清楚python底层是用什么平衡树实现的。

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
from sortedcontainers import SortedList
class MKAverage:

    def __init__(self, m: int, k: int):
        self.m, self.k = m, k
        self.q = collections.deque()
        self.sl = SortedList()
        self.total = self.first_k = self.last_k = 0

    def addElement(self, num: int) -> None:
        self.total += num
        self.q.append(num)
        index = self.sl.bisect_left(num)
        if index < self.k:
            self.first_k += num
            if len(self.sl) >= self.k:
                self.first_k -= self.sl[self.k-1]
        if index >= len(self.sl) + 1 - self.k:
            self.last_k += num
            if len(self.sl) >= self.k:
                self.last_k -= self.sl[-self.k]
        self.sl.add(num)
        if len(self.q) > self.m:
            num = self.q.popleft()
            self.total -= num
            index = self.sl.index(num)
            if index < self.k:
                self.first_k -= num
                self.first_k += self.sl[self.k]
            elif index >= len(self.sl) - self.k:
                self.last_k -= num
                self.last_k += self.sl[-self.k-1]
            self.sl.remove(num)

    def calculateMKAverage(self) -> int:
        if len(self.sl) < self.m:
            return -1
        else:
            return (self.total-self.first_k-self.last_k) // (self.m - 2 * self.k)