update some stock problem solution

6boris · 6boris · commit 34c5cc6c837c · 2019-06-07T03:12:49.000+08:00
diff --git a/README.md b/README.md
@@ -42,6 +42,7 @@ LeetCode of algorithms with golang solution(updating:smiley:).
 
 ## Community
 
+* [ACWING](https://www.acwing.com/) 一些算法竞赛大佬创建的平台，挺适合入门的。
 * [leetbook](https://github.com/hk029/leetbook) 某位大佬写的Leetcode题解，不过已经不更新了
 * [LeetCode-in-Go](https://github.com/aQuaYi/LeetCode-in-Go) 某位算法大佬的Golang题解
 
diff --git a/src/0072.Edit-Distance/README.md b/src/0072.Edit-Distance/README.md
@@ -1,34 +1,62 @@
-# [1. Add Sum][title]
+# [72. Edit Distance][title]
 
 ## Description
 
-Given two binary strings, return their sum (also a binary string).
+Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
 
-The input strings are both **non-empty** and contains only characters `1` or `0`.
+You have the following 3 operations permitted on a word:
+
+- Insert a character
+- Delete a character
+- Replace a character
 
 **Example 1:**
 
 ```
-Input: a = "11", b = "1"
-Output: "100"
+Input: word1 = "horse", word2 = "ros"
+Output: 3
+Explanation: 
+horse -> rorse (replace 'h' with 'r')
+rorse -> rose (remove 'r')
+rose -> ros (remove 'e')
 ```
 
 **Example 2:**
 
 ```
-Input: a = "1010", b = "1011"
-Output: "10101"
+Input: word1 = "intention", word2 = "execution"
+Output: 5
+Explanation: 
+intention -> inention (remove 't')
+inention -> enention (replace 'i' with 'e')
+enention -> exention (replace 'n' with 'x')
+exention -> exection (replace 'n' with 'c')
+exection -> execution (insert 'u')
 ```
 
 **Tags:** Math, String
 
 ## 题意
->给你两个二进制串，求其和的二进制串。
+>给定两个单词 word1 和 word2 ，请问最少需要进行多少次操作可以将 word1 变成 word2 。
 
 ## 题解
 
 ### 思路1
-> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
+> (动态规划) O(n2)
+
+经典的编辑距离问题。
+
+状态表示：`f[i,j]` 表示将 `word1` 的前 `i` 个字符变成 `word2` 的前 `j` 个字符，最少需要进行多少次操作。
+状态转移，一共有四种情况：
+
+- 将`word1[i]` 删除或在`word2[j]`后面添加`word1[i]`，则其操作次数等于`f[i−1,j]+1`；
+- 将`word2[j]`删除或在`word1[i]`后面添加`word2[j]`，则其操作次数等于 `f[i,j−1]+1`；
+- 如果`word1[i]=word2[j]`，则其操作次数等于 `f[i−1,j−1]`；
+- 如果`word1[i]≠word2[j]`，则其操作次数等于 `f[i−1,j−1]+1`；
+
+> 时间复杂度分析：
+
+- 状态数 O(n2)O(n2)，状态转移复杂度是 O(1)O(1)，所以总时间复杂度是 O(n2)O(n2)。
 
 ```go
 
diff --git a/src/0121.Best-Time-to-Buy-and-Sell-Stock/README.md b/src/0121.Best-Time-to-Buy-and-Sell-Stock/README.md
@@ -23,15 +23,40 @@ Output: "10101"
 **Tags:** Math, String
 
 ## 题意
->只允许买卖一次
+>假设你有一个数组，其中第i个元素表示第i天某个股票的价格。
+ 如果您只允许完成至多一笔交易（即买入一只股票并卖出一只股票），则设计一种算法以找到最大利润。
+ 必须先购买股票再出售股票。
 
 ## 题解
 
 ### 思路1
-> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
+> 贪心
 
-```go
+- 遍历一次即可得出结果
 
+```go
+func maxProfit2(prices []int) int {
+	profit, low := 0, prices[0]
+	for i := 0; i < len(prices); i++ {
+		profit = max(profit, prices[i]-low)
+		low = min(low, prices[i])
+	}
+	return profit
+}
+
+func min(x, y int) int {
+	if x > y {
+		return y
+	}
+	return x
+}
+
+func max(x, y int) int {
+	if x > y {
+		return x
+	}
+	return y
+}
 ```
 
 ### 思路2
diff --git a/src/0121.Best-Time-to-Buy-and-Sell-Stock/Solution.go b/src/0121.Best-Time-to-Buy-and-Sell-Stock/Solution.go
@@ -1,7 +1,5 @@
 package Solution
 
-import "math"
-
 /**
 持有一股
 买卖一次
@@ -28,16 +26,24 @@ func maxProfit1(prices []int) int {
 //	Greedy
 //	扫描一遍
 func maxProfit2(prices []int) int {
-	min := math.MaxInt32
-	max := 0
-
+	profit, low := 0, prices[0]
 	for i := 0; i < len(prices); i++ {
-		if prices[i] < min {
-			min = prices[i]
-		} else if max < prices[i]-min {
-			max = prices[i] - min
-		}
+		profit = max(profit, prices[i]-low)
+		low = min(low, prices[i])
+	}
+	return profit
+}
+
+func min(x, y int) int {
+	if x > y {
+		return y
 	}
+	return x
+}
 
-	return max
+func max(x, y int) int {
+	if x > y {
+		return x
+	}
+	return y
 }
diff --git a/src/0122.Best-Time-To-Buy-And-Sell-Stock-II/README.md b/src/0122.Best-Time-To-Buy-And-Sell-Stock-II/README.md
@@ -23,21 +23,59 @@ Output: "10101"
 **Tags:** Math, String
 
 ## 题意
->给你两个二进制串，求其和的二进制串。
-
+>假设你有一个数组，其中第i个元素表示第i天某个股票的价格。
+ 设计一种算法以找到最大利润，可以完成任意多次交易，但必须先购买股票再出售股票，不能同时多次交易。
+ 
 ## 题解
 
 ### 思路1
-> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
+> (动态规划) O(n)
 
-```go
+- 设计状态`f[i]`表示第`i`天，当前不持有股票的最大收益；`g[i]`表示第`i`天，当前持有股票的最大收益。
+- 状态转移为`f[i] = max(f[i - 1], g[i - 1] + prices[i])`，表示构成第i天不持有股票有两种方式，一种是前一天也不持有，另一种是前一天持有且这一天售出；二者取最大值。
+- `g[i] = max(g[i - 1], f[i - 1] - prices[i])`，表示构成第i天持有股票有两种方式，一种是前一天持有，另一种是前一天不持有，但这一天刚刚买入。
+- 最终答案为`f[n - 1]`，即最后一天不持有股票的最大收益。
 
+```go
+func maxProfit2(prices []int) int {
+	// 初始化DP
+	n := len(prices)
+	dp := make([][]int, 0)
+	for i := 0; i <= n; i++ {
+		dp = append(dp, make([]int, 2))
+	}
+	dp[0][0], dp[0][1] = 0, math.MinInt32
+	profit_max := 0
+	for i := 0; i < n; i++ {
+		dp[i+1][0] = max(dp[i][1]+prices[i], dp[i][0])
+		dp[i+1][1] = max(dp[i][0]-prices[i], dp[i][1])
+
+		profit_max = max(profit_max, dp[i+1][0])
+		profit_max = max(profit_max, dp[i+1][1])
+	}
+	return profit_max
+}
 ```
 
 ### 思路2
-> 思路2
-```go
+> 贪心:遍历一次数组，低进高出，把正的价格差相加起来就是最终利润。
+
+遍历一次数组，低进高出，把正的价格差相加起来就是最终利润。
+- 递增，如`[1,2,3]`，那么1买3卖 与 每天都买入卖出 等价
+- 递减，如`[3,2,1]`，赚钱是赚不了的
+- 先高再低，如`[1,3,2]`，那么只能在1买3卖捞一笔
+- 先低再高，如`[2,1,3]`，那么同样只能在1买3卖捞一笔
 
+```go
+func maxProfit(prices []int) int {
+	profit := 0
+	for i := 1; i < len(prices); i++ {
+		if prices[i] > prices[i-1] {
+			profit += prices[i] - prices[i-1]
+		}
+	}
+	return profit
+}
 ```
 
 ## 结语
diff --git a/src/0122.Best-Time-To-Buy-And-Sell-Stock-II/Solution.go b/src/0122.Best-Time-To-Buy-And-Sell-Stock-II/Solution.go
@@ -11,13 +11,13 @@ import (
 
 //	Greedy
 func maxProfit(prices []int) int {
-	maxprofix := 0
+	profit := 0
 	for i := 1; i < len(prices); i++ {
 		if prices[i] > prices[i-1] {
-			maxprofix += prices[i] - prices[i-1]
+			profit += prices[i] - prices[i-1]
 		}
 	}
-	return maxprofix
+	return profit
 }
 
 //	DP
@@ -26,6 +26,7 @@ func maxProfit(prices []int) int {
 //dp[i][0] = max(dp[i-1][1]+price[i],dp[i-1][0]) --> Sell on day i or do nothing
 //dp[i][1] = max(dp[i-1][0])-price[i],dp[i-1][1]) --> Buy on day i or do nothing
 //dp[0][0]=0,dp[0][1]=INT_MIN
+
 func maxProfit2(prices []int) int {
 	// 初始化DP
 	n := len(prices)
diff --git a/src/0123.Best-Time-to-Buy-and-Sell-Stock-III/README.md b/src/0123.Best-Time-to-Buy-and-Sell-Stock-III/README.md
@@ -37,12 +37,20 @@ Explanation: In this case, no transaction is done, i.e. max profit = 0.
 **Tags:** Math, String
 
 ## 题意
->买卖股票，持有一股，买卖2此
+>给你一个数组，第 ii 个元素表示第 ii 天股票的价格。
+ 你最多可以交易两次。
+ 请设计一个算法，求最大收益。
+ 
+> 注意：必须先买再卖，且每天只能买或者卖一次。
 
 ## 题解
 
 ### 思路1
-> 
+> 在整个区间的每一点切开， 然后分别计算左子区间和右子区间的最大值，然后再用O(n)时间找到整个区间的最大值。
+
+- 遍历一遍数组，求`[0,i−1][0,i−1`]区间的最大利润`f(i)`，具体做法是找当前最低价格`low`，判断是要以`low`买入当天卖出，还是不动
+- 从后往前遍历，求`[i,n−1][i,n−1]`区间的最大利润`g(i)`，具体做法是找当前最高价格`high`，判断是要当天买入以`high`卖出，还是不动
+- 遍历，求最大利润`max(f(i)+g(i))`
 
 ```go
 func maxProfit(prices []int) int {
diff --git a/src/0123.Best-Time-to-Buy-and-Sell-Stock-III/Solution.go b/src/0123.Best-Time-to-Buy-and-Sell-Stock-III/Solution.go
@@ -2,7 +2,7 @@ package Solution
 
 import "math"
 
-func maxProfit(prices []int) int {
+func maxProfit2(prices []int) int {
 	t1_b, t1_s, t2_b, t2_s := math.MinInt32, 0, math.MinInt32, 0
 
 	for _, v := range prices {
@@ -19,3 +19,29 @@ func max(a, b int) int {
 	}
 	return a
 }
+func min(x, y int) int {
+	if x > y {
+		return y
+	}
+	return y
+}
+
+func maxProfit(prices []int) int {
+	g, f := make([]int, len(prices)), make([]int, len(prices))
+	ans, n, low := 0, len(prices), prices[0]
+
+	for i := 1; i < n; i++ {
+		low = min(low, prices[i])
+		f[i] = max(f[i-1], prices[i]-low)
+	}
+	high := prices[n-1]
+	for i := n - 2; i >= 0; i-- {
+		high = max(high, prices[i])
+		g[i] = max(g[i+1], high-prices[i])
+	}
+
+	for i := 0; i < n; i++ {
+		ans = max(ans, f[i]+g[i])
+	}
+	return ans
+}
diff --git a/src/0123.Best-Time-to-Buy-and-Sell-Stock-III/Solution_test.go b/src/0123.Best-Time-to-Buy-and-Sell-Stock-III/Solution_test.go
@@ -30,6 +30,30 @@ func TestSolution1(t *testing.T) {
 	}
 }
 
+func TestSolution2(t *testing.T) {
+	//	测试用例
+	cases := []struct {
+		name   string
+		inputs []int
+		expect int
+	}{
+		{"TestCase", []int{3, 3, 5, 0, 0, 3, 1, 4}, 6},
+		{"TestCase", []int{1, 2, 3, 4, 5}, 4},
+		{"TestCase", []int{7, 6, 4, 3, 1}, 0},
+	}
+
+	//	开始测试
+	for i, c := range cases {
+		t.Run(c.name+strconv.Itoa(i), func(t *testing.T) {
+			got := maxProfit2(c.inputs)
+			if !reflect.DeepEqual(got, c.expect) {
+				t.Fatalf("expected: %v, but got: %v, with inputs: %v",
+					c.expect, got, c.inputs)
+			}
+		})
+	}
+}
+
 //	压力测试
 func BenchmarkSolution(b *testing.B) {
 
diff --git a/src/0300.Longest-Increasing-Subsequence/README.md b/src/0300.Longest-Increasing-Subsequence/README.md
@@ -24,10 +24,39 @@ Explanation: The longest increasing subsequence is [2,3,7,101], therefore the le
 ## 题解
 
 ### 思路1
-> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
+> （动态规划）O(n2)
 
-```go
+- 用数组`dp[i]`记录以`nums[i]`结尾（即`nums[i]`为最后一个数字）的最长递增子序列的长度，则递推方程为`dp[i]=max(dp[j]+1)`，其中要求`1≤j<i`且`nums[j]<nums[i]`。
+
+> 时间复杂度分析：
 
+- 对每个i(1≤i≤n)，都需要从1遍历到i，则时间复杂度为O(n2)，空间复杂度的话需要一个额外的dp数组，空间复杂度为O(n2)。
+
+> Code
+```go
+func lengthOfLIS(nums []int) int {
+	if len(nums) == 0 {
+		return 0
+	}
+	dp, ans := make([]int, len(nums)), 1
+
+	for i := 0; i < len(nums); i++ {
+		dp[i] = 1
+	}
+
+	for i := 1; i < len(nums); i++ {
+		for j := 0; j < i; j++ {
+			if nums[i] > nums[j] {
+				dp[i] = max(dp[i], dp[j]+1)
+			}
+			//fmt.Println(i, j, ans, dp, nums)
+		}
+		if dp[i] > ans {
+			ans = dp[i]
+		}
+	}
+	return ans
+}
 ```
 
 ### 思路2
diff --git a/src/0300.Longest-Increasing-Subsequence/Solution.go b/src/0300.Longest-Increasing-Subsequence/Solution.go
diff --git a/src/0714.Best-Time-to-Buy-and-Sell-Stockwith-Transaction-Fee/README.md b/src/0714.Best-Time-to-Buy-and-Sell-Stockwith-Transaction-Fee/README.md
diff --git a/src/0714.Best-Time-to-Buy-and-Sell-Stockwith-Transaction-Fee/Solution.go b/src/0714.Best-Time-to-Buy-and-Sell-Stockwith-Transaction-Fee/Solution.go
diff --git a/src/0714.Best-Time-to-Buy-and-Sell-Stockwith-Transaction-Fee/Solution_test.go b/src/0714.Best-Time-to-Buy-and-Sell-Stockwith-Transaction-Fee/Solution_test.go
