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

Commit51a192d

Browse files
authored
feat: add solutions to lc problem: No.3362 (#4421)
No.3362.Zero Array Transformation III
1 parent0482811 commit51a192d

File tree

7 files changed

+408
-7
lines changed

7 files changed

+408
-7
lines changed

‎solution/3300-3399/3362.Zero Array Transformation III/README.md

Lines changed: 138 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -97,32 +97,166 @@ tags:
9797

9898
<!-- solution:start-->
9999

100-
###方法一
100+
###方法一：贪心 + 差分数组 + 优先队列（大根堆）
101101

102102
<!-- tabs:start-->
103103

104104
####Python3
105105

106106
```python
107-
107+
classSolution:
108+
defmaxRemoval(self,nums: List[int],queries: List[List[int]]) ->int:
109+
queries.sort()
110+
pq= []
111+
d= [0]* (len(nums)+1)
112+
s= j=0
113+
for i, xinenumerate(nums):
114+
s+= d[i]
115+
while j<len(queries)and queries[j][0]<= i:
116+
heappush(pq,-queries[j][1])
117+
j+=1
118+
while s< xand pqand-pq[0]>= i:
119+
s+=1
120+
d[-heappop(pq)+1]-=1
121+
if s< x:
122+
return-1
123+
returnlen(pq)
108124
```
109125

110126
####Java
111127

112128
```java
113-
129+
classSolution {
130+
publicintmaxRemoval(int[]nums,int[][]queries) {
131+
Arrays.sort(queries, (a, b)->Integer.compare(a[0], b[0]));
132+
PriorityQueue<Integer> pq=newPriorityQueue<>((a, b)-> b- a);
133+
int n= nums.length;
134+
int[] d=newint[n+1];
135+
int s=0, j=0;
136+
for (int i=0; i< n; i++) {
137+
s+= d[i];
138+
while (j< queries.length&& queries[j][0]<= i) {
139+
pq.offer(queries[j][1]);
140+
j++;
141+
}
142+
while (s< nums[i]&&!pq.isEmpty()&& pq.peek()>= i) {
143+
s++;
144+
d[pq.poll()+1]--;
145+
}
146+
if (s< nums[i]) {
147+
return-1;
148+
}
149+
}
150+
return pq.size();
151+
}
152+
}
114153
```
115154

116155
####C++
117156

118157
```cpp
119-
158+
classSolution {
159+
public:
160+
int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
161+
sort(queries.begin(), queries.end());
162+
priority_queue<int> pq;
163+
int n = nums.size();
164+
vector<int> d(n + 1, 0);
165+
int s = 0, j = 0;
166+
for (int i = 0; i < n; ++i) {
167+
s += d[i];
168+
while (j < queries.size() && queries[j][0] <= i) {
169+
pq.push(queries[j][1]);
170+
++j;
171+
}
172+
while (s < nums[i] && !pq.empty() && pq.top() >= i) {
173+
++s;
174+
int end = pq.top();
175+
pq.pop();
176+
--d[end + 1];
177+
}
178+
if (s < nums[i]) {
179+
return -1;
180+
}
181+
}
182+
return pq.size();
183+
}
184+
};
120185
```
121186
122187
#### Go
123188
124189
```go
190+
func maxRemoval(nums []int, queries [][]int) int {
191+
sort.Slice(queries, func(i, j int) bool {
192+
return queries[i][0] < queries[j][0]
193+
})
194+
195+
var h hp
196+
heap.Init(&h)
197+
198+
n := len(nums)
199+
d := make([]int, n+1)
200+
s, j := 0, 0
201+
202+
for i := 0; i < n; i++ {
203+
s += d[i]
204+
for j < len(queries) && queries[j][0] <= i {
205+
heap.Push(&h, queries[j][1])
206+
j++
207+
}
208+
for s < nums[i] && h.Len() > 0 && h.IntSlice[0] >= i {
209+
s++
210+
end := heap.Pop(&h).(int)
211+
if end+1 < len(d) {
212+
d[end+1]--
213+
}
214+
}
215+
if s < nums[i] {
216+
return -1
217+
}
218+
}
219+
220+
return h.Len()
221+
}
222+
223+
type hp struct{ sort.IntSlice }
224+
225+
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
226+
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
227+
func (h *hp) Pop() any {
228+
a := h.IntSlice
229+
v := a[len(a)-1]
230+
h.IntSlice = a[:len(a)-1]
231+
return v
232+
}
233+
```
125234

235+
####TypeScript
236+
237+
```ts
238+
function maxRemoval(nums:number[],queries:number[][]):number {
239+
queries.sort((a,b)=>a[0]-b[0]);
240+
const pq=newMaxPriorityQueue<number>();
241+
const n=nums.length;
242+
const d:number[]=Array(n+1).fill(0);
243+
let [s, j]= [0,0];
244+
for (let i=0;i<n;i++) {
245+
s+=d[i];
246+
while (j<queries.length&&queries[j][0]<=i) {
247+
pq.enqueue(queries[j][1]);
248+
j++;
249+
}
250+
while (s<nums[i]&&!pq.isEmpty()&&pq.front()>=i) {
251+
s++;
252+
d[pq.dequeue()+1]--;
253+
}
254+
if (s<nums[i]) {
255+
return-1;
256+
}
257+
}
258+
returnpq.size();
259+
}
126260
```
127261

128262
<!-- tabs:end -->

‎solution/3300-3399/3362.Zero Array Transformation III/README_EN.md

Lines changed: 137 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -101,25 +101,159 @@ tags:
101101
####Python3
102102

103103
```python
104-
104+
classSolution:
105+
defmaxRemoval(self,nums: List[int],queries: List[List[int]]) ->int:
106+
queries.sort()
107+
pq= []
108+
d= [0]* (len(nums)+1)
109+
s= j=0
110+
for i, xinenumerate(nums):
111+
s+= d[i]
112+
while j<len(queries)and queries[j][0]<= i:
113+
heappush(pq,-queries[j][1])
114+
j+=1
115+
while s< xand pqand-pq[0]>= i:
116+
s+=1
117+
d[-heappop(pq)+1]-=1
118+
if s< x:
119+
return-1
120+
returnlen(pq)
105121
```
106122

107123
####Java
108124

109125
```java
110-
126+
classSolution {
127+
publicintmaxRemoval(int[]nums,int[][]queries) {
128+
Arrays.sort(queries, (a, b)->Integer.compare(a[0], b[0]));
129+
PriorityQueue<Integer> pq=newPriorityQueue<>((a, b)-> b- a);
130+
int n= nums.length;
131+
int[] d=newint[n+1];
132+
int s=0, j=0;
133+
for (int i=0; i< n; i++) {
134+
s+= d[i];
135+
while (j< queries.length&& queries[j][0]<= i) {
136+
pq.offer(queries[j][1]);
137+
j++;
138+
}
139+
while (s< nums[i]&&!pq.isEmpty()&& pq.peek()>= i) {
140+
s++;
141+
d[pq.poll()+1]--;
142+
}
143+
if (s< nums[i]) {
144+
return-1;
145+
}
146+
}
147+
return pq.size();
148+
}
149+
}
111150
```
112151

113152
####C++
114153

115154
```cpp
116-
155+
classSolution {
156+
public:
157+
int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
158+
sort(queries.begin(), queries.end());
159+
priority_queue<int> pq;
160+
int n = nums.size();
161+
vector<int> d(n + 1, 0);
162+
int s = 0, j = 0;
163+
for (int i = 0; i < n; ++i) {
164+
s += d[i];
165+
while (j < queries.size() && queries[j][0] <= i) {
166+
pq.push(queries[j][1]);
167+
++j;
168+
}
169+
while (s < nums[i] && !pq.empty() && pq.top() >= i) {
170+
++s;
171+
int end = pq.top();
172+
pq.pop();
173+
--d[end + 1];
174+
}
175+
if (s < nums[i]) {
176+
return -1;
177+
}
178+
}
179+
return pq.size();
180+
}
181+
};
117182
```
118183
119184
#### Go
120185
121186
```go
187+
func maxRemoval(nums []int, queries [][]int) int {
188+
sort.Slice(queries, func(i, j int) bool {
189+
return queries[i][0] < queries[j][0]
190+
})
191+
192+
var h hp
193+
heap.Init(&h)
194+
195+
n := len(nums)
196+
d := make([]int, n+1)
197+
s, j := 0, 0
198+
199+
for i := 0; i < n; i++ {
200+
s += d[i]
201+
for j < len(queries) && queries[j][0] <= i {
202+
heap.Push(&h, queries[j][1])
203+
j++
204+
}
205+
for s < nums[i] && h.Len() > 0 && h.IntSlice[0] >= i {
206+
s++
207+
end := heap.Pop(&h).(int)
208+
if end+1 < len(d) {
209+
d[end+1]--
210+
}
211+
}
212+
if s < nums[i] {
213+
return -1
214+
}
215+
}
216+
217+
return h.Len()
218+
}
219+
220+
type hp struct{ sort.IntSlice }
221+
222+
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
223+
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
224+
func (h *hp) Pop() any {
225+
a := h.IntSlice
226+
v := a[len(a)-1]
227+
h.IntSlice = a[:len(a)-1]
228+
return v
229+
}
230+
```
122231

232+
####TypeScript
233+
234+
```ts
235+
function maxRemoval(nums:number[],queries:number[][]):number {
236+
queries.sort((a,b)=>a[0]-b[0]);
237+
const pq=newMaxPriorityQueue<number>();
238+
const n=nums.length;
239+
const d:number[]=Array(n+1).fill(0);
240+
let [s, j]= [0,0];
241+
for (let i=0;i<n;i++) {
242+
s+=d[i];
243+
while (j<queries.length&&queries[j][0]<=i) {
244+
pq.enqueue(queries[j][1]);
245+
j++;
246+
}
247+
while (s<nums[i]&&!pq.isEmpty()&&pq.front()>=i) {
248+
s++;
249+
d[pq.dequeue()+1]--;
250+
}
251+
if (s<nums[i]) {
252+
return-1;
253+
}
254+
}
255+
returnpq.size();
256+
}
123257
```
124258

125259
<!-- tabs:end -->
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
classSolution {
2+
public:
3+
intmaxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
4+
sort(queries.begin(), queries.end());
5+
priority_queue<int> pq;
6+
int n = nums.size();
7+
vector<int>d(n +1,0);
8+
int s =0, j =0;
9+
for (int i =0; i < n; ++i) {
10+
s += d[i];
11+
while (j < queries.size() && queries[j][0] <= i) {
12+
pq.push(queries[j][1]);
13+
++j;
14+
}
15+
while (s < nums[i] && !pq.empty() && pq.top() >= i) {
16+
++s;
17+
int end = pq.top();
18+
pq.pop();
19+
--d[end +1];
20+
}
21+
if (s < nums[i]) {
22+
return -1;
23+
}
24+
}
25+
return pq.size();
26+
}
27+
};

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp