KK's blog

LeetCode 122 Best Time to Buy and Sell Stock II

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.

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.

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.

题目大意：

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

解题思路：

仍然是求最大利润，可以交易多次，但要先卖再买。容易想到是求所有上升坡的的总和。更简单而言，若将每一个上升坡，分成一小段(每天的交易)，求这些小段的和即可。
如：[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 121 Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

题目大意：

如果你只能进行一次交易（比如购买或者销售一个股票），设计一个算法来获取最大利润。

解题思路：

利润=当前价格-买入价，利润作为第一个变量求其最大值。由于买入价越低，利润可能会越大，所以第二个变量就要不断更新买入价
（最小值）。本题核心思路就是维护两个变量：最低价，利润。为什么不用最高价而选择利润呢？因为最低价和最高价没有顺序，最高价
必须在最低价后面，这样的利润才可实现，但如果是最低价和利润，就能确保这个顺序了，因为利润一定是在最低价后，否则这个利
润为负，不能为最大值。另一种稍麻烦的方法是凡是min更新，最高价就reset为0，大原则就是保持顺序。

注意事项：

1. 数组为空

Python代码：

1
2
3
4
5
6
7

def maxProfit(self, prices: List[int]) -> int:
	min_buy_idx, max_profit = 0, 0
	for i in range(len(prices)):
		max_profit = max(max_profit, prices[i] - prices[min_buy_idx])
		if prices[i] < prices[min_buy_idx]:
			min_buy_idx = i
	return max_profit

Java代码：

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

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

算法分析：

时间复杂度为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 目录

LeetCode 557 Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note:In the string, each word is separated by single space and there will not be any extra space in the string.

题目大意：

给定字符串，将每个单词逐字符逆置，返回新字符串。注意：字符串中单词之间有且只有1个空格分开。

解题思路：

这里考到StringBuilder，对于字符串连接效率高。还有一个小技巧，就是往输入参数附加一个空格，这样for循环结束后不用特别处理边界情况。
第一种方法是以单词为扫描单位，把字符串分成单词字符串数组，然后把每个单词反转及一个空格加入到结果sb中。
第二种方法是以字符为扫描单位，遇到空格是，就把之前存入的word放入sb中，再进行下一轮word扫描。

注意事项：

1. 用StringBuilder
2. 末尾加入空格

Java代码：

第一种方法

1
2
3
4
5
6
7
8

public String reverseWords(String s) {
	String[] tokens = s.split(" ");
	StringBuilder sb = new StringBuilder();
	for(String token : tokens)
		sb.append(new StringBuilder(token).reverse().toString()+" ");
	
	return sb.toString().trim();
}

第二种方法

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

public String reverseWords(String s) {
	s = s+" ";
	StringBuilder sb = new StringBuilder();
	StringBuilder word = new StringBuilder();
	for(char c : s.toCharArray()){
		if(c!=' ')
			word.append(c);
		else
		{
			sb.append(word.reverse().toString()+" ");
			word = new StringBuilder();
		}
	}
	return sb.toString().trim();
}

算法分析：

两种方法时间复杂度为O(n)，n为字符串长度。第一种方法空间复杂度为O(n)，而第二种方法为O(1)。

LeetCode 415 Add Strings

Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

1. The length of both num1 and num2 is < 5100.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

题目大意：

给出两个字符串形式的非负数num1和num2，返回num1和num2之和。

解题思路：

对每一位进行加法，注意进位和长度不一，类似于merge sort里面merge的实现。最要注意的是进位carry的edge case：for循环后最后值要特别处理。

注意事项：

1. 三个循环后carry要特殊处理
2. Python中，题目要求不能用int函数，就只能用ord(num1[i]) - ord(‘0’)

Python代码：

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

def addStrings(self, num1: str, num2: str) -> str:
	num1, num2 = num1[::-1], num2[::-1]
	res = ''
	i, j, carry = 0, 0, 0
	while i < len(num1) or j < len(num2):
		tmp = carry
		if i < len(num1):
			tmp += ord(num1[i]) - ord('0')
			i += 1
		if j < len(num2):
			tmp += ord(num2[j]) - ord('0')
			j += 1
		carry = 1 if tmp >= 10 else 0
		res += str(tmp % 10)
	if carry == 1:
		res += str(carry)
	return res[::-1]

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
26
27
28
29
30
31
32
33

public String addStrings(String num1, String num2) {
	StringBuffer sb = new StringBuffer();
	int i=num1.length()-1,j=num2.length()-1;
	int carry=0;
	while(i>=0 && j>=0){
		int tmp = Integer.parseInt(num1.charAt(i)+"")+Integer.parseInt(num2.charAt(j)+"")+carry;
		if(tmp>=10)
			carry = 1;
		else carry = 0;
		sb.append(tmp%10);
		i--;
		j--;
	}
	while(i>=0){
		int tmp = Integer.parseInt(num1.charAt(i)+"")+carry;
		if(tmp>=10)
			carry = 1;
		else carry = 0;
		sb.append(tmp%10);
		i--;
	}
	while(j>=0){
		int tmp = Integer.parseInt(num2.charAt(j)+"")+carry;
		if(tmp>=10)
			carry = 1;
		else carry = 0;
		sb.append(tmp%10);
		j--;
	}
	if(carry>0)
		sb.append(carry);
	return sb.reverse().toString();	
}

算法分析：

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