KK's blog

LeetCode 206 Reverse Linked List

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

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

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

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

The number of nodes in the list is the range [0, 5000]. -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

题目大意：

反转LL

解题思路：

简单题，但是经典题。循环体为，左方一个单独节点，右方为一个LL，将LL的首节点指向单独节点

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

注意事项：

利用模板，由于首节点会变，所以引入fake_node
空节点的处理

Python代码：

def reverseList(self, head: ListNode) -> ListNode:
	if not head:
		return None
	fake_head = ListNode(0)
	fake_head.next = head
	start, end = fake_head, head
	while end.next:
		# 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
	return fake_head.next

算法分析：

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

LeetCode 218 The Skyline Problem

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

LeetCode

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:

lefti is the x coordinate of the left edge of the ith building. righti is the x coordinate of the right edge of the ith building.
heighti is the height of the ith building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of “key points” sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline’s termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline’s contour.

Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3],[4 5],[7 5],[11 5],[12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...,[2 3],[4 5],[12 7],...]

Example 1:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

Example 2:

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

Constraints: 1 <= buildings.length <= 104
0 <= lefti < righti <= 231 - 1 1 <= heighti <= 231 - 1
* buildings is sorted by lefti in non-decreasing order.

题目大意：

N/A

解题思路：

Heap(高度最大堆) + 端点排序法(先端点再高度逆序)
不是高频题，但思路值得学习
本质和meeting rooms II一致，因为都是求重合，但这题是二维，后者是一维，区别是

具体线段有关，所以用高度堆而不是时间堆。高度起主要作用。高度存在起点和终点，它们是高度的时间合法性。
高度时间合法性同样用end time来验证，这里放到heap的第二元素中。
end time无法自动trigger让高度出堆，所以只能设计让end time也作为遍历的一部分去强行出堆。也就是start和end time作为新数组。

Heap(高度最大堆): LeetCode 253 Meeting Rooms II方法一，终点的最小堆
端点排序法(先端点再高度逆序)： LeetCode 253 Meeting Rooms II方法二
meeting room是新线段的start逼栈顶终点出堆，此题也是同样，但用高度的最大堆维护当前最高大厦，这与题意符合。

为什么要加入结束点?

两种情况，第一种情况没有问题，但第二种情况就会漏掉第一栋大厦的结束点。原因是出堆的点没有被处理，但出堆的点可能有多个而且若没有新大厦它不能出堆，所以结束点逼它出堆。
为什么高度逆序?

第一种情况在坐标2这个位置有两节点(2, 0, 0)第一栋大厦结束点, (2, 5, 3)第二栋大厦开始点，若不按高度排序，第一栋结束点会逼第一栋开始点出堆，产生天际线。若按高度逆序，后者先入堆，第一栋开始点出堆也不会产生天际线。类似于heapq.heapreplace先加入再删除或者LeetCode 354 Russian Doll Envelopes的排序方式

解题步骤：

N/A

注意事项：

先顺序排序端点再逆序高度，因为当结束点和始点重合时，让高度大的先入堆可以确保不会产生矮的天际线，否则这些矮的天际线实际被包含在高的大厦里。
结束点也要加入循环但不入堆。这样产生两点：
1) start >= heap[0][1]要取等号，否则不能让这栋大厦结束点出堆。
2) 结束点不入堆，因为它只用于产生结束点从而加入到结果集，它不产生高度，只有产生高度的点才会被加入到堆
与前高度不同，也就是高度发生变化就入堆
确保res[-1][1] != -heap[0][0]。用只有一栋大厦作为test case。
1) 因为用到了res[-1][1]，所以res初始化加入[-float(‘inf’), 0]，第一个值不会用到所以无所谓不妨去负无穷，高度为0；
2) 最后结果要排除这个点，取res[1:]
3) 因为要用到heap[0][0]，也就是heap要永远有节点。初始化加入[0, float(‘inf’)]，高度为0，用于产生在地平线的点的高度，结束点为无穷大，确保不会被逼出堆。
总结加入res中的为起始点，加入heap中的为结束点，它们高度均为0，但端点对称分别为负正无穷。

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

实现上有点似：
LeetCode 239 Sliding Window Maximum 模板，计算，排除
LeetCode 218 The Skyline Problem 模板，加入，计算

Python代码：

def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
	events = sorted(buildings + [[end, 0, 0] for _, end, _ in buildings], key=lambda x: (x[0], -x[2]))
	heap, res = [(0, float('inf'))], [[-float('inf'), 0]]
	for start, end, height in events:
		while heap and start >= heap[0][1]:
			heapq.heappop(heap)
		if height > 0: # don't push ends into the heap
			heapq.heappush(heap, (-height, end))
		if res[-1][1] != -heap[0][0]:
			res.append([start, -heap[0][0]])
	return res[1:]

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(k), k为重合天际线个数，此复杂度跟Meeting Rooms II一致

LeetCode 282 Expression Add Operators

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

LeetCode

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Example 1:

Input: num = “123”, target = 6
Output: [“123”,”1+2+3”]
Explanation: Both “123” and “1+2+3” evaluate to 6.

Example 2:

Input: num = “232”, target = 8
Output: [“23+2”,”2+32”]
Explanation: Both “23+2” and “2+32” evaluate to 8.

Example 3:

Input: num = “3456237490”, target = 9191
Output: []
Explanation: There are no expressions that can be created from “3456237490” to evaluate to 9191.

Constraints:

1 <= num.length <= 10 num consists of only digits.
* -231 <= target <= 231 - 1

题目大意：

求一串数字加入加减乘能得到target的所有可能性

解题思路：

求所有可能用DFS。属于分割型DFS，在数位之间加符号，数位可以是1个到多个。
一轮递归分割出符号 + 数字
另一种选择是数字 + 符号，但需要额外变量sign，因为不能立刻计算到结果。也不符合正常逻辑。所以选择前者。

由于运算都是二元，也就是用上述分割法，第一个数要特别处理。所以DFS中要特别处理第一个数。这样可以开始写加减。引入prev_res作为DFS参数，这样只要prev_res 加减该轮数字即可得到该轮结果。用DFS模板5个标准参数外加prev_res：

1	def dfs(self, num, st, target, prev_res, path, res):

这样只处理加减的DFS比较容易实现

最大难点在于乘法，参考LeetCode 227 Basic Calculator II，加减和乘除属于两层计算需要分别处理，所以引入新参数prev_multi_res，用于保存乘法结果，而刚才的命名为prev_add_res保存加减乘的全部结果

1	def dfs(self, num, st, target, prev_add_res, prev_multi_res, path, res):

举例2+3*4，按照原来的逻辑会计算到2+3=5，但此时如果遇到乘号，就要重新计算加法结果，先减去乘法结果，退回到2，再计算3*4=12这是乘法结果，再加回2得到新加法结果。进一步理解prev_multi_res，如果该轮是加减法，仍要将该轮的数作为prev_multi_res传到下轮DFS，因为如果下一轮是乘法，它就是第一个乘法的数。

解题步骤：

先实现加减法
再实现乘法

注意事项：

分割型DFS，选择每轮递归分割符号 + 数字。由于运算都是二元，特别处理第一个数
引入参数prev_add_res, prev_multi_res. prev_multi_res若是加减，用(+/-)cur_num, 否则用乘法结果prev_multi_res * cur_num。注意若是减法cur_num用负号
分割时数字不能有前缀0
prev_res不用恢复状态因为是标量

Python代码：

def addOperators(self, num: str, target: int) -> List[str]:
	res = []
	self.dfs(num, 0, target, 0, 0, '', res)
	return res

def dfs(self, num, st, target, prev_add_res, prev_multi_res, path, res):
	if st == len(num):
		if target == prev_add_res:
			res.append(path)
		return
	for i in range(st, len(num)):
		if i > st and num[st] == '0': # remember
			continue
		cur_num = int(num[st:i + 1])
		if not path: # remember
		    # first number, same as + case
			self.dfs(num, i + 1, target, prev_add_res + cur_num, cur_num, str(cur_num), res)
		else:
			self.dfs(num, i + 1, target, prev_add_res + cur_num, cur_num, path + '+' + str(cur_num), res) # use cur_num rather than cur
			self.dfs(num, i + 1, target, prev_add_res - cur_num, -cur_num, path + '-' + str(cur_num), res) # -cur_num rather than cur_num
			self.dfs(num, i + 1, target, (prev_add_res - prev_multi_res) + prev_multi_res * cur_num, prev_multi_res * cur_num, path + '*' + str(cur_num), res) # prev_multi_res * cur_num not cur_num

算法分析：

时间复杂度为O(4ⁿ)，空间复杂度O(n), 因为每个字符之间都有不加操作符，加3个操作符，所以是4，有n-1个间隔

LeetCode 315 Count of Smaller Numbers After Self

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

LeetCode

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Example 2:

Input: nums = [-1]
Output: [0]

Example 3:

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

Constraints:

1 <= nums.length <= 105 -104 <= nums[i] <= 104

题目大意：

数组中，统计每一位比自己小的数。

解题思路：

一开始考虑用递减栈。但不可行, 因为这是统计题，而不是求比自己大的一个数LeetCode 503 Next Greater Element II。类似于merge sort，考虑统计逆序数

解题步骤：

N/A

注意事项：

由于mergesort会改变数组顺序，所以统计数组count也要对应的数也会变，所以将原数组变成(数值, 下标)对，count就可以统计原数组
计算逆序对时候，放在nums[i][0] <= nums[j][0]中，核心在count[nums[i][1]] += j - mid - 1

Python代码：

def countSmaller(self, nums: List[int]) -> List[int]:
	count = [0] * len(nums)
	num_with_idx = [(n, i) for i, n in enumerate(nums)]
	self.merge_sort(num_with_idx, 0, len(nums) - 1, count)
	return count

def merge_sort(self, nums, start, end, count):
	if start >= end:
		return
	mid = start + (end - start) // 2
	self.merge_sort(nums, start, mid, count)
	self.merge_sort(nums, mid + 1, end, count)
	self.merge(nums, start, mid, end, count)

def merge(self, nums, start, mid, end, count):
	i, j = start, mid + 1
	res = []
	while i <= mid and j <= end:
		if nums[i][0] <= nums[j][0]:
			res.append(nums[i])
			count[nums[i][1]] += j - mid - 1
			i += 1
		else:
			res.append(nums[j])
			j += 1
	while i <= mid:
		res.append(nums[i])
		count[nums[i][1]] += j - mid - 1
		i += 1
	while j <= end:
		res.append(nums[j])
		j += 1
	nums[start:end + 1] = res

算法分析：

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

LeetCode 518 Coin Change 2

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

LeetCode

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10]
Output: 1

Constraints:

1 <= coins.length <= 300 1 <= coins[i] <= 5000
All the values of coins are unique. 0 <= amount <= 5000

题目大意：

求兑换硬币的种数

解题思路：

类似于LeetCode 322 Coin Change，那题求最小个数，此题求总数，也是用DP。
递归式：

1	dp[i] = sum(dp[j]), i = j + coins[i]

LeetCode 377 Combination Sum IV 题目基本一样，唯一区别是结果元素有序，属于排列
LeetCode 518 Coin Change 2 题目基本一样，唯一区别是结果元素无序，属于组合

解题步骤：

递归5部曲

注意事项：

for循环顺序不能错，先coin再dp，否则会有重复计算，如dp[3] = 2 + 1和1 + 2. 字面上理解也是可以知道重复。但如果coin先的话，就只能用1的硬币，第二轮是只能用2的硬币，如此类推，显然不会重复，dp[3] = dp[2] + 1(只用硬币1), dp[1] + 2(只用硬币2)

Python代码：

# dp[i] = dp[j], i = j + coins[i]
def change(self, amount: int, coins: List[int]) -> int:
	dp = [0] * (amount + 1)
	dp[0] = 1
	for coin in coins:
		for i in range(len(dp)): # [0, 0]
			if i + coin <= amount:
				dp[i + coin] += dp[i]
	return dp[-1]

算法分析：

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