Merge pull request 6boris#2 from kylesliu/develop

saenaii · web-flow · commit 5ada83ada3d0 · 2019-05-30T20:58:51.000+08:00
Develop
diff --git a/README.md b/README.md
@@ -35,6 +35,11 @@ LeetCode of algorithms with golang solution(updating:smiley:).
 
 [![Stargazers over time](https://starcharts.herokuapp.com/kylesliu/awesome-golang-leetcode.svg)](https://starcharts.herokuapp.com/kylesliu/awesome-golang-leetcode)
 
+## Community
+
+* [leetbook](https://github.com/hk029/leetbook) 某位大佬写的Leetcode题解，不过已经不更新了
+* [LeetCode-in-Go](https://github.com/aQuaYi/LeetCode-in-Go) 某位算法大佬的Golang题解
+
 ## Contributors
 
 Thanks goes to these wonderful people ([emoji key](https://github.com/all-contributors/all-contributors#emoji-key)):
diff --git a/src/0006.ZigZag-Conversion/Solution.go b/src/0006.ZigZag-Conversion/Solution.go
@@ -1,5 +1,7 @@
 package Solution
 
+import "fmt"
+
 func convert(s string, numRows int) string {
 	if numRows == 1 || numRows <= 0 || numRows > len(s) {
 		return s
@@ -23,10 +25,30 @@ func convert(s string, numRows int) string {
 			}
 		}
 	}
+	fmt.Println(strArr)
 	res := make([]byte, 0)
 
 	for _, str := range strArr {
 		res = append(res, str...)
 	}
 	return string(res)
 }
+func convert2(s string, numRows int) string {
+	if numRows <= 1 {
+		return s
+	}
+	lenth, cycle, n := len(s), 2*numRows-2, 0
+	result := make([]byte, lenth)
+	for i := 0; i < numRows; i++ {
+		for j1 := i; j1 < lenth; j1 = cycle + j1 {
+
+			n += copy(result[n:], string(s[j1]))
+			j2 := j1 + cycle - 2*i
+			if i != 0 && i != numRows-1 && j2 < lenth {
+				n += copy(result[n:], string(s[j2]))
+			}
+
+		}
+	}
+	return string(result)
+}
diff --git a/src/0322.Coin-Change/README.md b/src/0322.Coin-Change/README.md
@@ -0,0 +1,70 @@
+# [322. Coin Change][title]
+
+## Description
+
+You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
+
+**Example 1:**
+
+```
+Input: coins = [1, 2, 5], amount = 11
+Output: 3 
+Explanation: 11 = 5 + 5 + 1
+```
+
+**Example 2:**
+
+```
+Input: coins = [2], amount = 3
+Output: -1
+```
+
+**Tags:** Math, String
+
+## 题意
+> 给定 nn 种不同硬币的面值，以及需要凑出的总面值 totaltotal。请写一个函数，求最少需要多少硬币，可以凑出 totaltotal 的钱。
+  如果不存在任何一种拼凑方案，则返回-1。
+  
+
+
+## 题解
+
+### 动态规划
+> 状态表示：
+- dp[i]表示凑出 ii 价值的钱，最少需要多少个硬币。
+- 第i种硬币 dp[i] = min(dp[i], min(dp[i - coins[i]] ) + 1)
+
+```go
+func coinChange(coins []int, amount int) int {
+	dp := make([]int, amount+1)
+	for i := 0; i < amount+1; i++ {
+		dp[i] = amount + 1
+	}
+	dp[0] = 0
+
+	for i := 1; i <= amount; i++ {
+		for j := 0; j < len(coins); j++ {
+			if coins[j] <= i {
+				dp[i] = min(dp[i], dp[i-coins[j]]+1)
+			}
+		}
+	}
+	if dp[amount] > amount {
+		return -1
+	}
+	return dp[amount]
+}
+```
+
+### 思路2
+> 思路2
+```go
+
+```
+
+## 结语
+
+如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
+
+[title]: https://leetcode.com/problems/two-sum/description/
+[me]: https://github.com/kylesliu/awesome-golang-leetcode
diff --git a/src/0322.Coin-Change/Solution.go b/src/0322.Coin-Change/Solution.go
@@ -0,0 +1,28 @@
+package Solution
+
+func coinChange(coins []int, amount int) int {
+	dp := make([]int, amount+1)
+	for i := 0; i < amount+1; i++ {
+		dp[i] = amount + 1
+	}
+	dp[0] = 0
+
+	for i := 1; i <= amount; i++ {
+		for j := 0; j < len(coins); j++ {
+			if coins[j] <= i {
+				dp[i] = min(dp[i], dp[i-coins[j]]+1)
+			}
+		}
+	}
+	if dp[amount] > amount {
+		return -1
+	}
+	return dp[amount]
+}
+
+func min(x, y int) int {
+	if x > y {
+		return y
+	}
+	return x
+}
diff --git a/src/0322.Coin-Change/Solution_test.go b/src/0322.Coin-Change/Solution_test.go
@@ -0,0 +1,41 @@
+package Solution
+
+import (
+	"reflect"
+	"strconv"
+	"testing"
+)
+
+func TestSolution(t *testing.T) {
+	//	测试用例
+	cases := []struct {
+		name   string
+		inputs []int
+		amount int
+		expect int
+	}{
+		{"TestCase", []int{1, 2, 5}, 11, 3},
+		{"TestCase", []int{2}, 3, -1},
+	}
+
+	//	开始测试
+	for i, c := range cases {
+		t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
+			got := coinChange(c.inputs, c.amount)
+			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) {
+
+}
+
+//	使用案列
+func ExampleSolution() {
+
+}
diff --git a/src/0452.Minimum-Number-of-Arrows-to-Burst-Balloons/README.md b/src/0452.Minimum-Number-of-Arrows-to-Burst-Balloons/README.md
@@ -0,0 +1,53 @@
+# [452. Minimum Number of Arrows to Burst Balloons][title]
+
+## Description
+
+There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.
+
+An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.
+**Example 1:**
+
+```
+Input:
+[[10,16], [2,8], [1,6], [7,12]]
+
+Output:
+2
+Explanation:
+One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).
+
+```
+
+**Example 2:**
+
+```
+Input: a = "1010", b = "1011"
+Output: "10101"
+```
+
+**Tags:** Math, String
+
+## 题意
+> 求2数之和
+
+## 题解
+
+### 思路1
+> 。。。。
+
+```go
+
+```
+
+### 思路2
+> 思路2
+```go
+
+```
+
+## 结语
+
+如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
+
+[title]: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
+[me]: https://github.com/kylesliu/awesome-golang-leetcode
diff --git a/src/0452.Minimum-Number-of-Arrows-to-Burst-Balloons/Solution.go b/src/0452.Minimum-Number-of-Arrows-to-Burst-Balloons/Solution.go
@@ -0,0 +1,28 @@
+package Solution
+
+import (
+	"sort"
+)
+
+func findMinArrowShots(points [][]int) int {
+	if len(points) == 0 {
+		return 0
+	}
+	sort.Sort(ByLen(points))
+
+	res := 0
+	end := -1<<31 - 1
+	for _, interval := range points {
+		if interval[0] > end {
+			res += 1
+			end = interval[1]
+		}
+	}
+	return res
+}
+
+type ByLen [][]int
+
+func (a ByLen) Len() int           { return len(a) }
+func (a ByLen) Less(i, j int) bool { return a[i][1] < a[j][1] }
+func (a ByLen) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
diff --git a/src/0452.Minimum-Number-of-Arrows-to-Burst-Balloons/Solution_test.go b/src/0452.Minimum-Number-of-Arrows-to-Burst-Balloons/Solution_test.go
@@ -0,0 +1,44 @@
+package Solution
+
+import (
+	"reflect"
+	"strconv"
+	"testing"
+)
+
+func TestSolution(t *testing.T) {
+	//	测试用例
+	cases := []struct {
+		name   string
+		inputs [][]int
+		expect int
+	}{
+		{"TestCase", [][]int{
+			{10, 16},
+			{2, 8},
+			{1, 6},
+			{7, 12},
+		}, 2},
+	}
+
+	//	开始测试
+	for i, c := range cases {
+		t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
+			got := findMinArrowShots(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) {
+
+}
+
+//	使用案列
+func ExampleSolution() {
+
+}
