Skip to content

Commit 0482811

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lc problems: No.2357,2358 (#4420)
1 parent 9dbf88f commit 0482811

File tree

7 files changed

+91
-22
lines changed

7 files changed

+91
-22
lines changed

‎solution/2300-2399/2357.Make Array Zero by Subtracting Equal Amounts/README.md

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -69,9 +69,9 @@ tags:
6969

7070
### 方法一：哈希表或数组
7171

72-
我们观察到，每一次操作，都可以把数组 `nums` 中相同且非零的元素减少到 $0$，因此，我们只需要统计数组 `nums` 中有多少个不同的非零元素，即为最少操作数。统计不同的非零元素，可以使用哈希表或数组来实现。
72+
我们观察到，每一次操作，都可以把数组 $\textit{nums}$ 中相同且非零的元素减少到 $0$，因此，我们只需要统计数组 $\textit{nums}$ 中有多少个不同的非零元素，即为最少操作数。统计不同的非零元素，可以使用哈希表或数组来实现。
7373

74-
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。
74+
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\textit{nums}$ 的长度。
7575

7676
<!-- tabs:start -->
7777

@@ -141,9 +141,9 @@ func minimumOperations(nums []int) (ans int) {
141141

142142
```ts
143143
function minimumOperations(nums: number[]): number {
144-
const set = new Set(nums);
145-
set.delete(0);
146-
return set.size;
144+
const s = new Set(nums);
145+
s.delete(0);
146+
return s.size;
147147
}
148148
```
149149

@@ -153,9 +153,9 @@ function minimumOperations(nums: number[]): number {
153153
use std::collections::HashSet;
154154
impl Solution {
155155
pub fn minimum_operations(nums: Vec<i32>) -> i32 {
156-
let mut set = nums.iter().collect::<HashSet<&i32>>();
157-
set.remove(&0);
158-
set.len() as i32
156+
let mut s = nums.iter().collect::<HashSet<&i32>>();
157+
s.remove(&0);
158+
s.len() as i32
159159
}
160160
}
161161
```

‎solution/2300-2399/2357.Make Array Zero by Subtracting Equal Amounts/README_EN.md

Lines changed: 11 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -66,7 +66,11 @@ In the third operation, choose x = 2. Now, nums = [0,0,0,0,0].
6666

6767
<!-- solution:start -->
6868

69-
### Solution 1
69+
### Solution 1: Hash Table or Array
70+
71+
We observe that in each operation, all identical nonzero elements in the array $\textit{nums}$ can be reduced to $0$. Therefore, we only need to count the number of distinct nonzero elements in $\textit{nums}$, which is the minimum number of operations required. To count the distinct nonzero elements, we can use a hash table or an array.
72+
73+
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array $\textit{nums}$.
7074

7175
<!-- tabs:start -->
7276

@@ -136,9 +140,9 @@ func minimumOperations(nums []int) (ans int) {
136140

137141
```ts
138142
function minimumOperations(nums: number[]): number {
139-
const set = new Set(nums);
140-
set.delete(0);
141-
return set.size;
143+
const s = new Set(nums);
144+
s.delete(0);
145+
return s.size;
142146
}
143147
```
144148

@@ -148,9 +152,9 @@ function minimumOperations(nums: number[]): number {
148152
use std::collections::HashSet;
149153
impl Solution {
150154
pub fn minimum_operations(nums: Vec<i32>) -> i32 {
151-
let mut set = nums.iter().collect::<HashSet<&i32>>();
152-
set.remove(&0);
153-
set.len() as i32
155+
let mut s = nums.iter().collect::<HashSet<&i32>>();
156+
s.remove(&0);
157+
s.len() as i32
154158
}
155159
}
156160
```

‎solution/2300-2399/2357.Make Array Zero by Subtracting Equal Amounts/Solution.rs

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
11
use std::collections::HashSet;
22
impl Solution {
33
pub fn minimum_operations(nums: Vec<i32>) -> i32 {
4-
let mut set = nums.iter().collect::<HashSet<&i32>>();
5-
set.remove(&0);
6-
set.len() as i32
4+
let mut s = nums.iter().collect::<HashSet<&i32>>();
5+
s.remove(&0);
6+
s.len() as i32
77
}
88
}

‎solution/2300-2399/2357.Make Array Zero by Subtracting Equal Amounts/Solution.ts

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
function minimumOperations(nums: number[]): number {
2-
const set = new Set(nums);
3-
set.delete(0);
4-
return set.size;
2+
const s = new Set(nums);
3+
s.delete(0);
4+
return s.size;
55
}

‎solution/2300-2399/2358.Maximum Number of Groups Entering a Competition/README.md

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -160,6 +160,26 @@ function maximumGroups(grades: number[]): number {
160160
}
161161
```
162162

163+
#### Rust
164+
165+
```rust
166+
impl Solution {
167+
pub fn maximum_groups(grades: Vec<i32>) -> i32 {
168+
let n = grades.len() as i64;
169+
let (mut l, mut r) = (0i64, n);
170+
while l < r {
171+
let mid = (l + r + 1) / 2;
172+
if mid * mid + mid > 2 * n {
173+
r = mid - 1;
174+
} else {
175+
l = mid;
176+
}
177+
}
178+
l as i32
179+
}
180+
}
181+
```
182+
163183
<!-- tabs:end -->
164184

165185
<!-- solution:end -->

‎solution/2300-2399/2358.Maximum Number of Groups Entering a Competition/README_EN.md

Lines changed: 31 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,7 +65,17 @@ It can be shown that it is not possible to form more than 3 groups.
6565

6666
<!-- solution:start -->
6767

68-
### Solution 1
68+
### Solution 1: Greedy + Binary Search
69+
70+
Observing the conditions in the problem, the number of students in the $i$-th group must be less than that in the $(i+1)$-th group, and the total score of students in the $i$-th group must be less than that in the $(i+1)$-th group. We only need to sort the students by their scores in ascending order, and then assign $1$, $2$, ..., $k$ students to each group in order. If the last group does not have enough students for $k$, we can distribute these students to the previous last group.
71+
72+
Therefore, we need to find the largest $k$ such that $\frac{(1 + k) \times k}{2} \leq n$, where $n$ is the total number of students. We can use binary search to solve this.
73+
74+
We define the left boundary of binary search as $l = 1$ and the right boundary as $r = n$. Each time, the midpoint is $mid = \lfloor \frac{l + r + 1}{2} \rfloor$. If $(1 + mid) \times mid \gt 2 \times n$, it means $mid$ is too large, so we shrink the right boundary to $mid - 1$; otherwise, we increase the left boundary to $mid$.
75+
76+
Finally, we return $l$ as the answer.
77+
78+
The time complexity is $O(\log n)$ and the space complexity is $O(1)$, where $n$ is the total number of students.
6979

7080
<!-- tabs:start -->
7181

@@ -150,6 +160,26 @@ function maximumGroups(grades: number[]): number {
150160
}
151161
```
152162

163+
#### Rust
164+
165+
```rust
166+
impl Solution {
167+
pub fn maximum_groups(grades: Vec<i32>) -> i32 {
168+
let n = grades.len() as i64;
169+
let (mut l, mut r) = (0i64, n);
170+
while l < r {
171+
let mid = (l + r + 1) / 2;
172+
if mid * mid + mid > 2 * n {
173+
r = mid - 1;
174+
} else {
175+
l = mid;
176+
}
177+
}
178+
l as i32
179+
}
180+
}
181+
```
182+
153183
<!-- tabs:end -->
154184

155185
<!-- solution:end -->

‎solution/2300-2399/2358.Maximum Number of Groups Entering a Competition/Solution.rs

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
impl Solution {
2+
pub fn maximum_groups(grades: Vec<i32>) -> i32 {
3+
let n = grades.len() as i64;
4+
let (mut l, mut r) = (0i64, n);
5+
while l < r {
6+
let mid = (l + r + 1) / 2;
7+
if mid * mid + mid > 2 * n {
8+
r = mid - 1;
9+
} else {
10+
l = mid;
11+
}
12+
}
13+
l as i32
14+
}
15+
}

0 commit comments

Comments
 (0)