KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

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:

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

Example 2:

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

Constraints:

  • 1 <= n <= 8

</div>

题目大意：

给定n，求所有val为1-n的BST的所有可能性,返回结果是所有可能的root的集合。

解题思路：

DFS中比较难的catalan类型。

解题步骤：

N/A

注意事项：

  1. root = TreeNode(i)要在最内层for循环中
  2. 返回结果是解的集合，所以终止条件返回也需要是一个[None]

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# catelan dfs (type 4) LeetCode 095 Unique Binary Search Trees II
# return the root of all the possible trees
def generateTrees(self, n: int) -> List[TreeNode]:
	nums = [_ + 1 for _ in range(n)]
	return self.dfs4(nums, 0, n)

def dfs4(self, nums, start, end): # [start, end)
	if start >= end:
		return [None] # remember becaues we want the 2 for-loop happen
	res = []
	for i in range(start, end):
		left_root_nodes = self.dfs4(nums, start, i) # 0, 0
		right_root_nodes = self.dfs4(nums, i + 1, end) # 1, 1
		for left_root_node in left_root_nodes:
			for right_root_node in right_root_nodes:
				node = TreeNode(nums[i])
				node.left = left_root_node
				node.right = right_root_node
				res.append(node)
	return res

算法分析：

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

Posted on Edited on Disqus:

算法思路：

DFS将子问题的解存于结果中。cache[st] = result. st是子问题边界。

应用：

用于求所有可能性，且这些可能性有重复，记忆性搜索可以用于剪枝。

  1. Leetcode 139
  2. Leetcode 140

与DP的界线：

  1. 状态转移特别麻烦如有循环依赖, 不是顺序性。如棋盘，上下左右四个方向如1197 Minimum Knight Moves和word ladder
  2. 初始化状态不是特别容易找到

算法步骤：

  1. key为子问题索引st，value为子问题的解。不含path和res因为类似于Catalan，用子问题返回结果来组成此轮结果。f(input, st, endIndex, cache) -> List
  2. 紧跟终结条件，若在cache中，返回子问题的解。
  3. 循环结束，将子问题的结果存于cache。

注意事项：

  1. cache是一个解的集合，所以终止条件返回也需要是一个list

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def dfs(self, input, cache) -> List[int]:
	if <终止条件>:
		return [] # remember to use list
	if input in cache:
		return cache[input]
	res = []
	for i in range(len(input)):
		anwser = self.dfs(input[:i], cache)
		res.append(anwser)
	cache[input] = res
	return res

算法分析：

时间复杂度为O(解大小)，空间复杂度O(解大小).

例子：

LeetCode 140 Word Break II
这是单边catalan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
	word_set = set(wordDict)
	res = []
	cache = {}
	res = self.dfs(s, word_set, cache) #cat
	return res
# dfs(s) = word + dfs(s[i+1:])
def dfs(self, s, word_set, cache):
	if s == "":
		return [""]
	if s in cache:
		return cache[s]
	res = []
	for i in range(len(s)):
		if s[:i + 1] not in word_set:
			continue
		cur_list = self.dfs(s[i + 1:], word_set, cache) # i = 2, dfs("")
		for _s in cur_list: # [""]
			res.append((s[:i + 1] + " " + _s).strip()) #cat
	cache[s] = res
	return res

注意事项：

  1. 终止条件返回['']而不是[]，正如L017，空字符串作为初始结果。返回到上层要strip(), 因为ss可能为空
  2. 子问题用f=word + f并不是f=f + word, 这样最后结果避免反转。
  3. s[:i + 1]判断是否在字典中，而不是s[:i]，单词包括整个字符串。

Posted on Edited on Disqus:

算法思路：

递归分前半和后半排序然后合并。

应用：

  1. 排序
  2. 求逆序数

注意事项：

  1. merge函数中更改输入nums。
  2. line 15的等号决定是否stable sort。

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
def merge_sort(self, nums: List[int]):
	self.m_sort(nums, 0, len(nums) - 1)

def m_sort(self, nums: List[int], start: int, end: int):
	if start >= end:
		return
	mid = start + (end - start) // 2
	self.m_sort(nums, start, mid)
	self.m_sort(nums, mid + 1, end)
	self.merge(nums, start, mid, end)

def merge(self, nums: List[int], start: int, mid: int, end: int):
	i, j, res = start, mid + 1, []
	while i <= mid and j <= end:  # = decides if it is stable sort
		if nums[i] <= nums[j]:
			res.append(nums[i])
			i += 1
		else:
			res.append(nums[j])
			j += 1
	while i <= mid:
		res.append(nums[i])
		i += 1
	while j <= end:
		res.append(nums[j])
		j += 1
	nums[start:end + 1] = res

算法分析：

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

Posted on Edited on Disqus:

算法思路：

Leetcode 046的题目。这里作为知识点归纳。

  1. 类似于组合题，但用到了visited数组且递归中从i=0开始。

应用：

  1. 找所有可能性

注意事项：

  1. 每一种排列加入到结果集时要复制path。

学习要点：

详见DFS要点，大部分DFS题目涉及

  1. 用到全组合的API: dfs(nums, start, path, result), 4个参数
  2. 用到全组合的递归: dfs(nums, i + 1, path, result)
  3. 用到全排列的其他部分包括恢复状态和终止条件(加入res)

Leetcode 046 Permutations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def permute(self, nums: List[int]) -> List[List[int]]:
	if not nums:
		return [[]]
	path, res = [], []
	self.dfs(nums, set(), path, res)
	return res

def dfs(self, nums, visited, path, res): # 
	if len(path) == len(nums):
		res.append(list(path))
		return
	for i in range(len(nums)): 
		if i in visited:
			continue
		visited.add(i) # [2, 1]
		path.append(nums[i])
		self.dfs(nums, visited, path, res) 
		path.pop()
		visited.remove(i)

Java代码：

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
public List<List<Integer>> permute(int[] nums) {
	List<Integer> path = new ArrayList<>();
	List<List<Integer>> res = new ArrayList<>();
	if(nums == null) {
		return res;
	}
	dfs(nums, new HashSet<>(), path, res);
	return res;
}

void dfs(int[] nums, Set<Integer> visited, List<Integer> path, List<List<Integer>> res) {
	if(path.size() == nums.length) {
		res.add(new ArrayList<>(path));
		return;
	}
	
	for(int i = 0; i < nums.length; i++) {
		if(visited.contains(i))
			continue;
		visited.add(i);
		path.add(nums[i]);
		dfs(nums, visited, path, res);
		visited.remove(i);
		path.remove(path.size() - 1);
	}
}

算法分析：

时间复杂度为O(n*n!)，空间复杂度O(1)。解大小乘以path长度

Posted on Edited on Disqus:

算法思路：

对于拓扑排序来说， 我们的中心思想是要我们可以找到一个顺序，每一次我们可以进行的工序是现在没有先序依赖的工序，
按照这个顺序可以流畅的完成我们的任务。 思路基于BFS的队列实现。区别在于统计每个节点的入度数。此法也可用于无向图。

  1. 根据边统计每个节点的入度数记入in[i]，其他节点（含无边节点）入度数为0
  2. 找出度数为0的节点加入到Queue
  3. 取出队首节点，把此节点邻接的节点度数减1，如果度数为0，加入到队列，循环直到队列为空
  4. 如果队列为空但仍有节点度数不为0，存在循环，否则不存在

应用：

  1. 求最长或最短路径(Leetcode 310)
  2. 判断拓扑顺序(Leetcode外星人字典)
  3. 判断循环(Python代码返回None)

注意事项：

  1. graph要含所有节点，包括没有边的节点。否则结果会有遗漏
  2. in_degree初始化要对所有节点赋0. graph的值是node的下标, 注意in_degree的赋值.
  3. 第四步判断是否含循环必不可少，要根据题目要求来处理。除非L310 min height明确一定有解，而L269外星人字典就明确可能无解

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def topological_sort(self, graph: List[List[int]], n: int) -> List[int]:
	in_degree = [0] * n
	for i in range(len(graph)):
		for node in graph[i]:
			in_degree[node] += 1

	start_nodes = [i for i in range(len(in_degree)) if in_degree[i] == 0]
	queue, res = deque(start_nodes), []
	while queue:
		node = queue.popleft()
		res.append(node)
		for neighbor in graph[node]:
			in_degree[neighbor] -= 1
			if in_degree[neighbor] == 0:
				queue.append(neighbor)
	return res if len(res) == n else None

Java代码：

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
/*
 * graph: 邻接表
 * num: 节点个数 
 */
public void topologicalSort(ArrayList<ArrayList<Integer>> graph, int num) {
	int[] inDegree = new int[num];
	//populate inDegree
	for(ArrayList<Integer> adjacencyList : graph){
		for(Integer node : adjacencyList){
			inDegree[node]++;
		}       	
	}
	Queue<Integer> q = new LinkedList<Integer>();
	for(int i=0;i<inDegree.length;i++){
		if(inDegree[i]==0)
			q.offer(i);
	}
	int count = 0;
	while(!q.isEmpty()){
		Integer v = q.poll();
		count++;
		System.out.print(v + "->");
		for(int neighbor : graph.get(v)){
			if(--inDegree[neighbor]==0)
				q.offer(neighbor);
		}
	}
	/* check isCyclic  or not
	return count == num;;
	*/
}

算法分析：

时间复杂度为O(n)，w为树的所有层里面的最大长度，空间复杂度O(w)。

Free mock interview