KK's blog

LeetCode 337 House Robber III

Posted on 2022-02-03 Edited on 2026-06-03 Disqus:

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, 104]. 0 <= Node.val <= 104

题目大意：

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

解题思路：

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

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

DFS解题步骤：

N/A

注意事项：

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

Python代码：

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代码：

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)

LeetCode 364 Nested List Weight Sum II

Posted on 2022-02-03 Edited on 2026-06-03 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

注意事项：

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

Python代码：

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为每层最多节点数 + 最大层数

LeetCode 078 Subsets

Posted on 2022-02-02 Edited on 2026-06-03 Disqus:

LeetCode

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10 -10 <= nums[i] <= 10
All the numbers of nums are *unique.

题目大意：

求所有子集

解题思路：

组合知识点

解题步骤：

N/A

注意事项：

题目要求结果含空集

Python代码：

def subsets(self, nums: List[int]) -> List[List[int]]:
	if not nums:
		return []
	res = [[]]
	self.dfs(nums, 0, [], res)
	return res

def dfs(self, nums, st, path, res):
	if st == len(nums):
		return
	for i in range(st, len(nums)):
		path.append(nums[i])
		res.append(list(path))
		self.dfs(nums, i + 1, path, res)
		path.pop()

算法分析：

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

LeetCode 084 Largest Rectangle in Histogram

Posted on 2022-02-02 Edited on 2026-06-03 Disqus:

LeetCode

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

1 <= heights.length <= 105 0 <= heights[i] <= 104

题目大意：

求直方图中最大的矩形面积

解题思路：

类似于L042 Trapping Rain Water的stack法，但此题水量是反的。所以仍然用Stack，但用递增栈

解题步骤：

N/A

注意事项：

比L042稍简单，不用处理最后一个bar高度和宽度计算，但是用递增栈且公式中宽度计算仍然采用i - stack[-1] - 1，因为bar并不一定连续，如212, 最后一个2入栈，栈中剩下[_, 1]第一个2已经出栈了，但是可以有水量的。
原数组头尾加入0，头0是因为公式有stack[-1]避免越界，尾0是因为让所有留在栈中的bar出栈且计算。

大厦题，首尾加入节点：
LeetCode 084 Largest Rectangle in Histogram
LeetCode 218 The Skyline Problem

Python代码：

def largestRectangleArea(self, heights: List[int]) -> int:
	stack, res = [], 0
	heights.insert(0, 0) # remember
	heights.append(0)
	for i in range(len(heights)):
		while stack and heights[i] < heights[stack[-1]]:
			index = stack.pop()
			res = max(res, (i - stack[-1] - 1) * heights[index]) # remember i - stack[-1] - 1 not i - index
		stack.append(i)
	return res

算法分析：

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

LeetCode 092 Reverse Linked List II

Posted on 2022-02-02 Edited on 2026-06-03 Disqus:

LeetCode

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:

The number of nodes in the list is n. 1 <= n <= 500
-500 <= Node.val <= 500 1 <= left <= right <= n

Follow up: Could you do it in one pass?

题目大意：

反转链表中的子链表[left, right]，start和end是1-index位置, inclusive

解题思路：

锁定start和end节点，将end的后续节点一个个加到start直接后续

LeetCode 206 Reverse Linked List 反转整个LL
LeetCode 092 Reverse Linked List II 反转部分LL，此题更加一般化

模板：
不断将end直接后面的节点加到start直接后面
start(group n) -> NodeA （新状态） -> … -> end(group n+1) -> NodeA （前状态） -> …

找出start和end，start为反转部分的前一个，end为反转部分的首个节点

循环删除end直接后，再加入到start直接后

Python代码：

start, end = fake_head, head
while <反转链表长度>:
	# delete the node
	moved_node, end.next = end.next, end.next.next
	# insert the moved_node
	start.next, moved_node.next = moved_node, start.next

解题步骤：

N/A

注意事项：

经典题，见LeetCode 2074 Reverse Nodes in Even Length Groups。思路是锁定start和end节点，将end的后续节点一个个加到start直接后续
第二个循环中，right要记得减一，否则死循环

Python代码：

def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
	left, right = left - 1, right - 1
	fake_head = ListNode(0)
	fake_head.next = head
	it = fake_head
	while left > 0:
		it = it.next
		left -= 1
		right -= 1
	start, end = it, it.next
	while right > 0:
		moved_node, end.next = end.next, end.next.next # delete a node
		start.next, moved_node.next = moved_node, start.next # insert a node
		right -= 1 # remember
	return fake_head.next

算法分析：

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