KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the m x n maze, the ball’s start position and the destination, where start = [start<sub>row</sub>, start<sub>col</sub>] and destination = [destination<sub>row</sub>, destination<sub>col</sub>], return true if the ball can stop at the destination, otherwise return false.

You may assume that the borders of the maze are all walls (see examples).

Example 1:



Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.


Example 2:



Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
Output: false
Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.


Example 3:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
Output: false


Constraints:

m == maze.length n == maze[i].length
1 <= m, n <= 100 maze[i][j] is 0 or 1.
start.length == 2 destination.length == 2
0 <= start<sub>row</sub>, destination<sub>row</sub> <= m 0 <= start<sub>col</sub>, destination<sub>col</sub> <= n
Both the ball and the destination exist in an empty space, and they will not be in the same position initially. The maze contains at least 2 empty spaces.

题目大意：

球在玉米迷宫上滚，当遇到边界或玉米会停下，停下后可以转任意方向。求能否停在目标上。

算法思路：

二维数组求目标第一时间想到用BFS，此题求能停下的点而不是所有点。所以属于一组节点作为一层的BFS，也就是说只有能停下的位置才算BFS的一层，才加入都队列，其他停不来的点均忽略。这是此题的难点。

注意事项：

  1. 属于一组节点作为一层的BFS，能停下的点才加入到queue。比标准模板多了Line 10 - 11. 停下包括边界和玉米(maze[x][y] == 1)
  2. 要滚回一步Line 12 - 15，因为line 10循环的终结状态为出界或玉米上。要滚回一步到空地上。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
	queue = collections.deque([(start[0], start[1])])
	visited = set([(start[0], start[1])])
	while queue:
		node = queue.popleft()
		if node[0] == destination[0] and node[1] == destination[1]:
			return True
		for _dx, _dy in OFFSETS:
			x, y = node[0], node[1]
			while 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0: # remember maze[x][y] == 0
				x, y = x + _dx, y + _dy
			if (x - _dx, y - _dy) in visited: # remember
				continue
			queue.append((x - _dx, y - _dy))
			visited.add((x - _dx, y - _dy))
	return False

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given a string s, find the longest palindromic subsequence‘s length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = “bbbab”
Output: 4
Explanation: One possible longest palindromic subsequence is “bbbb”.


Example 2:

Input: s = “cbbd”
Output: 2
Explanation: One possible longest palindromic subsequence is “bb”.


Constraints:

1 <= s.length <= 1000 s consists only of lowercase English letters.

题目大意：

求字符串中最长回文序列

算法思路：

一开始看到子序列如LIS就想用DP，dp[i]表示以s[i]为结尾的最长回文子序列。但不容易推导公式，难点是没有限制左边界
所以应该扩展到二维dp[i][j]表示[i, j]之间的最长回文子序列。公式就简单多了

1
2
dp[i][j] = dp[i+1][j-1] + 2,             s[i] == s[j]
         = max(dp[i+1][j], dp[i][j-1]),  s[i] != s[j]

注意事项：

  1. 难点是想到用二维DP(区间型DP)。用区间型递归模板，注意dp[i + 1][j]并不是i - 1
  2. 初始值为dp[i][i] = 1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def longestPalindromeSubseq(self, s: str) -> int:
	dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
	for i in range(len(s)):
		dp[i][i] = 1
	for k in range(1, len(s)):
		for i in range(len(s) - k):
			j = i + k
			if s[i] == s[j]:
				dp[i][j] = dp[i + 1][j - 1] + 2
			else:
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
	return dp[0][-1]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1.

You are given a string colors where colors[i] is a lowercase English letter representing the color of the i<sup>th</sup> node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [a<sub>j</sub>, b<sub>j</sub>] indicates that there is a directed edge from node a<sub>j</sub> to node b<sub>j</sub>.

A valid path in the graph is a sequence of nodes x<sub>1</sub> -> x<sub>2</sub> -> x<sub>3</sub> -> ... -> x<sub>k</sub> such that there is a directed edge from x<sub>i</sub> to x<sub>i+1</sub> for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.

Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.

Example 1:



Input: colors = “abaca”, edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).


Example 2:



Input: colors = “a”, edges = [[0,0]]
Output: -1
Explanation: There is a cycle from 0 to 0.


Constraints:

n == colors.length m == edges.length
1 <= n <= 10<sup>5</sup> 0 <= m <= 10<sup>5</sup>
colors consists of lowercase English letters. 0 <= a<sub>j</sub>, b<sub>j</sub> < n

题目大意：

给定一个图，有n个节点，每个节点的颜色已知，用a-z表示，求所有不循环路径上同种颜色的最大节点数，若有循环返回-1.

算法思路：

拓扑排序 + DP

  1. 看到侦测循环考虑用拓扑排序
  2. 拓扑排序的同时，如果知道父亲节点有最大的同种颜色数，容易计算儿子的同种颜色数dp[child]
    dp[child] = max(dp[parent]) for all the parents for the child
    由于有26种颜色，扩展到最大的第i种颜色数dp[child][i]表示以child为结尾的路径上第i种颜色的累计最大节点数 
    1
    2
    dp[child][i] = max(dp[parent][i] + 1) if color[child] == color[parent] for all the immediate parents for the child, i = 1..26 
    			= max(dp[parent][i])     if color[child] != color[parent]

    注意事项：

  3. 见到最值且跟图相关，就考虑用BFS，而且要侦测循环就要用拓扑排序。要记录父节点颜色的累计和，考虑用DP，DP跟颜色相关且颜色都是小写字母，也就是26种
  4. 递归式是所有直接父节点的最大值。因为若有两条路径到达child这个节点，路径1第a种颜色有2个，而路径上第a种颜色有5个。
  5. 计算dp值在知道边的始点和终点上，也就是入度数减一之前。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
	graph = [[] for _ in range(len(colors))]
	in_degree = [0] * len(colors)
	for _edge in edges:
		graph[_edge[0]].append(_edge[1])
		in_degree[_edge[1]] += 1
	res = []
	dp = [[0 for _ in range(26)] for _ in range(len(colors))]
	initial_nodes = [i for i in range(len(in_degree)) if in_degree[i] == 0]
	for _node in initial_nodes:
		dp[_node][ord(colors[_node]) - ord('a')] = 1
	queue = collections.deque(initial_nodes)
	while queue:
		node = queue.popleft()
		res.append(node)
		for j in graph[node]:
			for i in range(26):
				dp[j][i] = max(dp[j][i], dp[node][i] + (1 if ord(colors[j]) - ord('a') == i else 0)) # remember max(dp[j][i]
			in_degree[j] -= 1
			if in_degree[j] == 0:
				queue.append(j)
	return -1 if len(colors) != len(res) else max(map(max, dp))

算法分析：

时间复杂度为O(V + E)，空间复杂度O(V + E)

Posted on Edited on Disqus:

LeetCode

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

**Input:** root = [1,2,2,3,4,4,3]
**Output:** true

Example 2:

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

Constraints:

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

Follow up: Could you solve it both recursively and iteratively?

题目大意：

判断二叉树是否对称

解题思路：

Easy题，但难点是转化成比较两棵树是否对称

解题步骤：

N/A

注意事项：

  1. 难点是转化成比较两棵树是否对称
  2. 还要比较值相等，root.val == root2.val

Python代码：

1
2
3
4
5
6
7
8
9
def isSymmetric(self, root: TreeNode) -> bool:
	return self.is_symmetric(root.left, root.right)

def is_symmetric(self, root, root2):
	if not root and not root2:
		return True
	if not root or not root2:
		return False
	return root.val == root2.val and self.is_symmetric(root.left, root2.right) and self.is_symmetric(root.right, root2.left)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Numbers can be regarded as the product of their factors.

For example, 8 = 2 x 2 x 2 = 2 x 4.

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note that the factors should be in the range [2, n - 1].

Example 1:

Input: n = 1
Output: []


Example 2:

Input: n = 12
Output: [[2,6],[3,4],[2,2,3]]


Example 3:

Input: n = 37
Output: []


Constraints: 1 <= n <= 10<sup>7</sup>

题目大意：

求所有因式分解

解题思路：

求所有解，所以用DFS。类似于LeetCode 039 Combination Sum元素可复用。

解题步骤：

N/A

注意事项：

  1. 类似于元素可复用的组合和。但更似全组合模板，append发生在循环中，而不是终止条件中。比如12，遇到2就把商[2, 6]加入到结果
  2. 数值区间的组合，start和target都是数值，而不是数组长度。i是从start开始，而不是从2开始，保证path里的数有序
  3. target // i < i 保证path里的数有序，否则12=232，不可行
  4. i从start循环到math.sqrt(n) + 1，否则会TLE

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def getFactors(self, n: int) -> List[List[int]]:
	res = []
	self.dfs(n, 2, n, [], res)
	return res

def dfs(self, n, start, target, path, res):
	if target == 1:
		return
	for i in range(start, int(math.sqrt(n) + 1)): # remember to use start
		if target % i != 0 or target // i < i: # remember
			continue
		path.append(i)
		res.append(list(path + [target // i]))
		self.dfs(n, i, target // i, path, res) 
		path.pop()

算法分析：

时间复杂度为O(2n)，空间复杂度O(# of prime factors)

Free mock interview