Skip to content

Commit e85f323

Browse files
halfrosthalfrost
committed
Add solution 1668、1669、1670、1672、1673
1 parent 2e796fe commit e85f323

30 files changed

+1266
-428
lines changed

‎leetcode/5557.Maximum-Repeating-Substring/5557. Maximum Repeating Substring.go renamed to ‎leetcode/1668.Maximum-Repeating-Substring/1668. Maximum Repeating Substring.go

File renamed without changes.

‎leetcode/5557.Maximum-Repeating-Substring/5557. Maximum Repeating Substring_test.go renamed to ‎leetcode/1668.Maximum-Repeating-Substring/1668. Maximum Repeating Substring_test.go

Lines changed: 15 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -5,48 +5,48 @@ import (
55
"testing"
66
)
77

8-
type question1665 struct {
9-
para1665
10-
ans1665
8+
type question1668 struct {
9+
para1668
10+
ans1668
1111
}
1212

1313
// para 是参数
1414
// one 代表第一个参数
15-
type para1665 struct {
15+
type para1668 struct {
1616
sequence string
1717
word string
1818
}
1919

2020
// ans 是答案
2121
// one 代表第一个答案
22-
type ans1665 struct {
22+
type ans1668 struct {
2323
one int
2424
}
2525

26-
func Test_Problem1665(t *testing.T) {
26+
func Test_Problem1668(t *testing.T) {
2727

28-
qs := []question1665{
28+
qs := []question1668{
2929

3030
{
31-
para1665{"ababc", "ab"},
32-
ans1665{2},
31+
para1668{"ababc", "ab"},
32+
ans1668{2},
3333
},
3434

3535
{
36-
para1665{"ababc", "ba"},
37-
ans1665{1},
36+
para1668{"ababc", "ba"},
37+
ans1668{1},
3838
},
3939

4040
{
41-
para1665{"ababc", "ac"},
42-
ans1665{0},
41+
para1668{"ababc", "ac"},
42+
ans1668{0},
4343
},
4444
}
4545

46-
fmt.Printf("------------------------Leetcode Problem 1665------------------------\n")
46+
fmt.Printf("------------------------Leetcode Problem 1668------------------------\n")
4747

4848
for _, q := range qs {
49-
_, p := q.ans1665, q.para1665
49+
_, p := q.ans1668, q.para1668
5050
fmt.Printf("【input】:%v 【output】:%v \n", p, maxRepeating(p.sequence, p.word))
5151
}
5252
fmt.Printf("\n\n\n")

‎leetcode/1668.Maximum-Repeating-Substring/README.md

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
# [1668. Maximum Repeating Substring](https://leetcode.com/problems/maximum-repeating-substring/)
2+
3+
4+
## 题目
5+
6+
For a string `sequence`, a string `word` is **`k`-repeating** if `word` concatenated `k` times is a substring of `sequence`. The `word`'s **maximum `k`-repeating value** is the highest value `k` where `word` is `k`-repeating in `sequence`. If `word` is not a substring of `sequence`, `word`'s maximum `k`-repeating value is `0`.
7+
8+
Given strings `sequence` and `word`, return *the **maximum `k`-repeating value** of `word` in `sequence`*.
9+
10+
**Example 1:**
11+
12+
```
13+
Input: sequence = "ababc", word = "ab"
14+
Output: 2
15+
Explanation: "abab" is a substring in "ababc".
16+
```
17+
18+
**Example 2:**
19+
20+
```
21+
Input: sequence = "ababc", word = "ba"
22+
Output: 1
23+
Explanation: "ba" is a substring in "ababc". "baba" is not a substring in "ababc".
24+
```
25+
26+
**Example 3:**
27+
28+
```
29+
Input: sequence = "ababc", word = "ac"
30+
Output: 0
31+
Explanation: "ac" is not a substring in "ababc".
32+
```
33+
34+
**Constraints:**
35+
36+
- `1 <= sequence.length <= 100`
37+
- `1 <= word.length <= 100`
38+
- `sequence` and `word` contains only lowercase English letters.
39+
40+
## 题目大意
41+
42+
给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的 重复值为 k 。单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值。如果 word 不是 sequence 的子串，那么重复值 k 为 0 。给你一个字符串 sequence 和 word ，请你返回 最大重复值 k 。
43+
44+
## 解题思路
45+
46+
- 循环叠加构造 `word`，每次构造出新的 `word` 都在 `sequence` 查找一次，如果找到就输出叠加次数，否则继续叠加构造，直到字符串长度和 `sequence` 一样长，最终都没有找到则输出 0 。
47+
48+
## 代码
49+
50+
```go
51+
package leetcode
52+
53+
import (
54+
"strings"
55+
)
56+
57+
func maxRepeating(sequence string, word string) int {
58+
for i := len(sequence) / len(word); i >= 0; i-- {
59+
tmp := ""
60+
for j := 0; j < i; j++ {
61+
tmp += word
62+
}
63+
if strings.Contains(sequence, tmp) {
64+
return i
65+
}
66+
}
67+
return 0
68+
}
69+
```

‎leetcode/1669.Merge-In-Between-Linked-Lists/1669. Merge In Between Linked Lists.go

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package leetcode
2+
3+
import (
4+
"github.com/halfrost/LeetCode-Go/structures"
5+
)
6+
7+
// ListNode define
8+
type ListNode = structures.ListNode
9+
10+
/**
11+
* Definition for singly-linked list.
12+
* type ListNode struct {
13+
* Val int
14+
* Next *ListNode
15+
* }
16+
*/
17+
18+
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
19+
n := list1
20+
var startRef, endRef *ListNode
21+
for i := 0; i <= b; i++ {
22+
if i == a-1 {
23+
startRef = n
24+
}
25+
if i == b {
26+
endRef = n
27+
}
28+
n = n.Next
29+
}
30+
startRef.Next = list2
31+
n = list2
32+
for n.Next != nil {
33+
n = n.Next
34+
}
35+
n.Next = endRef.Next
36+
return list1
37+
}

‎leetcode/1669.Merge-In-Between-Linked-Lists/1669. Merge In Between Linked Lists_test.go

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
7+
"github.com/halfrost/LeetCode-Go/structures"
8+
)
9+
10+
type question1669 struct {
11+
para1669
12+
ans1669
13+
}
14+
15+
// para 是参数
16+
// one 代表第一个参数
17+
type para1669 struct {
18+
one []int
19+
a int
20+
b int
21+
another []int
22+
}
23+
24+
// ans 是答案
25+
// one 代表第一个答案
26+
type ans1669 struct {
27+
one []int
28+
}
29+
30+
func Test_Problem1669(t *testing.T) {
31+
32+
qs := []question1669{
33+
34+
{
35+
para1669{[]int{0, 1, 2, 3, 4, 5}, 3, 4, []int{1000000, 1000001, 1000002}},
36+
ans1669{[]int{0, 1, 2, 1000000, 1000001, 1000002, 5}},
37+
},
38+
39+
{
40+
para1669{[]int{0, 1, 2, 3, 4, 5, 6}, 2, 5, []int{1000000, 1000001, 1000002, 1000003, 1000004}},
41+
ans1669{[]int{0, 1, 1000000, 1000001, 1000002, 1000003, 1000004, 6}},
42+
},
43+
44+
{
45+
para1669{[]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 3, 5, []int{1000000, 1000001, 1000002, 1000003, 1000004, 1000005, 1000006}},
46+
ans1669{[]int{0, 1, 2, 1000000, 1000001, 1000002, 1000003, 1000004, 1000005, 1000006, 6, 7, 8, 9}},
47+
},
48+
49+
{
50+
para1669{[]int{0, 1, 2}, 1, 1, []int{1000000, 1000001, 1000002, 1000003}},
51+
ans1669{[]int{0, 1000000, 1000001, 1000002, 1000003, 2}},
52+
},
53+
}
54+
55+
fmt.Printf("------------------------Leetcode Problem 1669------------------------\n")
56+
57+
for _, q := range qs {
58+
_, p := q.ans1669, q.para1669
59+
fmt.Printf("【input】:%v 【output】:%v\n", p, structures.List2Ints(mergeInBetween(structures.Ints2List(p.one), p.a, p.b, structures.Ints2List(p.another))))
60+
}
61+
fmt.Printf("\n\n\n")
62+
}

‎leetcode/1669.Merge-In-Between-Linked-Lists/README.md

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
# [1669. Merge In Between Linked Lists](https://leetcode.com/problems/merge-in-between-linked-lists/)
2+
3+
4+
## 题目
5+
6+
You are given two linked lists: `list1` and `list2` of sizes `n` and `m` respectively.
7+
8+
Remove `list1`'s nodes from the `ath` node to the `bth` node, and put `list2` in their place.
9+
10+
The blue edges and nodes in the following figure incidate the result:
11+
12+
![https://assets.leetcode.com/uploads/2020/11/05/fig1.png](https://assets.leetcode.com/uploads/2020/11/05/fig1.png)
13+
14+
*Build the result list and return its head.*
15+
16+
**Example 1:**
17+
18+
![https://assets.leetcode.com/uploads/2020/11/05/merge_linked_list_ex1.png](https://assets.leetcode.com/uploads/2020/11/05/merge_linked_list_ex1.png)
19+
20+
```
21+
Input: list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
22+
Output: [0,1,2,1000000,1000001,1000002,5]
23+
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.
24+
25+
```
26+
27+
**Example 2:**
28+
29+
![https://assets.leetcode.com/uploads/2020/11/05/merge_linked_list_ex2.png](https://assets.leetcode.com/uploads/2020/11/05/merge_linked_list_ex2.png)
30+
31+
```
32+
Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
33+
Output: [0,1,1000000,1000001,1000002,1000003,1000004,6]
34+
Explanation: The blue edges and nodes in the above figure indicate the result.
35+
36+
```
37+
38+
**Constraints:**
39+
40+
- `3 <= list1.length <= 104`
41+
- `1 <= a <= b < list1.length - 1`
42+
- `1 <= list2.length <= 104`
43+
44+
## 题目大意
45+
46+
给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。请你将 list1 中第 a 个节点到第 b 个节点删除，并将list2 接在被删除节点的位置。
47+
48+
## 解题思路
49+
50+
- 简单题，考查链表的基本操作。此题注意 a == b 的情况。
51+
52+
## 代码
53+
54+
```go
55+
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
56+
n := list1
57+
var startRef, endRef *ListNode
58+
for i := 0; i <= b; i++ {
59+
if i == a-1 {
60+
startRef = n
61+
}
62+
if i == b {
63+
endRef = n
64+
}
65+
n = n.Next
66+
}
67+
startRef.Next = list2
68+
n = list2
69+
for n.Next != nil {
70+
n = n.Next
71+
}
72+
n.Next = endRef.Next
73+
return list1
74+
}
75+
```

0 commit comments

Comments
 (0)