Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc35405a

Browse files
authored
Merge pull request6boris#77 from saenaii/develop
Develop
2 parentsa99b26b +d6aaf42 commitc35405a

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+
typeListNodestruct {
9+
Valint
10+
Next*ListNode
11+
}
12+
13+
//比较结果
14+
funcisEqual(l1*ListNode,l2*ListNode)bool {
15+
16+
forl1!=nil&&l2!=nil {
17+
ifl1.Val!=l2.Val {
18+
returnfalse
19+
}
20+
l1=l1.Next
21+
l2=l2.Next
22+
}
23+
ifl1==nil&&l2!=nil {
24+
returnfalse
25+
}
26+
ifl1!=nil&&l2==nil {
27+
returnfalse
28+
}
29+
returntrue
30+
}
31+
32+
funcPrintList(head*ListNode) {
33+
forhead!=nil {
34+
fmt.Print(head.Val,"->")
35+
head=head.Next
36+
}
37+
fmt.Println()
38+
}
39+
40+
// 根据数组反序列化链表
41+
funcUnmarshalListBySlice(nums []int)*ListNode {
42+
head:=&ListNode{Val:-1,Next:nil}
43+
tmp:=head
44+
for_,v:=rangenums {
45+
tmp.Next=&ListNode{Val:v,Next:nil}
46+
tmp=tmp.Next
47+
}
48+
returnhead.Next
49+
}
50+
51+
// 随机初始化链表
52+
funcUnmarshalListByRand(max_numint,lenint)*ListNode {
53+
head:=&ListNode{Val:-1,Next:nil}
54+
tmp:=head
55+
56+
fori:=0;i<len;i++ {
57+
tmp.Next=&ListNode{Val:rand.Intn(max_num),Next:nil}
58+
tmp=tmp.Next
59+
}
60+
returnhead.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+
funcrotateRight(head *ListNode,kint) *ListNode {
56+
ifnil == head ||0 == k {
57+
return head
58+
}
59+
head,length:=cycleList(head)
60+
if k >= length {
61+
k = k % length
62+
}
63+
fori:=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+
funccycleList(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-
funcSolution(xbool)bool {
4-
returnx
3+
funcSolution(head*ListNode,kint)*ListNode {
4+
ifnil==head||0==k {
5+
returnhead
6+
}
7+
head,length:=cycleList(head)
8+
ifk>=length {
9+
k=k%length
10+
}
11+
fori:=0;i<length-k-1;i++ {
12+
head=head.Next
13+
}
14+
p:=head.Next
15+
head.Next=nil
16+
returnp
517
}
18+
19+
funccycleList(l*ListNode) (*ListNode,int) {
20+
head,length:=l,1
21+
forl.Next!=nil {
22+
l=l.Next
23+
length++
24+
}
25+
l.Next=head
26+
returnhead,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+
typeInputCasestruct {
8+
element []int
9+
kint
10+
}
11+
812
funcTestSolution(t*testing.T) {
913
//测试用例
1014
cases:= []struct {
1115
namestring
12-
inputsbool
13-
expectbool
16+
inputsInputCase
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:=rangecases {
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
}
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+
typeListNodestruct {
9+
Valint
10+
Next*ListNode
11+
}
12+
13+
//比较结果
14+
funcisEqual(l1*ListNode,l2*ListNode)bool {
15+
16+
forl1!=nil&&l2!=nil {
17+
ifl1.Val!=l2.Val {
18+
returnfalse
19+
}
20+
l1=l1.Next
21+
l2=l2.Next
22+
}
23+
ifl1==nil&&l2!=nil {
24+
returnfalse
25+
}
26+
ifl1!=nil&&l2==nil {
27+
returnfalse
28+
}
29+
returntrue
30+
}
31+
32+
funcPrintList(head*ListNode) {
33+
forhead!=nil {
34+
fmt.Print(head.Val,"->")
35+
head=head.Next
36+
}
37+
fmt.Println()
38+
}
39+
40+
// 根据数组反序列化链表
41+
funcUnmarshalListBySlice(nums []int)*ListNode {
42+
head:=&ListNode{Val:-1,Next:nil}
43+
tmp:=head
44+
for_,v:=rangenums {
45+
tmp.Next=&ListNode{Val:v,Next:nil}
46+
tmp=tmp.Next
47+
}
48+
returnhead.Next
49+
}
50+
51+
// 随机初始化链表
52+
funcUnmarshalListByRand(max_numint,lenint)*ListNode {
53+
head:=&ListNode{Val:-1,Next:nil}
54+
tmp:=head
55+
56+
fori:=0;i<len;i++ {
57+
tmp.Next=&ListNode{Val:rand.Intn(max_num),Next:nil}
58+
tmp=tmp.Next
59+
}
60+
returnhead.Next
61+
}
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)
[8]ページ先頭
©2009-2025 Movatter.jp