Skip to content

Commit da8f70c

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1894. Find the Student that Will Replace the Chalk
1 parent 118e44d commit da8f70c

File tree

6 files changed

+235
-2
lines changed

6 files changed

+235
-2
lines changed

‎solution/1800-1899/1894.Find the Student that Will Replace the Chalk/README.md

Lines changed: 82 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -60,22 +60,103 @@
6060

6161
<!-- 这里可写通用的实现逻辑 -->
6262

63+
“前缀和 + 二分查找”实现。
64+
6365
<!-- tabs:start -->
6466

6567
### **Python3**
6668

6769
<!-- 这里可写当前语言的特殊实现逻辑 -->
6870

6971
```python
70-
72+
class Solution:
73+
def chalkReplacer(self, chalk: List[int], k: int) -> int:
74+
pre_sum = list(itertools.accumulate(chalk))
75+
k %= pre_sum[-1]
76+
left, right = 0, len(chalk) - 1
77+
while left < right:
78+
mid = (left + right) >> 1
79+
if pre_sum[mid] > k:
80+
right = mid
81+
else:
82+
left = mid + 1
83+
return left
7184
```
7285

7386
### **Java**
7487

7588
<!-- 这里可写当前语言的特殊实现逻辑 -->
7689

7790
```java
91+
class Solution {
92+
public int chalkReplacer(int[] chalk, int k) {
93+
int n = chalk.length;
94+
long[] preSum = new long[n + 1];
95+
for (int i = 0; i < n; ++i) {
96+
preSum[i + 1] = preSum[i] + chalk[i];
97+
}
98+
k %= preSum[n];
99+
int left = 0, right = n - 1;
100+
while (left < right) {
101+
int mid = (left + right) >> 1;
102+
if (preSum[mid + 1] > k) {
103+
right = mid;
104+
} else {
105+
left = mid + 1;
106+
}
107+
}
108+
return left;
109+
}
110+
}
111+
```
112+
113+
### **C++**
114+
115+
```cpp
116+
class Solution {
117+
public:
118+
int chalkReplacer(vector<int>& chalk, int k) {
119+
int n = chalk.size();
120+
vector<long long> preSum(n + 1);
121+
for (int i = 0; i < n; ++i) {
122+
preSum[i + 1] = preSum[i] + chalk[i];
123+
}
124+
k %= preSum[n];
125+
int left = 0, right = n - 1;
126+
while (left < right) {
127+
int mid = left + (right - left >> 1);
128+
if (preSum[mid + 1] > k) {
129+
right = mid;
130+
} else {
131+
left = mid + 1;
132+
}
133+
}
134+
return left;
135+
}
136+
};
137+
```
78138
139+
### **Go**
140+
141+
```go
142+
func chalkReplacer(chalk []int, k int) int {
143+
n := len(chalk)
144+
preSum := make([]int, n+1)
145+
for i := 0; i < n; i++ {
146+
preSum[i+1] = preSum[i] + chalk[i]
147+
}
148+
k %= preSum[n]
149+
left, right := 0, n-1
150+
for left < right {
151+
mid := left + ((right - left) >> 1)
152+
if preSum[mid+1] > k {
153+
right = mid
154+
} else {
155+
left = mid + 1
156+
}
157+
}
158+
return left
159+
}
79160
```
80161

81162
### **...**

‎solution/1800-1899/1894.Find the Student that Will Replace the Chalk/README_EN.md

Lines changed: 82 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -97,18 +97,99 @@ Student number 1 does not have enough chalk, so they will have to replace it.
9797

9898
## Solutions
9999

100+
PreSum and Binary search.
101+
100102
<!-- tabs:start -->
101103

102104
### **Python3**
103105

104106
```python
105-
107+
class Solution:
108+
def chalkReplacer(self, chalk: List[int], k: int) -> int:
109+
pre_sum = list(itertools.accumulate(chalk))
110+
k %= pre_sum[-1]
111+
left, right = 0, len(chalk) - 1
112+
while left < right:
113+
mid = (left + right) >> 1
114+
if pre_sum[mid] > k:
115+
right = mid
116+
else:
117+
left = mid + 1
118+
return left
106119
```
107120

108121
### **Java**
109122

110123
```java
124+
class Solution {
125+
public int chalkReplacer(int[] chalk, int k) {
126+
int n = chalk.length;
127+
long[] preSum = new long[n + 1];
128+
for (int i = 0; i < n; ++i) {
129+
preSum[i + 1] = preSum[i] + chalk[i];
130+
}
131+
k %= preSum[n];
132+
int left = 0, right = n - 1;
133+
while (left < right) {
134+
int mid = (left + right) >> 1;
135+
if (preSum[mid + 1] > k) {
136+
right = mid;
137+
} else {
138+
left = mid + 1;
139+
}
140+
}
141+
return left;
142+
}
143+
}
144+
```
145+
146+
### **C++**
147+
148+
```cpp
149+
class Solution {
150+
public:
151+
int chalkReplacer(vector<int>& chalk, int k) {
152+
int n = chalk.size();
153+
vector<long long> preSum(n + 1);
154+
for (int i = 0; i < n; ++i) {
155+
preSum[i + 1] = preSum[i] + chalk[i];
156+
}
157+
k %= preSum[n];
158+
int left = 0, right = n - 1;
159+
while (left < right) {
160+
int mid = left + (right - left >> 1);
161+
if (preSum[mid + 1] > k) {
162+
right = mid;
163+
} else {
164+
left = mid + 1;
165+
}
166+
}
167+
return left;
168+
}
169+
};
170+
```
111171
172+
### **Go**
173+
174+
```go
175+
func chalkReplacer(chalk []int, k int) int {
176+
n := len(chalk)
177+
preSum := make([]int, n+1)
178+
for i := 0; i < n; i++ {
179+
preSum[i+1] = preSum[i] + chalk[i]
180+
}
181+
k %= preSum[n]
182+
left, right := 0, n-1
183+
for left < right {
184+
mid := left + ((right - left) >> 1)
185+
if preSum[mid+1] > k {
186+
right = mid
187+
} else {
188+
left = mid + 1
189+
}
190+
}
191+
return left
192+
}
112193
```
113194

114195
### **...**

‎solution/1800-1899/1894.Find the Student that Will Replace the Chalk/Solution.cpp

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
class Solution {
2+
public:
3+
int chalkReplacer(vector<int>& chalk, int k) {
4+
int n = chalk.size();
5+
vector<long long> preSum(n + 1);
6+
for (int i = 0; i < n; ++i) {
7+
preSum[i + 1] = preSum[i] + chalk[i];
8+
}
9+
k %= preSum[n];
10+
int left = 0, right = n - 1;
11+
while (left < right) {
12+
int mid = left + (right - left >> 1);
13+
if (preSum[mid + 1] > k) {
14+
right = mid;
15+
} else {
16+
left = mid + 1;
17+
}
18+
}
19+
return left;
20+
}
21+
};

‎solution/1800-1899/1894.Find the Student that Will Replace the Chalk/Solution.go

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
func chalkReplacer(chalk []int, k int) int {
2+
n := len(chalk)
3+
preSum := make([]int, n+1)
4+
for i := 0; i < n; i++ {
5+
preSum[i+1] = preSum[i] + chalk[i]
6+
}
7+
k %= preSum[n]
8+
left, right := 0, n-1
9+
for left < right {
10+
mid := left + ((right - left) >> 1)
11+
if preSum[mid+1] > k {
12+
right = mid
13+
} else {
14+
left = mid + 1
15+
}
16+
}
17+
return left
18+
}

‎solution/1800-1899/1894.Find the Student that Will Replace the Chalk/Solution.java

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
class Solution {
2+
public int chalkReplacer(int[] chalk, int k) {
3+
int n = chalk.length;
4+
long[] preSum = new long[n + 1];
5+
for (int i = 0; i < n; ++i) {
6+
preSum[i + 1] = preSum[i] + chalk[i];
7+
}
8+
k %= preSum[n];
9+
int left = 0, right = n - 1;
10+
while (left < right) {
11+
int mid = (left + right) >> 1;
12+
if (preSum[mid + 1] > k) {
13+
right = mid;
14+
} else {
15+
left = mid + 1;
16+
}
17+
}
18+
return left;
19+
}
20+
}

‎solution/1800-1899/1894.Find the Student that Will Replace the Chalk/Solution.py

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
class Solution:
2+
def chalkReplacer(self, chalk: List[int], k: int) -> int:
3+
pre_sum = list(itertools.accumulate(chalk))
4+
k %= pre_sum[-1]
5+
left, right = 0, len(chalk) - 1
6+
while left < right:
7+
mid = (left + right) >> 1
8+
if pre_sum[mid] > k:
9+
right = mid
10+
else:
11+
left = mid + 1
12+
return left

0 commit comments

Comments
 (0)