KK's blog

LeetCode

<div><p>An <strong>ugly number</strong> is a positive integer whose prime factors are limited to <code>2</code>, <code>3</code>, and <code>5</code>.</p>

<p>Given an integer <code>n</code>, return <em>the</em> <code>n^th</code> <em><strong>ugly number</strong></em>.</p>

<p> </p> <p><strong>Example 1:</strong></p>

<pre><strong>Input:</strong> n = 10 <strong>Output:</strong> 12 <strong>Explanation:</strong> [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers. </pre>

<p><strong>Example 2:</strong></p>

<pre><strong>Input:</strong> n = 1 <strong>Output:</strong> 1 <strong>Explanation:</strong> 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5. </pre>

<p> </p> <p><strong>Constraints:</strong></p>

<ul> <li><code>1 <= n <= 1690</code></li> </ul> </div>

题目大意：

求第n个丑数，丑数是由2,3,5相乘获得

Heap算法思路(推荐)：

Heap

注意事项：

1. 与BFS模板一样，visited要在if里面。可以理解为一个数有三条边产生三个新数，所以和BFS模板一样

Python代码：

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

def nthUglyNumber(self, n: int) -> int:
	heap, visited = [1], set([1])
	primes = [2, 3, 5]
	res = 0
	while n >= 1:
		res = heappop(heap)
		for factor in primes:
			tmp = factor * res
			if tmp not in visited:
				heappush(heap, tmp)
				visited.add(tmp)
		n -= 1
	return res

算法分析：

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

双指针算法II解题思路：

比较难想，不推荐，但思路可用于其他题如L373。指针的数乘以指向数组的数，此题中指针为p2, p3, p5, 分别代表2， 3， 5， 数组为res数组，每次比较它们的积。

注意事项：

1. 与上题一样要去重，此时，3个乘积中可能会相同且最小，同时移动这些指针

Python代码：

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

def nthUglyNumber(self, n: int) -> int:
        res = [1]
        p2, p3, p5 = 0, 0, 0
        while n > 1:
            num = min(2 * res[p2], 3 * res[p3], 5 * res[p5])
            if num == 2 * res[p2]:
                p2 += 1
            if num == 3 * res[p3]:
                p3 += 1
            if num == 5 * res[p5]:
                p5 += 1
            res.append(num)
            n -= 1
        return res[-1]

算法分析：

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

LeetCode 297 Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

**Example: **

<pre>You may serialize the following tree:

1

/
2 3 /
4 5

as "[1,2,3,null,null,4,5]" </pre>

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

**Note: **Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

题目大意：

序列化和反序列化二叉树。

Python解法

算法思路：

N/A

注意事项：

1. BFS解码，空节点也要入列，因为要转成#，且不让代码往下执行
2. 难点是用#补充空节点，令每个非空节点必有左右儿子，这样解码就可以固定地每轮扫描两个。出列一个父节点，p扫描两个儿子且生成节点，若为#即空节点不入列，这和编码不同。主要因为编码的长度比节点数多，所以生成节点时，不需要再处理空节点。
   Line 25 - 32有重复，这里放在一起方便理解，也可以封装成函数
3. 类型转换int和str, Python用popleft不是pop
4. Line 11非空节点值要记得加入
5. 空节点或空字符单独处理

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

def serialize(self, root):
	if not root:
		return ''
	queue = collections.deque([root])
	res = []
	while queue:
		node = queue.popleft()
		if node:
			res.append(str(node.val))
		else:
			res.append('#')
			continue

		queue.append(node.left)
		queue.append(node.right)
	return ','.join(res)

def deserialize(self, data):
	if not data:
		return None
	vals = data.split(',')
	p = 0
	root = TreeNode(int(vals[0]))
	queue = collections.deque([root])
	while queue:
		node = queue.popleft()

		p += 1
		if vals[p] != '#':
			node.left = TreeNode(int(vals[p]))
			queue.append(node.left)
		p += 1
		if vals[p] != '#':
			node.right = TreeNode(int(vals[p]))
			queue.append(node.right)
	return root

Java解法

解题思路：

BFS可以涉及三重循环

1. q不为空
2. 是否按层遍历
3. 是否为图

这题不需要按层遍历，所以不用第二重。而且只是二叉树，不用第三重循环。

编码方式：

1
2
3
4
5
6
7
8

	      1
	    /   \
	   #     3
	        /  \
	       2   #
	      / \
	     #   #
=> 1,#,3,2,#,#,#

BFS解题步骤：

serialize:

1. 建queue，然后首节点入列
2. 进入q的非空循环，队首出列，分别加入左右子树。由于空子树也会被遍历，所以左右子树可能为空，队首为空时continue
   且val加入到结果字符串
3. 用#代替null且删去末尾的#和，

deserialize:
这方法难实现点。用两个指针来代表遍历上一层和该层节点们。q出列的节点是上一层节点head，而idx指向的是
该层节点。这样head.left = Node(tokens[idx])就建立了它们的关系。两指针分别向后一位。每轮循环父指针
向后一位，而idx向后两位，因为有左右儿子。

1. 建queue，然后首节点入列
2. 进入q的非空循环，队首出列，分别生成非空左右子树，且建立父子关系。idx走两步，非空儿子加入q。

注意事项：

1. #也要入栈，因为结果需要
2. 解码需要一个字符串扫描指针（类全局指针），左右儿子无条件扫两位。这点DFS也是一样的。
3. deserialize中循环条件要加入idx < tokens.length因为serialize末尾#已经删除。
4. 字符串相等判断用equals，不用==。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

public String serialize2(TreeNode root){
	if(root == null)
		return "{}";

	StringBuilder sb = new StringBuilder();
	Queue<TreeNode> q = new LinkedList<>();
	q.add(root);
	while(!q.isEmpty()) {		
		TreeNode n = q.poll();
		sb.append(n == null ? "null" : n.val);
		sb.append(",");
		if(n == null)
			continue;
		q.add(n.left);
		q.add(n.right);
	}
	String res = sb.toString().replaceAll("null", "#");
	int endIdx = res.length() - 1;
	while(res.charAt(endIdx) == ',' || res.charAt(endIdx) == '#')
		endIdx--;
	return "{" + res.substring(0, endIdx + 1) + "}";
}

public TreeNode deserialize2(String data) {
	String str = data.substring(1, data.length() - 1);
	if("".equals(str))
		return null;
	
	String[] tokens = str.split(",");
	int idx = 1;
	Queue<TreeNode> q = new LinkedList<>();
	TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
	q.offer(root);
	while(!q.isEmpty() && idx < tokens.length) {
		TreeNode head = q.poll();
		if(head == null)
			continue;
		head.left = generateChildNode(idx++, tokens, q);
		head.right = generateChildNode(idx++, tokens, q);
	}
	return root;
}

TreeNode generateChildNode(int idx, String[] tokens, Queue<TreeNode> q) {
	TreeNode root = null;
	if(idx < tokens.length && !"#".equals(tokens[idx])) {
		root = new TreeNode(Integer.parseInt(tokens[idx]));
		q.offer(root);
	}
	return root;
}

DFS算法II解题思路：

DFS的serialize很简单，但deserialize比较难。有点类似于前序遍历的递归版。因为编码时候就是前序遍历，解码时候也是先root再左右。 需要维护一个指针p来记录已处理的字符串。

编码方式：

1
2
3
4

    1
  2   3
5  6
=> 1,2,5,#,#,6,#,#,3,#,#

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
34
35
36
37
38

public String serialize(TreeNode root){
	if(root==null)
		return "#";
	String rootStr = root.val+"";
	String lStr = serialize(root.left);
	String rStr = serialize(root.right);
	return rootStr+","+lStr+","+rStr;
}

int p=0;
String[] items = null;

public TreeNode deserialize(String data){
	p = 0;
	items = null;
	return deserializeR(data);
}

public TreeNode deserializeR(String data){
	if(data==null||data.length()==0)
		return null;
	if(p>=data.length())
		return null;
	String curVal = getNext(data);
	if(curVal.equals("#"))
		return null;
	
	TreeNode newRoot = new TreeNode(Integer.parseInt(curVal));
	newRoot.left = deserializeR(data);
	newRoot.right = deserializeR(data);
	return newRoot;
}

public String getNext(String s){
	if(items==null)
		items = s.split(",");
	return items[p++];
}

LeetCode

<div>

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u<sub>1</sub>, v<sub>1</sub>), (u<sub>2</sub>, v<sub>2</sub>), ..., (u<sub>k</sub>, v<sub>k</sub>) with the smallest sums.

Example 1:

<pre>Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Output: [[1,2],[1,4],[1,6]] Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6] </pre>

Example 2:

<pre>Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2 Output: [[1,1],[1,1]] Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3] </pre>

Example 3:

<pre>Input: nums1 = [1,2], nums2 = [3], k = 3 Output: [[1,3],[2,3]] Explanation: All possible pairs are returned from the sequence: [1,3],[2,3] </pre>

Constraints:

• 1 <= nums1.length, nums2.length <= 10<sup>5</sup>
• -10<sup>9</sup> <= nums1[i], nums2[i] <= 10<sup>9</sup>
• nums1 and nums2 both are sorted in ascending order.
• 1 <= k <= 1000

</div>

注意事项：

1. 类似于BFS模板，只不过是将queue换成heap。
2. 将两数和加入到heap中，而不是下标的和(粗心)

Python代码：

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

OFFSET = [(0, 1), (1, 0)]
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
	heap, res = [(nums1[0] + nums2[0], 0, 0)], []
	visited = set([0, 0])
	while heap:
		node = heapq.heappop(heap)
		res.append([nums1[node[1]], nums2[node[2]]])
		if len(res) == k:
			break
		for _dx, _dy in OFFSET:
			_x, _y = node[1] + _dx, node[2] + _dy
			if _x < len(nums1) and _y < len(nums2) and (_x, _y) not in visited:
				heapq.heappush(heap, (nums1[_x] + nums2[_y], _x, _y))
				visited.add((_x, _y))
	return res

算法分析：

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

LeetCode

<div>

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

<pre>Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] </pre>

Example 2:

<pre>Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]] </pre>

Constraints:

• 1 <= nums.length <= 200
• -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
• -10<sup>9</sup> <= target <= 10<sup>9</sup>

</div>

题目大意：

求四数和等于target。这些数值结果排序后不能重复。

解题思路：

类似于3sum，但需要更加一般化。用递归。不能用求所有笛卡尔积版的Two sum，会TLE。

解题步骤：

N/A

注意事项：

1. k_sum接口含k_sum(nums, target, k), 基础case为two_sum, 遍历nums每个元素，若重复跳过，将(子数组，target-nums[i], k-1)递归，返回结果拼接
2. two_sum也是遇到重复元素跳过，若等于target，要左右指针均移动

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

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
	nums.sort()
	return self.k_sum(nums, target, 4)

def k_sum(self, nums, target, k):
	if k == 2:
		return self.two_sum(nums, target)
	# assume 3 sum
	res = []
	for i in range(len(nums)):
		if i >= 1 and nums[i - 1] == nums[i]: # remember
			continue
		sub_res = self.k_sum(nums[i + 1:], target - nums[i], k - 1)
		for li in sub_res:
			res.append([nums[i]] + li)
	return res

def two_sum(self, nums, target):
	i, j, res = 0, len(nums) - 1, []
	while i < j:
		if (i >= 1 and nums[i - 1] == nums[i]) or nums[i] + nums[j] < target:
			i += 1
		elif (j + 1 < len(nums) and nums[j] == nums[j + 1]) or nums[i] + nums[j] > target:
			j -= 1
		else:
			res.append([nums[i], nums[j]]) # remember to use list rather than tuple
			i += 1 # remember
			j -= 1
	return res

算法分析：

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

LeetCode

<div>

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.

You can return the answer in any order.

Example 1:

<pre>Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2 Output: [7,4,1] Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1. </pre>

Example 2:

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

Constraints:

• The number of nodes in the tree is in the range [1, 500].
• 0 <= Node.val <= 500
• All the values Node.val are unique.
• target is the value of one of the nodes in the tree.
• 0 <= k <= 1000

</div>

算法思路：

有三种情况，都容易忽略： 1. 儿子节点 2. 所有父节点路劲上 3. 兄弟节点路径上。而第三种情况要搜另一边的儿子节点（左右不确定）要用visited记录，而且不一定是父亲的兄弟节点，可能爷爷的非父亲的儿子节点。
既然不是单向搜索，不妨转换为图，然后用计算距离BFS模板，只要用map来记录某节点的父亲节点或者增加一个域。BFS中for neighbor in [node.left, node, right, node.parent]

注意事项：

1. root的parent是None，所以从root去赋值parent，而不是从parent root给儿子赋parent
2. Line 13 node.left, node.right, node.parent都可能为None，所以Line14要加not neighbor
3. BFS从target开始而不是root

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

def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
	if not root:
		return []
	self.dfs(root, None)
	queue, visited, distance_to_tgt,  = collections.deque([target]), set([target]), collections.defaultdict(int)
	distance_to_tgt[target], res = 0, []
	while queue:
		node = queue.popleft()
		if distance_to_tgt[node] == k:
			res.append(node.val)
		if distance_to_tgt[node] > k:
			break
		for neighbor in [node.left, node.right, node.parent]:
			if not neighbor or neighbor in visited:  # remember not neighbor
				continue
			queue.append(neighbor)
			visited.add(neighbor)
			distance_to_tgt[neighbor] = distance_to_tgt[node] + 1
	return res

def dfs(self, root, parent):
	if not root:
		return None
	root.parent = parent
	'''if root.left:
		root.left.parent = root
	if root.right:
		root.right.parent = root'''
	self.dfs(root.left, root)  # remember to pass parent
	self.dfs(root.right, root)

算法分析：

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