KK's blog

LeetCode 729 My Calendar I

Posted on 2021-12-31 Edited on 2026-06-03 Disqus:

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

MyCalendar() Initializes the calendar object. boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Example 1:

Input
[“MyCalendar”, “book”, “book”, “book”]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

Constraints:

0 <= start < end <= 10<sup>9</sup> At most 1000 calls will be made to book.

暴力法算法思路(推荐)：

存储所有区间

注意事项：

区间比较难写，用符合加入会议条件的相反来写，not (start >= root.end or end <= root.start)

Python代码：

class MyCalendar(TestCases):

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

    def book(self, start: int, end: int) -> bool:
        for s, e in self.calendar:
            if not (start >= e or end <= s):
                return False
        self.calendar.append((start, end))
        return True

算法分析：

时间复杂度为O(n²), 空间复杂度O(n)

端点排序法解题思路II：

区间重合题考虑用heap或者端点排序法，输入是必须有序，所以此题可以令区间有序，而heap用于处理重合情况下的计算，此题不适用，所以用端点排序法。

解题步骤：

N/A

注意事项：

区间端点排序，(endpoint, 1/-1), 1表示始点，-1表示终点。用bisect搜索时，注意输入也要用两维(start, 1)
难点在于比较结果决定返回Ture or False。两种情况返回False：好的情况是输入区间的搜索结果的下标应该相等表示可以插入到现有两区间之间，所以若不等，就不符合。第二种是若现有区间完全覆盖新区间，此时搜索结果下标也一样，所以此情况新区间终点的搜索结果(后一个节点)是终点。同时为保证搜索结果不处理越界，加入空端点
若同一个端点同时存在始点和端点，不用合并，因为它们已经按-1, 1排序了。

Python代码：

class MyCalendar(TestCases):

    def __init__(self):
        self.calendar = [(float('-inf'), -1), (float('inf'), 1)]

    def book(self, start: int, end: int) -> bool:
        index_start = bisect.bisect(self.calendar, (start, 1)) # remember params
        index_end = bisect.bisect(self.calendar, (end, -1))
        if index_start != index_end or self.calendar[index_end][1] == -1:
            return False
        # no need to merge endpoints coz they are sorted in (a, -1), (a, 1) as expected
        bisect.insort(self.calendar, (start, 1))
        bisect.insort(self.calendar, (end, -1))
        return True

算法分析：

时间复杂度为O(n²)，由于insort是插入需要移动数组，所以是O(n), 空间复杂度O(n)

线段树算法III思路(不推荐)：

区间重合题考虑用heap类似meeting rooms，输入是必须有序，但这里新区间与已有区间不是有序且不能online处理，所以不能用heap。
考虑用start, end排序，二分法查找，只能处理单次，因为插入不方便。
要查找和插入都能低于O(n)，就只能用TreeMap。类似于线段树存储区间，此题每个Node存储一个区间。新区间的end，start分别与root的start和end比较，若不重合，就递归到左右子树。此树投影为离散且不重合的区间。

注意事项：

考察二叉树插入算法，返回值需要是TreeNode，如root.left = self.dfs(root.left, start, end)。由于需要知道是否成功插入，所以返回值多加一个boolean
区间比较难写，用符合加入会议条件的相反来写，not (start >= root.end or end <= root.start)
is_left or is_right任意一个加入成功都可以，所以是or不是and

Python代码：

class MyCalendar(TestCases):

    def __init__(self):
        self.head = None

    def book(self, start: int, end: int) -> bool:
        root, is_booked = self.dfs(self.head, start, end)
        self.head = root
        return is_booked

    def dfs(self, root, start, end):
        if not root:
            return TreeNode(start, end), True
        #if root.start <= start < root.end or root.start < end <= root.end: # remember
        if not (start >= root.end or end <= root.start):
            return root, False
        is_left = is_right = False
        if end <= root.start:
            root.left, is_left = self.dfs(root.left, start, end)
        else:
            root.right, is_right = self.dfs(root.right, start, end)
        return root, is_left or is_right # remember or

算法分析：

时间复杂度为O(nlogn)，最差情况为O(n²)，空间复杂度O(n)

LeetCode 103 Binary Tree Zigzag Level Order Traversal

Posted on 2021-12-30 Edited on 2026-06-03 Disqus:

LeetCode

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000]. -100 <= Node.val <= 100

题目大意：

按层遍历二叉树。偶数层逆向

解题思路：

用BFS按层遍历模板

解题步骤：

N/A

注意事项：

多这一行level.append(node.val)

Python代码：

def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
	if not root:
		return []
	res = []
	queue = collections.deque([root])
	while queue:
		level = []
		for _ in range(len(queue)):
			node = queue.popleft()
			level.append(node.val)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		if len(res) % 2 == 1:
			res.append(level[::-1])
		else:
			res.append(level)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal

Posted on 2021-12-30 Edited on 2026-06-03 Disqus:

LeetCode

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints:

1 <= preorder.length <= 3000 inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000 preorder and inorder consist of unique values.
Each value of inorder also appears in preorder. preorder is guaranteed to be the preorder traversal of the tree.
inorder is *guaranteed to be the inorder traversal of the tree.

算法思路：

N/A

注意事项：

用递归实现，in_order字符串分左右两段子串递归到左右儿子，pre_order字符串每轮递归用pop(0)原地去除首位，再递归到儿子节点
终止条件为in_order字符串为空。

Python代码：

def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
	if not inorder:
		return None
	head = preorder.pop(0)
	index = inorder.index(head)
	left_inorder, right_inorder = inorder[:index], inorder[index + 1:]

	root = TreeNode(head)
	root.left = self.buildTree(preorder, left_inorder)
	root.right = self.buildTree(preorder, right_inorder)
	return root

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

LeetCode 122 Best Time to Buy and Sell Stock II

Posted on 2021-12-30 Edited on 2026-06-03 Disqus:

LeetCode 122 Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the i<sup>th</sup> day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

`1 <= prices.length <= 3 10⁴*0 <= prices[i] <= 10⁴`

题目大意：

设计一个算法寻找最大收益。你可以随便完成多少次交易（比如，多次买入卖出）。然而你不能一次进行多次交易。

解题思路：

仍然是求最大利润，可以交易多次，但要先卖再买。容易想到是求所有上升坡的的总和。更简单而言，若将每一个上升坡，分成一小段(每天的交易)，求这些小段的和即可。
如：[6, 1, 2, 3, 4]中的1, 2, 3, 4序列来说，对于两种操作方案：
1 在1买入，4卖出
2 在1买入，2卖出同时买入，3卖出同时买入，4卖出
这两种操作下，收益是一样的。这种方法，避免检测下坡以及计算每段的和。

Python代码：

def maxProfit(self, prices: List[int]) -> int:
	res = 0
	for i in range(1, len(prices)):
		if prices[i] - prices[i - 1] > 0:
			res += prices[i] - prices[i - 1]
	return res

注意事项：

数组为空

Java代码：

public int maxProfit(int[] prices) {
	if(prices.length==0)
		return 0;
	int profit = 0;
	for(int i=1;i<prices.length;i++){
		if(prices[i-1]<prices[i])
			profit += prices[i] - prices[i-1];
	}
	return profit;
}

算法分析：

时间复杂度为O(n)，n为字符串长度，空间复杂度O(1)。

LeetCode 039 Combination Sum

Posted on 2021-12-29 Edited on 2026-06-03 Disqus:

LeetCode

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

1 <= candidates.length <= 30 1 <= candidates[i] <= 200
All elements of candidates are distinct. 1 <= target <= 500

题目大意：

求组合和等于目标。元素可以复用

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

用标准组合模板dfs(self, candidates, start, target, path, res)，元素可以复用，所以下一轮递归从i开始
Python中path.pop()没有参数

Python代码：

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
	candidates.sort()
	res = []
	self.dfs(candidates, 0, target, [], res)
	return res

def dfs(self, candidates, start, target, path, res): # [1, 2], 0, 0, [1, 1], [1, 1]
	if target < 0:
		return
	if target == 0:
		res.append(list(path))
		return
	for i in range(start, len(candidates)): # [2]
		path.append(candidates[i]) # [1,1]
		self.dfs(candidates, i, target - candidates[i], path, res)
		path.pop()

算法分析：

时间复杂度为O(2ⁿ)，空间复杂度O(n)

暴力法算法思路(推荐)：

注意事项：

Python代码：

算法分析：

端点排序法解题思路II：

解题步骤：

注意事项：

Python代码：

算法分析：

线段树算法III思路(不推荐)：

注意事项：

Python代码：

算法分析：

题目大意：

解题思路：

解题步骤：

注意事项：

Python代码：

算法分析：

算法思路：

注意事项：

Python代码：

算法分析：

题目大意：

解题思路：

Python代码：

注意事项：

Java代码：

算法分析：

相关题目：

题目大意：

解题思路：

解题步骤：

注意事项：

Python代码：

算法分析：