Skip to content

Commit c35405a

Browse files
6boris6boris
authored
Merge pull request 6boris#77 from saenaii/develop
Develop
2 parents a99b26b + d6aaf42 commit c35405a

File tree

8 files changed

+294
-55
lines changed

8 files changed

+294
-55
lines changed

‎src/0061.Rotate-List/ListNode.go

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package Solution
2+
3+
import (
4+
"fmt"
5+
"math/rand"
6+
)
7+
8+
type ListNode struct {
9+
Val int
10+
Next *ListNode
11+
}
12+
13+
// 比较结果
14+
func isEqual(l1 *ListNode, l2 *ListNode) bool {
15+
16+
for l1 != nil && l2 != nil {
17+
if l1.Val != l2.Val {
18+
return false
19+
}
20+
l1 = l1.Next
21+
l2 = l2.Next
22+
}
23+
if l1 == nil && l2 != nil {
24+
return false
25+
}
26+
if l1 != nil && l2 == nil {
27+
return false
28+
}
29+
return true
30+
}
31+
32+
func PrintList(head *ListNode) {
33+
for head != nil {
34+
fmt.Print(head.Val, "->")
35+
head = head.Next
36+
}
37+
fmt.Println()
38+
}
39+
40+
// 根据数组反序列化链表
41+
func UnmarshalListBySlice(nums []int) *ListNode {
42+
head := &ListNode{Val: -1, Next: nil}
43+
tmp := head
44+
for _, v := range nums {
45+
tmp.Next = &ListNode{Val: v, Next: nil}
46+
tmp = tmp.Next
47+
}
48+
return head.Next
49+
}
50+
51+
// 随机初始化链表
52+
func UnmarshalListByRand(max_num int, len int) *ListNode {
53+
head := &ListNode{Val: -1, Next: nil}
54+
tmp := head
55+
56+
for i := 0; i < len; i++ {
57+
tmp.Next = &ListNode{Val: rand.Intn(max_num), Next: nil}
58+
tmp = tmp.Next
59+
}
60+
return head.Next
61+
}

‎src/0061.Rotate-List/README.md

Lines changed: 58 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,48 +1,87 @@
1-
# [1. Add Sum][title]
1+
# [61. Rotate List][title]
22

33
## Description
44

5-
Given two binary strings, return their sum (also a binary string).
6-
7-
The input strings are both **non-empty** and contains only characters `1` or `0`.
5+
Given a linked list, rotate the list to the right by k places, where k is non-negative.
86

97
**Example 1:**
108

119
```
12-
Input: a = "11", b = "1"
13-
Output: "100"
10+
Input: 1->2->3->4->5->NULL, k = 2
11+
Output: 4->5->1->2->3->NULL
12+
Explanation:
13+
rotate 1 steps to the right: 5->1->2->3->4->NULL
14+
rotate 2 steps to the right: 4->5->1->2->3->NULL
1415
```
1516

1617
**Example 2:**
1718

1819
```
19-
Input: a = "1010", b = "1011"
20-
Output: "10101"
20+
Input: 0->1->2->NULL, k = 4
21+
Output: 2->0->1->NULL
22+
Explanation:
23+
rotate 1 steps to the right: 2->0->1->NULL
24+
rotate 2 steps to the right: 1->2->0->NULL
25+
rotate 3 steps to the right: 0->1->2->NULL
26+
rotate 4 steps to the right: 2->0->1->NULL
2127
```
2228

23-
**Tags:** Math, String
29+
**Tags:** Linked List
2430

2531
## 题意
26-
>给你两个二进制串，求其和的二进制串。
32+
> 给定一个链表和一个数字，将单链表向右移动 k 位。
2733
2834
## 题解
2935

3036
### 思路1
31-
> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
32-
33-
```go
37+
1. 先计算出链表的长度，判断 k 是否大于链表的长度。
38+
1. 如果 k 大于链表的长度，取 k = k % len(LinkedList)
39+
1. 将链表变为环形链表。
40+
1. 移动 length - k - 1 位，然后断开链表。
3441

35-
```
36-
37-
### 思路2
38-
> 思路2
3942
```go
40-
43+
/*
44+
* @lc app=leetcode id=61 lang=golang
45+
*
46+
* [61] Rotate List
47+
*/
48+
/**
49+
* Definition for singly-linked list.
50+
* type ListNode struct {
51+
* Val int
52+
* Next *ListNode
53+
* }
54+
*/
55+
func rotateRight(head *ListNode, k int) *ListNode {
56+
if nil == head || 0 == k {
57+
return head
58+
}
59+
head, length := cycleList(head)
60+
if k >= length {
61+
k = k % length
62+
}
63+
for i := 0; i < length - k - 1; i++ {
64+
head = head.Next
65+
}
66+
p := head.Next
67+
head.Next = nil
68+
return p
69+
}
70+
71+
func cycleList(l *ListNode) (*ListNode, int) {
72+
head, length := l, 1
73+
for l.Next != nil {
74+
l = l.Next
75+
length++
76+
}
77+
l.Next = head
78+
return head, length
79+
}
4180
```
4281

4382
## 结语
4483

4584
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
4685

47-
[title]: https://leetcode.com/problems/two-sum/description/
86+
[title]: https://leetcode.com/problems/rotate-list/description/
4887
[me]: https://github.com/kylesliu/awesome-golang-leetcode

‎src/0061.Rotate-List/Solution.go

Lines changed: 24 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,27 @@
11
package Solution
22

3-
func Solution(x bool) bool {
4-
return x
3+
func Solution(head *ListNode, k int) *ListNode {
4+
if nil == head || 0 == k {
5+
return head
6+
}
7+
head, length := cycleList(head)
8+
if k >= length {
9+
k = k % length
10+
}
11+
for i := 0; i < length - k - 1; i++ {
12+
head = head.Next
13+
}
14+
p := head.Next
15+
head.Next = nil
16+
return p
517
}
18+
19+
func cycleList(l *ListNode) (*ListNode, int) {
20+
head, length := l, 1
21+
for l.Next != nil {
22+
l = l.Next
23+
length++
24+
}
25+
l.Next = head
26+
return head, length
27+
}

‎src/0061.Rotate-List/Solution_test.go

Lines changed: 29 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,29 +1,48 @@
11
package Solution
22

33
import (
4-
"reflect"
54
"testing"
65
)
76

7+
type InputCase struct {
8+
element []int
9+
k int
10+
}
11+
812
func TestSolution(t *testing.T) {
913
// 测试用例
1014
cases := []struct {
1115
name string
12-
inputs bool
13-
expect bool
16+
inputs InputCase
17+
expect []int
1418
}{
15-
{"TestCacse 1", true, true},
16-
{"TestCacse 1", true, true},
17-
{"TestCacse 1", false, false},
19+
{
20+
"TestCase 1",
21+
InputCase{
22+
[]int{1,2,3,4,5},
23+
2,
24+
},
25+
[]int{4,5,1,2,3},
26+
},
27+
{
28+
"TestCase 2",
29+
InputCase{
30+
[]int{0, 1, 2},
31+
4,
32+
},
33+
[]int{2, 0, 1},
34+
},
1835
}
1936

2037
// 开始测试
2138
for _, c := range cases {
2239
t.Run(c.name, func(t *testing.T) {
23-
ret := Solution(c.inputs)
24-
if !reflect.DeepEqual(ret, c.expect) {
25-
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
26-
c.expect, ret, c.inputs)
40+
listNode := UnmarshalListBySlice(c.inputs.element)
41+
ret := Solution(listNode, c.inputs.k)
42+
if !isEqual(ret, UnmarshalListBySlice(c.expect)) {
43+
PrintList(ret)
44+
PrintList(UnmarshalListBySlice(c.expect))
45+
t.Fatalf("expected: %v, but got: %v, with inputs: %v", c.expect, ret, c.inputs)
2746
}
2847
})
2948
}

‎src/0082.Remove-Duplicates-from-Sorted-List-II/ListNode.go

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package Solution
2+
3+
import (
4+
"fmt"
5+
"math/rand"
6+
)
7+
8+
type ListNode struct {
9+
Val int
10+
Next *ListNode
11+
}
12+
13+
// 比较结果
14+
func isEqual(l1 *ListNode, l2 *ListNode) bool {
15+
16+
for l1 != nil && l2 != nil {
17+
if l1.Val != l2.Val {
18+
return false
19+
}
20+
l1 = l1.Next
21+
l2 = l2.Next
22+
}
23+
if l1 == nil && l2 != nil {
24+
return false
25+
}
26+
if l1 != nil && l2 == nil {
27+
return false
28+
}
29+
return true
30+
}
31+
32+
func PrintList(head *ListNode) {
33+
for head != nil {
34+
fmt.Print(head.Val, "->")
35+
head = head.Next
36+
}
37+
fmt.Println()
38+
}
39+
40+
// 根据数组反序列化链表
41+
func UnmarshalListBySlice(nums []int) *ListNode {
42+
head := &ListNode{Val: -1, Next: nil}
43+
tmp := head
44+
for _, v := range nums {
45+
tmp.Next = &ListNode{Val: v, Next: nil}
46+
tmp = tmp.Next
47+
}
48+
return head.Next
49+
}
50+
51+
// 随机初始化链表
52+
func UnmarshalListByRand(max_num int, len int) *ListNode {
53+
head := &ListNode{Val: -1, Next: nil}
54+
tmp := head
55+
56+
for i := 0; i < len; i++ {
57+
tmp.Next = &ListNode{Val: rand.Intn(max_num), Next: nil}
58+
tmp = tmp.Next
59+
}
60+
return head.Next
61+
}

‎src/0082.Remove-Duplicates-from-Sorted-List-II/README.md

Lines changed: 11 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,33 @@
1-
# [1. Add Sum][title]
1+
# [82. Remove Duplicates from Sorted List II[title]
22

33
## Description
44

5-
Given two binary strings, return their sum (also a binary string).
6-
7-
The input strings are both **non-empty** and contains only characters `1` or `0`.
5+
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
86

97
**Example 1:**
108

119
```
12-
Input: a = "11", b = "1"
13-
Output: "100"
10+
Input: 1->2->3->3->4->4->5
11+
Output: 1->2->5
1412
```
1513

1614
**Example 2:**
1715

1816
```
19-
Input: a = "1010", b = "1011"
20-
Output: "10101"
17+
Input: 1->1->1->2->3
18+
Output: 2->3
2119
```
2220

23-
**Tags:** Math, String
21+
**Tags:** Linked List
2422

2523
## 题意
26-
>给你两个二进制串，求其和的二进制串。
24+
> 给定一个有序的单链表，删除其中的重复元素。
2725
2826
## 题解
2927

3028
### 思路1
31-
> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
29+
> 使用两个指针，一个指针指向当前元素，另一个指针指向前一个元素。
30+
> 不断判断当前元素和下一个元素是否相等，如果相等，当前元素指向下一个，否则，令前一个指针指向当前节点的下一个节点。
3231
3332
```go
3433

@@ -44,5 +43,5 @@ Output: "10101"
4443

4544
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
4645

47-
[title]: https://leetcode.com/problems/two-sum/description/
46+
[title]: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/
4847
[me]: https://github.com/kylesliu/awesome-golang-leetcode

0 commit comments

Comments
 (0)