Skip to content

Commit 796cccc

Browse files
halfrosthalfrost
committed
Add solution 0382
1 parent 61d7c48 commit 796cccc

File tree

3 files changed

+179
-0
lines changed

3 files changed

+179
-0
lines changed

‎leetcode/0382.Linked-List-Random-Node/382. Linked List Random Node.go

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package leetcode
2+
3+
import (
4+
"math/rand"
5+
6+
"github.com/halfrost/LeetCode-Go/structures"
7+
)
8+
9+
// ListNode define
10+
type ListNode = structures.ListNode
11+
12+
/**
13+
* Definition for singly-linked list.
14+
* type ListNode struct {
15+
* Val int
16+
* Next *ListNode
17+
* }
18+
*/
19+
type Solution struct {
20+
head *ListNode
21+
}
22+
23+
/** @param head The linked list's head.
24+
Note that the head is guaranteed to be not null, so it contains at least one node. */
25+
func Constructor(head *ListNode) Solution {
26+
return Solution{head: head}
27+
}
28+
29+
/** Returns a random node's value. */
30+
func (this *Solution) GetRandom() int {
31+
scope, selectPoint, curr := 1, 0, this.head
32+
for curr != nil {
33+
if rand.Float64() < 1.0/float64(scope) {
34+
selectPoint = curr.Val
35+
}
36+
scope += 1
37+
curr = curr.Next
38+
}
39+
return selectPoint
40+
}
41+
42+
/**
43+
* Your Solution object will be instantiated and called as such:
44+
* obj := Constructor(head);
45+
* param_1 := obj.GetRandom();
46+
*/

‎leetcode/0382.Linked-List-Random-Node/382. Linked List Random Node_test.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
7+
"github.com/halfrost/LeetCode-Go/structures"
8+
)
9+
10+
func Test_Problem382(t *testing.T) {
11+
header := structures.Ints2List([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 0})
12+
obj := Constructor(header)
13+
fmt.Printf("obj = %v\n", structures.List2Ints(header))
14+
param1 := obj.GetRandom()
15+
fmt.Printf("param_1 = %v\n", param1)
16+
param1 = obj.GetRandom()
17+
fmt.Printf("param_1 = %v\n", param1)
18+
param1 = obj.GetRandom()
19+
fmt.Printf("param_1 = %v\n", param1)
20+
param1 = obj.GetRandom()
21+
fmt.Printf("param_1 = %v\n", param1)
22+
param1 = obj.GetRandom()
23+
fmt.Printf("param_1 = %v\n", param1)
24+
param1 = obj.GetRandom()
25+
fmt.Printf("param_1 = %v\n", param1)
26+
27+
fmt.Printf("\n\n\n")
28+
}

‎leetcode/0382.Linked-List-Random-Node/README.md

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
# [382. Linked List Random Node](https://leetcode.com/problems/linked-list-random-node/)
2+
3+
4+
## 题目
5+
6+
Given a singly linked list, return a random node's value from the linked list. Each node must have the **same probability** of being chosen.
7+
8+
Implement the `Solution` class:
9+
10+
- `Solution(ListNode head)` Initializes the object with the integer array nums.
11+
- `int getRandom()` Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen.
12+
13+
**Example 1:**
14+
15+
![https://assets.leetcode.com/uploads/2021/03/16/getrand-linked-list.jpg](https://assets.leetcode.com/uploads/2021/03/16/getrand-linked-list.jpg)
16+
17+
```
18+
Input
19+
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
20+
[[[1, 2, 3]], [], [], [], [], []]
21+
Output
22+
[null, 1, 3, 2, 2, 3]
23+
24+
Explanation
25+
Solution solution = new Solution([1, 2, 3]);
26+
solution.getRandom(); // return 1
27+
solution.getRandom(); // return 3
28+
solution.getRandom(); // return 2
29+
solution.getRandom(); // return 2
30+
solution.getRandom(); // return 3
31+
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
32+
33+
```
34+
35+
**Constraints:**
36+
37+
- The number of nodes in the linked list will be in the range `[1, 104]`.
38+
- `-10^4 <= Node.val <= 10^4`
39+
- At most `10^4` calls will be made to `getRandom`.
40+
41+
**Follow up:**
42+
43+
- What if the linked list is extremely large and its length is unknown to you?
44+
- Could you solve this efficiently without using extra space?
45+
46+
## 题目大意
47+
48+
给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
49+
50+
进阶: 如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
51+
52+
## 解题思路
53+
54+
- rand.Float64() 可以返回 [0.0,1.0) 之间的随机数。利用这个函数完成我们的随机化取节点的过程。
55+
56+
## 代码
57+
58+
```go
59+
package leetcode
60+
61+
import (
62+
"math/rand"
63+
64+
"github.com/halfrost/LeetCode-Go/structures"
65+
)
66+
67+
// ListNode define
68+
type ListNode = structures.ListNode
69+
70+
/**
71+
* Definition for singly-linked list.
72+
* type ListNode struct {
73+
* Val int
74+
* Next *ListNode
75+
* }
76+
*/
77+
type Solution struct {
78+
head *ListNode
79+
}
80+
81+
/** @param head The linked list's head.
82+
Note that the head is guaranteed to be not null, so it contains at least one node. */
83+
func Constructor(head *ListNode) Solution {
84+
return Solution{head: head}
85+
}
86+
87+
/** Returns a random node's value. */
88+
func (this *Solution) GetRandom() int {
89+
scope, selectPoint, curr := 1, 0, this.head
90+
for curr != nil {
91+
if rand.Float64() < 1.0/float64(scope) {
92+
selectPoint = curr.Val
93+
}
94+
scope += 1
95+
curr = curr.Next
96+
}
97+
return selectPoint
98+
}
99+
100+
/**
101+
* Your Solution object will be instantiated and called as such:
102+
* obj := Constructor(head);
103+
* param_1 := obj.GetRandom();
104+
*/
105+
```

0 commit comments

Comments
 (0)