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

Commit4fca0e8

Browse files
authored
Added tasks 3498-3505
1 parent3424093 commit4fca0e8

File tree

25 files changed

+1205
-3
lines changed

25 files changed

+1205
-3
lines changed

‎build.gradle

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -12,10 +12,10 @@ repositories {
1212
}
1313

1414
dependencies {
15-
testImplementation'org.junit.jupiter:junit-jupiter:[5.11.3,)'
15+
testImplementation'org.junit.jupiter:junit-jupiter:[5.12.0,)'
1616
testImplementation'org.hamcrest:hamcrest-core:[3.0,)'
17-
testImplementation'org.zapodot:embedded-db-junit-jupiter:[2.2.0,)'
18-
testRuntimeOnly'org.junit.platform:junit-platform-launcher:[1.11.3,)'
17+
testImplementation'org.zapodot:embedded-db-junit-jupiter:2.2.0'
18+
testRuntimeOnly'org.junit.platform:junit-platform-launcher:[1.12.0,)'
1919
}
2020

2121
test {
Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
packageg3401_3500.s3498_reverse_degree_of_a_string;
2+
3+
// #Easy #String #Simulation #2025_04_01_Time_1_ms_(100.00%)_Space_42.64_MB_(92.21%)
4+
5+
publicclassSolution {
6+
publicintreverseDegree(Strings) {
7+
intans =0;
8+
for (inti =0;i <s.length(); ++i) {
9+
ans += (26 - (s.charAt(i) -'a')) * (i +1);
10+
}
11+
returnans;
12+
}
13+
}
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
3498\. Reverse Degree of a String
2+
3+
Easy
4+
5+
Given a string`s`, calculate its**reverse degree**.
6+
7+
The**reverse degree** is calculated as follows:
8+
9+
1. For each character, multiply its position in the_reversed_ alphabet (`'a'` = 26,`'b'` = 25, ...,`'z'` = 1) with its position in the string**(1-indexed)**.
10+
2. Sum these products for all characters in the string.
11+
12+
Return the**reverse degree** of`s`.
13+
14+
**Example 1:**
15+
16+
**Input:** s = "abc"
17+
18+
**Output:** 148
19+
20+
**Explanation:**
21+
22+
| Letter| Index in Reversed Alphabet| Index in String| Product|
23+
|---------|----------------------------|----------------|---------|
24+
|`'a'`| 26| 1| 26|
25+
|`'b'`| 25| 2| 50|
26+
|`'c'`| 24| 3| 72|
27+
28+
The reversed degree is`26 + 50 + 72 = 148`.
29+
30+
**Example 2:**
31+
32+
**Input:** s = "zaza"
33+
34+
**Output:** 160
35+
36+
**Explanation:**
37+
38+
| Letter| Index in Reversed Alphabet| Index in String| Product|
39+
|---------|----------------------------|----------------|---------|
40+
|`'z'`| 1| 1| 1|
41+
|`'a'`| 26| 2| 52|
42+
|`'z'`| 1| 3| 3|
43+
|`'a'`| 26| 4| 104|
44+
45+
The reverse degree is`1 + 52 + 3 + 104 = 160`.
46+
47+
**Constraints:**
48+
49+
*`1 <= s.length <= 1000`
50+
*`s` contains only lowercase English letters.
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
packageg3401_3500.s3499_maximize_active_section_with_trade_i;
2+
3+
// #Medium #String #Enumeration #2025_04_01_Time_54_ms_(97.98%)_Space_45.89_MB_(76.19%)
4+
5+
publicclassSolution {
6+
publicintmaxActiveSectionsAfterTrade(Strings) {
7+
intoneCount =0;
8+
intconvertedOne =0;
9+
intcurZeroCount =0;
10+
intlastZeroCount =0;
11+
for (inti =0;i <s.length(); ++i) {
12+
if (s.charAt(i) =='0') {
13+
curZeroCount++;
14+
}else {
15+
if (curZeroCount !=0) {
16+
lastZeroCount =curZeroCount;
17+
}
18+
curZeroCount =0;
19+
oneCount++;
20+
}
21+
convertedOne =Math.max(convertedOne,curZeroCount +lastZeroCount);
22+
}
23+
// corner case
24+
if (convertedOne ==curZeroCount ||convertedOne ==lastZeroCount) {
25+
returnoneCount;
26+
}
27+
returnoneCount +convertedOne;
28+
}
29+
}
Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
3499\. Maximize Active Section with Trade I
2+
3+
Medium
4+
5+
You are given a binary string`s` of length`n`, where:
6+
7+
*`'1'` represents an**active** section.
8+
*`'0'` represents an**inactive** section.
9+
10+
You can perform**at most one trade** to maximize the number of active sections in`s`. In a trade, you:
11+
12+
* Convert a contiguous block of`'1'`s that is surrounded by`'0'`s to all`'0'`s.
13+
* Afterward, convert a contiguous block of`'0'`s that is surrounded by`'1'`s to all`'1'`s.
14+
15+
Return the**maximum** number of active sections in`s` after making the optimal trade.
16+
17+
**Note:** Treat`s` as if it is**augmented** with a`'1'` at both ends, forming`t = '1' + s + '1'`. The augmented`'1'`s**do not** contribute to the final count.
18+
19+
**Example 1:**
20+
21+
**Input:** s = "01"
22+
23+
**Output:** 1
24+
25+
**Explanation:**
26+
27+
Because there is no block of`'1'`s surrounded by`'0'`s, no valid trade is possible. The maximum number of active sections is 1.
28+
29+
**Example 2:**
30+
31+
**Input:** s = "0100"
32+
33+
**Output:** 4
34+
35+
**Explanation:**
36+
37+
* String`"0100"` → Augmented to`"101001"`.
38+
* Choose`"0100"`, convert <code>"10<ins>**1**</ins>001"</code> → <code>"1<ins>**0000**</ins>1"</code> → <code>"1<ins>**1111**</ins>1"</code>.
39+
* The final string without augmentation is`"1111"`. The maximum number of active sections is 4.
40+
41+
**Example 3:**
42+
43+
**Input:** s = "1000100"
44+
45+
**Output:** 7
46+
47+
**Explanation:**
48+
49+
* String`"1000100"` → Augmented to`"110001001"`.
50+
* Choose`"000100"`, convert <code>"11000<ins>**1**</ins>001"</code> → <code>"11<ins>**000000**</ins>1"</code> → <code>"11<ins>**111111**</ins>1"</code>.
51+
* The final string without augmentation is`"1111111"`. The maximum number of active sections is 7.
52+
53+
**Example 4:**
54+
55+
**Input:** s = "01010"
56+
57+
**Output:** 4
58+
59+
**Explanation:**
60+
61+
* String`"01010"` → Augmented to`"1010101"`.
62+
* Choose`"010"`, convert <code>"10<ins>**1**</ins>0101"</code> → <code>"1<ins>**000**</ins>101"</code> → <code>"1<ins>**111**</ins>101"</code>.
63+
* The final string without augmentation is`"11110"`. The maximum number of active sections is 4.
64+
65+
**Constraints:**
66+
67+
* <code>1 <= n == s.length <= 10<sup>5</sup></code>
68+
*`s[i]` is either`'0'` or`'1'`
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
packageg3401_3500.s3500_minimum_cost_to_divide_array_into_subarrays;
2+
3+
// #Hard #Array #Dynamic_Programming #Prefix_Sum
4+
// #2025_04_01_Time_26_ms_(93.46%)_Space_44.97_MB_(94.77%)
5+
6+
@SuppressWarnings("java:S107")
7+
publicclassSolution {
8+
publiclongminimumCost(int[]nums,int[]cost,intk) {
9+
intn =nums.length;
10+
longkLong =k;
11+
long[]preNums =newlong[n +1];
12+
long[]preCost =newlong[n +1];
13+
for (inti =0;i <n;i++) {
14+
preNums[i +1] =preNums[i] +nums[i];
15+
preCost[i +1] =preCost[i] +cost[i];
16+
}
17+
long[]dp =newlong[n +1];
18+
for (inti =0;i <=n;i++) {
19+
dp[i] =Long.MAX_VALUE /2;
20+
}
21+
dp[0] =0L;
22+
for (intr =1;r <=n;r++) {
23+
for (intl =0;l <r;l++) {
24+
longsumNums =preNums[r] * (preCost[r] -preCost[l]);
25+
longsumCost =kLong * (preCost[n] -preCost[l]);
26+
dp[r] =Math.min(dp[r],dp[l] +sumNums +sumCost);
27+
}
28+
}
29+
returndp[n];
30+
}
31+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
3500\. Minimum Cost to Divide Array Into Subarrays
2+
3+
Hard
4+
5+
You are given two integer arrays,`nums` and`cost`, of the same size, and an integer`k`.
6+
7+
You can divide`nums` into**non-empty subarrays**. The cost of the <code>i<sup>th</sup></code> subarray consisting of elements`nums[l..r]` is:
8+
9+
*`(nums[0] + nums[1] + ... + nums[r] + k * i) * (cost[l] + cost[l + 1] + ... + cost[r])`.
10+
11+
**Note** that`i` represents the order of the subarray: 1 for the first subarray, 2 for the second, and so on.
12+
13+
Return the**minimum** total cost possible from any valid division.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[3,1,4], cost =[4,6,6], k = 1
18+
19+
**Output:** 110
20+
21+
**Explanation:**
22+
23+
The minimum total cost possible can be achieved by dividing`nums` into subarrays`[3, 1]` and`[4]`.
24+
25+
* The cost of the first subarray`[3,1]` is`(3 + 1 + 1 * 1) * (4 + 6) = 50`.
26+
* The cost of the second subarray`[4]` is`(3 + 1 + 4 + 1 * 2) * 6 = 60`.
27+
28+
**Example 2:**
29+
30+
**Input:** nums =[4,8,5,1,14,2,2,12,1], cost =[7,2,8,4,2,2,1,1,2], k = 7
31+
32+
**Output:** 985
33+
34+
**Explanation:**
35+
36+
The minimum total cost possible can be achieved by dividing`nums` into subarrays`[4, 8, 5, 1]`,`[14, 2, 2]`, and`[12, 1]`.
37+
38+
* The cost of the first subarray`[4, 8, 5, 1]` is`(4 + 8 + 5 + 1 + 7 * 1) * (7 + 2 + 8 + 4) = 525`.
39+
* The cost of the second subarray`[14, 2, 2]` is`(4 + 8 + 5 + 1 + 14 + 2 + 2 + 7 * 2) * (2 + 2 + 1) = 250`.
40+
* The cost of the third subarray`[12, 1]` is`(4 + 8 + 5 + 1 + 14 + 2 + 2 + 12 + 1 + 7 * 3) * (1 + 2) = 210`.
41+
42+
**Constraints:**
43+
44+
*`1 <= nums.length <= 1000`
45+
*`cost.length == nums.length`
46+
*`1 <= nums[i], cost[i] <= 1000`
47+
*`1 <= k <= 1000`
Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
packageg3501_3600.s3501_maximize_active_section_with_trade_ii;
2+
3+
// #Hard #Array #String #Binary_Search #Segment_Tree
4+
// #2025_04_01_Time_256_ms_(63.33%)_Space_106.80_MB_(56.67%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
importjava.util.List;
9+
10+
publicclassSolution {
11+
privatestaticfinalintINF = (int)1e9;
12+
privatestaticfinalintNEG_INF = -INF;
13+
14+
publicList<Integer>maxActiveSectionsAfterTrade(Strings,int[][]queries) {
15+
intn =s.length();
16+
intactiveCount =0;
17+
for (charch :s.toCharArray()) {
18+
if (ch =='1') {
19+
activeCount++;
20+
}
21+
}
22+
List<int[]>segments =newArrayList<>();
23+
intstart =0;
24+
for (inti =0;i <n;i++) {
25+
if (i ==n -1 ||s.charAt(i) !=s.charAt(i +1)) {
26+
segments.add(newint[] {start,i -start +1});
27+
start =i +1;
28+
}
29+
}
30+
intsegmentCount =segments.size();
31+
intmaxPower =20;
32+
int[][]rmq =newint[maxPower][segmentCount];
33+
for (inti =0;i <maxPower;i++) {
34+
Arrays.fill(rmq[i],NEG_INF);
35+
}
36+
for (inti =0;i <segmentCount;i++) {
37+
if (s.charAt(segments.get(i)[0]) =='0' &&i +2 <segmentCount) {
38+
rmq[0][i] =segments.get(i)[1] +segments.get(i +2)[1];
39+
}
40+
}
41+
for (intpower =1,rangeLen =2;power <maxPower;power++,rangeLen *=2) {
42+
for (inti =0,j =rangeLen -1;j <segmentCount;i++,j++) {
43+
rmq[power][i] =Math.max(rmq[power -1][i],rmq[power -1][i +rangeLen /2]);
44+
}
45+
}
46+
List<Integer>result =newArrayList<>();
47+
for (int[]query :queries) {
48+
intleft =query[0];
49+
intright =query[1];
50+
intleftIndex =binarySearch(segments,left) -1;
51+
intrightIndex =binarySearch(segments,right) -1;
52+
if (rightIndex -leftIndex +1 <=2) {
53+
result.add(activeCount);
54+
continue;
55+
}
56+
intbestIncrease =Math.max(getMaxInRange(rmq,leftIndex +1,rightIndex -3),0);
57+
bestIncrease =
58+
Math.max(
59+
bestIncrease,
60+
calculateNewSections(
61+
s,segments,left,right,leftIndex,rightIndex,leftIndex));
62+
bestIncrease =
63+
Math.max(
64+
bestIncrease,
65+
calculateNewSections(
66+
s,
67+
segments,
68+
left,
69+
right,
70+
leftIndex,
71+
rightIndex,
72+
rightIndex -2));
73+
result.add(activeCount +bestIncrease);
74+
}
75+
returnresult;
76+
}
77+
78+
privateintbinarySearch(List<int[]>segments,intkey) {
79+
intlo =0;
80+
inthi =segments.size();
81+
while (lo <hi) {
82+
intmid =lo + (hi -lo) /2;
83+
if (segments.get(mid)[0] >key) {
84+
hi =mid;
85+
}else {
86+
lo =mid +1;
87+
}
88+
}
89+
returnlo;
90+
}
91+
92+
privateintgetMaxInRange(int[][]rmq,intleft,intright) {
93+
if (left >right) {
94+
returnNEG_INF;
95+
}
96+
intpower =31 -Integer.numberOfLeadingZeros(right -left +1);
97+
returnMath.max(rmq[power][left],rmq[power][right - (1 <<power) +1]);
98+
}
99+
100+
privateintgetSegmentSize(
101+
List<int[]>segments,intleft,intright,intleftIndex,intrightIndex,inti) {
102+
if (i ==leftIndex) {
103+
returnsegments.get(leftIndex)[1] - (left -segments.get(leftIndex)[0]);
104+
}
105+
if (i ==rightIndex) {
106+
returnright -segments.get(rightIndex)[0] +1;
107+
}
108+
returnsegments.get(i)[1];
109+
}
110+
111+
privateintcalculateNewSections(
112+
Strings,
113+
List<int[]>segments,
114+
intleft,
115+
intright,
116+
intleftIndex,
117+
intrightIndex,
118+
inti) {
119+
if (i <0 ||i +2 >=segments.size() ||s.charAt(segments.get(i)[0]) =='1') {
120+
returnNEG_INF;
121+
}
122+
intsize1 =getSegmentSize(segments,left,right,leftIndex,rightIndex,i);
123+
intsize2 =getSegmentSize(segments,left,right,leftIndex,rightIndex,i +2);
124+
returnsize1 +size2;
125+
}
126+
}

0 commit comments

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