Merge pull request halfrost#84 from frankegoesdown/0910-smallest-range-ii

halfrost · halfrost · commit 354c802c2208 · 2020-12-25T15:19:01.000+08:00
add 0910 smallest-range-ii
diff --git a/leetcode/0910.Smallest-Range-II/910.Smallest Range II.go b/leetcode/0910.Smallest-Range-II/910.Smallest Range II.go
@@ -0,0 +1,30 @@
+package leetcode
+
+import "sort"
+
+func smallestRangeII(A []int, K int) int {
+	n := len(A)
+	sort.Ints(A)
+	res := A[n-1] - A[0]
+	for i := 0; i < n-1; i++ {
+		a, b := A[i], A[i+1]
+		high := max(A[n-1]-K, a+K)
+		low := min(A[0]+K, b-K)
+		res = min(res, high-low)
+	}
+	return res
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}
diff --git a/leetcode/0910.Smallest-Range-II/910.Smallest Range II_test.go b/leetcode/0910.Smallest-Range-II/910.Smallest Range II_test.go
@@ -0,0 +1,48 @@
+package leetcode
+
+import (
+	"fmt"
+	"testing"
+)
+
+type question910 struct {
+	para910
+	ans910
+}
+
+type para910 struct {
+	A []int
+	K int
+}
+
+type ans910 struct {
+	one int
+}
+
+// Test_Problem910 ...
+func Test_Problem910(t *testing.T) {
+
+	qs := []question910{
+
+		{
+			para910{[]int{1}, 0},
+			ans910{0},
+		},
+		{
+			para910{[]int{0, 10}, 2},
+			ans910{6},
+		},
+		{
+			para910{[]int{1, 3, 6}, 3},
+			ans910{3},
+		},
+	}
+
+	fmt.Printf("------------------------Leetcode Problem 910------------------------\n")
+
+	for _, q := range qs {
+		_, p := q.ans910, q.para910
+		fmt.Printf("【input】:%v       【output】:%v\n", p, smallestRangeII(p.A, p.K))
+	}
+	fmt.Printf("\n\n\n")
+}
diff --git a/leetcode/0910.Smallest-Range-II/README.md b/leetcode/0910.Smallest-Range-II/README.md
@@ -0,0 +1,82 @@
+# [910. Smallest Range II](https://leetcode.com/problems/smallest-range-ii/)
+
+## 题目
+
+Given an array `A` of integers, for each integer `A[i]` we need to choose **either `x = -K` or `x = K`**, and add `x` to `A[i]` **(only once)**.
+
+After this process, we have some array `B`.
+
+Return the smallest possible difference between the maximum value of `B` and the minimum value of `B`.
+
+**Example 1:**
+
+```
+Input: A = [1], K = 0
+Output: 0
+Explanation: B = [1]
+```
+
+**Example 2:**
+
+```
+Input: A = [0,10], K = 2
+Output: 6
+Explanation: B = [2,8]
+```
+
+**Example 3:**
+
+```
+Input: A = [1,3,6], K = 3
+Output: 3
+Explanation: B = [4,6,3]
+```
+
+**Note:**
+
+1. `1 <= A.length <= 10000`
+2. `0 <= A[i] <= 10000`
+3. `0 <= K <= 10000`
+
+## 题目大意
+
+给你一个整数数组 A，对于每个整数 A[i]，可以选择 x = -K 或是 x = K （K 总是非负整数），并将 x 加到 A[i] 中。在此过程之后，得到数组 B。返回 B 的最大值和 B 的最小值之间可能存在的最小差值。
+
+## 解题思路
+
+- 简单题。先排序，找出 A 数组中最大的差值。然后循环扫一遍数组，利用双指针，选择 x = -K 或是 x = K ，每次选择都更新一次最大值和最小值之间的最小差值。循环一次以后便可以找到满足题意的答案。
+
+## 代码
+
+```go
+package leetcode
+
+import "sort"
+
+func smallestRangeII(A []int, K int) int {
+	n := len(A)
+	sort.Ints(A)
+	res := A[n-1] - A[0]
+	for i := 0; i < n-1; i++ {
+		a, b := A[i], A[i+1]
+		high := max(A[n-1]-K, a+K)
+		low := min(A[0]+K, b-K)
+		res = min(res, high-low)
+	}
+	return res
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}
+```
diff --git a/website/content/ChapterFour/0910.Smallest-Range-II.md b/website/content/ChapterFour/0910.Smallest-Range-II.md
@@ -0,0 +1,82 @@
+# [910. Smallest Range II](https://leetcode.com/problems/smallest-range-ii/)
+
+## 题目
+
+Given an array `A` of integers, for each integer `A[i]` we need to choose **either `x = -K` or `x = K`**, and add `x` to `A[i]` **(only once)**.
+
+After this process, we have some array `B`.
+
+Return the smallest possible difference between the maximum value of `B` and the minimum value of `B`.
+
+**Example 1:**
+
+```
+Input: A = [1], K = 0
+Output: 0
+Explanation: B = [1]
+```
+
+**Example 2:**
+
+```
+Input: A = [0,10], K = 2
+Output: 6
+Explanation: B = [2,8]
+```
+
+**Example 3:**
+
+```
+Input: A = [1,3,6], K = 3
+Output: 3
+Explanation: B = [4,6,3]
+```
+
+**Note:**
+
+1. `1 <= A.length <= 10000`
+2. `0 <= A[i] <= 10000`
+3. `0 <= K <= 10000`
+
+## 题目大意
+
+给你一个整数数组 A，对于每个整数 A[i]，可以选择 x = -K 或是 x = K （K 总是非负整数），并将 x 加到 A[i] 中。在此过程之后，得到数组 B。返回 B 的最大值和 B 的最小值之间可能存在的最小差值。
+
+## 解题思路
+
+- 简单题。先排序，找出 A 数组中最大的差值。然后循环扫一遍数组，利用双指针，选择 x = -K 或是 x = K ，每次选择都更新一次最大值和最小值之间的最小差值。循环一次以后便可以找到满足题意的答案。
+
+## 代码
+
+```go
+package leetcode
+
+import "sort"
+
+func smallestRangeII(A []int, K int) int {
+	n := len(A)
+	sort.Ints(A)
+	res := A[n-1] - A[0]
+	for i := 0; i < n-1; i++ {
+		a, b := A[i], A[i+1]
+		high := max(A[n-1]-K, a+K)
+		low := min(A[0]+K, b-K)
+		res = min(res, high-low)
+	}
+	return res
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}
+```
diff --git a/website/content/menu/index.md b/website/content/menu/index.md
@@ -428,6 +428,7 @@ headless: true
     - [0901.Online-Stock-Span]({{< relref "/ChapterFour/0901.Online-Stock-Span.md" >}})
     - [0904.Fruit-Into-Baskets]({{< relref "/ChapterFour/0904.Fruit-Into-Baskets.md" >}})
     - [0907.Sum-of-Subarray-Minimums]({{< relref "/ChapterFour/0907.Sum-of-Subarray-Minimums.md" >}})
+    - [0910.Smallest-Range-II]({{< relref "/ChapterFour/0910.Smallest-Range-II.md" >}})
     - [0911.Online-Election]({{< relref "/ChapterFour/0911.Online-Election.md" >}})
     - [0914.X-of-a-Kind-in-a-Deck-of-Cards]({{< relref "/ChapterFour/0914.X-of-a-Kind-in-a-Deck-of-Cards.md" >}})
     - [0918.Maximum-Sum-Circular-Subarray]({{< relref "/ChapterFour/0918.Maximum-Sum-Circular-Subarray.md" >}})
