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 a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer’s value set to its depth. Let maxDepth be the maximum depth of any integer.

The weight of an integer is maxDepth - (the depth of the integer) + 1.

Return the sum of each integer in nestedList multiplied by its weight.

Example 1:



Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1’s with a weight of 1, one 2 with a weight of 2.
11 + 11 + 22 + 11 + 11 = 8


Example 2:



Input: nestedList = [1,[4,[6]]]
Output: 17
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1.
13 + 42 + 61 = 17


Constraints:

1 <= nestedList.length <= 50 The values of the integers in the nested list is in the range [-100, 100].
The maximum *depth of any integer is less than or equal to 50.

题目大意：

求NestedInteger的和。越浅，权重越高

解题思路：

BFS按层遍历。此题类似于LeetCode 339 Nested List Weight Sum。归纳成更一般的方法：因为权重只与第几层有关。所以先求每一层的和，存到sums里面，再按照题目要求每个和乘以相应的权重求和。

Nested List题目：
LeetCode 341 Flatten Nested List Iterator Iterator - Stack
LeetCode 339 Nested List Weight Sum - BFS
LeetCode 364 Nested List Weight Sum II - BFS

解题步骤：

N/A

注意事项：

  1. queue.extend(node.getList())将节点的儿子节点即node.getList()放入queue

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def depthSumInverse(self, nestedList) -> int:
	queue = collections.deque(nestedList)
	sums, max_depth, res = [], 0, 0
	while queue:
		layer_sum = 0
		for _ in range(len(queue)):
			node = queue.popleft()
			if node.isInteger():
				layer_sum += node.getInteger()
			else:
				queue.extend(node.getList()) # remember
		sums.append(layer_sum)
		max_depth += 1
	for i, n in enumerate(sums):
		res += n * (max_depth - i)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(k), k为每层最多节点数 + 最大层数

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)

Posted on Edited on Disqus:

LeetCode



The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1:



Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.


Example 2:



Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.


Constraints:

The number of nodes in the tree is in the range [1, 10<sup>4</sup>]. 0 <= Node.val <= 10<sup>4</sup>

题目大意：

二叉树，相隔一层投，求最大值

解题思路：

多状态DP。返回值为，第一个是以root为结尾的最大值，第二个为儿子层总和的最大值。

与LeetCode 309 Best Time to Buy and Sell Stock with Cooldown相似

DFS解题步骤：

N/A

注意事项：

  1. 以儿子层的前n最大值 = max(left) + max(right)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def rob2(self, root: TreeNode) -> int:
	res = self.dfs2(root)
	return max(res)

def dfs2(self, root):
	if not root:
		return (0, 0)

	left = self.dfs2(root.left)
	right = self.dfs2(root.right)

	return root.val + left[1] + right[1], max(left) + max(right)

算法分析：

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

记忆法搜索算法II解题思路：

递归式：

1
2
f(n) = root.val + g(root.left) + g(root.right)  
g(n) = max(f(root.left), g(root.left)) + max(f(root.right), g(root.right))

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def rob(self, root: TreeNode) -> int:
	f, g = {}, {}
	res = self.dfs(root, f, g)
	return max(res)

def dfs(self, root, f, g):
	if not root:
		return (0, 0)
	if root.left not in f or root.left not in g:
		f[root.left], g[root.left] = self.dfs(root.left, f, g)
	if root.right not in f or root.right not in g:
		f[root.right], g[root.right] = self.dfs(root.right, f, g)
	f[root] = root.val + g[root.left] + g[root.right]
	g[root] = max(f[root.left], g[root.left]) + max(f[root.right], g[root.right])
	return f[root], g[root]

算法分析：

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

Posted on Disqus:

LeetCode



Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example 1:

Input: s = “eceba”, k = 2
Output: 3
Explanation: The substring is “ece” with length 3.


Example 2:

Input: s = “aa”, k = 1
Output: 2
Explanation: The substring is “aa” with length 2.


Constraints:

`1 <= s.length <= 5 104*0 <= k <= 50`

题目大意：

求最长子串，它含有最多k种字符

解题思路：

同向双指针，属于最长串类型

解题步骤：

N/A

注意事项：

  1. while条件中，反计算char_to_count，还要pop key

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
	char_to_count, left, max_len = collections.defaultdict(int), 0, 0
	for i, char in enumerate(s):
		char_to_count[char] += 1
		while len(char_to_count) > k:
			char_to_count[s[left]] -= 1
			if char_to_count[s[left]] == 0:
				char_to_count.pop(s[left])
			left += 1
		max_len = max(max_len, i - left + 1)
	return max_len

算法分析：

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

Free mock interview