KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. You may return the answer in any order.

Example 1:

Input: s = “()())()”
Output: [“(())()”,”()()()”]


Example 2:

Input: s = “(a)())()”
Output: [“(a())()”,”(a)()()”]


Example 3:

Input: s = “)(“
Output: [“”]


Constraints:

1 <= s.length <= 25 s consists of lowercase English letters and parentheses '(' and ')'.
* There will be at most 20 parentheses in s.

题目大意：

求最小去掉不合法括号数之后的所有结果

算法思路：

最值问题考虑用DP和BFS，DP难以拆分子问题。所以考虑用BFS + 括号是否合法

LeetCode 1249 Minimum Remove to Make Valid Parentheses 求一个最优解 Medium, Stack
LeetCode 921 Minimum Add to Make Parentheses Valid 求一个最优解 Medium, Stack
LeetCode 301 Remove Invalid Parentheses 求所有最优解 Hard，此题 答案包含上题, BFS

注意事项：

  1. 由于()())() -> (())()，所以去掉的括号不一定都不合法，所以BFS要尝试删除每一个括号。若节点合法，加入结果且记录最小删除数，因为要求同一距离下的所有结果，所以用这个最小数来剪枝。
  2. 输入含小写字母，所以无论是判断括号是否合法还是生成儿子节点都要跳过
  3. 模板中含if neighbor in visited，不能忘记写

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def removeInvalidParentheses(self, s: str) -> List[str]:
	queue = collections.deque([s])
	visited = set([s])
	res, min_dis = [], float('inf')
	distance = collections.defaultdict(int)
	while queue:
		node = queue.popleft()
		if self.is_valid(node):
			res.append(node)
			min_dis = min(min_dis, distance[node])
			continue
		if distance[node] > min_dis:
			continue
		for i in range(len(node)):
			if node[i] not in ['(', ')']:  # remember
				continue
			child = node[:i] + node[i + 1:]
			if child in visited: # remember
				continue
			queue.append(child)
			visited.add(child)
			distance[child] = distance[node] + 1
	return res

def is_valid(self, s): # remember not to use get_invalid_index ()())() -> (())()
	stack = []
	for i, char in enumerate(s):
		if char not in ['(', ')']: # remember
			continue
		if char == ')' and stack and s[stack[-1]] == '(':
			stack.pop()
		else:
			stack.append(i)
	return False if stack else True

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given a string s, find the longest palindromic subsequence‘s length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = “bbbab”
Output: 4
Explanation: One possible longest palindromic subsequence is “bbbb”.


Example 2:

Input: s = “cbbd”
Output: 2
Explanation: One possible longest palindromic subsequence is “bb”.


Constraints:

1 <= s.length <= 1000 s consists only of lowercase English letters.

题目大意：

求字符串中最长回文序列

算法思路：

一开始看到子序列如LIS就想用DP，dp[i]表示以s[i]为结尾的最长回文子序列。但不容易推导公式，难点是没有限制左边界
所以应该扩展到二维dp[i][j]表示[i, j]之间的最长回文子序列。公式就简单多了

1
2
dp[i][j] = dp[i+1][j-1] + 2,             s[i] == s[j]
         = max(dp[i+1][j], dp[i][j-1]),  s[i] != s[j]

注意事项：

  1. 难点是想到用二维DP(区间型DP)。用区间型递归模板，注意dp[i + 1][j]并不是i - 1
  2. 初始值为dp[i][i] = 1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def longestPalindromeSubseq(self, s: str) -> int:
	dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
	for i in range(len(s)):
		dp[i][i] = 1
	for k in range(1, len(s)):
		for i in range(len(s) - k):
			j = i + k
			if s[i] == s[j]:
				dp[i][j] = dp[i + 1][j - 1] + 2
			else:
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
	return dp[0][-1]

算法分析：

时间复杂度为O(n*n)，空间复杂度O(n*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



There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the m x n maze, the ball’s start position and the destination, where start = [start<sub>row</sub>, start<sub>col</sub>] and destination = [destination<sub>row</sub>, destination<sub>col</sub>], return true if the ball can stop at the destination, otherwise return false.

You may assume that the borders of the maze are all walls (see examples).

Example 1:



Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.


Example 2:



Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
Output: false
Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.


Example 3:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
Output: false


Constraints:

m == maze.length n == maze[i].length
1 <= m, n <= 100 maze[i][j] is 0 or 1.
start.length == 2 destination.length == 2
0 <= start<sub>row</sub>, destination<sub>row</sub> <= m 0 <= start<sub>col</sub>, destination<sub>col</sub> <= n
Both the ball and the destination exist in an empty space, and they will not be in the same position initially. The maze contains at least 2 empty spaces.

题目大意：

球在玉米迷宫上滚，当遇到边界或玉米会停下，停下后可以转任意方向。求能否停在目标上。

算法思路：

二维数组求目标第一时间想到用BFS，此题求能停下的点而不是所有点。所以属于一组节点作为一层的BFS，也就是说只有能停下的位置才算BFS的一层，才加入都队列，其他停不来的点均忽略。这是此题的难点。

注意事项：

  1. 属于一组节点作为一层的BFS，能停下的点才加入到queue。比标准模板多了Line 10 - 11. 停下包括边界和玉米(maze[x][y] == 1)
  2. 要滚回一步Line 12 - 15，因为line 10循环的终结状态为出界或玉米上。要滚回一步到空地上。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
	queue = collections.deque([(start[0], start[1])])
	visited = set([(start[0], start[1])])
	while queue:
		node = queue.popleft()
		if node[0] == destination[0] and node[1] == destination[1]:
			return True
		for _dx, _dy in OFFSETS:
			x, y = node[0], node[1]
			while 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0: # remember maze[x][y] == 0
				x, y = x + _dx, y + _dy
			if (x - _dx, y - _dy) in visited: # remember
				continue
			queue.append((x - _dx, y - _dy))
			visited.add((x - _dx, y - _dy))
	return False

算法分析：

时间复杂度为O(nm)，空间复杂度O(nm)

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)

Free mock interview