KK's blog

LeetCode 628 Maximum Product of Three Numbers

Posted on 2022-01-29 Edited on 2026-06-03 Disqus:

LeetCode

<div>

Given an integer array nums, find three numbers whose product is maximum and return the maximum product.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

3 <= nums.length <= 104
-1000 <= nums[i] <= 1000

</div>

题目大意：

求数组任意三个数的最大乘积

排序法解题思路：

数学题，正负数分开，最大只可以是排序后最大的三个数(全正，全负)或最大整数乘以最小两个负数(正负均有)

解题步骤：

N/A

注意事项：

Python代码：

1
2
3

def maximumProduct(self, nums: List[int]) -> int:
	nums.sort()
	return max(nums[-1] * nums[-2] * nums[-3], nums[-1] * nums[0] * nums[1])

算法分析：

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

Heap算法II解题思路：

由上述思路进一步优化，不需要全部排序，只需要知道最大的3个数和最小的两个数即可

Python代码：

def maximumProduct2(self, nums: List[int]) -> int:
	largest = heapq.nlargest(3, nums)
	smallest = heapq.nsmallest(2, nums)
	return max(largest[0] * largest[1] * largest[2], largest[0] * smallest[0] * smallest[1])

算法分析：

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

LeetCode 1048 Longest String Chain

Posted on 2022-01-28 Edited on 2026-06-03 Disqus:

LeetCode 1048 Longest String Chain

<div>

You are given an array of words where each word consists of lowercase English letters.

wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.

For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chainis a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

Example 1:

<pre>Input: words = ["a","b","ba","bca","bda","bdca"] Output: 4 Explanation: One of the longest word chains is ["a","ba","bda","bdca"]. </pre>

Example 2:

<pre>Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"] Output: 5 Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"]. </pre>

Example 3:

<pre>Input: words = ["abcd","dbqca"] Output: 1 Explanation: The trivial word chain ["abcd"] is one of the longest word chains. ["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed. </pre>

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of lowercase English letters.

</div>

Problem Overview

Get longgest one-character transformation in the given list

Thinking Process

This problem is similar to Word Break (reversed to get neighbors) but it is a multi-source longest path problem.

Steps

Loop through each word
BFS from each word and get the max distance
Get the max of distance

Notes

max_dis = 1 by default in BFS
To improve the complexity, make the distance map global so that the distance of each node will be calculated once.
To do that, sort the list from longest to shortest and make sure the it is greedy to get the max distance

Python代码：

def longestStrChain(self, words: List[str]) -> int:
	word_dict, distance = set(words), {}
	max_dis = 0
	words.sort(key=len, reverse=True)  # remember
	for word in words:
		dis = self.bfs(word, word_dict, distance)
		max_dis = max(max_dis, dis)
	return max_dis

def bfs(self, word, word_dict, distance):
	queue = deque([word])
	visited = {word}
	if word in distance:  # remember
		return distance[word]
	distance[word] = 1
	max_dis = 1
	while queue:
		node = queue.popleft()
		for neighbor in self.get_neighbors(node, word_dict):
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
			distance[neighbor] = distance[node] + 1
			max_dis = max(max_dis, distance[neighbor])
	return max_dis

def get_neighbors(self, word, word_dict):
	res = []
	for i in range(len(word)):
		new_word = word[:i] + word[i + 1:]
		if new_word in word_dict:
			res.append(new_word)
	return res

Analysis

Though there is a loop and bfs like n^2, actually it is a traversal in a graph. n * L (n is # of nodes, L is max of path
single-source) is the num of edges. Another L is to get neighbors.
Time complexity<code>O(nlogn + n*L2)</code>, Space complexityO(n).

LeetCode 366 Find Leaves of Binary Tree

Posted on 2022-01-27 Edited on 2026-06-03 Disqus:

LeetCode

<div>

Given the root of a binary tree, collect a tree's nodes as if you were doing this:

Collect all the leaf nodes.
Remove all the leaf nodes.
Repeat until the tree is empty.

Example 1:

<pre>Input: root = [1,2,3,4,5] Output: [[4,5,3],[2],[1]] Explanation: [[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned. </pre>

Example 2:

<pre>Input: root = [1] Output: [[1]] </pre>

Constraints:

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

</div>

题目大意：

求逐层叶子剥离的所有叶子节点，按剥离顺序放入结果

解题思路：

考虑BFS从上到下，但深度不对，因为是从叶子节点开始计算的，如例子所示，根节点1的高度取决于儿子的最大深度。所以应该从底到上计算，也就是DFS

解题步骤：

N/A

注意事项：

从底到上计算高度，取左右树的最大高度

Python代码：

def findLeaves(self, root: TreeNode) -> List[List[int]]:
	res = []
	self.dfs(root, res)
	return res

def dfs(self, root, res):
	if not root:
		return 0
	if not root.left and not root.right:
		if len(res) == 0:
			res.append([root.val])
		else:
			res[0].append(root.val)
		return 1
	left_depth = self.dfs(root.left, res)
	right_depth = self.dfs(root.right, res)
	depth = max(left_depth, right_depth) + 1
	if depth - 1 < len(res):
		res[depth - 1].append(root.val)
	else:
		res.append([root.val])
	return depth

算法分析：

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

LeetCode 370 Range Addition

Posted on 2022-01-27 Edited on 2026-06-03 Disqus:

LeetCode

<div>

You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].

You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] by inci.

Return arr after applying all the updates.

Example 1:

<pre>Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] Output: [-2,0,3,5,3] </pre>

Example 2:

<pre>Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]] Output: [0,-4,2,2,2,4,4,-4,-4,-4] </pre>

Constraints:

1 <= length <= 105
0 <= updates.length <= 104
0 <= startIdxi <= endIdxi < length
-1000 <= inci <= 1000

</div>

题目大意：

统一加一个数到子数组中，如此有好几个操作，求最后数组结果

解题思路：

差分数组，数加到首节点，数减在末节点 + 1，最后累加

解题步骤：

N/A

注意事项：

数加到首节点，数减在末节点 + 1，最后累加
端点需要累加res[li[0]] += li[2], 而不是res[li[0]] = li[2]
len(res)而不是len(li)

Python代码：

def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
	res = [0] * length
	for li in updates:
		res[li[0]] += li[2] # remember += not =
		if li[1] + 1 < len(res): # remember not len(li)
			res[li[1] + 1] += -li[2] # remember += not =
	for i in range(1, len(res)):
		res[i] += res[i - 1]
	return res

算法分析：

时间复杂度为O(n + m)，空间复杂度O(1), n, m分别为数组长度和update个数

LeetCode 399 Evaluate Division

Posted on 2022-01-27 Edited on 2026-06-03 Disqus:

LeetCode

<div>

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

<pre>Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000] Explanation: Given: a / b = 2.0, b / c = 3.0 queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? return: [6.0, 0.5, -1.0, 1.0, -1.0 ] </pre>

Example 2:

<pre>Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] Output: [3.75000,0.40000,5.00000,0.20000] </pre>

Example 3:

<pre>Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] Output: [0.50000,2.00000,-1.00000,-1.00000] </pre>

Constraints:

1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj consist of lower case English letters and digits.

</div>

题目大意：

根据已知除法结果求其他除法表达式

解题思路：

这是G家的面试题。图问题，因为每个除法式相乘可以得到query所要的，所以属于图问题。可以用BFS来遍历图，如已知a/b = 2, b/c = 3, 需要知道a/c, 就是2 x 3，所以只要从a开始， c为BFS的target，迭代时不断相乘

解题步骤：

N/A

注意事项：

核心思想： BFS来遍历图，迭代时不断相乘。无向图，因为a/c也可以c/a.
BFS的注意事项后两个：BFS无解时候不存在的时候返回-1
两种edge cases：若query中任意元素不在图中，返回-1(题目要求), 若元素相等，返回1

Python代码：

def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
	graph = collections.defaultdict(list)
	for i, li in enumerate(equations):
		graph[li[0]].append((li[1], values[i]))
		graph[li[1]].append((li[0], 1 / values[i])) # remember it is an undirected graph
	res = []
	for query in queries:
		if query[0] not in graph or query[1] not in graph:
			res.append(-1.0)
		elif query[0] in graph and query[0] == query[1]:
			res.append(1.0)
		else:
			val = self.bfs(graph, query)
			res.append(val)
	return res

def bfs(self, graph, query):
	queue = collections.deque([(query[0], 1)])
	visited = set([queue[0]])
	while queue:
		node, parent_val = queue.popleft()
		if node == query[1]:
			return parent_val
		for neighbor, val in graph[node]:
			if neighbor in visited:
				continue
			queue.append((neighbor, parent_val * val))
			visited.add(neighbor)
	return -1 # remember

算法分析：

时间复杂度为O(（V + E) * m)，空间复杂度O(E), m为query数