KK's blog

LeetCode

<div>

Fruits are available at some positions on an infinite x-axis. You are given a 2D integer array fruits where fruits[i] = [position<sub>i</sub>, amount<sub>i</sub>] depicts amount<sub>i</sub> fruits at the position position<sub>i</sub>. fruits is already sorted by position<sub>i</sub> in ascending order, and each position<sub>i</sub> is unique.

You are also given an integer startPos and an integer k. Initially, you are at the position startPos. From any position, you can either walk to the left or right. It takes one step to move one unit on the x-axis, and you can walk at most k steps in total. For every position you reach, you harvest all the fruits at that position, and the fruits will disappear from that position.

Return the maximum total number of fruits you can harvest.

Example 1:

<pre>Input: fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4 Output: 9 Explanation: The optimal way is to:

• Move right to position 6 and harvest 3 fruits
• Move right to position 8 and harvest 6 fruits You moved 3 steps and harvested 3 + 6 = 9 fruits in total. </pre>

Example 2:

<pre>Input: fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4 Output: 14 Explanation: You can move at most k = 4 steps, so you cannot reach position 0 nor 10. The optimal way is to:

• Harvest the 7 fruits at the starting position 5
• Move left to position 4 and harvest 1 fruit
• Move right to position 6 and harvest 2 fruits
• Move right to position 7 and harvest 4 fruits You moved 1 + 3 = 4 steps and harvested 7 + 1 + 2 + 4 = 14 fruits in total. </pre>

Example 3:

<pre>Input: fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2 Output: 0 Explanation: You can move at most k = 2 steps and cannot reach any position with fruits. </pre>

Constraints:

• 1 <= fruits.length <= 10<sup>5</sup>
• fruits[i].length == 2
• 0 <= startPos, position<sub>i</sub> <= 2 * 10<sup>5</sup>
• position<sub>i-1</sub> < position<sub>i</sub> for any i > 0 (0-indexed)
• 1 <= amount<sub>i</sub> <= 10<sup>4</sup>
• 0 <= k <= 2 * 10<sup>5</sup>

</div>

题目大意：

向左向右在规定步数内采集每一格的水果，求最大水果数

算法思路：

一开始考虑用BFS，但由于每个点可以走两次，如先往左再往右，所以不能用BFS
每个点不能走3次，因为贪婪法。所以只要计算单向路径的水果数，单向路径水果数只要计算[startPos - k - 1, startPos + k + 1]的这个区间即可
然后重复路径的范围是[0, k/2 + 1], 枚举这些值然后用presum得到单向路径水果数。

注意事项：

1. 先判断不合法的情况sum(gas) < sum(cost)

Python代码：

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

def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
	pos_to_fruits = collections.defaultdict(int)
	for pair in fruits:
		pos_to_fruits[pair[0]] = pair[1]
	presum = collections.defaultdict(int)
	presum[startPos - k - 1] = pos_to_fruits[startPos - k - 1]
	for i in range(startPos - k, startPos + k + 1):
		presum[i] += presum[i-1] + pos_to_fruits[i]
	res = 0
	for i in range(k//2 + 1):
		res = max(res, presum[startPos + k - i * 2] - presum[startPos - i - 1])
		res = max(res, presum[startPos + i] - presum[startPos - k + i * 2 - 1])
	return res

算法分析：

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

LeetCode

<div>

Given an integer array nums and an integer k, return the k<sup>th</sup> largest element in the array.

Note that it is the k<sup>th</sup> largest element in the sorted order, not the k<sup>th</sup> distinct element.

Example 1:

<pre>Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 </pre>

Example 2:

<pre>Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4 </pre>

Constraints:

• 1 <= k <= nums.length <= 10<sup>4</sup>
• -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

</div>

题目大意：

求第k大的数(1th index)

Heap算法思路：

求第k个最大也就是用最小堆(大->小)

注意事项：

N/A

Python代码：

1
2
3
4
5
6
7
8

def findKthLargest(self, nums: List[int], k: int) -> int:
	res = []  # min heap
	for i in range(len(nums)):
		if i < k:
			heapq.heappush(res, nums[i])
		elif nums[i] > res[0]:
			heapq.heapreplace(res, nums[i])
	return res[0]

算法分析：

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

Quickselect算法II解题思路：

N/A

注意事项：

1. 递归调用仍用m，而不是跟pivot_pos相关，因为m是下标位置
2. partition中range用[start, end)而不是len

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def findKthLargest(self, nums: List[int], k: int) -> int:
	m = len(nums) - k
	return self.quick_select(nums, 0, len(nums) - 1, m)

def quick_select(self, nums, start, end, m):
	if start > end:
		return -1
	pivot_pos = self.partition(nums, start, end)
	if m == pivot_pos:
		return nums[pivot_pos]
	elif m < pivot_pos:
		return self.quick_select(nums, start, pivot_pos - 1, m)
	else:
		return self.quick_select(nums, pivot_pos + 1, end, m)  # remember use m not related to pivot_pos

def partition(self, nums, start, end):
	pivot, no_smaller_index = nums[end], start
	for i in range(start, end):  # remember use start and end not len
		if nums[i] < pivot:
			nums[i], nums[no_smaller_index] = nums[no_smaller_index], nums[i]
			no_smaller_index += 1
	nums[no_smaller_index], nums[end] = nums[end], nums[no_smaller_index]
	return no_smaller_index

算法分析：

T(n) = T(n/2)+n, 时间复杂度为O(n)，空间复杂度O(1)

排序算法III解题思路：

先排序

算法分析：

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

LeetCode

<div>

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

Example 1:

<pre>Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf" </pre>

Example 2:

<pre>Input: words = ["z","x"] Output: "zx" </pre>

Example 3:

<pre>Input: words = ["z","x","z"] Output: "" Explanation: The order is invalid, so return "". </pre>

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists of only lowercase English letters.

</div>

算法思路：

N/A

注意事项：

1. 题目要求： 空字符顺序前于非空字母，否则字典不合法，如abc -> ab, c不能前于空字符，无解。简而言之，后面单词不能是前面的前缀return False if len(word) > len(word2) else True
2. 模板问题： graph要含所有节点，包括没有边的节点。否则结果会有遗漏graph = Counter({c: [] for word in words for c in word})
3. 模板问题： in_degree初始化要对所有节点赋0， in_degree[c] = 0。in_degree = collections.defaultdict(int)并不能产生key
4. 模板问题： 第四步判断是否含循环必不可少，题目要求可能不合法，return res if len(graph) == len(res) else ''
5. 语法错误： graph.items()记得加items。res是str不是list

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 alienOrder(self, words: List[str]) -> str:
	# graph = collections.defaultdict(list)
	graph = Counter({c: [] for word in words for c in word})
	for i in range(1, len(words)):
		if not self.populate_one_order(words[i - 1], words[i], graph):
			return ''
	in_degree = collections.defaultdict(int)
	for c in graph.keys():
		in_degree[c] = 0
	for key, li in graph.items():
		for j in range(len(li)):
			in_degree[li[j]] += 1
	res = ''
	queue = deque([node for node, in_degree_num in in_degree.items() if in_degree_num == 0])
	while queue:
		node = queue.popleft()
		res += node
		for neighbor in graph[node]:
			in_degree[neighbor] -= 1
			if in_degree[neighbor] == 0:
				queue.append(neighbor)
	return res if len(graph) == len(res) else ''

def populate_one_order(self, word, word2, graph):
	for j in range(min(len(word), len(word2))):
		if word[j] != word2[j]:
			graph[word[j]].append(word2[j])
			return True
	return False if len(word) > len(word2) else True

算法分析：

时间复杂度为O(V + E)，空间复杂度O(O + E)，V为节点数，E为边数，n为单词数，L为最长单词长度，O = nL， E = L，而空间复杂度图的空间为O + E，而queue空间最多为26条边，26个字母，in_degree空间为O(V)。所以总的时间复杂度为O(nL)，空间复杂度O(nL)

LeetCode

<div>

Given a pattern and a string s, return true if s matches the pattern.

A string s matches a pattern if there is some bijective mapping of single characters to strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

Example 1:

<pre>Input: pattern = "abab", s = "redblueredblue" Output: true Explanation: One possible mapping is as follows: 'a' -> "red" 'b' -> "blue"</pre>

Example 2:

<pre>Input: pattern = "aaaa", s = "asdasdasdasd" Output: true Explanation: One possible mapping is as follows: 'a' -> "asd" </pre>

Example 3:

<pre>Input: pattern = "abab", s = "asdasdasdasd" Output: true Explanation: One possible mapping is as follows: 'a' -> "a" 'b' -> "sdasd" Note that 'a' and 'b' cannot both map to "asd" since the mapping is a bijection. </pre>

Example 4:

<pre>Input: pattern = "aabb", s = "xyzabcxzyabc" Output: false </pre>

Constraints:

• 1 <= pattern.length, s.length <= 20
• pattern and s consist of only lower-case English letters.

</div>

算法思路：

类似于word break，但由于要存储处理过map和set，DP不能处理，所以只能用DFS

注意事项：

1. 比较映射，用Map比较A->B的映射，如已有a->dog, 另一对映射a->cat通过查找Map知道不合法。B->A的映射可通过将map的所有value存到一个set中知道。如a->dog, b->dog. b不在Map中但b对应的dog在set中，不合法。
   DFS的API为dfs(pattern, word, pattern_to_word, used_set)
2. 若pattern的字母出现过，如aba，不应进入循环，更不应该加入到map和set中，应该用startswith比较word判断是否合法，若是，直接下一轮DFS(Line 11 -15)
3. 1中的两情况的第一种情况以及第二种情况的前半部分(b不在map中)在2中已经处理，所以只要在循环中处理第二种情况后半部分(b对应的dog在set中)即可(Line 22 - 23)

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

def wordPatternMatch(self, pattern: str, s: str) -> bool:
	if not pattern or not s:
		return False
	return self.dfs(pattern, s, 0, 0, {}, set())

def dfs(self, pattern, s, start_p, start_s, pattern_to_s, s_set):
	if start_p >= len(pattern) and start_s >= len(s):
		return True
	if start_p >= len(pattern) or start_s >= len(s):
		return False
	char = pattern[start_p]
	if char in pattern_to_s:
		word = pattern_to_s[char]
		if not s[start_s:].startswith(word):
			return False
		return self.dfs(pattern, s, start_p + 1, start_s + len(word), pattern_to_s, s_set)
		
	for j in range(start_s, len(s)):
		matched_word = s[start_s:j + 1]
		'''if char in pattern_to_s and pattern_to_s[char] != matched_word:
			continue
		if char not in pattern_to_s and matched_word in s_set:  # remembers
			continue'''
		if matched_word in s_set:
			continue
		pattern_to_s[char] = matched_word
		s_set.add(matched_word)
		if self.dfs(pattern, s, start_p + 1, j + 1, pattern_to_s, s_set):
			return True
		s_set.remove(matched_word)
		pattern_to_s.pop(char)
	return False

算法分析：

时间复杂度为O(解大小)，空间复杂度为O(解大小)。

LeetCode

<div>

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

<pre>Input: n = 5, bad = 4 Output: 4 Explanation: call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Then 4 is the first bad version. </pre>

Example 2:

<pre>Input: n = 1, bad = 1 Output: 1 </pre>

Constraints:

• 1 <= bad <= n <= 2<sup>31</sup> - 1

</div>

算法思路：

N/A

注意事项：

1. 题目是先good再bad，所以用first position模板

Python代码：

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

def firstBadVersion(self, n):
	start, end = 0, n
	while start + 1 < end:
		mid = start + (end - start) // 2
		if isBadVersion(mid):
			end = mid
		else:
			start = mid
	if isBadVersion(start):
		return start
	if isBadVersion(end):
		return end
	return -1   

Java代码：

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

public int firstBadVersion(int n) {
	int start = 1, end = n;
	while(start + 1 < end) {
		int mid = start + (end - start) / 2;
		if(isBadVersion(mid)) 
			end = mid;
		else 
			start = mid;
	}
	if(isBadVersion(start))
		return start;
	else
		return end;
}

算法分析：

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