Skip to content

Commit 45fb40e

Browse files
halfrosthalfrost
committed
Add solution 0368、0377、0696
1 parent 1cdbefd commit 45fb40e

38 files changed

+1371
-665
lines changed

‎README.md

Lines changed: 465 additions & 464 deletions
Large diffs are not rendered by default.

‎leetcode/0368.Largest-Divisible-Subset/368. Largest Divisible Subset.go

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package leetcode
2+
3+
import "sort"
4+
5+
func largestDivisibleSubset(nums []int) []int {
6+
sort.Ints(nums)
7+
dp, res := make([]int, len(nums)), []int{}
8+
for i := range dp {
9+
dp[i] = 1
10+
}
11+
maxSize, maxVal := 1, 1
12+
for i := 1; i < len(nums); i++ {
13+
for j, v := range nums[:i] {
14+
if nums[i]%v == 0 && dp[j]+1 > dp[i] {
15+
dp[i] = dp[j] + 1
16+
}
17+
}
18+
if dp[i] > maxSize {
19+
maxSize, maxVal = dp[i], nums[i]
20+
}
21+
}
22+
if maxSize == 1 {
23+
return []int{nums[0]}
24+
}
25+
for i := len(nums) - 1; i >= 0 && maxSize > 0; i-- {
26+
if dp[i] == maxSize && maxVal%nums[i] == 0 {
27+
res = append(res, nums[i])
28+
maxVal = nums[i]
29+
maxSize--
30+
}
31+
}
32+
return res
33+
}

‎leetcode/0368.Largest-Divisible-Subset/368. Largest Divisible Subset_test.go

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question368 struct {
9+
para368
10+
ans368
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para368 struct {
16+
one []int
17+
}
18+
19+
// ans 是答案
20+
// one 代表第一个答案
21+
type ans368 struct {
22+
one []int
23+
}
24+
25+
func Test_Problem368(t *testing.T) {
26+
27+
qs := []question368{
28+
29+
{
30+
para368{[]int{1, 2, 3}},
31+
ans368{[]int{1, 2}},
32+
},
33+
34+
{
35+
para368{[]int{1, 2, 4, 8}},
36+
ans368{[]int{1, 2, 4, 8}},
37+
},
38+
}
39+
40+
fmt.Printf("------------------------Leetcode Problem 368------------------------\n")
41+
42+
for _, q := range qs {
43+
_, p := q.ans368, q.para368
44+
fmt.Printf("【input】:%v 【output】:%v\n", p, largestDivisibleSubset(p.one))
45+
}
46+
fmt.Printf("\n\n\n")
47+
}

‎leetcode/0368.Largest-Divisible-Subset/README.md

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
# [368. Largest Divisible Subset](https://leetcode.com/problems/largest-divisible-subset/)
2+
3+
4+
## 题目
5+
6+
Given a set of **distinct** positive integers `nums`, return the largest subset `answer` such that every pair `(answer[i], answer[j])` of elements in this subset satisfies:
7+
8+
- `answer[i] % answer[j] == 0`, or
9+
- `answer[j] % answer[i] == 0`
10+
11+
If there are multiple solutions, return any of them.
12+
13+
**Example 1:**
14+
15+
```
16+
Input: nums = [1,2,3]
17+
Output: [1,2]
18+
Explanation: [1,3] is also accepted.
19+
20+
```
21+
22+
**Example 2:**
23+
24+
```
25+
Input: nums = [1,2,4,8]
26+
Output: [1,2,4,8]
27+
28+
```
29+
30+
**Constraints:**
31+
32+
- `1 <= nums.length <= 1000`
33+
- `1 <= nums[i] <= 2 * 109`
34+
- All the integers in `nums` are **unique**.
35+
36+
## 题目大意
37+
38+
给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
39+
40+
- answer[i] % answer[j] == 0 ，或
41+
- answer[j] % answer[i] == 0
42+
43+
如果存在多个有效解子集，返回其中任何一个均可。
44+
45+
## 解题思路
46+
47+
- 根据题目数据规模 1000，可以估计此题大概率是动态规划，并且时间复杂度是 O(n^2)。先将集合排序，以某一个小的数作为基准，不断的选择能整除的数加入集合。按照这个思路考虑，此题和第 300 题经典的 LIS 解题思路一致。只不过 LIS 每次选择更大的数，此题除了选择更大的数，只不过多了一个判断，这个更大的数能否整除当前集合里面的所有元素。按照此法一定可以找出最大的集合。
48+
- 剩下的问题是如何输出最大集合。这道题的集合具有重叠子集的性质，例如 [2,4,8,16] 这个集合，长度是 4，它一定包含长度为 3 的子集，因为从它里面随便取 3 个数形成的子集也满足元素相互能整除的条件。同理，它也一定包含长度为 2，长度为 1 的子集。由于有这个性质，可以利用 dp 数组里面的数据，输出最大集合。例如，[2,4,6,8,9,13,16,40]，由动态规划可以找到最大集合是 [2,4,8,16]。长度为 4 的找到了，再找长度为 3 的，[2,4,8]，[2,4,40]。在最大集合中，最大元素是 16，所以 [2,4,40] 这个集合排除，它的最大元素大于 16。选定 [2,4,8] 这个集合，此时最大元素是 8 。以此类推，筛选到最后，便可以输出 [16,8,4,2] 这个组最大集合的答案了。
49+
50+
## 代码
51+
52+
```go
53+
package leetcode
54+
55+
import "sort"
56+
57+
func largestDivisibleSubset(nums []int) []int {
58+
sort.Ints(nums)
59+
dp, res := make([]int, len(nums)), []int{}
60+
for i := range dp {
61+
dp[i] = 1
62+
}
63+
maxSize, maxVal := 1, 1
64+
for i := 1; i < len(nums); i++ {
65+
for j, v := range nums[:i] {
66+
if nums[i]%v == 0 && dp[j]+1 > dp[i] {
67+
dp[i] = dp[j] + 1
68+
}
69+
}
70+
if dp[i] > maxSize {
71+
maxSize, maxVal = dp[i], nums[i]
72+
}
73+
}
74+
if maxSize == 1 {
75+
return []int{nums[0]}
76+
}
77+
for i := len(nums) - 1; i >= 0 && maxSize > 0; i-- {
78+
if dp[i] == maxSize && maxVal%nums[i] == 0 {
79+
res = append(res, nums[i])
80+
maxVal = nums[i]
81+
maxSize--
82+
}
83+
}
84+
return res
85+
}
86+
```

‎leetcode/9990377.Combination-Sum-IV/377. Combination Sum IV.go renamed to ‎leetcode/0377.Combination-Sum-IV/377. Combination Sum IV.go

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,20 @@
11
package leetcode
22

33
func combinationSum4(nums []int, target int) int {
4+
dp := make([]int, target+1)
5+
dp[0] = 1
6+
for i := 1; i <= target; i++ {
7+
for _, num := range nums {
8+
if i-num >= 0 {
9+
dp[i] += dp[i-num]
10+
}
11+
}
12+
}
13+
return dp[target]
14+
}
15+
16+
// 暴力解法超时
17+
func combinationSum41(nums []int, target int) int {
418
if len(nums) == 0 {
519
return 0
620
}

‎leetcode/9990377.Combination-Sum-IV/377. Combination Sum IV_test.go renamed to ‎leetcode/0377.Combination-Sum-IV/377. Combination Sum IV_test.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@ func Test_Problem377(t *testing.T) {
3434

3535
{
3636
para377{[]int{1, 2, 3}, 32},
37-
ans377{7},
37+
ans377{181997601},
3838
},
3939
}
4040

‎leetcode/0377.Combination-Sum-IV/README.md

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
# [377. Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/)
2+
3+
4+
## 题目
5+
6+
Given an array of **distinct** integers `nums` and a target integer `target`, return *the number of possible combinations that add up to* `target`.
7+
8+
The answer is **guaranteed** to fit in a **32-bit** integer.
9+
10+
**Example 1:**
11+
12+
```
13+
Input: nums = [1,2,3], target = 4
14+
Output: 7
15+
Explanation:
16+
The possible combination ways are:
17+
(1, 1, 1, 1)
18+
(1, 1, 2)
19+
(1, 2, 1)
20+
(1, 3)
21+
(2, 1, 1)
22+
(2, 2)
23+
(3, 1)
24+
Note that different sequences are counted as different combinations.
25+
26+
```
27+
28+
**Example 2:**
29+
30+
```
31+
Input: nums = [9], target = 3
32+
Output: 0
33+
```
34+
35+
**Constraints:**
36+
37+
- `1 <= nums.length <= 200`
38+
- `1 <= nums[i] <= 1000`
39+
- All the elements of `nums` are **unique**.
40+
- `1 <= target <= 1000`
41+
42+
**Follow up:** What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
43+
44+
## 题目大意
45+
46+
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。
47+
48+
## 解题思路
49+
50+
- Combination Sum 这是系列问题。拿到题目，笔者先用暴力解法 dfs 尝试了一版，包含的重叠子问题特别多，剪枝条件也没有写好，果然超时。元素只有 [1,2,3] 这三种，target = 32，这组数据居然有 181997601 这么多种情况。仔细看了题目数据规模 1000，基本可以断定此题是动态规划，并且时间复杂度是 O(n^2)。
51+
- 本题和完全背包有点像，但是还是有区别。完全背包的取法内部不区分顺序。例如 5 = 1 + 2 + 2。但是本题是 3 种答案 (1，2，2)，(2，1，2)，(2，2，1)。定义 dp[i] 为总和为 target = i 的组合总数。最终答案存在 dp[target] 中。状态转移方程为：
52+
53+
$$dp[i] =\left\{\begin{matrix}1,i=0\\ \sum dp[i-j],i\neq 0\end{matrix}\right.$$
54+
55+
- 这道题最后有一个进阶问题。如果给定的数组中含有负数，则会导致出现无限长度的排列。例如，假设数组 nums 中含有正整数 a 和负整数 −b（其中 a>0,b>0,-b<0），则有 a×b+(−b)×a=0，对于任意一个元素之和等于 target 的排列，在该排列的后面添加 b 个 a 和 a 个 −b 之后，得到的新排列的元素之和仍然等于 target，而且还可以在新排列的后面继续 b 个 a 和 a 个 −b。因此只要存在元素之和等于 target 的排列，就能构造出无限长度的排列。如果允许负数出现，则必须限制排列的最大长度，不然会出现无限长度的排列。
56+
57+
## 代码
58+
59+
```go
60+
package leetcode
61+
62+
func combinationSum4(nums []int, target int) int {
63+
dp := make([]int, target+1)
64+
dp[0] = 1
65+
for i := 1; i <= target; i++ {
66+
for _, num := range nums {
67+
if i-num >= 0 {
68+
dp[i] += dp[i-num]
69+
}
70+
}
71+
}
72+
return dp[target]
73+
}
74+
75+
// 暴力解法超时
76+
func combinationSum41(nums []int, target int) int {
77+
if len(nums) == 0 {
78+
return 0
79+
}
80+
c, res := []int{}, 0
81+
findcombinationSum4(nums, target, 0, c, &res)
82+
return res
83+
}
84+
85+
func findcombinationSum4(nums []int, target, index int, c []int, res *int) {
86+
if target <= 0 {
87+
if target == 0 {
88+
*res++
89+
}
90+
return
91+
}
92+
for i := 0; i < len(nums); i++ {
93+
c = append(c, nums[i])
94+
findcombinationSum4(nums, target-nums[i], i, c, res)
95+
c = c[:len(c)-1]
96+
}
97+
}
98+
```

‎leetcode/0696.Count-Binary-Substrings/696. Count Binary Substrings.go

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package leetcode
2+
3+
func countBinarySubstrings(s string) int {
4+
last, res := 0, 0
5+
for i := 0; i < len(s); {
6+
c, count := s[i], 1
7+
for i++; i < len(s) && s[i] == c; i++ {
8+
count++
9+
}
10+
res += min(count, last)
11+
last = count
12+
}
13+
return res
14+
}
15+
16+
func min(a, b int) int {
17+
if a < b {
18+
return a
19+
}
20+
return b
21+
}

‎leetcode/0696.Count-Binary-Substrings/696. Count Binary Substrings_test.go

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question696 struct {
9+
para696
10+
ans696
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para696 struct {
16+
one string
17+
}
18+
19+
// ans 是答案
20+
// one 代表第一个答案
21+
type ans696 struct {
22+
one int
23+
}
24+
25+
func Test_Problem696(t *testing.T) {
26+
27+
qs := []question696{
28+
29+
{
30+
para696{"00110011"},
31+
ans696{6},
32+
},
33+
34+
{
35+
para696{"10101"},
36+
ans696{4},
37+
},
38+
39+
{
40+
para696{"0110001111"},
41+
ans696{6},
42+
},
43+
44+
{
45+
para696{"0001111"},
46+
ans696{3},
47+
},
48+
}
49+
50+
fmt.Printf("------------------------Leetcode Problem 696------------------------\n")
51+
52+
for _, q := range qs {
53+
_, p := q.ans696, q.para696
54+
fmt.Printf("【input】:%v 【output】:%v\n", p, countBinarySubstrings(p.one))
55+
}
56+
fmt.Printf("\n\n\n")
57+
}

0 commit comments

Comments
 (0)