KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:



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


Example 2:

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


Example 3:

Input: root = []
Output: []


Constraints:

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

题目大意：

二叉树按层遍历

解题思路：

用BFS模板

解题步骤：

N/A

注意事项：

  1. res.append(level)不是res.append(list(level))因为level = []已重新初始化。
  2. 关键行： 多这一行level.append(node.val)，其他一样

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def levelOrder(self, root: TreeNode) -> List[List[int]]:
	if not root:
		return []
	queue, res = collections.deque([root]), []
	while queue:
		level = []
		for _ in range(len(queue)):
			node = queue.popleft()
			level.append(node.val)

			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		res.append(level)
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

Input: s = “leetcode”
Output: 0


Example 2:

Input: s = “loveleetcode”
Output: 2


Example 3:

Input: s = “aabb”
Output: -1


Constraints:

1 <= s.length <= 10<sup>5</sup> s consists of only lowercase English letters.

题目大意：

求字符串中第一个唯一的字符下标

解题思路：

Easy题。先统计频率，然后再遍历一次字符串找到频率为1的字符

解题步骤：

N/A

注意事项：

  1. Python代码：

    1
    2
    3
    4
    5
    6
    def firstUniqChar(self, s: str) -> int:
    	char_to_count = collections.Counter(s)
    	for i in range(len(s)):
    		if char_to_count[s[i]] == 1:
    			return i
    	return -1

算法分析：

时间复杂度为O(n)，空间复杂度O(1), 26个字母为常量空间

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.

题目大意：

判断Sudoku是否合法

解题思路：

类似于Leetcode 037，用3个global的dict

解题步骤：

N/A

注意事项：

  1. 此题和L37有点不同，可以当版上的数是一个个填上的，所以无需初始化将数直接加入到dict中。而是每一位判断是否合法再加入。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def isValidSudoku(self, board: List[List[str]]) -> bool:
	row_dict = [collections.defaultdict(int) for _ in range(len(board))]
	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] == '.':
				continue
			if not self.is_valid(i, j, board[i][j], row_dict, col_dict, box_dict):
				return False
			row_dict[i][board[i][j]] = 1
			col_dict[j][board[i][j]] = 1
			box_dict[i // 3 * 3 + j // 3][board[i][j]] = 1
	return True

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

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

Input: num1 = “2”, num2 = “3”
Output: “6”


Example 2:

Input: num1 = “123”, num2 = “456”
Output: “56088”


Constraints:

1 <= num1.length, num2.length <= 200 num1 and num2 consist of digits only.
* Both num1 and num2 do not contain any leading zero, except the number 0 itself.

题目大意：

求字符串乘法结果

解题思路：

模拟小学乘法

解题步骤：

N/A

注意事项：

  1. 模拟小学乘法，开一个大小为len(num1) + len(num2)的整数数组，内外循环计算每位结果。这位可能是大于20的数，如20, 30..。计算前先反转输入，得到最后结果后也反转。
  2. 结果要消除前缀0，但注意0乘以0的情况会返回空，所以要特别处理。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def multiply(self, num1: str, num2: str) -> str:
	digits = [0] * (len(num1) + len(num2))
	num1, num2 = num1[::-1], num2[::-1]
	for i in range(len(num1)):
		for j in range(len(num2)):
			digits[i + j] += int(num1[i]) * int(num2[j])
	carry, res = 0, ''
	for i in range(len(digits)):
		n = digits[i] + carry
		carry = n // 10
		res += str(n % 10)
	return '0' if res[::-1].lstrip('0') == '' else res[::-1].lstrip('0')

算法分析：

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

Posted on Edited on Disqus:

LeetCode 044 Wildcard Matching



Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

‘?’ Matches any single character.
‘‘ Matches any sequence of characters (including the empty sequence).


The matching should cover the entire input string (not partial).

Note: s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like <font face="monospace">?</font> or ``.

Example 1:

Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.


Example 2:

Input:
s = “aa”
p = ““
Output: true
Explanation: ‘‘ matches any sequence.


Example 3:

Input:
s = “cb”
p = “?a”
Output: false
Explanation: ‘?’ matches ‘c’, but the second letter is ‘a’, which does not match ‘b’.


Example 4:

Input:
s = “adceb”
p = “ab”
Output: true
Explanation: The first ‘‘ matches the empty sequence, while the second ‘‘ matches the substring “dce”.


Example 5:

Input:
s = “acdcb”
p = “ac?b”
*Output: false


题目大意：

通配符外卡匹配问题，有特殊字符”*“和”?”，其中”?” 能代替任何字符，”*“能代替任何字符串。

解题思路：

这是经典题。两字符串匹配题基本就是DP而且知道子问题答案可以推导下一个。

  1. 定义dp[i][j]为字符串s[i-1]和p[j-1]是否能匹配。
  2. 递归式为
    1
    2
    dp[i][j] = dp[i-1][j-1] && (p[j-1] == ? || s[i-1] == p[j-1])  if p[j-1] != \* 
               dp[i-1][j] || dp[i][j-1]                           if p[j-1] == \*
    第一种情况为非*，通配一样字符或?
    第二种情况为*，如果通配就是只移动s，dp[i-1][j]。若不通配（通配完）就只移动p。
  3. 方向为从左到右，从上到下。初始值为dp[0][0] = true。以及若s为空，p为多个*时候，dp[0][j]=true。

注意事项：

  1. 递归式含*不匹配情况dp[i][j-1]，容易忽略。
  2. 初始化s为空，p为多个*。根据递归式来写，i=0时，递归式只剩下dp[i][j-1]。将i = 0带入到内外循环代码实现即可(先写内外循环)
  3. 模板问题： dp初始化先col再row； i循环到len(dp)而不是len(s); 用到p时候是p[i - 1]而不是p[i]

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def isMatch(self, s: str, p: str) -> bool:
	dp = [[False for _ in range(len(p) + 1)] for _ in range(len(s) + 1)] # remember p then s
	dp[0][0] = True
	for j in range(1, len(dp[0])):
		if p[j - 1] == '*':
			dp[0][j] = dp[0][j - 1]
	for i in range(1, len(dp)): # remember len(dp) not len(s)
		for j in range(1, len(dp[0])):
			if p[j - 1] != '*': # remember j-1 not j
				dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '?')
			else:
				dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
	return dp[-1][-1]

注意事项：

  1. 递归式含*不匹配情况dp[i][j-1]，我写的时候忽略了。
  2. 初始化s为空，p为多个*。此情况其实与递归式符合，因为i=1开始，所以i=0的时候，dp[i-1][j]为负值省去，
    只取dp[i][j-1]。
  3. 一开始写的corner case并入到递归式处理。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isMatch(String s, String p) {
	//if(s.isEmpty() && p.isEmpty())
		//return true;
	//if(!s.isEmpty() && p.isEmpty())
		//return false;
	//if(s.isEmpty() && !p.isEmpty() && isAllStars(p))
		//return true;
	//if(s.isEmpty() && !p.isEmpty())
		//return false;
	
	boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
	dp[0][0] = true;
	for(int j = 1; j < dp[0].length; j++)
		// remember empty s can match any prefix *** character in p making sure dp[0][j] = true
		if(p.charAt(j-1) == '*')
			dp[0][j] = dp[0][j-1];
	for(int i = 1; i < dp.length; i++)
		for(int j = 1; j < dp[0].length; j++)
			dp[i][j] = (dp[i-1][j-1] && (p.charAt(j-1) == '?' || s.charAt(i-1) == p.charAt(j-1)))
			// miss dp[i][j-1] means no match on *
			|| ((dp[i-1][j] || dp[i][j-1]) && p.charAt(j-1) == '*'); 
	return dp[dp.length -1][dp[0].length - 1];
}

算法分析：

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

Free mock interview