KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.



Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.



Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.



 


Example 1:



Input: n = 4
Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above


Example 2:



Input: n = 1
Output: [[“Q”]]


 


Constraints:




  • 1 <= n <= 9


题目大意：

八皇后问题，求所有解

Global dict算法思路(推荐)：

DFS填位法模板

注意事项：

  1. 用3个set，col_set, 对角线，反对角线set来提高效率。
  2. path用append的方法加入，这样终止条件用n来比较，不能用len(path)
  3. 打印函数中，one_result在每轮后reset；字符串不能改其中一个，只能用子串+Q+子串： (‘.’ path[i]) + ‘Q’ + (‘.’ (n - path[i] - 1))

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 solveNQueens(self, n: int) -> List[List[str]]:
	res, path = [], []
	self.dfs(n, 0, path, res, set(), set(), set())
	result = self.convert(res)
	return result

def dfs(self, n, start, path, res, col_set, diag_set, anti_diag_set):
	if start == n: # remember not len(path)
		res.append(list(path))
		return
	for i in range(n): # 4
		if not self.is_valid(start, i, col_set, diag_set, anti_diag_set):
			continue
		path.append(i)  # [0, 2]
		col_set.add(i)
		diag_set.add(start - i)
		anti_diag_set.add(start + i)
		self.dfs(n, start + 1, path, res, col_set, diag_set, anti_diag_set)
		anti_diag_set.remove(start + i)
		diag_set.remove(start - i)
		col_set.remove(i)
		path.pop()

def is_valid(self, i, val, col_set, diag_set, anti_diag_set):
	if val in col_set or i - val in diag_set or i + val in anti_diag_set:
		return False
	return True

算法分析：

时间复杂度为O(n x n!)，解大小乘以path长度,空间复杂度O(n^2)

常数空间算法II解题思路(推荐)：

较直观的方法，但复杂度稍差

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
36
37
38
def solveNQueens2(self, n: int) -> List[List[str]]:
	res, path = [], []
	self.dfs2(n, 0, path, res)
	result = self.convert(res)
	return result

def dfs2(self, n, start, path, res):
	if start == n: # remember not len(path)
		res.append(list(path))
		return
	for i in range(n): # 4
		path.append(i) # [0, 2]
		if self.is_valid2(path):
			self.dfs2(n, start + 1, path, res)
		path.pop()

def is_valid2(self, path):
	if len(path) != len(set(path)):
		return False
	for i in range(len(path)):
		for j in range(i + 1, len(path)):
			#if i == j:
			 #   continue
			if abs(i - j) == abs(path[i] - path[j]):
				return False
	return True

def convert(self, res):
	result, one_result = [], []
	for k in range(len(res)):
		one_result = [] # remember
		path = res[k]
		n = len(path)
		for i in range(n):
			s = ('.' * path[i]) + 'Q' + ('.' * (n - path[i] - 1))  # remember not s[path[i]] = 'Q'
			one_result.append(s)
		result.append(one_result)
	return result

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
32
33
public List<List<String>> solveNQueens2(int n) {
	List<List<String>> res = new ArrayList<>();
	int[] col = new int[n];
	solveR(n, col, 0, res);
	return res;
}

// 5/2/2020
void solveR(int n, int[] col, int st, List<List<String>> res) {
	if(st == n) {
		print(col, res);
		return;
	}
	
	for(int i = 0; i < n; i++) {
		col[st] = i;
		if(isValid(col, st))
			solveR(n, col, st + 1, res);
	}
}

boolean isValid(int[] col, int k) {
	for(int i = 0; i < k; i++) {
		if(col[i] == col[k])
			return false;
	}

	for(int i = 0; i < k; i++) {
		if(Math.abs(k - i) == Math.abs(col[k] - col[i])) //use abs
			return false;
	}
	return true;
}

算法分析：

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

Posted on Edited on Disqus:

LeetCode 415 Add Strings

Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

  1. The length of both num1 and num2 is < 5100.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

题目大意：

给出两个字符串形式的非负数num1和num2，返回num1和num2之和。

解题思路：

对每一位进行加法，注意进位和长度不一，类似于merge sort里面merge的实现。最要注意的是进位carry的edge case：for循环后最后值要特别处理。

注意事项：

  1. 三个循环后carry要特殊处理
  2. Python中，题目要求不能用int函数，就只能用ord(num1[i]) - ord(‘0’)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def addStrings(self, num1: str, num2: str) -> str:
	num1, num2 = num1[::-1], num2[::-1]
	res = []
	i, j, carry = 0, 0, 0
	while i < len(num1) or j < len(num2) or carry:
		tmp = carry
		if i < len(num1):
			tmp += ord(num1[i]) - ord('0')
			i += 1
		if j < len(num2):
			tmp += ord(num2[j]) - ord('0')
			j += 1
		carry = 1 if tmp >= 10 else 0
		res.append(str(tmp % 10))
	return ''.join(res[::-1])

算法分析：

时间复杂度为O(n)，n为字符串较长者长度。空间复杂度为O(n)。

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
32
33
public String addStrings(String num1, String num2) {
	StringBuffer sb = new StringBuffer();
	int i=num1.length()-1,j=num2.length()-1;
	int carry=0;
	while(i>=0 && j>=0){
		int tmp = Integer.parseInt(num1.charAt(i)+"")+Integer.parseInt(num2.charAt(j)+"")+carry;
		if(tmp>=10)
			carry = 1;
		else carry = 0;
		sb.append(tmp%10);
		i--;
		j--;
	}
	while(i>=0){
		int tmp = Integer.parseInt(num1.charAt(i)+"")+carry;
		if(tmp>=10)
			carry = 1;
		else carry = 0;
		sb.append(tmp%10);
		i--;
	}
	while(j>=0){
		int tmp = Integer.parseInt(num2.charAt(j)+"")+carry;
		if(tmp>=10)
			carry = 1;
		else carry = 0;
		sb.append(tmp%10);
		j--;
	}
	if(carry>0)
		sb.append(carry);
	return sb.reverse().toString();	
}

算法分析：

时间复杂度为O(n)，n为字符串较长者长度。空间复杂度为O(1)。

此方案由于用了string concatenation，所以复杂度为O(n^2). 所以不推荐

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def addStrings(self, num1: str, num2: str) -> str:
	num1, num2 = num1[::-1], num2[::-1]
	res = ''
	i, j, carry = 0, 0, 0
	while i < len(num1) or j < len(num2):
		tmp = carry
		if i < len(num1):
			tmp += ord(num1[i]) - ord('0')
			i += 1
		if j < len(num2):
			tmp += ord(num2[j]) - ord('0')
			j += 1
		carry = 1 if tmp >= 10 else 0
		res += str(tmp % 10)
	if carry == 1:
		res += str(carry)
	return res[::-1]

Posted on Edited on Disqus:

LeetCode



Given the root of a binary tree, return the vertical order traversal of its nodes’ values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Example 1:



Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]


Example 2:



Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]


Example 3:



Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]


Constraints:

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

题目大意：

按列顺序打印二叉树

BFS解题思路(推荐)：

从root开始从0编号，左右节点分别为-1, 1，如此类推，就可以标记所有节点，从而将这些节点加入结果集。

LeetCode 314 Binary Tree Vertical Order Traversal 同一列，从上到下，从左到右排序
LeetCode 987 Vertical Order Traversal of a Binary Tree 同一列，从上到下，同一行值从小到大排序

解题步骤：

N/A

注意事项：

  1. BFS引入(vertical_id, root)来做计算。由于结果列表如vertical_id = -1, 1可以从左或右加入，用dict来记录vertical到list更好合理
  2. 由于vertical_id是连续的，所以不妨用min_col, max_col来记录dict的范围，保证从dict到结果集是按顺序加入。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
	if not root:
		return []
	idx_to_list, res = collections.defaultdict(list), []
	queue = collections.deque([(0, root)])
	min_col, max_col = float('inf'), float('-inf')
	while queue:
		vertical_id, node = queue.popleft()
		min_col, max_col = min(min_col, vertical_id), max(max_col, vertical_id)
		idx_to_list[vertical_id].append(node.val)
		if node.left:
			queue.append((vertical_id - 1, node.left))
		if node.right:
			queue.append((vertical_id + 1, node.right))
	for i in range(min_col, max_col + 1):
		res.append(idx_to_list[i])
	return res

算法分析：

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

BFS算法II解题思路：

先写了这个，优化后才得到算法I。区别在于keys需要排序

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def verticalOrder1_1(self, root: TreeNode) -> List[List[int]]:
	if not root:
		return []
	idx_to_list, res = collections.defaultdict(list), []
	queue = collections.deque([(0, root)])
	while queue:
		vertical_id, node = queue.popleft()
		idx_to_list[vertical_id].append(node.val)
		if node.left:
			queue.append((vertical_id - 1, node.left))
		if node.right:
			queue.append((vertical_id + 1, node.right))
	sorted_keys = sorted(list(idx_to_list.keys()))
	for i in sorted_keys:
		res.append(idx_to_list[i])
	return res

算法分析：

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

DFS算法III解题思路(不推荐)：

最开始的思路，很容易错，因为不符合题目的按层遍历的顺序。题目要求同一column的节点是从上到下，从左到右。DFS与此违反。
反例：

这个例子DFS的结果是[[3], [1, 5], [6, 2]]，但是[6, 2]违反了这个要求。

注意事项：

  1. 要将同一个column节点从上到下从左到右排序，就要记录height和左到右的顺序(height_id, len(idx_to_list[vertical_id]) - 1, root.val)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def verticalOrder2(self, root: TreeNode) -> List[List[int]]:
	idx_to_list, res = collections.defaultdict(list), []
	self.dfs(root, 0, 0, idx_to_list)
	sorted_keys = sorted(list(idx_to_list.keys()))
	for i in sorted_keys:
		li = sorted(idx_to_list[i])
		res.append([node[2] for node in li])
	return res

def dfs(self, root, height_id, vertical_id, idx_to_list):
	if not root:
		return
	idx_to_list[vertical_id].append((height_id, len(idx_to_list[vertical_id]) - 1, root.val))
	self.dfs(root.left, height_id + 1, vertical_id - 1, idx_to_list)
	self.dfs(root.right, height_id + 1, vertical_id + 1, idx_to_list)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Example 1:



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


Example 2:

Input: root = []
Output: []


Example 3:

Input: root = [1]
Output: [1]


Constraints:

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

Follow up: Recursive solution is trivial, could you do it iteratively?

题目大意：

求树的中序遍历

解题思路：

DFS

解题步骤：

N/A

注意事项：

N/A

Python代码：

1
2
3
4
5
6
7
def inorderTraversal(self, root: TreeNode) -> List[int]:
	return self.dfs(root)

def dfs(self, root):
	if not root:
		return []
	return self.dfs(root.left) + [root.val] + self.dfs(root.right)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given the root of a binary tree, return the preorder traversal of its nodes’ values.

Example 1:



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


Example 2:

Input: root = []
Output: []


Example 3:

Input: root = [1]
Output: [1]


Constraints:

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

Follow up: Recursive solution is trivial, could you do it iteratively?

题目大意：

求树的前序遍历

解题思路：

DFS

解题步骤：

N/A

注意事项：

N/A

Python代码：

1
2
3
4
5
6
7
def preorderTraversal(self, root: TreeNode) -> List[int]:
	return self.dfs(root)

def dfs(self, root):
	if not root:
		return []
	return [root.val] + self.dfs(root.left) + self.dfs(root.right)

算法分析：

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

Free mock interview