update the 45 problem

6boris · 6boris · commit 5b678249531a · 2019-04-17T13:02:34.000+08:00
diff --git a/src/0045.Jump-Game-II/Solution.go b/src/0045.Jump-Game-II/Solution.go
@@ -1,6 +1,7 @@
 package Solution
 
 import (
+	"fmt"
 	"math"
 )
 
@@ -54,6 +55,34 @@ func jump2(nums []int) int {
 	return res
 }
 
+/**
+1
+
+*/
+func jump3(nums []int) int {
+	//	如果数组小于2，则说明不用跳跃返回0
+	if len(nums) < 2 {
+		return 0
+	}
+	//	当前可达到的最远位置，遍历过程中可达到最远位置，最小步数
+	current_max_index, pre_max_max_index, jump_min := nums[0], nums[0], 1
+
+	for i := 1; i < len(nums); i++ {
+		//	如果无法向前移动才进行跳跃
+		if i > current_max_index {
+			jump_min++
+			//	更新当前可以到达的最远位置
+			current_max_index = pre_max_max_index
+		}
+		if pre_max_max_index < nums[i]+i {
+			//	跟新最远位置
+			pre_max_max_index = nums[i] + i
+		}
+		fmt.Println("i:", i, current_max_index, pre_max_max_index, jump_min)
+	}
+	return jump_min
+}
+
 func Min(x, y int) int {
 	if x > y {
 		return y
diff --git a/src/0045.Jump-Game-II/Solution_test.go b/src/0045.Jump-Game-II/Solution_test.go
@@ -36,9 +36,10 @@ func TestSolution2(t *testing.T) {
 		inputs []int
 		expect int
 	}{
-		{"TestCacse 1", []int{2, 3, 1, 1, 4}, 2},
-		{"TestCacse 1", []int{2}, 0},
-		{"TestCacse 1", []int{10, 3, 4}, 1},
+		{"TestCase 1", []int{2, 3, 1, 1, 4}, 2},
+		{"TestCase 1", []int{2}, 0},
+		{"TestCase 1", []int{10, 3, 4}, 1},
+		{"TestCase 4", []int{4, 1, 1, 3, 1, 1, 1}, 2},
 	}
 
 	//	开始测试
@@ -53,6 +54,31 @@ func TestSolution2(t *testing.T) {
 	}
 }
 
+func TestSolution3(t *testing.T) {
+	//	测试用例
+	cases := []struct {
+		name   string
+		inputs []int
+		expect int
+	}{
+		{"TestCase 1", []int{2, 3, 1, 1, 4}, 2},
+		{"TestCase 2", []int{2}, 0},
+		{"TestCase 3", []int{10, 3, 4}, 1},
+		{"TestCase 4", []int{4, 1, 1, 3, 1, 1, 1}, 2},
+	}
+
+	//	开始测试
+	for _, c := range cases {
+		t.Run(c.name, func(t *testing.T) {
+			ret := jump3(c.inputs)
+			if !reflect.DeepEqual(ret, c.expect) {
+				t.Fatalf("expected: %v, but got: %v, with inputs: %v",
+					c.expect, ret, c.inputs)
+			}
+		})
+	}
+}
+
 //	压力测试
 func BenchmarkSolution(b *testing.B) {
 
