Skip to content

Commit e631cba

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lc problems: No.3062,3063 (doocs#2391)
* No.3062.Winner of the Linked List Game * No.3063.Linked List Frequency
1 parent c285f5f commit e631cba

File tree

17 files changed

+726
-18
lines changed

17 files changed

+726
-18
lines changed

‎solution/3000-3099/3061.Calculate Trapping Rain Water/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -56,7 +56,7 @@ Heights table:
5656
| 6 |
5757
+---------------------+
5858
<strong>Explanation:</strong>
59-
<img src="https://assets.leetcode.com/uploads/2024/02/26/trapping_rain_water.png" style="width:500px; height:200px;" />
59+
<img src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3000-3099/3061.Calculate%20Trapping%20Rain%20Water/images/trapping_rain_water.png" style="width:500px; height:200px;" />
6060

6161
The elevation map depicted above (in the black section) is graphically represented with the x-axis denoting the id and the y-axis representing the heights [0,1,0,2,1,0,1,3,2,1,2,1]. In this scenario, 6 units of rainwater are trapped within the blue section.
6262
</pre>

‎solution/3000-3099/3061.Calculate Trapping Rain Water/README_EN.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -54,7 +54,7 @@ Heights table:
5454
| 6 |
5555
+---------------------+
5656
<strong>Explanation:</strong>
57-
<img src="https://assets.leetcode.com/uploads/2024/02/26/trapping_rain_water.png" style="width:500px; height:200px;" />
57+
<img src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3000-3099/3061.Calculate%20Trapping%20Rain%20Water/images/trapping_rain_water.png" style="width:500px; height:200px;" />
5858

5959
The elevation map depicted above (in the black section) is graphically represented with the x-axis denoting the id and the y-axis representing the heights [0,1,0,2,1,0,1,3,2,1,2,1]. In this scenario, 6 units of rainwater are trapped within the blue section.
6060
</pre>

‎solution/3000-3099/3061.Calculate Trapping Rain Water/images/trapping_rain_water.png

22.3 KB
Loading

‎solution/3000-3099/3062.Winner of the Linked List Game/README.md

Lines changed: 136 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -87,24 +87,156 @@
8787

8888
## 解法
8989

90-
### 方法一
90+
### 方法一：模拟
91+
92+
遍历链表，每次取出两个节点，比较它们的值，然后根据比较结果更新奇数和偶数的得分。最后比较奇数和偶数的得分，返回结果。
93+
94+
时间复杂度 $O(n)$，其中 $n$ 是链表的长度。空间复杂度 $O(1)$。
9195

9296
<!-- tabs:start -->
9397

9498
```python
95-
99+
# Definition for singly-linked list.
100+
# class ListNode:
101+
# def __init__(self, val=0, next=None):
102+
# self.val = val
103+
# self.next = next
104+
class Solution:
105+
def gameResult(self, head: Optional[ListNode]) -> str:
106+
odd = even = 0
107+
while head:
108+
a = head.val
109+
b = head.next.val
110+
odd += a < b
111+
even += a > b
112+
head = head.next.next
113+
if odd > even:
114+
return "Odd"
115+
if odd < even:
116+
return "Even"
117+
return "Tie"
96118
```
97119

98120
```java
99-
121+
/**
122+
* Definition for singly-linked list.
123+
* public class ListNode {
124+
* int val;
125+
* ListNode next;
126+
* ListNode() {}
127+
* ListNode(int val) { this.val = val; }
128+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
129+
* }
130+
*/
131+
class Solution {
132+
public String gameResult(ListNode head) {
133+
int odd = 0, even = 0;
134+
for (; head != null; head = head.next.next) {
135+
int a = head.val;
136+
int b = head.next.val;
137+
odd += a < b ? 1 : 0;
138+
even += a > b ? 1 : 0;
139+
}
140+
if (odd > even) {
141+
return "Odd";
142+
}
143+
if (odd < even) {
144+
return "Even";
145+
}
146+
return "Tie";
147+
}
148+
}
100149
```
101150

102151
```cpp
103-
152+
/**
153+
* Definition for singly-linked list.
154+
* struct ListNode {
155+
* int val;
156+
* ListNode *next;
157+
* ListNode() : val(0), next(nullptr) {}
158+
* ListNode(int x) : val(x), next(nullptr) {}
159+
* ListNode(int x, ListNode *next) : val(x), next(next) {}
160+
* };
161+
*/
162+
class Solution {
163+
public:
164+
string gameResult(ListNode* head) {
165+
int odd = 0, even = 0;
166+
for (; head != nullptr; head = head->next->next) {
167+
int a = head->val;
168+
int b = head->next->val;
169+
odd += a < b;
170+
even += a > b;
171+
}
172+
if (odd > even) {
173+
return "Odd";
174+
}
175+
if (odd < even) {
176+
return "Even";
177+
}
178+
return "Tie";
179+
}
180+
};
104181
```
105182
106183
```go
184+
/**
185+
* Definition for singly-linked list.
186+
* type ListNode struct {
187+
* Val int
188+
* Next *ListNode
189+
* }
190+
*/
191+
func gameResult(head *ListNode) string {
192+
var odd, even int
193+
for ; head != nil; head = head.Next.Next {
194+
a, b := head.Val, head.Next.Val
195+
if a < b {
196+
odd++
197+
}
198+
if a > b {
199+
even++
200+
}
201+
}
202+
if odd > even {
203+
return "Odd"
204+
}
205+
if odd < even {
206+
return "Even"
207+
}
208+
return "Tie"
209+
}
210+
```
107211

212+
```ts
213+
/**
214+
* Definition for singly-linked list.
215+
* class ListNode {
216+
* val: number
217+
* next: ListNode | null
218+
* constructor(val?: number, next?: ListNode | null) {
219+
* this.val = (val===undefined ? 0 : val)
220+
* this.next = (next===undefined ? null : next)
221+
* }
222+
* }
223+
*/
224+
225+
function gameResult(head: ListNode | null): string {
226+
let [odd, even] = [0, 0];
227+
for (; head; head = head.next.next) {
228+
const [a, b] = [head.val, head.next.val];
229+
odd += a < b ? 1 : 0;
230+
even += a > b ? 1 : 0;
231+
}
232+
if (odd > even) {
233+
return 'Odd';
234+
}
235+
if (odd < even) {
236+
return 'Even';
237+
}
238+
return 'Tie';
239+
}
108240
```
109241

110242
<!-- tabs:end -->

‎solution/3000-3099/3062.Winner of the Linked List Game/README_EN.md

Lines changed: 136 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -85,24 +85,156 @@
8585

8686
## Solutions
8787

88-
### Solution 1
88+
### Solution 1: Simulation
89+
90+
Traverse the linked list, each time taking out two nodes, compare their values, and then update the scores of odd and even numbers based on the comparison results. Finally, compare the scores of odd and even numbers and return the result.
91+
92+
The time complexity is $O(n)$, where $n$ is the length of the linked list. The space complexity is $O(1)$.
8993

9094
<!-- tabs:start -->
9195

9296
```python
93-
97+
# Definition for singly-linked list.
98+
# class ListNode:
99+
# def __init__(self, val=0, next=None):
100+
# self.val = val
101+
# self.next = next
102+
class Solution:
103+
def gameResult(self, head: Optional[ListNode]) -> str:
104+
odd = even = 0
105+
while head:
106+
a = head.val
107+
b = head.next.val
108+
odd += a < b
109+
even += a > b
110+
head = head.next.next
111+
if odd > even:
112+
return "Odd"
113+
if odd < even:
114+
return "Even"
115+
return "Tie"
94116
```
95117

96118
```java
97-
119+
/**
120+
* Definition for singly-linked list.
121+
* public class ListNode {
122+
* int val;
123+
* ListNode next;
124+
* ListNode() {}
125+
* ListNode(int val) { this.val = val; }
126+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
127+
* }
128+
*/
129+
class Solution {
130+
public String gameResult(ListNode head) {
131+
int odd = 0, even = 0;
132+
for (; head != null; head = head.next.next) {
133+
int a = head.val;
134+
int b = head.next.val;
135+
odd += a < b ? 1 : 0;
136+
even += a > b ? 1 : 0;
137+
}
138+
if (odd > even) {
139+
return "Odd";
140+
}
141+
if (odd < even) {
142+
return "Even";
143+
}
144+
return "Tie";
145+
}
146+
}
98147
```
99148

100149
```cpp
101-
150+
/**
151+
* Definition for singly-linked list.
152+
* struct ListNode {
153+
* int val;
154+
* ListNode *next;
155+
* ListNode() : val(0), next(nullptr) {}
156+
* ListNode(int x) : val(x), next(nullptr) {}
157+
* ListNode(int x, ListNode *next) : val(x), next(next) {}
158+
* };
159+
*/
160+
class Solution {
161+
public:
162+
string gameResult(ListNode* head) {
163+
int odd = 0, even = 0;
164+
for (; head != nullptr; head = head->next->next) {
165+
int a = head->val;
166+
int b = head->next->val;
167+
odd += a < b;
168+
even += a > b;
169+
}
170+
if (odd > even) {
171+
return "Odd";
172+
}
173+
if (odd < even) {
174+
return "Even";
175+
}
176+
return "Tie";
177+
}
178+
};
102179
```
103180
104181
```go
182+
/**
183+
* Definition for singly-linked list.
184+
* type ListNode struct {
185+
* Val int
186+
* Next *ListNode
187+
* }
188+
*/
189+
func gameResult(head *ListNode) string {
190+
var odd, even int
191+
for ; head != nil; head = head.Next.Next {
192+
a, b := head.Val, head.Next.Val
193+
if a < b {
194+
odd++
195+
}
196+
if a > b {
197+
even++
198+
}
199+
}
200+
if odd > even {
201+
return "Odd"
202+
}
203+
if odd < even {
204+
return "Even"
205+
}
206+
return "Tie"
207+
}
208+
```
105209

210+
```ts
211+
/**
212+
* Definition for singly-linked list.
213+
* class ListNode {
214+
* val: number
215+
* next: ListNode | null
216+
* constructor(val?: number, next?: ListNode | null) {
217+
* this.val = (val===undefined ? 0 : val)
218+
* this.next = (next===undefined ? null : next)
219+
* }
220+
* }
221+
*/
222+
223+
function gameResult(head: ListNode | null): string {
224+
let [odd, even] = [0, 0];
225+
for (; head; head = head.next.next) {
226+
const [a, b] = [head.val, head.next.val];
227+
odd += a < b ? 1 : 0;
228+
even += a > b ? 1 : 0;
229+
}
230+
if (odd > even) {
231+
return 'Odd';
232+
}
233+
if (odd < even) {
234+
return 'Even';
235+
}
236+
return 'Tie';
237+
}
106238
```
107239

108240
<!-- tabs:end -->

‎solution/3000-3099/3062.Winner of the Linked List Game/Solution.cpp

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* struct ListNode {
4+
* int val;
5+
* ListNode *next;
6+
* ListNode() : val(0), next(nullptr) {}
7+
* ListNode(int x) : val(x), next(nullptr) {}
8+
* ListNode(int x, ListNode *next) : val(x), next(next) {}
9+
* };
10+
*/
11+
class Solution {
12+
public:
13+
string gameResult(ListNode* head) {
14+
int odd = 0, even = 0;
15+
for (; head != nullptr; head = head->next->next) {
16+
int a = head->val;
17+
int b = head->next->val;
18+
odd += a < b;
19+
even += a > b;
20+
}
21+
if (odd > even) {
22+
return "Odd";
23+
}
24+
if (odd < even) {
25+
return "Even";
26+
}
27+
return "Tie";
28+
}
29+
};

‎solution/3000-3099/3062.Winner of the Linked List Game/Solution.go

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* type ListNode struct {
4+
* Val int
5+
* Next *ListNode
6+
* }
7+
*/
8+
func gameResult(head *ListNode) string {
9+
var odd, even int
10+
for ; head != nil; head = head.Next.Next {
11+
a, b := head.Val, head.Next.Val
12+
if a < b {
13+
odd++
14+
}
15+
if a > b {
16+
even++
17+
}
18+
}
19+
if odd > even {
20+
return "Odd"
21+
}
22+
if odd < even {
23+
return "Even"
24+
}
25+
return "Tie"
26+
}

0 commit comments

Comments
 (0)