KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



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.

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

存储所有区间

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
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(n2), 空间复杂度O(n)

端点排序法解题思路II：

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

解题步骤：

N/A

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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(n2)，由于insort是插入需要移动数组，所以是O(n), 空间复杂度O(n)

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

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

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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(n2)，空间复杂度O(n)

Posted on Edited on Disqus:

LeetCode



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

A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three 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 MyCalendarTwo class:

MyCalendarTwo() 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 triple booking. Otherwise, return false and do not add the event to the calendar.

Example 1:

Input
[“MyCalendarTwo”, “book”, “book”, “book”, “book”, “book”, “book”]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

Explanation
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True, The event can be booked.
myCalendarTwo.book(50, 60); // return True, The event can be booked.
myCalendarTwo.book(10, 40); // return True, The event can be double booked.
myCalendarTwo.book(5, 15);  // return False, The event ca not be booked, because it would result in a triple booking.
myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.


Constraints:

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

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

存储所有区间和重合区间

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MyCalendar(TestCases):
    def __init__(self):
        self.calendar = []
        self.overlaps = []

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

        for s, e in self.calendar:
            if not (start >= e or end <= s):
                self.overlaps.append((max(start, s), min(end, e)))
        self.calendar.append((start, end))
        return True

算法分析：

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

算法II解题思路：

有重复区间，考虑用meeting rooms的方法二。用一个map来存储endpoint包括start和end的频率，若遇到start，map[start]++, 若遇到end, map[end]–，插入一个区间后，遍历所有endpoints，若超过3就返回False
虽然复杂度稍差，系数更大。但此法更有推广性，如果允许重复会议更多，此法可扩展

注意事项：

  1. 先插入有序区间，然后统计看是否有重复区间超过2.
  2. 若是False，用remove这个函数要删除刚插入的。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MyCalendar(TestCases):
    def __init__(self):
        self.calendar = []

    def book(self, start: int, end: int) -> bool:
        bisect.insort(self.calendar, (start, 1))
        bisect.insort(self.calendar, (end, -1))
        active_meeting = 0
        for endpoint, _type in self.calendar:
            if _type == 1:
                active_meeting += 1
            else:
                active_meeting -= 1
            if active_meeting >= 3:
                self.calendar.remove((start, 1))
                self.calendar.remove((end, -1))
                return False
        return True

算法分析：

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

Posted on Edited on 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

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)

Posted on Edited on 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

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
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)

Posted on Edited on 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 104*0 <= prices[i] <= 104`

题目大意：

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

解题思路：

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

Python代码：

1
2
3
4
5
6
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

注意事项：

  1. 数组为空

Java代码：

1
2
3
4
5
6
7
8
9
10
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 121 Best Time to Buy and Sell Stock
LeetCode 122 Best Time to Buy and Sell Stock II
LeetCode 309 Best Time to Buy and Sell Stock with Cooldown
LeetCode 123 Best Time to Buy and Sell Stock III

Free mock interview