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

Commit1dffcda

Browse files
authored
Added tasks 3572-3579
1 parentc74cdf6 commit1dffcda

File tree

24 files changed

+1012
-0
lines changed

24 files changed

+1012
-0
lines changed
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
packageg3501_3600.s3572_maximize_ysum_by_picking_a_triplet_of_distinct_xvalues;
2+
3+
// #Medium #Array #Hash_Table #Sorting #Greedy #Heap_Priority_Queue
4+
// #2025_06_10_Time_2_ms_(100.00%)_Space_64.25_MB_(40.62%)
5+
6+
publicclassSolution {
7+
publicintmaxSumDistinctTriplet(int[]x,int[]y) {
8+
intindex = -1;
9+
intmax = -1;
10+
intsum =0;
11+
for (inti =0;i <y.length;i++) {
12+
if (y[i] >max) {
13+
max =y[i];
14+
index =i;
15+
}
16+
}
17+
sum +=max;
18+
if (max == -1) {
19+
return -1;
20+
}
21+
intindex2 = -1;
22+
max = -1;
23+
for (inti =0;i <y.length;i++) {
24+
if (y[i] >max &&x[i] !=x[index]) {
25+
max =y[i];
26+
index2 =i;
27+
}
28+
}
29+
sum +=max;
30+
if (max == -1) {
31+
return -1;
32+
}
33+
max = -1;
34+
for (inti =0;i <y.length;i++) {
35+
if (y[i] >max &&x[i] !=x[index] &&x[i] !=x[index2]) {
36+
max =y[i];
37+
}
38+
}
39+
if (max == -1) {
40+
return -1;
41+
}
42+
sum +=max;
43+
returnsum;
44+
}
45+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
3572\. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values
2+
3+
Medium
4+
5+
You are given two integer arrays`x` and`y`, each of length`n`. You must choose three**distinct** indices`i`,`j`, and`k` such that:
6+
7+
*`x[i] != x[j]`
8+
*`x[j] != x[k]`
9+
*`x[k] != x[i]`
10+
11+
Your goal is to**maximize** the value of`y[i] + y[j] + y[k]` under these conditions. Return the**maximum** possible sum that can be obtained by choosing such a triplet of indices.
12+
13+
If no such triplet exists, return -1.
14+
15+
**Example 1:**
16+
17+
**Input:** x =[1,2,1,3,2], y =[5,3,4,6,2]
18+
19+
**Output:** 14
20+
21+
**Explanation:**
22+
23+
* Choose`i = 0` (`x[i] = 1`,`y[i] = 5`),`j = 1` (`x[j] = 2`,`y[j] = 3`),`k = 3` (`x[k] = 3`,`y[k] = 6`).
24+
* All three values chosen from`x` are distinct.`5 + 3 + 6 = 14` is the maximum we can obtain. Hence, the output is 14.
25+
26+
**Example 2:**
27+
28+
**Input:** x =[1,2,1,2], y =[4,5,6,7]
29+
30+
**Output:**\-1
31+
32+
**Explanation:**
33+
34+
* There are only two distinct values in`x`. Hence, the output is -1.
35+
36+
**Constraints:**
37+
38+
*`n == x.length == y.length`
39+
* <code>3 <= n <= 10<sup>5</sup></code>
40+
* <code>1 <= x[i], y[i] <= 10<sup>6</sup></code>
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
packageg3501_3600.s3573_best_time_to_buy_and_sell_stock_v;
2+
3+
// #Medium #Array #Dynamic_Programming #2025_06_10_Time_10_ms_(99.46%)_Space_44.46_MB_(97.36%)
4+
5+
publicclassSolution {
6+
publiclongmaximumProfit(int[]prices,intk) {
7+
intn =prices.length;
8+
long[]prev =newlong[n];
9+
long[]curr =newlong[n];
10+
for (intt =1;t <=k;t++) {
11+
longbestLong = -prices[0];
12+
longbestShort =prices[0];
13+
curr[0] =0;
14+
for (inti =1;i <n;i++) {
15+
longres =curr[i -1];
16+
res =Math.max(res,prices[i] +bestLong);
17+
res =Math.max(res, -prices[i] +bestShort);
18+
curr[i] =res;
19+
bestLong =Math.max(bestLong,prev[i -1] -prices[i]);
20+
bestShort =Math.max(bestShort,prev[i -1] +prices[i]);
21+
}
22+
long[]tmp =prev;
23+
prev =curr;
24+
curr =tmp;
25+
}
26+
returnprev[n -1];
27+
}
28+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
3573\. Best Time to Buy and Sell Stock V
2+
3+
Medium
4+
5+
You are given an integer array`prices` where`prices[i]` is the price of a stock in dollars on the <code>i<sup>th</sup></code> day, and an integer`k`.
6+
7+
You are allowed to make at most`k` transactions, where each transaction can be either of the following:
8+
9+
***Normal transaction**: Buy on day`i`, then sell on a later day`j` where`i < j`. You profit`prices[j] - prices[i]`.
10+
11+
***Short selling transaction**: Sell on day`i`, then buy back on a later day`j` where`i < j`. You profit`prices[i] - prices[j]`.
12+
13+
14+
**Note** that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.
15+
16+
Return the**maximum** total profit you can earn by making**at most**`k` transactions.
17+
18+
**Example 1:**
19+
20+
**Input:** prices =[1,7,9,8,2], k = 2
21+
22+
**Output:** 14
23+
24+
**Explanation:**
25+
26+
We can make $14 of profit through 2 transactions:
27+
28+
* A normal transaction: buy the stock on day 0 for $1 then sell it on day 2 for $9.
29+
* A short selling transaction: sell the stock on day 3 for $8 then buy back on day 4 for $2.
30+
31+
**Example 2:**
32+
33+
**Input:** prices =[12,16,19,19,8,1,19,13,9], k = 3
34+
35+
**Output:** 36
36+
37+
**Explanation:**
38+
39+
We can make $36 of profit through 3 transactions:
40+
41+
* A normal transaction: buy the stock on day 0 for $12 then sell it on day 2 for $19.
42+
* A short selling transaction: sell the stock on day 3 for $19 then buy back on day 4 for $8.
43+
* A normal transaction: buy the stock on day 5 for $1 then sell it on day 6 for $19.
44+
45+
**Constraints:**
46+
47+
* <code>2 <= prices.length <= 10<sup>3</sup></code>
48+
* <code>1 <= prices[i] <= 10<sup>9</sup></code>
49+
*`1 <= k <= prices.length / 2`
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
packageg3501_3600.s3574_maximize_subarray_gcd_score;
2+
3+
// #Hard #Array #Math #Enumeration #Number_Theory
4+
// #2025_06_10_Time_13_ms_(100.00%)_Space_45.07_MB_(78.08%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
importjava.util.List;
9+
10+
@SuppressWarnings("unchecked")
11+
publicclassSolution {
12+
publiclongmaxGCDScore(int[]nums,intk) {
13+
intmx =0;
14+
for (intx :nums) {
15+
mx =Math.max(mx,x);
16+
}
17+
intwidth =32 -Integer.numberOfLeadingZeros(mx);
18+
List<Integer>[]lowbitPos =newList[width];
19+
Arrays.setAll(lowbitPos,i ->newArrayList<>());
20+
int[][]intervals =newint[width +1][3];
21+
intsize =0;
22+
longans =0;
23+
for (inti =0;i <nums.length;i++) {
24+
intx =nums[i];
25+
inttz =Integer.numberOfTrailingZeros(x);
26+
lowbitPos[tz].add(i);
27+
for (intj =0;j <size;j++) {
28+
intervals[j][0] =gcd(intervals[j][0],x);
29+
}
30+
intervals[size][0] =x;
31+
intervals[size][1] =i -1;
32+
intervals[size][2] =i;
33+
size++;
34+
intidx =1;
35+
for (intj =1;j <size;j++) {
36+
if (intervals[j][0] !=intervals[j -1][0]) {
37+
intervals[idx][0] =intervals[j][0];
38+
intervals[idx][1] =intervals[j][1];
39+
intervals[idx][2] =intervals[j][2];
40+
idx++;
41+
}else {
42+
intervals[idx -1][2] =intervals[j][2];
43+
}
44+
}
45+
size =idx;
46+
for (intj =0;j <size;j++) {
47+
intg =intervals[j][0];
48+
intl =intervals[j][1];
49+
intr =intervals[j][2];
50+
ans =Math.max(ans, (long)g * (i -l));
51+
List<Integer>pos =lowbitPos[Integer.numberOfTrailingZeros(g)];
52+
intminL =pos.size() >k ?Math.max(l,pos.get(pos.size() -k -1)) :l;
53+
if (minL <r) {
54+
ans =Math.max(ans, (long)g *2 * (i -minL));
55+
}
56+
}
57+
}
58+
returnans;
59+
}
60+
61+
privateintgcd(inta,intb) {
62+
while (a !=0) {
63+
inttmp =a;
64+
a =b %a;
65+
b =tmp;
66+
}
67+
returnb;
68+
}
69+
}
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
3574\. Maximize Subarray GCD Score
2+
3+
Hard
4+
5+
You are given an array of positive integers`nums` and an integer`k`.
6+
7+
You may perform at most`k` operations. In each operation, you can choose one element in the array and**double** its value. Each element can be doubled**at most** once.
8+
9+
The**score** of a contiguous**subarray** is defined as the**product** of its length and the_greatest common divisor (GCD)_ of all its elements.
10+
11+
Your task is to return the**maximum****score** that can be achieved by selecting a contiguous subarray from the modified array.
12+
13+
**Note:**
14+
15+
* The**greatest common divisor (GCD)** of an array is the largest integer that evenly divides all the array elements.
16+
17+
**Example 1:**
18+
19+
**Input:** nums =[2,4], k = 1
20+
21+
**Output:** 8
22+
23+
**Explanation:**
24+
25+
* Double`nums[0]` to 4 using one operation. The modified array becomes`[4, 4]`.
26+
* The GCD of the subarray`[4, 4]` is 4, and the length is 2.
27+
* Thus, the maximum possible score is`2 × 4 = 8`.
28+
29+
**Example 2:**
30+
31+
**Input:** nums =[3,5,7], k = 2
32+
33+
**Output:** 14
34+
35+
**Explanation:**
36+
37+
* Double`nums[2]` to 14 using one operation. The modified array becomes`[3, 5, 14]`.
38+
* The GCD of the subarray`[14]` is 14, and the length is 1.
39+
* Thus, the maximum possible score is`1 × 14 = 14`.
40+
41+
**Example 3:**
42+
43+
**Input:** nums =[5,5,5], k = 1
44+
45+
**Output:** 15
46+
47+
**Explanation:**
48+
49+
* The subarray`[5, 5, 5]` has a GCD of 5, and its length is 3.
50+
* Since doubling any element doesn't improve the score, the maximum score is`3 × 5 = 15`.
51+
52+
**Constraints:**
53+
54+
*`1 <= n == nums.length <= 1500`
55+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
56+
*`1 <= k <= n`
Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
packageg3501_3600.s3575_maximum_good_subtree_score;
2+
3+
// #Hard #Array #Dynamic_Programming #Depth_First_Search #Tree #Bit_Manipulation #Bitmask
4+
// #2025_06_10_Time_92_ms_(98.73%)_Space_55.23_MB_(11.71%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
importjava.util.List;
9+
10+
@SuppressWarnings("unchecked")
11+
publicclassSolution {
12+
privateintdigits =10;
13+
privateintfull =1 <<digits;
14+
privatelongneg =Long.MIN_VALUE /4;
15+
privatelongmod = (long)1e9 +7;
16+
privateList<Integer>[]tree;
17+
privateint[]val;
18+
privateint[]mask;
19+
privateboolean[]isOk;
20+
privatelongres =0;
21+
22+
publicintgoodSubtreeSum(int[]vals,int[]par) {
23+
intn =vals.length;
24+
val =vals;
25+
mask =newint[n];
26+
isOk =newboolean[n];
27+
for (inti =0;i <n;i++) {
28+
intm =0;
29+
intv =vals[i];
30+
booleanvalid =true;
31+
while (v >0) {
32+
intd =v %10;
33+
if (((m >>d) &1) ==1) {
34+
valid =false;
35+
break;
36+
}
37+
m |=1 <<d;
38+
v /=10;
39+
}
40+
mask[i] =m;
41+
isOk[i] =valid;
42+
}
43+
tree =newArrayList[n];
44+
Arrays.setAll(tree,ArrayList::new);
45+
introot =0;
46+
for (inti =1;i <n;i++) {
47+
tree[par[i]].add(i);
48+
}
49+
dfs(root);
50+
return (int) (res %mod);
51+
}
52+
53+
privatelong[]dfs(intu) {
54+
long[]dp =newlong[full];
55+
Arrays.fill(dp,neg);
56+
dp[0] =0;
57+
if (isOk[u]) {
58+
dp[mask[u]] =val[u];
59+
}
60+
for (intv :tree[u]) {
61+
long[]child =dfs(v);
62+
long[]newDp =Arrays.copyOf(dp,full);
63+
for (intm1 =0;m1 <full;m1++) {
64+
if (dp[m1] <0) {
65+
continue;
66+
}
67+
intremain =full -1 -m1;
68+
for (intm2 =remain;m2 >0;m2 = (m2 -1) &remain) {
69+
if (child[m2] <0) {
70+
continue;
71+
}
72+
intnewM =m1 |m2;
73+
newDp[newM] =Math.max(newDp[newM],dp[m1] +child[m2]);
74+
}
75+
}
76+
dp =newDp;
77+
}
78+
longbest =0;
79+
for (longv :dp) {
80+
best =Math.max(best,v);
81+
}
82+
res = (res +best) %mod;
83+
returndp;
84+
}
85+
}

0 commit comments

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