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

Commitc0158b7

Browse files
authored
Added tasks 3477-3480
1 parentd7ee11b commitc0158b7

File tree

12 files changed

+508
-0
lines changed

12 files changed

+508
-0
lines changed
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
packageg3401_3500.s3477_fruits_into_baskets_ii;
2+
3+
// #Easy #Array #Binary_Search #Simulation #Segment_Tree
4+
// #2025_03_10_Time_1_ms_(100.00%)_Space_44.78_MB_(36.06%)
5+
6+
publicclassSolution {
7+
publicintnumOfUnplacedFruits(int[]fruits,int[]baskets) {
8+
intn =fruits.length;
9+
intcurrfruits;
10+
intcount =0;
11+
for (inti =0;i <n;i++) {
12+
currfruits =fruits[i];
13+
for (intj =0;j <n;j++) {
14+
if (baskets[j] >=currfruits) {
15+
count++;
16+
baskets[j] =0;
17+
break;
18+
}
19+
}
20+
}
21+
returnn -count;
22+
}
23+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
3477\. Fruits Into Baskets II
2+
3+
Easy
4+
5+
You are given two arrays of integers,`fruits` and`baskets`, each of length`n`, where`fruits[i]` represents the**quantity** of the <code>i<sup>th</sup></code> type of fruit, and`baskets[j]` represents the**capacity** of the <code>j<sup>th</sup></code> basket.
6+
7+
From left to right, place the fruits according to these rules:
8+
9+
* Each fruit type must be placed in the**leftmost available basket** with a capacity**greater than or equal** to the quantity of that fruit type.
10+
* Each basket can hold**only one** type of fruit.
11+
* If a fruit type**cannot be placed** in any basket, it remains**unplaced**.
12+
13+
Return the number of fruit types that remain unplaced after all possible allocations are made.
14+
15+
**Example 1:**
16+
17+
**Input:** fruits =[4,2,5], baskets =[3,5,4]
18+
19+
**Output:** 1
20+
21+
**Explanation:**
22+
23+
*`fruits[0] = 4` is placed in`baskets[1] = 5`.
24+
*`fruits[1] = 2` is placed in`baskets[0] = 3`.
25+
*`fruits[2] = 5` cannot be placed in`baskets[2] = 4`.
26+
27+
Since one fruit type remains unplaced, we return 1.
28+
29+
**Example 2:**
30+
31+
**Input:** fruits =[3,6,1], baskets =[6,4,7]
32+
33+
**Output:** 0
34+
35+
**Explanation:**
36+
37+
*`fruits[0] = 3` is placed in`baskets[0] = 6`.
38+
*`fruits[1] = 6` cannot be placed in`baskets[1] = 4` (insufficient capacity) but can be placed in the next available basket,`baskets[2] = 7`.
39+
*`fruits[2] = 1` is placed in`baskets[1] = 4`.
40+
41+
Since all fruits are successfully placed, we return 0.
42+
43+
**Constraints:**
44+
45+
*`n == fruits.length == baskets.length`
46+
*`1 <= n <= 100`
47+
*`1 <= fruits[i], baskets[i] <= 1000`
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
packageg3401_3500.s3478_choose_k_elements_with_maximum_sum;
2+
3+
// #Medium #Array #Sorting #Heap_Priority_Queue
4+
// #2025_03_10_Time_105_ms_(98.60%)_Space_69.10_MB_(28.75%)
5+
6+
importjava.util.Arrays;
7+
importjava.util.PriorityQueue;
8+
9+
publicclassSolution {
10+
publiclong[]findMaxSum(int[]nums1,int[]nums2,intk) {
11+
intn =nums1.length;
12+
long[]ans =newlong[n];
13+
Point[]ps =newPoint[n];
14+
for (inti =0;i <n;i++) {
15+
ps[i] =newPoint(nums1[i],nums2[i],i);
16+
}
17+
Arrays.sort(ps, (p1,p2) ->Integer.compare(p1.x,p2.x));
18+
PriorityQueue<Integer>pq =newPriorityQueue<>();
19+
longs =0;
20+
inti =0;
21+
while (i <n) {
22+
intj =i;
23+
while (j <n &&ps[j].x ==ps[i].x) {
24+
ans[ps[j].i] =s;
25+
j++;
26+
}
27+
for (intp =i;p <j;p++) {
28+
intcur =ps[p].y;
29+
if (pq.size() <k) {
30+
pq.offer(cur);
31+
s +=cur;
32+
}elseif (cur >pq.peek()) {
33+
s -=pq.poll();
34+
pq.offer(cur);
35+
s +=cur;
36+
}
37+
}
38+
i =j;
39+
}
40+
returnans;
41+
}
42+
43+
privatestaticclassPoint {
44+
intx;
45+
inty;
46+
inti;
47+
48+
Point(intx,inty,inti) {
49+
this.x =x;
50+
this.y =y;
51+
this.i =i;
52+
}
53+
}
54+
}
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
3478\. Choose K Elements With Maximum Sum
2+
3+
Medium
4+
5+
You are given two integer arrays,`nums1` and`nums2`, both of length`n`, along with a positive integer`k`.
6+
7+
For each index`i` from`0` to`n - 1`, perform the following:
8+
9+
* Find**all** indices`j` where`nums1[j]` is less than`nums1[i]`.
10+
* Choose**at most**`k` values of`nums2[j]` at these indices to**maximize** the total sum.
11+
12+
Return an array`answer` of size`n`, where`answer[i]` represents the result for the corresponding index`i`.
13+
14+
**Example 1:**
15+
16+
**Input:** nums1 =[4,2,1,5,3], nums2 =[10,20,30,40,50], k = 2
17+
18+
**Output:**[80,30,0,80,50]
19+
20+
**Explanation:**
21+
22+
* For`i = 0`: Select the 2 largest values from`nums2` at indices`[1, 2, 4]` where`nums1[j] < nums1[0]`, resulting in`50 + 30 = 80`.
23+
* For`i = 1`: Select the 2 largest values from`nums2` at index`[2]` where`nums1[j] < nums1[1]`, resulting in 30.
24+
* For`i = 2`: No indices satisfy`nums1[j] < nums1[2]`, resulting in 0.
25+
* For`i = 3`: Select the 2 largest values from`nums2` at indices`[0, 1, 2, 4]` where`nums1[j] < nums1[3]`, resulting in`50 + 30 = 80`.
26+
* For`i = 4`: Select the 2 largest values from`nums2` at indices`[1, 2]` where`nums1[j] < nums1[4]`, resulting in`30 + 20 = 50`.
27+
28+
**Example 2:**
29+
30+
**Input:** nums1 =[2,2,2,2], nums2 =[3,1,2,3], k = 1
31+
32+
**Output:**[0,0,0,0]
33+
34+
**Explanation:**
35+
36+
Since all elements in`nums1` are equal, no indices satisfy the condition`nums1[j] < nums1[i]` for any`i`, resulting in 0 for all positions.
37+
38+
**Constraints:**
39+
40+
*`n == nums1.length == nums2.length`
41+
* <code>1 <= n <= 10<sup>5</sup></code>
42+
* <code>1 <= nums1[i], nums2[i] <= 10<sup>6</sup></code>
43+
*`1 <= k <= n`
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
packageg3401_3500.s3479_fruits_into_baskets_iii;
2+
3+
// #Medium #Array #Binary_Search #Ordered_Set #Segment_Tree
4+
// #2025_03_10_Time_38_ms_(97.76%)_Space_67.52_MB_(38.48%)
5+
6+
publicclassSolution {
7+
publicintnumOfUnplacedFruits(int[]fruits,int[]baskets) {
8+
intn =baskets.length;
9+
intsize =1;
10+
while (size <n) {
11+
size <<=1;
12+
}
13+
int[]seg =newint[2 *size];
14+
for (inti =0;i <n;i++) {
15+
seg[size +i] =baskets[i];
16+
}
17+
for (inti =n;i <size;i++) {
18+
seg[size +i] =0;
19+
}
20+
for (inti =size -1;i >0;i--) {
21+
seg[i] =Math.max(seg[i <<1],seg[i <<1 |1]);
22+
}
23+
intans =0;
24+
for (intf :fruits) {
25+
if (seg[1] <f) {
26+
ans++;
27+
continue;
28+
}
29+
intidx =1;
30+
while (idx <size) {
31+
if (seg[idx <<1] >=f) {
32+
idx =idx <<1;
33+
}else {
34+
idx =idx <<1 |1;
35+
}
36+
}
37+
update(seg,idx -size,0,size);
38+
}
39+
returnans;
40+
}
41+
42+
privatevoidupdate(int[]seg,intpos,intval,intsize) {
43+
inti =pos +size;
44+
seg[i] =val;
45+
for (i /=2;i >0;i /=2) {
46+
seg[i] =Math.max(seg[i <<1],seg[i <<1 |1]);
47+
}
48+
}
49+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
3479\. Fruits Into Baskets III
2+
3+
Medium
4+
5+
You are given two arrays of integers,`fruits` and`baskets`, each of length`n`, where`fruits[i]` represents the**quantity** of the <code>i<sup>th</sup></code> type of fruit, and`baskets[j]` represents the**capacity** of the <code>j<sup>th</sup></code> basket.
6+
7+
From left to right, place the fruits according to these rules:
8+
9+
* Each fruit type must be placed in the**leftmost available basket** with a capacity**greater than or equal** to the quantity of that fruit type.
10+
* Each basket can hold**only one** type of fruit.
11+
* If a fruit type**cannot be placed** in any basket, it remains**unplaced**.
12+
13+
Return the number of fruit types that remain unplaced after all possible allocations are made.
14+
15+
**Example 1:**
16+
17+
**Input:** fruits =[4,2,5], baskets =[3,5,4]
18+
19+
**Output:** 1
20+
21+
**Explanation:**
22+
23+
*`fruits[0] = 4` is placed in`baskets[1] = 5`.
24+
*`fruits[1] = 2` is placed in`baskets[0] = 3`.
25+
*`fruits[2] = 5` cannot be placed in`baskets[2] = 4`.
26+
27+
Since one fruit type remains unplaced, we return 1.
28+
29+
**Example 2:**
30+
31+
**Input:** fruits =[3,6,1], baskets =[6,4,7]
32+
33+
**Output:** 0
34+
35+
**Explanation:**
36+
37+
*`fruits[0] = 3` is placed in`baskets[0] = 6`.
38+
*`fruits[1] = 6` cannot be placed in`baskets[1] = 4` (insufficient capacity) but can be placed in the next available basket,`baskets[2] = 7`.
39+
*`fruits[2] = 1` is placed in`baskets[1] = 4`.
40+
41+
Since all fruits are successfully placed, we return 0.
42+
43+
**Constraints:**
44+
45+
*`n == fruits.length == baskets.length`
46+
* <code>1 <= n <= 10<sup>5</sup></code>
47+
* <code>1 <= fruits[i], baskets[i] <= 10<sup>9</sup></code>
Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
packageg3401_3500.s3480_maximize_subarrays_after_removing_one_conflicting_pair;
2+
3+
// #Hard #Array #Prefix_Sum #Enumeration #Segment_Tree
4+
// #2025_03_10_Time_20_ms_(98.86%)_Space_141.78_MB_(52.27%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publiclongmaxSubarrays(intn,int[][]conflictingPairs) {
10+
longtotalSubarrays = (long)n * (n +1) /2;
11+
int[]h =newint[n +1];
12+
int[]d2 =newint[n +1];
13+
Arrays.fill(h,n +1);
14+
Arrays.fill(d2,n +1);
15+
for (int[]pair :conflictingPairs) {
16+
inta =pair[0];
17+
intb =pair[1];
18+
if (a >b) {
19+
inttemp =a;
20+
a =b;
21+
b =temp;
22+
}
23+
if (b <h[a]) {
24+
d2[a] =h[a];
25+
h[a] =b;
26+
}elseif (b <d2[a]) {
27+
d2[a] =b;
28+
}
29+
}
30+
int[]f =newint[n +2];
31+
f[n +1] =n +1;
32+
f[n] =h[n];
33+
for (inti =n -1;i >=1;i--) {
34+
f[i] =Math.min(h[i],f[i +1]);
35+
}
36+
// forbiddenCount(x) returns (n - x + 1) if x <= n, else 0.
37+
// This is the number of forbidden subarrays starting at some i when f[i] = x.
38+
longoriginalUnion =0;
39+
for (inti =1;i <=n;i++) {
40+
if (f[i] <=n) {
41+
originalUnion += (n -f[i] +1);
42+
}
43+
}
44+
longoriginalValid =totalSubarrays -originalUnion;
45+
longbest =originalValid;
46+
// For each index j (1 <= j <= n) where a candidate conflicting pair exists,
47+
// simulate removal of the pair that gave h[j] (if any).
48+
// (If there is no candidate pair at j, h[j] remains n+1.)
49+
for (intj =1;j <=n;j++) {
50+
// no conflicting pair at index j
51+
if (h[j] ==n +1) {
52+
continue;
53+
}
54+
// Simulate removal: new candidate at j becomes d2[j]
55+
intnewCandidate = (j <n) ?Math.min(d2[j],f[j +1]) :d2[j];
56+
// We'll recompute the new f values for indices 1..j.
57+
// Let newF[i] denote the updated value.
58+
// For i > j, newF[i] remains as original f[i].
59+
// For i = j, newF[j] = min( newCandidate, f[j+1] ) (which is newCandidate by
60+
// definition).
61+
intnewFj =newCandidate;
62+
// forbiddenCount(x) is defined as (n - x + 1) if x<= n, else 0.
63+
longdelta =forbiddenCount(newFj,n) -forbiddenCount(f[j],n);
64+
intcur =newFj;
65+
// Now update backwards for i = j-1 down to 1.
66+
for (inti =j -1;i >=1;i--) {
67+
intnewVal =Math.min(h[i],cur);
68+
// no further change for i' <= i
69+
if (newVal ==f[i]) {
70+
break;
71+
}
72+
delta +=forbiddenCount(newVal,n) -forbiddenCount(f[i],n);
73+
cur =newVal;
74+
}
75+
longnewUnion =originalUnion +delta;
76+
longnewValid =totalSubarrays -newUnion;
77+
best =Math.max(best,newValid);
78+
}
79+
returnbest;
80+
}
81+
82+
privatelongforbiddenCount(intx,intn) {
83+
returnx <=n ? (n -x +1) :0;
84+
}
85+
}

0 commit comments

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