KK's blog

LeetCode 241 Different Ways to Add Parentheses

Posted on 2022-01-18 Disqus:

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

Example 1:

Input: expression = “2-1-1”
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2

Example 2:

Input: expression = “23-45”
Output: [-34,-14,-10,-10,10]
Explanation:
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10

Constraints:

1 <= expression.length <= 20 expression consists of digits and the operator '+', '-', and '*'.
* All the integer values in the input expression are in the range [0, 99].

题目大意：

给定一个字符串含数字和加减乘除，求所有加括号方法得到的结果

Catalan解题思路(推荐)：

求所有结果，用DFS，由于需要左右递归，双边递归，所以用Catalan法模板

解题步骤：

N/A

注意事项：

终止条件返回是一个list
Python中用eval来计算字符串运算结果返回值为整数，所以归纳左右递归结果要用str转为字符串

Python代码：

def diffWaysToCompute(self, expression: str) -> List[int]:
	if expression.isdigit():
		return [int(expression)] # remember to use list
	res = []
	for i, char in enumerate(expression):
		if char not in '+-*/':
			continue
		left_res = self.diffWaysToCompute(expression[:i])
		right_res = self.diffWaysToCompute(expression[i + 1:])
		res += [eval(str(_l) + char + str(_r)) for _l in left_res for _r in right_res] # remember eval and str
	return res

算法分析：

时间复杂度Catalan数为O(C[n] += C[i-1]*C[n-i])，空间复杂度O(1)

记忆性搜索算法II解题思路：

大致同上，只不过加入记忆性搜索算法，但优化不算大

Python代码：

def diffWaysToCompute2(self, expression) -> List[int]:
	return self.dfs(expression, {})

def dfs(self, expression: str, cache) -> List[int]:
	if expression.isdigit():
		return [int(expression)] # remember to use list
	if expression in cache:
		return cache[expression]
	res = []
	for i, char in enumerate(expression):
		if char not in '+-*/':
			continue
		left_res = self.dfs(expression[:i], cache)
		right_res = self.dfs(expression[i + 1:], cache)
		res += [eval(str(_l) + char + str(_r)) for _l in left_res for _r in right_res] # remember eval and str
	cache[expression] = res
	return res

LeetCode 095 Unique Binary Search Trees II

Posted on 2022-01-18 Disqus:

LeetCode

Given an integer n, return all the structurally unique BST’s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example 1:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Example 2:

Input: n = 1
Output: [[1]]

Constraints:

* 1 <= n <= 8

题目大意：

给定n，求所有val为1-n的BST的所有可能性

解题思路：

DFS中比较难的catalan类型。

解题步骤：

N/A

注意事项：

root = TreeNode(i)要在最内层for循环中

Python代码：

def generateTrees(self, n: int) -> List[TreeNode]:
	return self.dfs(1, n)

def dfs(self, start, end):
	if start > end:
		return [None]
	if start == end:
		return [TreeNode(start)]
	res = []
	for i in range(start, end + 1):
		left_nodes = self.dfs(start, i - 1)
		right_nodes = self.dfs(i + 1, end)
		for _l in left_nodes:
			for _r in right_nodes:
				root = TreeNode(i)
				root.left = _l
				root.right = _r
				res.append(root)
	return res

算法分析：

时间复杂度Catalan数为O(C[n] += C[i-1]*C[n-i])，空间复杂度O(1)

LeetCode 240 Search a 2D Matrix II

Posted on 2022-01-18 Disqus:

LeetCode

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

Constraints:

m == matrix.length n == matrix[i].length
1 <= n, m <= 300 -109 <= matrix[i][j] <= 109
All the integers in each row are sorted in ascending order. All the integers in each column are sorted in ascending order.
* -109 <= target <= 109

题目大意：

矩阵按行按列有序，求是否存在target

解题思路：

矩阵有序题有3道：
LeetCode 074 Search a 2D Matrix 每一行有序，下一行的首元素大于上一行的尾元素 + 找target
LeetCode 240 Search a 2D Matrix II 按行按列有序 + 找target
LeetCode 378 Kth Smallest Element in a Sorted Matrix 按行按列有序 + 找第k大
矩阵结构方面，第一道每一行都是独立，所以可以独立地按行按列做二分法
后两道，矩阵二维连续，所以解法都是类BFS，从某个点开始，然后比较它相邻的两个点。出发点不同，第二道在近似矩阵中点(右上角或左下角)，第三道在左上角出发。

解题步骤：

N/A

注意事项：

从右上角出发，比较左和下节点。

Python代码：

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
	i, j = 0, len(matrix[0]) - 1
	while i < len(matrix) and j >= 0:
		if matrix[i][j] == target:
			return True
		if target < matrix[i][j]:
			j -= 1
		else:
			i += 1
	return False

算法分析：

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

LeetCode 235 Lowest Common Ancestor of a Binary Search Tree

Posted on 2022-01-18 Disqus:

LeetCode

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

Constraints:

The number of nodes in the tree is in the range [2, 105]. -109 <= Node.val <= 109
All Node.val are unique. p != q
* p and q will exist in the BST.

题目大意：

BST中求给定的两节点的最低共同父亲节点

解题思路：

三种情况，也是用DFS

解题步骤：

N/A

注意事项：

pq一定存在，所以有**三种情况： 1) p或q是root，另一是其子孙。 2) p，q分列root两边。 3) p，q在root的一边。跟LeetCode 236 Lowest Common Ancestor of a Binary Tree不同的是，
第二种情况，不用递归即知道，因为这是BST。第一和第三种情况同
第二种情况由于要比较p, q, root顺序，所以要令p, q有序，Line 4-5

Python代码：

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
	if not root:
		return None
	if p.val > q.val: # remember
		return self.lowestCommonAncestor(root, q, p)
	if p.val <= root.val <= q.val or p == root or q == root: # remember root is p or q
		return root
	if p.val < root.val and q.val < root.val:
		return self.lowestCommonAncestor(root.left, p, q)
	else:
		return self.lowestCommonAncestor(root.right, p, q)

算法分析：

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

LeetCode 234 Palindrome Linked List

Posted on 2022-01-18 Disqus:

LeetCode

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

The number of nodes in the list is in the range [1, 105]. 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

题目大意：

求一个LL是否回文

解题思路：

快慢指针 + Stack

解题步骤：

N/A

注意事项：

快慢指针找到中点，找的同时，慢指针所有节点入栈。慢指针继续走，比较stack节点和慢指针节点。
不涉及删除，所以不需要哟用到fake_node
中位数可能有1-2个。奇偶问题，若fast指向节点(另一情况是None), 表明是奇数个，slow在第二个循环前多走一步，跳过最中间的节点

Python代码：

def isPalindrome(self, head: ListNode) -> bool:
	fast, slow = head, head
	stack = []
	while fast and fast.next:
		stack.append(slow)
		slow = slow.next
		fast = fast.next.next
	if fast:
		slow = slow.next
	while slow:
		if stack.pop().val != slow.val:
			return False
		slow = slow.next
	return True

算法分析：

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