KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used. Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.


Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.


Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.


Constraints:

2 <= k <= 9 1 <= n <= 60

题目大意：

数字1-9的组合个数为k的组合和等于k，每个元素最多用一次

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

  1. Leetcode 40和77的结合。个数和target都要达到。用if k == 0 and target == 0

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
	nums = [_ for _ in range(1, 10)]
	res = []
	self.dfs(nums, 0, k, n, [], res)
	return res

def dfs(self, nums, start, k, target, path, res):
	if k == 0 and target == 0:
		res.append(list(path))
		return
	if k == 0:
		return
	for i in range(start, len(nums)):
		path.append(nums[i])
		self.dfs(nums, i + 1, k - 1, target - nums[i], path, res)
		path.pop()

算法分析：

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

Posted on Edited on Disqus:

LeetCode

Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: 1. Each of the digits 1-9 must occur exactly once in each row. 2. Each of the digits 1-9 must occur exactly once in each column. 3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells. Example 1: 

Input: board = [[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”],[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”],[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”],[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”],[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”],[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”],[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”],[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”],[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]
Output: [[“5”,”3”,”4”,”6”,”7”,”8”,”9”,”1”,”2”],[“6”,”7”,”2”,”1”,”9”,”5”,”3”,”4”,”8”],[“1”,”9”,”8”,”3”,”4”,”2”,”5”,”6”,”7”],[“8”,”5”,”9”,”7”,”6”,”1”,”4”,”2”,”3”],[“4”,”2”,”6”,”8”,”5”,”3”,”7”,”9”,”1”],[“7”,”1”,”3”,”9”,”2”,”4”,”8”,”5”,”6”],[“9”,”6”,”1”,”5”,”3”,”7”,”2”,”8”,”4”],[“2”,”8”,”7”,”4”,”1”,”9”,”6”,”3”,”5”],[“3”,”4”,”5”,”2”,”8”,”6”,”1”,”7”,”9”]]
Explanation: The input board is shown above and the only valid solution is shown below:




Constraints: board.length == 9 board[i].length == 9 board[i][j] is a digit or '.'. It is guaranteed that the input board has only one solution.

题目大意：

日本游戏。需要保证每行每列每个9个方块的数是1-9里唯一。

Global dict解题思路(推荐)：

DFS。利用DFS模板

解题步骤：

N/A

注意事项：

  1. 用三种全局性dict(row, col, box)来记录所有已填的数，方便dfs时候迅速判断是否合法。这是比算法II优胜的地方。Python中不存在list of set只能用list of dict： [collections.defaultdict(int) for _ in range(len(board))]
  2. 初始化要将棋局上所有已有的数加入到dict中。一开始是dfs时候才加，但这样填的数不知道后面的格是否已经存在。题意保证有解，所以这些数不需验证重复。
  3. for循环是1-9是数字但棋盘是字符，所以要字符和数字转化，选择统一转成数字，不转的话dict会实效。
  4. box_dict的id转换： i // 3 * 3 + j // 3
  5. 终止条件为start_x == len(board) - 1 and start_y == len(board[0])

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
39
40
41
42
43
44
def solveSudoku(self, board: List[List[str]]) -> None:
	row_dict = [collections.defaultdict(int) for _ in range(len(board))] # remember
	col_dict = [collections.defaultdict(int) for _ in range(len(board))]
	box_dict = [collections.defaultdict(int) for _ in range(len(board))]

	for i in range(len(board)):
		for j in range(len(board[0])):
			if board[i][j] != '.':
				self.add_to_dict(board, i, j, row_dict, col_dict, box_dict) # rememeber
	return self.dfs(board, 0, 0, row_dict, col_dict, box_dict)

def dfs(self, board, start_x, start_y, row_dict, col_dict, box_dict):
	if start_x == len(board) - 1 and start_y == len(board[0]):
		return True
	if start_y == len(board[0]):
		start_x += 1
		start_y = 0
	if board[start_x][start_y] != '.':
		return self.dfs(board, start_x, start_y + 1, row_dict, col_dict, box_dict) # guarantee solution
	for k in range(1, 10):
		if not self.is_valid(board, k, start_x, start_y, row_dict, col_dict, box_dict):
			continue
		board[start_x][start_y] = str(k)
		self.add_to_dict(board, start_x, start_y, row_dict, col_dict, box_dict)
		if self.dfs(board, start_x, start_y + 1, row_dict, col_dict, box_dict):
			return True
		self.remove_from_dict(board, start_x, start_y, row_dict, col_dict, box_dict)
		board[start_x][start_y] = '.'
	return False

def add_to_dict(self, board, i, j, row_dict, col_dict, box_dict):
	row_dict[i][int(board[i][j])] = 1 # remember
	col_dict[j][int(board[i][j])] = 1
	box_dict[i // 3 * 3 + j // 3][int(board[i][j])] = 1

def remove_from_dict(self, board, i, j, row_dict, col_dict, box_dict):
	row_dict[i].pop(int(board[i][j]))
	col_dict[j].pop(int(board[i][j]))
	box_dict[i // 3 * 3 + j // 3].pop(int(board[i][j]))

def is_valid(self, board, k, i, j, row_dict, col_dict, box_dict):
	if k in row_dict[i] or k in col_dict[j] or k in box_dict[i // 3 * 3 + j // 3]: # remember
		return False
	return True

算法分析：

三重循环，时间复杂度为O(9n*n)，空间复杂度O(n)，n为边长

常量空间算法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
39
40
41
42
43
def solveSudoku2(self, board: List[List[str]]) -> None:
	return self.dfs2(board, 0, 0)

def dfs2(self, board, start_x, start_y):
	if start_x == len(board) - 1 and start_y == len(board[0]):
		return True
	if start_y == len(board[0]):
		start_x += 1
		start_y = 0
	if board[start_x][start_y] != '.':
		return self.dfs2(board, start_x, start_y + 1) # guarantee solution
		'''
		if self.is_sudoku(board, start_x, start_y):
			return self.dfs(board, start_x, start_y + 1)
		else:
			return False
		'''
	for k in range(1, 10):
		board[start_x][start_y] = str(k)
		if self.is_sudoku2(board, start_x, start_y) and self.dfs2(board, start_x, start_y + 1):
			return True
		board[start_x][start_y] = '.'
	return False

def is_sudoku2(self, board, x, y):
	# row, # col, # square
	if self.is_valid(board, x, 0, x, len(board[0]) - 1) and self.is_valid(board, 0, y, len(board) - 1, y) and \
			self.is_valid(board, x // 3 * 3, y // 3 * 3, x // 3 * 3 + 2, y // 3 * 3 + 2):
		return True
	else:
		return False

def is_valid(self, board, start_x, start_y, end_x, end_y):
	num_set = set()
	for i in range(start_x, end_x + 1):
		for j in range(start_y, end_y + 1):
			val = board[i][j]
			if val == '.':
				continue
			if int(val) in num_set:
				return False
			num_set.add(int(val))
	return True

算法分析：

三重循环，时间复杂度为O(81n*n)，空间复杂度O(1)，n为边长

Posted on Edited on Disqus:

LeetCode



Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}


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

Example 1:



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


Example 2:



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


Example 3:

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


Constraints:

The number of nodes in the tree is in the range [2, 10<sup>5</sup>]. -10<sup>9</sup> <= Node.val <= 10<sup>9</sup>
All Node.val are unique. p != q
* p and q exist in the tree.

题目大意：

求带父节点的树中的两个节点的LCA。节点值唯一，且两输入节点不同，且一定存在

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. 某一个节点的左右父节点存入set中，另一节点的每个父节点在set中找

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
	parent_set = set()
	it = p
	while it:
		parent_set.add(it)
		it = it.parent
	it = q
	while it:
		if it in parent_set:
			return it
		it = it.parent
	return None

算法分析：

时间复杂度为O(n + m)，空间复杂度O(n)，n和m为所有父亲路径长

Posted on Edited on Disqus:

LeetCode

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.



Given an integer n, return the nth ugly number.



 


Example 1:



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


Example 2:



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


 


Constraints:




  • 1 <= n <= 1690


题目大意：

求第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).

Posted on Edited on Disqus:

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: 

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as `"[1,2,3,null,null,4,5]"`

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++];
}
Free mock interview