以后把每天做的题做个简单的记录,方便后面总结
0X00 leetcode 做了六道
- 二叉树中的最大路径和 (124)
- 在二叉树中分配硬币 (979)
- 搜索插入位置 (35)
- 在排序数组中查找元素的第一个和最后一个位置(34)
- 基于时间的键值存储(981)
- 二分查找(704)
0X01 每道题的小小记录
二叉树中的最大路径和 (124)
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.ans = float('-Infinity')
def postorder(root):
if root is None: return 0
l = max(0, postorder(root.left))
r = max(0, postorder(root.right))
self.ans = max(l+r+root.val, self.ans)
return max(l, r) + root.val
postorder(root)
return self.ans
hard 题关键在于理解题目:
一段最长路径必须包括子树的根节点
但最长路径不需要一定包含整棵树的根节点
所以我们应该自底向上记录最长路径,而不是去取包含根节点的最长路径
在二叉树中分配硬币 (979)
class Solution:
def distributeCoins(self, root: TreeNode) -> int:
self.ans = 0
def postorder(root):
if root is None:return 0
l = postorder(root.left)
r = postorder(root.right)
self.ans += abs(l) + abs(r)
return l + r + root.val - 1
postorder(root)
return self.ans
中等难度,这道题也是自底向上,后续遍历
关键在于理解:让父节点去处理子节点的硬币分配,但是要子节点去告诉父节点,需要怎么分配
搜索插入位置 (35)
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target: return mid
elif nums[mid] > target: right = mid - 1
else: left = mid + 1
return left
简单难度,这是一道模板题目,要永远记住这个模板.其中 left 就是最后的插入位置
且 left 的范围是 [0, len]
在排序数组中查找元素的第一个和最后一个位置(34)
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left, right = 0, len(nums) - 1
idx = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
idx = mid
break
elif nums[mid] > target: right = mid - 1
else: left = mid + 1
if idx == -1:
return [-1, -1]
left = right = idx
while right < len(nums) and nums[right] == target:
right += 1
right -= 1
while left > -1 and nums[left] == target:
left -= 1
left += 1
return [left, right]
35 模板改的
基于时间的键值存储(981)
class TimeMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.Map = {}
def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.Map:
self.Map[key] = [(timestamp, value)]
else:
self.Map[key].append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
if key not in self.Map: return ""
values = self.Map[key]
left, right = 0, len(values) - 1
while left <= right:
mid = left + (right - left) // 2
if timestamp == values[mid][0]:
return values[mid][1]
elif timestamp > values[mid][0]: left = mid + 1
else: right = mid - 1
if left > 0: return values[left-1][1]
return ""
根据 35 模板改的
二分查找(704)
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target: return mid
elif nums[mid] > target: right = mid - 1
else: left = mid + 1
return -1
35 模板改的
