KK's blog

LeetCode 399 Evaluate Division

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

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:

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 ]

Example 2:

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]

Example 3:

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]

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.

题目大意：

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

解题思路：

这是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数

LeetCode 370 Range Addition

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

LeetCode

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:

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

Example 2:

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

Constraints:

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

题目大意：

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

解题思路：

差分数组，数加到首节点，数减在末节点 + 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 366 Find Leaves of Binary Tree

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

LeetCode

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:

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.

Example 2:

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

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

题目大意：

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

解题思路：

考虑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 359 Logger Rate Limiter

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

LeetCode

Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed at most every 10 seconds (i.e. a message printed at timestamp t will prevent other identical messages from being printed until timestamp t + 10).

All messages will come in chronological order. Several messages may arrive at the same timestamp.

Implement the Logger class:

Logger() Initializes the logger object. bool shouldPrintMessage(int timestamp, string message) Returns true if the message should be printed in the given timestamp, otherwise returns false.

Example 1:

Input
[“Logger”, “shouldPrintMessage”, “shouldPrintMessage”, “shouldPrintMessage”, “shouldPrintMessage”, “shouldPrintMessage”, “shouldPrintMessage”]
[[], [1, “foo”], [2, “bar”], [3, “foo”], [8, “bar”], [10, “foo”], [11, “foo”]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, “foo”);  // return true, next allowed timestamp for “foo” is 1 + 10 = 11
logger.shouldPrintMessage(2, “bar”);  // return true, next allowed timestamp for “bar” is 2 + 10 = 12
logger.shouldPrintMessage(3, “foo”);  // 3 < 11, return false
logger.shouldPrintMessage(8, “bar”);  // 8 < 12, return false
logger.shouldPrintMessage(10, “foo”); // 10 < 11, return false
logger.shouldPrintMessage(11, “foo”); // 11 >= 11, return true, next allowed timestamp for “foo” is 11 + 10 = 21

Constraints:

0 <= timestamp <= 109 Every timestamp will be passed in non-decreasing order (chronological order).
1 <= message.length <= 30 At most 104 calls will be made to shouldPrintMessage.

题目大意：

实现Logger打印的rate limiter

解题思路：

题不难，但有实际意义

解题步骤：

N/A

注意事项：

shouldPrintMessage只有返回True时候才记录时间点。否则不记录。这属于元素相等的test case

Python代码：

class Logger(TestCases):

    def __init__(self):
        self.throttle_interval = 10
        self.msg_to_timestamp = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message in self.msg_to_timestamp and timestamp - self.msg_to_timestamp[message] < self.throttle_interval:
            return False
        self.msg_to_timestamp[message] = timestamp
        return True

算法分析：

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

LeetCode 332 Reconstruct Itinerary

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

LeetCode 332 Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

题目大意：

给定一组机票，用出发机场和到达机场[from, to]来表示，重建行程的顺序。所有的机票都属于一个从JFK（肯尼迪国际机场）出发的旅客。因此，行程必须从JFK开始。

注意：

如果存在多重有效的行程，你应当返回字典序最小的那个。例如，行程[“JFK”, “LGA”]的字典序比[“JFK”, “LGB”]要小。
所有的机场用3个大写字母表示（IATA编码）。
你可以假设所有的机票均至少包含一条有效的行程。

解题思路：

这条题实质是记录DFS路径的题目，且对儿子节点的选择是有顺序的。值得注意的是并不是所有路径都是可形成回路，所以需要DFS搜索。
既然是要记录路径就需要用数组保存结果，而有顺序则表示要排序。

建图，用邻接表来表示HashMap> graph
对每个节点的邻节点LinkList进行排序
从JFK开始dfs。1)终止条件为所有ticket都遍历了(达成回路)或者不能够遍历完。2)路径存在数组中。 3)通过删除节点表示已访问DFS该节点后图要恢复成原状态。

注意事项：

通过删除节点表示已访问DFS该节点后图要恢复成原状态。用下标i来删除，这样才能保证删除再加入仍然有序。另一种方法是用visited边来记录避免修改图。本文用前者
剪枝：如果找到结果就返回
这题只有一条path，不是所有可能性，但让需要用res，复制path到res，因为path会恢复状态。

Python代码：

def findItinerary2(self, tickets: List[List[str]]) -> List[str]:
	graph = collections.defaultdict(list)
	for li in tickets:
		graph[li[0]].append(li[1])
	for li in graph.values():
		li.sort()
	path, res = ['JFK'], []
	self.dfs2(graph, 'JFK', len(tickets), path, res)
	return res[0]

def dfs2(self, graph, start, ticket_left, path, res):
	if ticket_left == 0:
		res.append(list(path)) # remember
		return True
	for i, neighbor in enumerate(graph[start]):
		path.append(neighbor)
		graph[start].pop(i) # remember
		if self.dfs2(graph, neighbor, ticket_left - 1, path, res):
			return True
		graph[start].insert(i, neighbor)
		path.pop()
	return False

注意事项：

终止条件为所有ticket都遍历了(达成完整路)或者不能够遍历完Dfs API含ticketLeft。如{“JFK”,”KUL”},{“JFK”,”NRT”},{“NRT”,”JFK”}，虽然KUL在NRT前，但KUL不能组成回路。
DFS路径尽量存在数组中，否则用ArrayList中就要先add再remove。
通过删除节点表示已访问DFS该节点后图要恢复成原状态。

Java代码：

public List<String> findItinerary(String[][] tickets) {
	HashMap<String, LinkedList<String>> graph = new HashMap<String, LinkedList<String>>();
	for(int i=0;i<tickets.length;i++){
		LinkedList<String> neighbor = graph.get(tickets[i][0]);
		if(neighbor==null)
			neighbor = new LinkedList<String>();
		neighbor.add(tickets[i][1]);
		graph.put(tickets[i][0], neighbor);
	}
	Iterator<String> it = graph.keySet().iterator();
	while(it.hasNext()){
		String key = it.next();
		LinkedList<String> neighbor = graph.get(key);
		Collections.sort(neighbor);
		graph.put(key, neighbor);
	}
	String[] re = new String[tickets.length+1];
	String cur = "JFK";
	re[0] = cur;
	isDFS(graph,cur,tickets.length,tickets.length,re);
	return new ArrayList<String>(Arrays.asList(re));
}

public boolean isDFS(HashMap<String, LinkedList<String>> graph, String departCity
		,int ticketLeft, int ticketNum, String[] re){
	if(ticketLeft==0)
		return true;    	
	LinkedList<String> desCity = graph.get(departCity);
	if(desCity==null)
		return false;
	for(int i=0;i<desCity.size();i++){
		String cur = desCity.get(i);
		re[ticketNum-ticketLeft+1] = cur;
		desCity.remove(i);
		graph.put(departCity, desCity);
		if(isDFS(graph,cur,ticketLeft-1,ticketNum,re))
			return true;;
		desCity.add(i,cur);
		graph.put(departCity, desCity);
	}
	return false;
}

算法分析：

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