KK's blog

LeetCode

<div>

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

Example 1:

<pre>Input: root = [4,2,5,1,3]

Output: [1,2,3,4,5]

Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship. </pre>

Example 2:

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

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000
• All the values of the tree are unique.

</div>

题目大意：

将二叉树变成双向链表，left为父节点，right为儿子节点

解题思路：

类似于LeetCode 114 Flatten Binary Tree to Linked List，先假设左右儿子，已经是双向LL，下面就是将root这个节点插入到两个LL之间其将它们首尾相连

解题步骤：

N/A

注意事项：

1. 要将左右儿子节点的LL，首尾相连。首尾节点获得要在if语句前，因为右儿子的left会连到root，就找不到它的尾部。首尾相连要发生在最后。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def treeToDoublyList(self, root: 'Node') -> 'Node':
	if not root:
		return None
	if not root.left and not root.right:
		root.left, root.right = root, root
		return root
	left_head = self.treeToDoublyList(root.left)
	right_head = self.treeToDoublyList(root.right)
	# remember this part and order, can't be placed after ifs
	new_head = left_head if left_head else root
	new_tail = right_head.left if right_head else root
	if left_head:
		left_head.left.right, root.left = root, left_head.left
	if right_head:
		root.right, right_head.left = right_head, root
	new_head.left, new_tail.right = new_tail, new_head
	return new_head

算法分析：

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

LeetCode

<div>

You are given two strings order and s. All the words of order are unique and were sorted in some custom order previously.

Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.

Return any permutation of s that satisfies this property.

Example 1:

<pre>Input: order = "cba", s = "abcd" Output: "cbad" Explanation: "a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a". Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs. </pre>

Example 2:

<pre>Input: order = "cbafg", s = "abcd" Output: "cbad" </pre>

Constraints:

• 1 <= order.length <= 26
• 1 <= s.length <= 200
• order and s consist of lowercase English letters.
• All the characters of order are unique.

</div>

题目大意：

给一个字符串，求这个字符串的一个排列，使得字母顺序按照另一个给定字符串order的顺序。

解题思路：

由限制条件知道，order字母是唯一的，order字母可以重复。所以只要统计s频率，然后按照字母顺序开始重写

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
9
10

def customSortString(self, order: str, s: str) -> str:
	char_to_count = collections.Counter(s)
	res = ''
	for c in order:
		if c in char_to_count:
			res += c * char_to_count[c]
			char_to_count.pop(c)
	for c, count in char_to_count.items():
		res += c * count
	return res

算法分析：

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

LeetCode

<div>

Given a string <font face="monospace">s</font> of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

Example 1:

<pre>Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de" Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted. </pre>

Example 2:

<pre>Input: s = "a)b(c)d" Output: "ab(c)d" </pre>

Example 3:

<pre>Input: s = "))((" Output: "" Explanation: An empty string is also valid. </pre>

Example 4:

<pre>Input: s = "(a(b(c)d)" Output: "a(b(c)d)" </pre>

Constraints:

• 1 <= s.length <= 10<sup>5</sup>
• s[i] is either'(' , ')', or lowercase English letter.

</div>

题目大意：

去掉最小不合法括号数剩下的字符串。

Stack算法思路：

括号题优先考虑用Stack。此题将下标存于stack中，stack留下的是不合法括号下标，也就是需要删除的

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. 当括号配对时才出栈 Line 6

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def minRemoveToMakeValid(self, s: str) -> str:
	stack, res = [], ''
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		elif stack and s[stack[-1]] == '(' and s[i] == ')':  # remember
			stack.pop()
		elif s[i] == ')':
			stack.append(i)
	for i in range(len(s)):
		if i in set(stack):
			continue
		res += s[i]
	return res      

算法分析：

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

LeetCode

<div>

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:

<pre>Input: s = "()())()" Output: ["(())()","()()()"] </pre>

Example 2:

<pre>Input: s = "(a)())()" Output: ["(a())()","(a)()()"] </pre>

Example 3:

<pre>Input: s = ")(" Output: [""] </pre>

Constraints:

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

</div>

题目大意：

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

算法思路：

最值问题考虑用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
35

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

算法分析：

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

LeetCode

<div>

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Example 1:

<pre>Input: root = [10,5,15,3,7,null,18], low = 7, high = 15 Output: 32 Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32. </pre>

Example 2:

<pre>Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10 Output: 23 Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23. </pre>

Constraints:

• The number of nodes in the tree is in the range [1, 2 * 10<sup>4</sup>].
• 1 <= Node.val <= 10<sup>5</sup>
• 1 <= low <= high <= 10<sup>5</sup>
• All Node.val are unique.

</div>

题目大意：

给定[low, high]和BST，求满足条件的BST的节点和

解题思路：

Easy题，DFS，条件比较容易错

解题步骤：

N/A

注意事项：

1. 两个条件，若root.val在范围内，加入和。若low小于root.val(这里不取等号，因为所有节点是唯一，不存在相等节点)， 表示范围适用于左节点，同理右节点。

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
	if not root:
		return 0
	res = 0
	if low <= root.val <= high:
		res += root.val
	if low < root.val:
		res += self.rangeSumBST(root.left, low, high)
	if root.val < high:
		res += self.rangeSumBST(root.right, low, high)
	return res

算法分析：

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