KK's blog

每天积累多一些

0%

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

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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(2n)，空间复杂度O(n)

Posted on Edited on 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代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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题基本一致，但单元测试更加严格，加入含最大整数值的区间。

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

注意事项：

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

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

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

  1. 先解出L56
  2. 再解此题

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

注意事项：

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

Python代码：

1
2
3
4
5
6
# 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)

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

注意事项：

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

Python代码：

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

Posted on Edited on Disqus:

LeetCode



Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used. Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.


Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.


Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.


Constraints:

2 <= k <= 9 1 <= n <= 60

题目大意：

数字1-9的组合个数为k的组合和等于k，每个元素最多用一次

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

  1. Leetcode 40和77的结合。个数和target都要达到。用if k == 0 and target == 0

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
	nums = [_ for _ in range(1, 10)]
	res = []
	self.dfs(nums, 0, k, n, [], res)
	return res

def dfs(self, nums, start, k, target, path, res):
	if k == 0 and target == 0:
		res.append(list(path))
		return
	if k == 0:
		return
	for i in range(start, len(nums)):
		path.append(nums[i])
		self.dfs(nums, i + 1, k - 1, target - nums[i], path, res)
		path.pop()

算法分析：

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

Free mock interview