Merge remote-tracking branch 'origin/develop' into develop

6boris · 6boris · commit 417be8735a17 · 2019-04-26T12:14:38.000+08:00
diff --git a/src/0128.Longest-Consecutive-Sequence/Solution.go b/src/0128.Longest-Consecutive-Sequence/Solution.go
@@ -0,0 +1,60 @@
+package Soluation
+
+var p map[int]int
+var rank map[int]int
+
+func longestConsecutive(nums []int) int {
+    l := len(nums)
+    if l < 1 {
+        return 0
+    }
+    p, rank = initialize(nums)
+    hash := make(map[int]int)
+    for _, v := range nums {
+        hash[v] = 1
+        if _, ok := hash[v-1]; ok {
+            union(v, v-1)
+        }
+        if _, ok := hash[v+1]; ok {
+            union(v, v+1)
+        }
+    }
+    
+    ans := 0
+    for _, v := range rank {
+        if v > ans {
+            ans = v
+        }
+    }
+    return ans
+}
+
+func initialize(nums []int) (map[int]int, map[int]int) {
+    p, rank = make(map[int]int), make(map[int]int)
+    for _, v := range nums {
+        p[v]    = v
+        rank[v] = 1
+    }
+    return p, rank
+}
+
+func find(x int) int {
+    if p[x] != x {
+        p[x] = find(p[x])
+    }
+    return p[x]
+}
+
+func union(x, y int) {
+    x = find(x)
+    y = find(y)
+    if x != y {
+        if rank[x] >= rank[y] {
+            rank[x] += rank[y]
+            p[y] = x
+        } else {
+            rank[y] += rank[x]
+            p[x] = y
+        }
+    }
+}
diff --git a/src/0128.Longest-Consecutive-Sequence/Solution_test.go b/src/0128.Longest-Consecutive-Sequence/Solution_test.go
@@ -0,0 +1,41 @@
+package Soluation
+
+import (
+	"reflect"
+	"testing"
+)
+
+func TestSolution(t *testing.T) {
+	// 测试用例
+	cases := []struct {
+		name 	string
+		inputs	[]int
+		expect 	int
+	}{
+		{
+			"TestCases 1",
+			[]int{100, 4, 200, 1, 3, 2},
+			4,
+		},
+	}
+
+	// 开始测试
+	for _, c := range cases {
+		t.Run(c.name, func(t *testing.T) {
+			got := longestConsecutive(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() {
+
+}
diff --git a/src/0128.Longest-Consecutive-Sequence/readme.md b/src/0128.Longest-Consecutive-Sequence/readme.md
@@ -0,0 +1,98 @@
+# [128. Longest Consecutive Sequence][title]
+
+## Description
+Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
+
+Your algorithm should run in O(n) complexity.
+
+**Example:**
+
+```
+Input: [100, 4, 200, 1, 3, 2]
+Output: 4
+Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
+```
+
+## 题意
+> 给定一个未排序的整数数组，找出最长连续序列的长度。
+
+
+## 题解
+
+### 思路1
+> 使用并查集，将相邻的元素合并，找到元素最多的集合。
+
+```go
+var p map[int]int
+var rank map[int]int
+
+func longestConsecutive(nums []int) int {
+    l := len(nums)
+    if l < 1 {
+        return 0
+    }
+    p, rank = initialize(nums)
+    hash := make(map[int]int)
+    for _, v := range nums {
+        hash[v] = 1
+        if _, ok := hash[v-1]; ok {
+            union(v, v-1)
+        }
+        if _, ok := hash[v+1]; ok {
+            union(v, v+1)
+        }
+    }
+    
+    ans := 0
+    for _, v := range rank {
+        if v > ans {
+            ans = v
+        }
+    }
+    fmt.Println(rank)
+    return ans
+}
+
+func initialize(nums []int) (map[int]int, map[int]int) {
+    p, rank = make(map[int]int), make(map[int]int)
+    for _, v := range nums {
+        p[v]    = v
+        rank[v] = 1
+    }
+    return p, rank
+}
+
+func find(x int) int {
+    if p[x] != x {
+        p[x] = find(p[x])
+    }
+    return p[x]
+}
+
+func union(x, y int) {
+    x = find(x)
+    y = find(y)
+    if x != y {
+        if rank[x] >= rank[y] {
+            rank[x] += rank[y]
+            p[y] = x
+        } else {
+            rank[y] += rank[x]
+            p[x] = y
+        }
+    }
+}
+```
+
+### 思路2
+> 思路2
+```go
+
+```
+
+## 结语
+
+如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
+
+[title]: https://leetcode.com/problems/longest-consecutive-sequence/description/  
+[me]: https://github.com/kylesliu/awesome-golang-leetcode
diff --git a/src/0674.longest-continuous-increasing-subsequence/Soluation.go b/src/0674.longest-continuous-increasing-subsequence/Soluation.go
@@ -0,0 +1,19 @@
+package Soluation
+
+func findLengthOfLCIS(nums []int) int {
+    if 0 == len(nums) {
+        return 0
+    }
+    ans, sum := 1, 1
+    for i := 1; i < len(nums); i++ {
+        if nums[i] > nums[i-1] {
+            sum++
+        } else {
+            sum = 1
+        }
+        if sum > ans {
+            ans = sum
+        }
+    }
+    return ans
+}
diff --git a/src/0674.longest-continuous-increasing-subsequence/Soluation_test.go b/src/0674.longest-continuous-increasing-subsequence/Soluation_test.go
@@ -0,0 +1,46 @@
+package Soluation
+
+import (
+	"reflect"
+	"testing"
+)
+
+func TestSolution(t *testing.T) {
+	// 测试用例
+	cases := []struct {
+		name 	string
+		inputs	[]int
+		expect 	int
+	}{
+		{
+			"TestCases 1",
+			[]int{1,3,5,4,7},
+			3,
+		},
+		{
+			"TestCases 2",
+			[]int{2,2,2,2,2},
+			1,
+		},
+	}
+
+	// 开始测试
+	for _, c := range cases {
+		t.Run(c.name, func(t *testing.T) {
+			got := findLengthOfLCIS(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() {
+
+}
diff --git a/src/0674.longest-continuous-increasing-subsequence/readme.md b/src/0674.longest-continuous-increasing-subsequence/readme.md
@@ -0,0 +1,58 @@
+# [674.  Longest Continuous Increasing Subsequence][title]
+
+## Description
+
+Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).
+
+**Example 1:**
+```
+Input: [1,3,5,4,7]
+Output: 3
+Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. 
+Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4. 
+```
+
+**Example 2:**
+```
+Input: [2,2,2,2,2]
+Output: 1
+Explanation: The longest continuous increasing subsequence is [2], its length is 1. 
+```
+
+## Note
+Length of the array will not exceed 10,000.
+
+## 题意
+> 求一个数组的最长连续上升序列长度。
+
+## 题解
+
+### 思路 1
+> 判断相邻两个元素，后一个是否大于前一个，如果是就 +1，否则重置计数器。
+
+```go
+func findLengthOfLCIS(nums []int) int {
+    if 0 == len(nums) {
+        return 0
+    }
+    ans, sum := 1, 1
+    for i := 1; i < len(nums); i++ {
+        if nums[i] > nums[i-1] {
+            sum++
+        } else {
+            sum = 1
+        }
+        if sum > ans {
+            ans = sum
+        }
+    }
+    return ans
+}
+```
+
+## 结语
+
+如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
+
+[title]: https://leetcode.com/problems/longest-continuous-increasing-subsequence/description/  
+[me]: https://github.com/kylesliu/awesome-golang-leetcode
diff --git a/src/0695.max-area-of-island/Soluation.go b/src/0695.max-area-of-island/Soluation.go
@@ -0,0 +1,32 @@
+package Soluation
+
+func maxAreaOfIsland(grid [][]int) int {
+    ans := 0
+    height, width := len(grid), len(grid[0])
+
+    for i := 0; i < height; i++ {
+        for j := 0; j < width; j++ {
+            tmp := 0;
+            if 1 == grid[i][j] {
+                tmp = dfs(grid, i, j)
+                if tmp > ans {
+                    ans = tmp
+                }
+            }
+        }
+    }
+    return ans
+}
+
+func dfs(grid [][]int, i, j int) int {
+    res := 0
+    if i >= 0 && i < len(grid) && j >= 0 && j < len(grid[0]) && 1 == grid[i][j] {
+        grid[i][j] = 0
+        up := dfs(grid, i-1, j)
+        down := dfs(grid, i+1, j)
+        left := dfs(grid, i, j-1)
+        right := dfs(grid, i, j+1)
+        res = up + down + left + right + 1
+    }
+    return res
+}
diff --git a/src/0695.max-area-of-island/Soluation_test.go b/src/0695.max-area-of-island/Soluation_test.go
diff --git a/src/0695.max-area-of-island/readme.md b/src/0695.max-area-of-island/readme.md
