Merge pull request halfrost#222 from gostool/leetcode1296

halfrost · web-flow · commit 97312873b2a6 · 2022-01-14T21:23:00.000-08:00
Leetcode1296
diff --git a/leetcode/1296.Divide-Array-in-Sets-of-K-Consecutive-Numbers/1296.Divide Array in Sets of K Consecutive Numbers.go b/leetcode/1296.Divide-Array-in-Sets-of-K-Consecutive-Numbers/1296.Divide Array in Sets of K Consecutive Numbers.go
@@ -0,0 +1,23 @@
+package leetcode
+
+import "sort"
+
+func isPossibleDivide(nums []int, k int) bool {
+	mp := make(map[int]int)
+	for _, v := range nums {
+		mp[v] += 1
+	}
+	sort.Ints(nums)
+	for _, num := range nums {
+		if mp[num] == 0 {
+			continue
+		}
+		for diff := 0; diff < k; diff++ {
+			if mp[num+diff] == 0 {
+				return false
+			}
+			mp[num+diff] -= 1
+		}
+	}
+	return true
+}
diff --git a/leetcode/1296.Divide-Array-in-Sets-of-K-Consecutive-Numbers/1296.Divide Array in Sets of K Consecutive Numbers_test.go b/leetcode/1296.Divide-Array-in-Sets-of-K-Consecutive-Numbers/1296.Divide Array in Sets of K Consecutive Numbers_test.go
@@ -0,0 +1,51 @@
+package leetcode
+
+import (
+	"fmt"
+	"testing"
+)
+
+type question1296 struct {
+	para1296
+	ans1296
+}
+
+// para 是参数
+type para1296 struct {
+	nums []int
+	k    int
+}
+
+// ans 是答案
+type ans1296 struct {
+	ans bool
+}
+
+func Test_Problem1296(t *testing.T) {
+
+	qs := []question1296{
+
+		{
+			para1296{[]int{1, 2, 3, 3, 4, 4, 5, 6}, 4},
+			ans1296{true},
+		},
+
+		{
+			para1296{[]int{3, 2, 1, 2, 3, 4, 3, 4, 5, 9, 10, 11}, 3},
+			ans1296{true},
+		},
+
+		{
+			para1296{[]int{1, 2, 3, 4}, 3},
+			ans1296{false},
+		},
+	}
+
+	fmt.Printf("------------------------Leetcode Problem 1296------------------------\n")
+
+	for _, q := range qs {
+		_, p := q.ans1296, q.para1296
+		fmt.Printf("【input】:%v    【output】:%v\n", p, isPossibleDivide(p.nums, p.k))
+	}
+	fmt.Printf("\n\n\n")
+}
diff --git a/leetcode/1296.Divide-Array-in-Sets-of-K-Consecutive-Numbers/README.md b/leetcode/1296.Divide-Array-in-Sets-of-K-Consecutive-Numbers/README.md
@@ -0,0 +1,72 @@
+# [1296. Divide Array in Sets of K Consecutive Numbers](https://leetcode-cn.com/problems/divide-array-in-sets-of-k-consecutive-numbers/)
+
+## 题目
+
+Given an array of integers nums and a positive integer k, check whether it is possible to divide this array into sets of k consecutive numbers.
+
+Return true if it is possible. Otherwise, return false.
+
+**Example 1**:
+
+    Input: nums = [1,2,3,3,4,4,5,6], k = 4
+    Output: true
+    Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].
+
+**Example 2**:
+
+    Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
+    Output: true
+    Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].
+
+**Example 3**:
+
+    Input: nums = [1,2,3,4], k = 3
+    Output: false
+    Explanation: Each array should be divided in subarrays of size 3.
+
+**Constraints:**
+
+- 1 <= k <= nums.length <= 100000
+- 1 <= nums[i] <= 1000000000
+
+## 题目大意
+
+给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。
+如果可以，请返回 true；否则，返回 false。
+
+## 解题思路
+
+贪心算法
+
+- 对nums升序排序
+- 对nums内数字进行哈希计数（key:数字，value:数量）
+- 遍历nums中的数字，以数量大于1的数字作为连续数字开头，寻找连续数字后续元素，若无法找到 k 个连续数字则返回false
+- 所有数字都能找到 k 个连续数字返回true
+
+##代码
+
+```go
+package leetcode
+
+import "sort"
+
+func isPossibleDivide(nums []int, k int) bool {
+	mp := make(map[int]int)
+	for _, v := range nums {
+		mp[v] += 1
+	}
+	sort.Ints(nums)
+	for _, num := range nums {
+		if mp[num] == 0 {
+			continue
+		}
+		for diff := 0; diff < k; diff++ {
+			if mp[num+diff] == 0 {
+				return false
+			}
+			mp[num+diff] -= 1
+		}
+	}
+	return true
+}
+```
