KK's blog

每天积累多一些

0%

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)

Posted on Edited on Disqus:

LeetCode



Given the root of an n-ary tree, return the preorder traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

Example 1:



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


Example 2:



Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]


Constraints:

The number of nodes in the tree is in the range [0, 10<sup>4</sup>]. 0 <= Node.val <= 10<sup>4</sup>
The height of the n-ary tree is less than or equal to 1000.

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

题目大意：

求n个儿子的树的前序遍历

DFS解题思路：

严格按照定义，先root，再加入儿子节点

解题步骤：

N/A

注意事项：

  1. root.children可能为None，所以要default成[]

Python代码：

1
2
3
4
5
6
7
8
9
10
def preorder(self, root: 'Node') -> List[int]:
	return self.dfs(root)

def dfs(self, root):
	if not root:
		return []
	res = [root.val]
	for child in root.children or []:
		res.extend(self.dfs(child))
	return res

算法分析：

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

迭代算法II解题思路：

用stack，但不能用模板，因为太多儿子，所以类似于Iterator方法Leetcode 341 Flatten Nested List Iterator ，先把该层的儿子节点反着加入到stack，保证后加入的后遍历。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def iterative_preorder(self, root: 'Node') -> List[int]:
	if not root:
		return []
	res, stack = [], []
	stack.append(root)

	while stack:
		node = stack.pop()
		res.append(node.val)
		for child in reversed(node.children or []):
			stack.append(child)
	return res

算法分析：

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

Free mock interview