红黑树刷题（上）

981. 基于时间的键值存储

class TimeMap:

    def __init__(self):
        self.data = dict()

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.data:
            self.data[key] = list()
        self.data[key].append((timestamp, value))


    def get(self, key: str, timestamp: int) -> str:
        if key not in self.data:
            return ""
        vals = self.data[key]
        if timestamp >= vals[-1][0]:
            return vals[-1][1]
        if timestamp < vals[0][0]:
            return ""
        idx = self.bs(vals, timestamp, 0, len(vals) - 1)
        return vals[idx - 1][1] if idx - 1>= 0 else ""
    
    def bs(self, nums, timestamp, l, r):
        if l >= r: return l 
        mid = (l + r) // 2
        if nums[mid][0] > timestamp:
            return self.bs(nums, timestamp, l, mid)
        else:
            return self.bs(nums, timestamp, mid + 1, r)
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)
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

971. 翻转二叉树以匹配先序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorder(self, root, voyage, ans):
        if not root: return True 
        if root.val != voyage[self.idx]:
            ans *= 0
            ans.append(-1)
            return False 
        self.idx += 1
        if root.left and root.left.val != voyage[self.idx]:
            root.left, root.right = root.right, root.left
            ans.append(root.val)
        if not self.preorder(root.left ,voyage, ans): return False
        if not self.preorder(root.right, voyage ,ans): return False
        return True
    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:
        ans = []
        self.idx = 0
        self.preorder(root, voyage, ans)
        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

1339. 分裂二叉树的最大乘积

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getSum(self, root):
        if not root: return 0
        sum_val = root.val + self.getSum(root.left) + self.getSum(root.right)
        if abs(sum_val  - self.target) < abs(self.ans - self.target):
            self.ans = sum_val
        return sum_val
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        self.ans = 0
        self.target = 0
        sum_val = self.getSum(root)
        self.target = sum_val // 2
        self.getSum(root)
        return self.ans * (sum_val - self.ans) % 1000000007
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

449. 序列化和反序列化二叉搜索树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string.
        """
        def preorder(root):
            if not root: return []
            return [root.val] + preorder(root.left) + preorder(root.right)
        return ','.join(map(str, preorder(root)))     
    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.
        """
        if not data: return None
        pres = list(map(int, data.split(',')))
        return self.buildtree(pres, 0, len(pres) - 1)
    def buildtree(self, nums, l, r):
        if l > r:return None
        mid = l + 1
        while mid <= r and nums[l] > nums[mid]: mid += 1
        root  = TreeNode(nums[l])
        root.left = self.buildtree(nums, l + 1, mid - 1)
        root.right = self.buildtree(nums, mid, r)
        return root
        

# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# 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

剑指 Offer II 053. 二叉搜索树中的中序后继

1

117. 填充每个节点的下一个右侧节点指针 II

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root: return None 
        queue = root
        while queue:
            newhead = None
            pre = None
            while queue:
                if queue.left:
                    if not newhead: newhead = queue.left 
                    if pre: pre.next = queue.left
                    pre = queue.left
                if queue.right:
                    if not newhead: newhead = queue.right
                    if pre: pre.next = queue.right
                    pre = queue.right
                queue = queue.next
            queue = newhead
        return root 
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

78. 子集

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        I = 1 << n
        mark = dict()
        j = 1
        ans = []
        for i in range(10):
            mark[j] = i 
            j <<= 1
        for i in range(I):
            data = i 
            arr = []
            while data:
                idx = data & -data
                arr.append(nums[mark[idx]])
                data &= data - 1
            ans.append(arr)
        return ans 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

220. 存在重复元素 III

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        bucket = dict()
        if t < 0: return False 
        for i in range(len(nums)):
            key = nums[i] // (t + 1)
            if key in bucket:
                return True 
            if key - 1 in bucket and abs(nums[i] - bucket[key - 1]) <= t:
                return True
            if key + 1 in bucket and abs(nums[i] - bucket[key + 1]) <= t:
                return True
            bucket[key] = nums[i]
            if i >= k: bucket.pop(nums[i - k] // (t + 1))
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

47. 全排列 II

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        def dfs(nums, buff, n, vis):
            if len(buff) == n:
                ans.append(buff[:])
            for i in range(n):
                if vis[i] or (i > 0 and nums[i] == nums[i - 1] and not vis[i - 1]): continue 
                buff.append(nums[i])
                vis[i] = 1
                dfs(nums, buff, n, vis)
                buff.pop()
                vis[i] = 0
        vis = [0] * len(nums)
        ans = []
        dfs(nums, [], len(nums), vis)
        return ans 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

41. 缺失的第一个正数

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            while nums[i] != i + 1:
                if nums[i] <= 0 or nums[i] >= len(nums) + 1: break
                if nums[nums[i] - 1] == nums[i]: break 
                idx = nums[i] - 1
                nums[i], nums[idx] = nums[idx], nums[i]
        idx = 0
        while idx < len(nums) and nums[idx] == idx + 1: idx += 1
        return idx + 1

1
2
3
4
5
6
7
8
9
10
11
12