KK's blog

LeetCode 039 Combination Sum

Posted on 2021-12-29 Edited on 2026-06-03 Disqus:

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

1 <= candidates.length <= 30 1 <= candidates[i] <= 200
All elements of candidates are distinct. 1 <= target <= 500

题目大意：

求组合和等于目标。元素可以复用

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

用标准组合模板dfs(self, candidates, start, target, path, res)，元素可以复用，所以下一轮递归从i开始
Python中path.pop()没有参数

Python代码：

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
	candidates.sort()
	res = []
	self.dfs(candidates, 0, target, [], res)
	return res

def dfs(self, candidates, start, target, path, res): # [1, 2], 0, 0, [1, 1], [1, 1]
	if target < 0:
		return
	if target == 0:
		res.append(list(path))
		return
	for i in range(start, len(candidates)): # [2]
		path.append(candidates[i]) # [1,1]
		self.dfs(candidates, i, target - candidates[i], path, res)
		path.pop()

算法分析：

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

LeetCode 040 Combination Sum II

Posted on 2021-12-29 Edited on 2026-06-03 Disqus:

LeetCode

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]

Constraints:

1 <= candidates.length <= 100 1 <= candidates[i] <= 50
* 1 <= target <= 30

题目大意：

求组合和等于目标。元素不可复用且结果去重

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

类似于Leetcode 39，有两点不同。要去重，i > start并不是i > 0, 且比较前一个元素
因为元素不可重复，下一轮递归i + 1

Python代码：

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
	candidates.sort()
	res = []
	self.dfs(candidates, 0, target, [], res)
	return list(res)

def dfs(self, candidates, start, target, path, res): # [1, 2], 0, 0, [1, 1], [1, 1]
	if target < 0:
		return
	if target == 0:
		res.append(list(path))
		return
	for i in range(start, len(candidates)): # [2]
		if i > start and candidates[i - 1] == candidates[i]:
			continue
		path.append(candidates[i]) # [1,1]
		self.dfs(candidates, i + 1, target - candidates[i], path, res)
		path.pop()

算法分析：

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

LeetCode 057 Insert Interval

Posted on 2021-12-29 Edited on 2026-06-03 Disqus:

LeetCode 057 Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

题目大意：

对于给出的互不重叠且按照左端点排序的区间序列，将一个新的区间插入到这个序列当中（合并重叠的区间），使其仍然保持原本的性质。

Python代码：

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
	intervals.append(newInterval)
	intervals.sort(key=lambda x: x[0])
	new_interval = [intervals[0][0], intervals[0][0]]
	res = []
	for interval in intervals:
		if self.can_merge(new_interval, interval):
			new_interval = self.merge_two_intervals(new_interval, interval)
		else:
			res.append(new_interval)
			new_interval = interval
	res.append(new_interval)
	return res

def can_merge(self, interval, interval2):
	return interval[1] >= interval2[0]

def merge_two_intervals(self, interval, interval2):
	return [interval[0], max(interval[1], interval2[1])]

解题思路：

与L56题基本一致，但单元测试更加严格，加入含最大整数值的区间。

先找到start大于等于待插入区间的区间，然后待插入区间插入其前。
归结成L56题

注意事项：

先找到start大于等于待插入区间的区间，然后待插入区间插入其前。

Python代码：

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
	j = 0
	while j < len(intervals):
		if intervals[j][0] >= newInterval[0]:
			break
		j += 1
	intervals.insert(j, newInterval)

	new_interval = [intervals[0][0], intervals[0][0]]
	res = []
	for interval in intervals:
		if self.can_merge(new_interval, interval):
			new_interval = self.merge_two_intervals(new_interval, interval)
		else:
			res.append(new_interval)
			new_interval = interval
	res.append(new_interval)
	return res

def can_merge(self, interval, interval2):
	return interval[1] >= interval2[0]

def merge_two_intervals(self, interval, interval2):
	return [interval[0], max(interval[1], interval2[1])]

注意事项：

判断是否合并的API中，加入in2.start == Integer.MAX_VALUE返回false。

Java代码：

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
	int st = 0;
	for(;st<intervals.size();st++){
		if(intervals.get(st).start>=newInterval.start){
			break;
		}
	}
	intervals.add(st, newInterval);
	
	intervals.add(new Interval(Integer.MAX_VALUE, Integer.MAX_VALUE));
	List<Interval> re = new ArrayList<Interval>();
	Interval newInterval2 = null;
	for(int i=1;i<intervals.size();i++){
		if(newInterval2==null)
			newInterval2 = intervals.get(i-1);
		if(canMerge(newInterval2,intervals.get(i))){
			newInterval2 = mergeIntervals(newInterval2,intervals.get(i));
		}
		else{
			re.add(newInterval2);
			newInterval2 = null;
		}
	}
	return re;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(1)，因为不用排序。

Follow-up:

先解出L56
再解此题

LeetCode 070 Climbing Stairs

Posted on 2021-12-29 Edited on 2026-06-03 Disqus:

LeetCode

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

* 1 <= n <= 45

题目大意：

爬楼梯的方法数。一次可以爬一级或二级

解题思路：

DP的经典题
递归式

1	dp[n] = dp[n - 1] + dp[n - 2]

解题步骤：

N/A

注意事项：

递归式含两个前状态，所以用两个变量。Python的优势是可以同时赋值，所以不需要用临时变量

Python代码：

# dp[n] = dp[n - 1] + dp[n - 2]
def climbStairs(self, n: int) -> int:
	prev, cur = 1, 1
	for i in range(2, n + 1): # 4
		cur, prev = cur + prev, cur # 5, 3
	return cur

算法分析：

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

LeetCode 114 Flatten Binary Tree to Linked List

Posted on 2021-12-29 Edited on 2026-06-03 Disqus:

LeetCode

Given the root of a binary tree, flatten the tree into a “linked list”: The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The “linked list” should be in the same order as a pre-order traversal of the binary tree. Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]

Constraints: The number of nodes in the tree is in the range [0, 2000]. -100 <= Node.val <= 100 Follow up: Can you flatten the tree in-place (with O(1) extra space)?

题目大意：

将二叉树转成以右节点相连的LL

解题思路：

递归需要知道左右递归末尾节点，这样才可以将右节点的首节点接到左节点的末尾。所以递归函数输入是root，返回LL末尾节点

解题步骤：

N/A

注意事项：

递归函数输入是root，返回LL末尾节点
如果left_end是空，也就是没有左节点，就不用交换。返回right_end, left_end, root三者中非空者。

Python代码：

def flatten(self, root: TreeNode) -> None:
	self.dfs(root)

def dfs(self, root: TreeNode) -> None:
	if not root:
		return None
	left_end = self.dfs(root.left)
	right_end = self.dfs(root.right)

	if left_end: # remember
		left_end.right = root.right
		root.right, root.left = root.left, None
	if right_end:
		return right_end
	elif left_end:
		return left_end
	else:
		return root

算法分析：

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