KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

<pre>Input: root = [1,2,2,3,4,4,3] Output: true </pre>

Example 2:

<pre>Input: root = [1,2,2,null,3,null,3] Output: false </pre>

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?</div>

题目大意：

判断二叉树是否对称

解题思路：

Easy题，但难点是转化成比较两棵树是否对称

解题步骤：

N/A

注意事项：

  1. 难点是转化成比较两棵树是否对称
  2. 还要比较值相等，root.val == root2.val

Python代码：

1
2
3
4
5
6
7
8
9
def isSymmetric(self, root: TreeNode) -> bool:
	return self.is_symmetric(root.left, root.right)

def is_symmetric(self, root, root2):
	if not root and not root2:
		return True
	if not root or not root2:
		return False
	return root.val == root2.val and self.is_symmetric(root.left, root2.right) and self.is_symmetric(root.right, root2.left)

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Numbers can be regarded as the product of their factors.

  • For example, 8 = 2 x 2 x 2 = 2 x 4.

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note that the factors should be in the range [2, n - 1].

Example 1:

<pre>Input: n = 1 Output: [] </pre>

Example 2:

<pre>Input: n = 12 Output: [[2,6],[3,4],[2,2,3]] </pre>

Example 3:

<pre>Input: n = 37 Output: [] </pre>

Constraints:

  • 1 <= n <= 10<sup>7</sup>

</div>

题目大意：

求所有因式分解

解题思路：

求所有解，所以用DFS。类似于LeetCode 039 Combination Sum元素可复用。

解题步骤：

N/A

注意事项：

  1. 类似于元素可复用的组合和。但更似全组合模板，append发生在循环中，而不是终止条件中。比如12，遇到2就把商[2, 6]加入到结果
  2. 数值区间的组合，start和target都是数值，而不是数组长度。i是从start开始，而不是从2开始，保证path里的数有序
  3. target // i < i 保证path里的数有序，否则12=232，不可行
  4. i从start循环到math.sqrt(n) + 1，否则会TLE

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def getFactors(self, n: int) -> List[List[int]]:
	res = []
	self.dfs(n, 2, n, [], res)
	return res

def dfs(self, n, start, target, path, res):
	if target == 1:
		return
	for i in range(start, int(math.sqrt(n) + 1)): # remember to use start
		if target % i != 0 or target // i < i: # remember
			continue
		path.append(i)
		res.append(list(path + [target // i]))
		self.dfs(n, i, target // i, path, res) 
		path.pop()

算法分析：

时间复杂度为<code>O(2<sup>n</sup>)</code>，空间复杂度O(# of prime factors)

Posted on Edited on Disqus:

LeetCode

<div>

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:

<pre>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.</pre>

Constraints:

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

</div>

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

存储所有区间

注意事项：

  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

算法分析：

时间复杂度为<code>O(n<sup>2</sup>)</code>, 空间复杂度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

算法分析：

时间复杂度为<code>O(n<sup>2</sup>)</code>，由于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)，最差情况为<code>O(n<sup>2</sup>)</code>，空间复杂度O(n)

Posted on Edited on Disqus:

LeetCode

<div>

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:

<pre>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. </pre>

Constraints:

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

</div>

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

存储所有区间和重合区间

注意事项：

  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

算法分析：

时间复杂度为<code>O(n<sup>2</sup>)</code>, 空间复杂度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

算法分析：

时间复杂度为<code>O(n<sup>2</sup>)</code>, 空间复杂度O(n)

Posted on Edited on Disqus:

LeetCode

<div>

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:

<pre>Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]] </pre>

Example 2:

<pre>Input: root = [1] Output: [[1]] </pre>

Example 3:

<pre>Input: root = [] Output: [] </pre>

Constraints:

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

</div>

题目大意：

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

解题思路：

用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)

Free mock interview