KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:



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


Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]


Constraints:

1 <= preorder.length <= 3000 inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000 preorder and inorder consist of unique values.
Each value of inorder also appears in preorder. preorder is guaranteed to be the preorder traversal of the tree.
inorder is *guaranteed to be the inorder traversal of the tree.

算法思路：

N/A

注意事项：

  1. 用递归实现，in_order字符串分左右两段子串递归到左右儿子，pre_order字符串每轮递归用pop(0)原地去除首位，再递归到儿子节点
  2. 终止条件为in_order字符串为空。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
	if not inorder:
		return None
	head = preorder.pop(0)
	index = inorder.index(head)
	left_inorder, right_inorder = inorder[:index], inorder[index + 1:]

	root = TreeNode(head)
	root.left = self.buildTree(preorder, left_inorder)
	root.right = self.buildTree(preorder, right_inorder)
	return root

算法分析：

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

Posted on Edited on Disqus:

LeetCode



We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:



Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job.
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.


Example 2:



Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job.
Profit obtained 150 = 20 + 70 + 60.


Example 3:



Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6


Constraints:

`1 <= startTime.length == endTime.length == profit.length <= 5 104*1 <= startTime[i] < endTime[i] <= 109*1 <= profit[i] <= 104`

算法思路：

DP + 排序
一开始以为类似于meeting rooms II，所以用heap，但只能计算conflicts不能计算profits，但排序思想有用。
求最值问题第一时间考虑用DP，所以考虑以第i-1个job为结尾的最大利润： 


dp[i] = max -> dp[j] + profits[i-1]), 第i个job的startTime[i-1] >= endTime[j], 第j个job与第i个job没有conflicts
            -> dp[j]                                                          第j个job与第i个job有conflicts

复杂度为O(n^2)

写出递归式后，求startTime >= endTime其实就是按endTime排序，这样有助于搜索这个条件. 这里有个难点是要加强命题至累计利润，因为正如Cooldown股票题一样，dp[j]不应该是以job j为结尾的最大利润，而应该是前j个job的最大利润，这些job不一定都是相邻
加强命题dp[i]是累计利润，也就是并不需要计算所有dp[j…i]的值（第一式子），公式变成 


dp[i] = max -> dp[j] + profits[i-1]), j = start[i-1]对应的Endtime下标, 第j个job与第i个job没有conflicts
            -> dp[j]                                                   第j个job与第i个job有conflicts

要找出这个j，就对刚才排序了的endtime数组用bisect找下标。类似于LIS, 复杂度为O(nlogn)

注意事项：

  1. bisect的使用求大于startTime的endTime下标，此下标j减一正是所求，但dp和数组中下标转换是差1，所以dp[j - 1 + 1]是前值的DP值。
  2. 加强命题至累计利润dp[i], 见line 9 - 10

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
	job_by_endtime, dp, max_profit = [], [0] * (len(startTime) + 1), 0
	for i in range(len(startTime)):
		job_by_endtime.append((endTime[i], startTime[i], profit[i]))
	job_by_endtime.sort()
	end_time_sorted = [pair[0] for pair in job_by_endtime]
	for i in range(1, len(dp)):
		j = bisect.bisect(end_time_sorted, job_by_endtime[i - 1][1]) # previous end time <= current start time
		dp[i] = max(max_profit, dp[j] + job_by_endtime[i - 1][2]) # remember
		max_profit = max(max_profit, dp[i]) # remember
	return dp[-1]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



A certain bug’s home is on the x-axis at position x. Help them get there from position 0.

The bug jumps according to the following rules:

It can jump exactly a positions forward (to the right). It can jump exactly b positions backward (to the left).
It cannot jump backward twice in a row. It cannot jump to any forbidden positions.

The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

Example 1:

Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output: 3
Explanation: 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.


Example 2:

Input: forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
Output: -1


Example 3:

Input: forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
Output: 2
Explanation: One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home.


Constraints:

1 <= forbidden.length <= 1000 1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000 All the elements in forbidden are distinct.
* Position x is not forbidden.

题目大意：

求从0到x的最小步数，可以往前跳a步，往后跳b步，不能跳到负数，不能连续两次往前跳，不能跳到被禁止的位置。

算法思路：

类似于Jump game，不过此题要用真的BFS，用三个元素push如queue: (point, distance, is_backward), is_backward记录是否回退两次而剪枝，distance是结果。

注意事项：

  1. 用BFS模板，但此题到了某个位置可以有两个状态：向前跳和向后跳。所以visited不能只含位置，必须包含方向，(position, is_backward). if (neighbor, neighbor_is_backward) in visited也记得包含方向，否则LTE，因为Python不会检查是否tuple
  2. upper limit为max(x, max(forbidden)) + a + b，否则LTE，这个比较推导，可以这么理解max(x, max(forbidden))之后可以自由不受限制地走，必定存在一个点之后会重复且无意义，如a和b的最小倍数。举个例子找规律，a=2, b=1, x=10, 要走到11的话就要先到x+a+b再往回走

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
	forbidden_set = set(forbidden)
	limit = max(x, max(forbidden)) + a + b
	queue = collections.deque([(0, 0, False)])
	visited = set([(0, False)])  # remember two states
	while queue:
		node = queue.popleft()
		if node[0] == x:
			return node[1]
		for neighbor in [node[0] + a, node[0] - b]:
			if neighbor in forbidden_set or neighbor < 0 or neighbor > limit: # remember limit
				continue
			if neighbor == node[0] - b and node[2]: # no backward twice
				continue
			neighbor_is_backward = True if neighbor == node[0] - b else False
			if (neighbor, neighbor_is_backward) in visited: # remember not neighbor in visited - LTE
				continue
			queue.append((neighbor, node[1] + 1, neighbor_is_backward))
			visited.add((neighbor, neighbor_is_backward))
	return -1

算法分析：

时间复杂度为O(max(x, max(forbidden)) + a + b)，空间复杂度O(max(x, max(forbidden)) + a + b)

Posted on Edited on Disqus:

LeetCode



Give a binary string s, return the number of non-empty substrings that have the same number of 0‘s and 1‘s, and all the 0‘s and all the 1‘s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: s = “00110011”
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1’s and 0’s: “0011”, “01”, “1100”, “10”, “0011”, and “01”.
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, “00110011” is not a valid substring because all the 0’s (and 1’s) are not grouped together.


Example 2:

Input: s = “10101”
Output: 4
Explanation: There are 4 substrings: “10”, “01”, “10”, “01” that have equal number of consecutive 1’s and 0’s.


Constraints:

1 <= s.length <= 10<sup>5</sup> s[i] is either '0' or '1'.

题目大意：

子串中，连续0和连续1的个数中间对称，求这样的子串的个数

算法思路：

这题至少medium，一开始考虑给定一个字符串怎么判断是否满足条件，统计个数和flag变化。然后是双重循环分别以a[0..n-1]为开头的子串判断，若不满足就跳出内循环，复杂度为O(n).
既然是连续，又是只有0和1，不妨考虑统计个数。如00110011,统计0和1的个数为count=[2,2,2,2]相邻的数代表不同种类，所以去min(count[i-1], count[i])，如2, 2可以是01/10, 0011/1100两种，具体以哪个数开始取决于数组本身。统计i=[1..n-1]即所求。复杂度为O(n).

注意事项：

  1. 累计思想，按0和1累计得到累计数组，然后求相邻最小个数的和。
  2. 循环出来，处理最后一个部分。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def countBinarySubstrings(self, s: str) -> int:
	presum, count, res = [], 1, 0
	for i in range(1, len(s)): #
		if s[i - 1] == s[i]:
			count += 1
		else:
			presum.append(count) #[2, 2,2,2]
			count = 1
	if count > 0:
		presum.append(count)
	for i in range(1, len(presum)):
		res += min(presum[i - 1], presum[i])
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(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]

注意事项：

  1. 见到最值且跟图相关，就考虑用BFS，而且要侦测循环就要用拓扑排序。要记录父节点颜色的累计和，考虑用DP，DP跟颜色相关且颜色都是小写字母，也就是26种
  2. 递归式是所有直接父节点的最大值。因为若有两条路径到达child这个节点，路径1第a种颜色有2个，而路径上第a种颜色有5个。
  3. 计算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)

Free mock interview