KK's blog

LeetCode

<div>

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

<pre>Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] </pre>

Example 2:

<pre>Input: preorder = [-1], inorder = [-1] Output: [-1] </pre>

Constraints:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

</div>

算法思路：

N/A

注意事项：

1. 用递归实现，in_order字符串分左右两段子串递归到左右儿子，pre_order字符串每轮递归用pop(0)原地去除首位，再递归到儿子节点
2. 终止条件为in_order字符串为空。

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
	if not inorder:
		return None
	head = preorder.pop(0)
	index = inorder.index(head)
	left_inorder, right_inorder = inorder[:index], inorder[index + 1:]

	root = TreeNode(head)
	root.left = self.buildTree(preorder, left_inorder)
	root.right = self.buildTree(preorder, right_inorder)
	return root

算法分析：

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

LeetCode 122 Best Time to Buy and Sell Stock II

<div>

You are given an integer array prices where prices[i] is the price of a given stock on the i<sup>th</sup> day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

<pre>Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7. </pre>

Example 2:

<pre>Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4. </pre>

Example 3:

<pre>Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0. </pre>

Constraints:

• 1 <= prices.length <= 3 * 10<sup>4</sup>
• 0 <= prices[i] <= 10<sup>4</sup>

</div>

题目大意：

设计一个算法寻找最大收益。你可以随便完成多少次交易（比如，多次买入卖出）。然而你不能一次进行多次交易。

解题思路：

仍然是求最大利润，可以交易多次，但要先卖再买。容易想到是求所有上升坡的的总和。更简单而言，若将每一个上升坡，分成一小段(每天的交易)，求这些小段的和即可。
如：[6, 1, 2, 3, 4]中的1, 2, 3, 4序列来说，对于两种操作方案：
1 在1买入，4卖出
2 在1买入，2卖出同时买入，3卖出同时买入，4卖出
这两种操作下，收益是一样的。这种方法，避免检测下坡以及计算每段的和。

Python代码：

1
2
3
4
5
6

def maxProfit(self, prices: List[int]) -> int:
	res = 0
	for i in range(1, len(prices)):
		if prices[i] - prices[i - 1] > 0:
			res += prices[i] - prices[i - 1]
	return res

注意事项：

1. 数组为空

Java代码：

1
2
3
4
5
6
7
8
9
10

public int maxProfit(int[] prices) {
	if(prices.length==0)
		return 0;
	int profit = 0;
	for(int i=1;i<prices.length;i++){
		if(prices[i-1]<prices[i])
			profit += prices[i] - prices[i-1];
	}
	return profit;
}

算法分析：

时间复杂度为O(n)，n为字符串长度，空间复杂度O(1)。

相关题目：

LeetCode 121 Best Time to Buy and Sell Stock
LeetCode 122 Best Time to Buy and Sell Stock II LeetCode 309 Best Time to Buy and Sell Stock with Cooldown LeetCode 123 Best Time to Buy and Sell Stock III

LeetCode

<div>

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:

<pre>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. </pre>

Example 2:

<pre>Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]] </pre>

Example 3:

<pre>Input: candidates = [2], target = 1 Output: [] </pre>

Constraints:

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

</div>

题目大意：

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

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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()

算法分析：

时间复杂度为<code>O(2ⁿ)</code>，空间复杂度O(n)

LeetCode

<div>

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:

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

Example 2:

<pre>Input: candidates = [2,5,2,1,2], target = 5 Output: [ [1,2,2], [5] ] </pre>

Constraints:

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

</div>

题目大意：

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

解题思路：

用组合模板，先排序

解题步骤：

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()

算法分析：

时间复杂度为<code>O(2ⁿ)</code>，空间复杂度O(n)

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. 再解此题