add 174 problem solution

6boris · 6boris · commit b98f6d5d6e24 · 2020-03-02T22:32:34.000+08:00
diff --git a/src/0174.Dungeon-Game/README.md b/src/0174.Dungeon-Game/README.md
@@ -13,16 +13,86 @@ Output: "100"
 ```
 
 ## 题意
-> ...
+> 给定一个整数数组，计算给定区间中所有数的和。
+
+> 注意： 
+- 你可以假设询问过程中数组不会被修改；
+- sumRange()会被调用多次；
 
 ## 题解
 
 ### 思路1
-> ...
-Dungeon Game
+> 暴力循环求解
+>时间复杂度 O(N^2)  空间复杂度 O(1)
+```go
+package main
+
+type NumArray struct {
+	Sum []int
+}
+func Constructor(nums []int) NumArray {
+	var s NumArray
+	s.Sum = nums
+	return s
+}
+
+func (this *NumArray) SumRange(i int, j int) int {
+	ans := 0
+	for k := i; k <= j; k++ {
+		ans += this.Sum[k]
+	}
+	return ans
+}
+```
+### 思路2
+> 将结果全部缓存
+> 时间复杂度 O(N^2)  空间复杂度 O(N^2)
 ```go
+package main
+
+type NumArray struct {
+	m   map[[2]int]int
+}
+func Constructor(nums []int) NumArray {
+	s := NumArray{m: map[[2]int]int{}}
+
+	for i := 0; i < len(nums); i++ {
+		sum := 0
+		for j := i; j < len(nums); j++ {
+			sum += nums[j]
+			s.m[[2]int{i, j}] = sum
+		}
+	}
+	return s
+}
+
+func (this *NumArray) SumRange(i int, j int) int {
+	return this.m[[2]int{i, j}]
+}
 ```
 
+### 思路3
+> 动态规划
+> 时间复杂度 O(N^2)  空间复杂度 O(N)
+```go
+package main
+
+type NumArray struct {
+	Sum []int
+}
+func Constructor(nums []int) NumArray {
+	var res NumArray
+	res.Sum = make([]int, len(nums)+1)
+	for k, v := range nums {
+		res.Sum[k+1] = res.Sum[k] + v
+	}
+	return res
+}
+
+func (this *NumArray) SumRange(i int, j int) int {
+	return this.Sum[j+1] - this.Sum[i]
+}
+```
 
 ## 结语
 
diff --git a/src/0174.Dungeon-Game/Solution.go b/src/0174.Dungeon-Game/Solution.go
@@ -1,5 +1,61 @@
 package Solution
 
-func Solution(x bool) bool {
-	return x
+type NumArray struct {
+	Sum []int
+	m   map[[2]int]int
 }
+
+//	暴力循环
+func Constructor(nums []int) NumArray {
+	var s NumArray
+	s.Sum = nums
+	return s
+}
+
+func (this *NumArray) SumRange(i int, j int) int {
+	ans := 0
+	for k := i; k <= j; k++ {
+		ans += this.Sum[k]
+	}
+	return ans
+}
+
+//	利用 map 做缓存
+func Constructor2(nums []int) NumArray {
+	s := NumArray{m: map[[2]int]int{}}
+
+	for i := 0; i < len(nums); i++ {
+		sum := 0
+		for j := i; j < len(nums); j++ {
+			sum += nums[j]
+			s.m[[2]int{i, j}] = sum
+		}
+	}
+	return s
+}
+
+func (this *NumArray) SumRange2(i int, j int) int {
+	return this.m[[2]int{i, j}]
+}
+
+//	DP
+//	sum[i] = nums[0] +  nums[1] + nums[2]
+//	sum[i+1] = sum[i] + nums[i+1]
+func Constructor3(nums []int) NumArray {
+	var res NumArray
+	res.Sum = make([]int, len(nums)+1)
+	for k, v := range nums {
+		res.Sum[k+1] = res.Sum[k] + v
+	}
+	return res
+}
+
+func (this *NumArray) SumRange3(i int, j int) int {
+	return this.Sum[j+1] - this.Sum[i]
+}
+
+/**
+ * Your NumArray object will be instantiated and called as such:
+ * obj := Constructor(nums);
+ * param_1 := obj.SumRange(i,j);
+ */
diff --git a/src/0174.Dungeon-Game/Solution_test.go b/src/0174.Dungeon-Game/Solution_test.go
@@ -10,21 +10,74 @@ func TestSolution(t *testing.T) {
 	//	测试用例
 	cases := []struct {
 		name   string
-		inputs bool
-		expect bool
+		input1 []int
+		input2 [][]int
+		expect []int
 	}{
-		{"TestCase", true, true},
-		{"TestCase", true, true},
-		{"TestCase", false, false},
+		{"TestCase", []int{-2, 0, 3, -5, 2, -1}, [][]int{{0, 2}, {2, 5}, {0, 5}}, []int{1, -1, -3}},
 	}
 
 	//	开始测试
 	for i, c := range cases {
 		t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
-			got := Solution(c.inputs)
-			if !reflect.DeepEqual(got, c.expect) {
-				t.Fatalf("expected: %v, but got: %v, with inputs: %v",
-					c.expect, got, c.inputs)
+			obj := Constructor(c.input1)
+			for i := 0; i < len(c.input2); i++ {
+				got := obj.SumRange(c.input2[i][0], c.input2[i][1])
+				if !reflect.DeepEqual(got, c.expect[i]) {
+					t.Fatalf("expected: %v, but got: %v, with input2: %v input1: %v ",
+						c.expect[i], got, c.input2[i], c.input1[i])
+				}
+			}
+		})
+	}
+}
+
+func TestSolution2(t *testing.T) {
+	//	测试用例
+	cases := []struct {
+		name   string
+		input1 []int
+		input2 [][]int
+		expect []int
+	}{
+		{"TestCase", []int{-2, 0, 3, -5, 2, -1}, [][]int{{0, 2}, {2, 5}, {0, 5}}, []int{1, -1, -3}},
+	}
+
+	//	开始测试
+	for i, c := range cases {
+		t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
+			obj := Constructor2(c.input1)
+			for i := 0; i < len(c.input2); i++ {
+				got := obj.SumRange2(c.input2[i][0], c.input2[i][1])
+				if !reflect.DeepEqual(got, c.expect[i]) {
+					t.Fatalf("expected: %v, but got: %v, with input2: %v input1: %v ",
+						c.expect[i], got, c.input2[i], c.input1[i])
+				}
+			}
+		})
+	}
+}
+func TestSolution3(t *testing.T) {
+	//	测试用例
+	cases := []struct {
+		name   string
+		input1 []int
+		input2 [][]int
+		expect []int
+	}{
+		{"TestCase", []int{-2, 0, 3, -5, 2, -1}, [][]int{{0, 2}, {2, 5}, {0, 5}}, []int{1, -1, -3}},
+	}
+
+	//	开始测试
+	for i, c := range cases {
+		t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
+			obj := Constructor3(c.input1)
+			for i := 0; i < len(c.input2); i++ {
+				got := obj.SumRange3(c.input2[i][0], c.input2[i][1])
+				if !reflect.DeepEqual(got, c.expect[i]) {
+					t.Fatalf("expected: %v, but got: %v, with input2: %v input1: %v ",
+						c.expect[i], got, c.input2[i], c.input1[i])
+				}
 			}
 		})
 	}
