KK's blog

每天积累多一些

0%

Posted on Edited on 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

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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)

Posted on Edited on Disqus:

LeetCode



You are given an integer length and an array updates where updates[i] = [startIdx<sub>i</sub>, endIdx<sub>i</sub>, inc<sub>i</sub>].

You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the i<sup>th</sup> operation, you should increment all the elements arr[startIdx<sub>i</sub>], arr[startIdx<sub>i</sub> + 1], ..., arr[endIdx<sub>i</sub>] by inc<sub>i</sub>.

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 <= 10<sup>5</sup> 0 <= updates.length <= 10<sup>4</sup>
0 <= startIdx<sub>i</sub> <= endIdx<sub>i</sub> < length -1000 <= inc<sub>i</sub> <= 1000

题目大意：

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

解题思路：

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

解题步骤：

N/A

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
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个数

Posted on Edited on Disqus:

LeetCode



Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

Solution(int[] nums) Initializes the object with the integer array nums. int[] reset() Resets the array to its original configuration and returns it.
int[] shuffle() Returns a random shuffling of the array.

Example 1:

Input
[“Solution”, “shuffle”, “reset”, “shuffle”]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // Shuffle the array [1,2,3] and return its result.
                       // Any permutation of [1,2,3] must be equally likely to be returned.
                       // Example: return [3, 1, 2]
solution.reset();      // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle();    // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]



Constraints: 1 <= nums.length <= 200
-10<sup>6</sup> <= nums[i] <= 10<sup>6</sup> All the elements of nums are unique.
At most `5 104calls **in total** will be made toresetandshuffle`.

题目大意：

随机重排数组

解题思路：

水塘抽样法

先看算法，再理解，第i个元素会被交换的概率：
某一个元素保留概率为(n - i) / (n - i + 1)
某一个元素交换概率为1 / (n - i)
所以从左到右遍历到第i个元素时，它被交换到后面的概率为 所有前面都保留 乘以 第i轮循环时被交换：

1
(n - 1) / n * (n - 2) / (n - 1) ... (n - i) / (n - i + 1) * 1 / (n - i)

前面都约了，最后等于1 / n

解题步骤：

N/A

注意事项：

  1. 死记算法，跟后面的元素互换
  2. 复制原数组以防被改

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def __init__(self, nums: List[int]):
	self.original = list(nums)
	self.nums = nums

def reset(self) -> List[int]:
	return list(self.original)

def shuffle(self) -> List[int]:
	for i in range(len(self.nums)):
		swap_idx = random.randrange(i, len(self.nums))
		self.nums[i], self.nums[swap_idx] = self.nums[swap_idx], self.nums[i]
	return self.nums

算法分析：

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

Posted on Edited on Disqus:

LeetCode



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

You are also given some queries, where queries[j] = [C<sub>j</sub>, D<sub>j</sub>] represents the j<sup>th</sup> query where you must find the answer for C<sub>j</sub> / D<sub>j</sub> = ?.

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 <= A<sub>i</sub>.length, B<sub>i</sub>.length <= 5 values.length == equations.length
0.0 < values[i] <= 20.0 1 <= queries.length <= 20
queries[i].length == 2 1 <= C<sub>j</sub>.length, D<sub>j</sub>.length <= 5
* A<sub>i</sub>, B<sub>i</sub>, C<sub>j</sub>, D<sub>j</sub> 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

注意事项：

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

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

Posted on Edited on 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 <= 10<sup>9</sup> Every timestamp will be passed in non-decreasing order (chronological order).
1 <= message.length <= 30 At most 10<sup>4</sup> calls will be made to shouldPrintMessage.

题目大意：

实现Logger打印的rate limiter

解题思路：

题不难，但有实际意义

解题步骤：

N/A

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
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)

Free mock interview