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)
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
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
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
剑指 Offer II 053. 二叉搜索树中的中序后继
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
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
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
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
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
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/76876.html
