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

Commitbd92171

Browse files
authored
Added tasks 3722-3729
1 parent3777781 commitbd92171

File tree

24 files changed

+894
-0
lines changed

24 files changed

+894
-0
lines changed
Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
packageg3701_3800.s3722_lexicographically_smallest_string_after_reverse;
2+
3+
// #Medium #Binary_Search #Two_Pointers #Enumeration #Biweekly_Contest_168
4+
// #2025_10_29_Time_7_ms_(100.00%)_Space_45.70_MB_(100.00%)
5+
6+
publicclassSolution {
7+
publicStringlexSmallest(Strings) {
8+
intn =s.length();
9+
char[]arr =s.toCharArray();
10+
char[]best =arr.clone();
11+
// Check all reverse first k operations
12+
for (intk =1;k <=n;k++) {
13+
if (isBetterReverseFirstK(arr,k,best)) {
14+
updateBestReverseFirstK(arr,k,best);
15+
}
16+
}
17+
// Check all reverse last k operations
18+
for (intk =1;k <=n;k++) {
19+
if (isBetterReverseLastK(arr,k,best)) {
20+
updateBestReverseLastK(arr,k,best);
21+
}
22+
}
23+
returnnewString(best);
24+
}
25+
26+
privatebooleanisBetterReverseFirstK(char[]arr,intk,char[]best) {
27+
for (inti =0;i <arr.length;i++) {
28+
charcurrentChar = (i <k) ?arr[k -1 -i] :arr[i];
29+
if (currentChar <best[i]) {
30+
returntrue;
31+
}
32+
if (currentChar >best[i]) {
33+
returnfalse;
34+
}
35+
}
36+
returnfalse;
37+
}
38+
39+
privatebooleanisBetterReverseLastK(char[]arr,intk,char[]best) {
40+
intn =arr.length;
41+
for (inti =0;i <n;i++) {
42+
charcurrentChar = (i <n -k) ?arr[i] :arr[n -1 - (i - (n -k))];
43+
if (currentChar <best[i]) {
44+
returntrue;
45+
}
46+
if (currentChar >best[i]) {
47+
returnfalse;
48+
}
49+
}
50+
returnfalse;
51+
}
52+
53+
privatevoidupdateBestReverseFirstK(char[]arr,intk,char[]best) {
54+
for (inti =0;i <k;i++) {
55+
best[i] =arr[k -1 -i];
56+
}
57+
if (arr.length -k >=0) {
58+
System.arraycopy(arr,k,best,k,arr.length -k);
59+
}
60+
}
61+
62+
privatevoidupdateBestReverseLastK(char[]arr,intk,char[]best) {
63+
intn =arr.length;
64+
if (n -k >=0) {
65+
System.arraycopy(arr,0,best,0,n -k);
66+
}
67+
for (inti =0;i <k;i++) {
68+
best[n -k +i] =arr[n -1 -i];
69+
}
70+
}
71+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
3722\. Lexicographically Smallest String After Reverse
2+
3+
Medium
4+
5+
You are given a string`s` of length`n` consisting of lowercase English letters.
6+
7+
You must perform**exactly** one operation by choosing any integer`k` such that`1 <= k <= n` and either:
8+
9+
* reverse the**first**`k` characters of`s`, or
10+
* reverse the**last**`k` characters of`s`.
11+
12+
Return the**lexicographically smallest** string that can be obtained after**exactly** one such operation.
13+
14+
A string`a` is**lexicographically smaller** than a string`b` if, at the first position where they differ,`a` has a letter that appears earlier in the alphabet than the corresponding letter in`b`. If the first`min(a.length, b.length)` characters are the same, then the shorter string is considered lexicographically smaller.
15+
16+
**Example 1:**
17+
18+
**Input:** s = "dcab"
19+
20+
**Output:** "acdb"
21+
22+
**Explanation:**
23+
24+
* Choose`k = 3`, reverse the first 3 characters.
25+
* Reverse`"dca"` to`"acd"`, resulting string`s = "acdb"`, which is the lexicographically smallest string achievable.
26+
27+
**Example 2:**
28+
29+
**Input:** s = "abba"
30+
31+
**Output:** "aabb"
32+
33+
**Explanation:**
34+
35+
* Choose`k = 3`, reverse the last 3 characters.
36+
* Reverse`"bba"` to`"abb"`, so the resulting string is`"aabb"`, which is the lexicographically smallest string achievable.
37+
38+
**Example 3:**
39+
40+
**Input:** s = "zxy"
41+
42+
**Output:** "xzy"
43+
44+
**Explanation:**
45+
46+
* Choose`k = 2`, reverse the first 2 characters.
47+
* Reverse`"zx"` to`"xz"`, so the resulting string is`"xzy"`, which is the lexicographically smallest string achievable.
48+
49+
**Constraints:**
50+
51+
*`1 <= n == s.length <= 1000`
52+
*`s` consists of lowercase English letters.
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
packageg3701_3800.s3723_maximize_sum_of_squares_of_digits;
2+
3+
// #Medium #Math #Greedy #Biweekly_Contest_168
4+
// #2025_10_29_Time_14_ms_(98.69%)_Space_46.36_MB_(47.20%)
5+
6+
publicclassSolution {
7+
publicStringmaxSumOfSquares(intplaces,intsum) {
8+
Stringans ="";
9+
intnines =sum /9;
10+
if (places <nines) {
11+
returnans;
12+
}elseif (places ==nines) {
13+
intremSum =sum -nines *9;
14+
if (remSum >0) {
15+
returnans;
16+
}
17+
ans ="9".repeat(nines);
18+
}else {
19+
intremSum =sum -nines *9;
20+
ans ="9".repeat(nines) +remSum;
21+
intextra =places -ans.length();
22+
if (extra >0) {
23+
ans =ans + ("0".repeat(extra));
24+
}
25+
}
26+
returnans;
27+
}
28+
}
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
3723\. Maximize Sum of Squares of Digits
2+
3+
Medium
4+
5+
You are given two**positive** integers`num` and`sum`.
6+
7+
A positive integer`n` is**good** if it satisfies both of the following:
8+
9+
* The number of digits in`n` is**exactly**`num`.
10+
* The sum of digits in`n` is**exactly**`sum`.
11+
12+
The**score** of a**good** integer`n` is the sum of the squares of digits in`n`.
13+
14+
Return a**string** denoting the**good** integer`n` that achieves the**maximum****score**. If there are multiple possible integers, return the**maximum** one. If no such integer exists, return an empty string.
15+
16+
**Example 1:**
17+
18+
**Input:** num = 2, sum = 3
19+
20+
**Output:** "30"
21+
22+
**Explanation:**
23+
24+
There are 3 good integers: 12, 21, and 30.
25+
26+
* The score of 12 is <code>1<sup>2</sup> + 2<sup>2</sup> = 5</code>.
27+
* The score of 21 is <code>2<sup>2</sup> + 1<sup>2</sup> = 5</code>.
28+
* The score of 30 is <code>3<sup>2</sup> + 0<sup>2</sup> = 9</code>.
29+
30+
The maximum score is 9, which is achieved by the good integer 30. Therefore, the answer is`"30"`.
31+
32+
**Example 2:**
33+
34+
**Input:** num = 2, sum = 17
35+
36+
**Output:** "98"
37+
38+
**Explanation:**
39+
40+
There are 2 good integers: 89 and 98.
41+
42+
* The score of 89 is <code>8<sup>2</sup> + 9<sup>2</sup> = 145</code>.
43+
* The score of 98 is <code>9<sup>2</sup> + 8<sup>2</sup> = 145</code>.
44+
45+
The maximum score is 145. The maximum good integer that achieves this score is 98. Therefore, the answer is`"98"`.
46+
47+
**Example 3:**
48+
49+
**Input:** num = 1, sum = 10
50+
51+
**Output:** ""
52+
53+
**Explanation:**
54+
55+
There are no integers that have exactly 1 digit and whose digits sum to 10. Therefore, the answer is`""`.
56+
57+
**Constraints:**
58+
59+
* <code>1 <= num <= 2 * 10<sup>5</sup></code>
60+
* <code>1 <= sum <= 2 * 10<sup>6</sup></code>
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
packageg3701_3800.s3724_minimum_operations_to_transform_array;
2+
3+
// #Medium #Array #Greedy #Biweekly_Contest_168
4+
// #2025_10_29_Time_2_ms_(100.00%)_Space_61.71_MB_(16.98%)
5+
6+
publicclassSolution {
7+
publiclongminOperations(int[]nums1,int[]nums2) {
8+
intn =nums1.length;
9+
intlast =nums2[n];
10+
longsteps =1;
11+
longminDiffFromLast =Long.MAX_VALUE;
12+
for (inti =0;i <n;i++) {
13+
intmin =Math.min(nums1[i],nums2[i]);
14+
intmax =Math.max(nums1[i],nums2[i]);
15+
steps +=Math.abs(max -min);
16+
if (minDiffFromLast >0) {
17+
if (min <=last &&last <=max) {
18+
minDiffFromLast =0;
19+
}else {
20+
minDiffFromLast =
21+
Math.min(
22+
minDiffFromLast,
23+
Math.min(Math.abs(min -last),Math.abs(max -last)));
24+
}
25+
}
26+
}
27+
returnsteps +minDiffFromLast;
28+
}
29+
}
Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
3724\. Minimum Operations to Transform Array
2+
3+
Medium
4+
5+
You are given two integer arrays`nums1` of length`n` and`nums2` of length`n + 1`.
6+
7+
You want to transform`nums1` into`nums2` using the**minimum** number of operations.
8+
9+
You may perform the following operations**any** number of times, each time choosing an index`i`:
10+
11+
***Increase**`nums1[i]` by 1.
12+
***Decrease**`nums1[i]` by 1.
13+
***Append**`nums1[i]` to the**end** of the array.
14+
15+
Return the**minimum** number of operations required to transform`nums1` into`nums2`.
16+
17+
**Example 1:**
18+
19+
**Input:** nums1 =[2,8], nums2 =[1,7,3]
20+
21+
**Output:** 4
22+
23+
**Explanation:**
24+
25+
| Step|`i`| Operation|`nums1[i]`| Updated`nums1`|
26+
|------|------|------------|-------------|----------------|
27+
| 1| 0| Append| -|[2, 8, 2]|
28+
| 2| 0| Decrement| Decreases to 1|[1, 8, 2]|
29+
| 3| 1| Decrement| Decreases to 7|[1, 7, 2]|
30+
| 4| 2| Increment| Increases to 3|[1, 7, 3]|
31+
32+
Thus, after 4 operations`nums1` is transformed into`nums2`.
33+
34+
**Example 2:**
35+
36+
**Input:** nums1 =[1,3,6], nums2 =[2,4,5,3]
37+
38+
**Output:** 4
39+
40+
**Explanation:**
41+
42+
| Step|`i`| Operation|`nums1[i]`| Updated`nums1`|
43+
|------|------|------------|-------------|----------------|
44+
| 1| 1| Append| -|[1, 3, 6, 3]|
45+
| 2| 0| Increment| Increases to 2|[2, 3, 6, 3]|
46+
| 3| 1| Increment| Increases to 4|[2, 4, 6, 3]|
47+
| 4| 2| Decrement| Decreases to 5|[2, 4, 5, 3]|
48+
49+
Thus, after 4 operations`nums1` is transformed into`nums2`.
50+
51+
**Example 3:**
52+
53+
**Input:** nums1 =[2], nums2 =[3,4]
54+
55+
**Output:** 3
56+
57+
**Explanation:**
58+
59+
| Step|`i`| Operation|`nums1[i]`| Updated`nums1`|
60+
|------|------|------------|-------------|----------------|
61+
| 1| 0| Increment| Increases to 3|[3]|
62+
| 2| 0| Append| -|[3, 3]|
63+
| 3| 1| Increment| Increases to 4|[3, 4]|
64+
65+
Thus, after 3 operations`nums1` is transformed into`nums2`.
66+
67+
**Constraints:**
68+
69+
* <code>1 <= n == nums1.length <= 10<sup>5</sup></code>
70+
*`nums2.length == n + 1`
71+
* <code>1 <= nums1[i], nums2[i] <= 10<sup>5</sup></code>
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
packageg3701_3800.s3725_count_ways_to_choose_coprime_integers_from_rows;
2+
3+
// #Hard #Array #Dynamic_Programming #Math #Matrix #Number_Theory #Combinatorics
4+
// #Biweekly_Contest_168 #2025_10_29_Time_31_ms_(94.07%)_Space_47.74_MB_(49.21%)
5+
6+
importjava.util.HashMap;
7+
importjava.util.Map;
8+
9+
publicclassSolution {
10+
privatestaticfinalintMOD =1_000_000_007;
11+
12+
publicintcountCoprime(int[][]mat) {
13+
intm =mat.length;
14+
intn =mat[0].length;
15+
intmaxVal =0;
16+
for (int[]ints :mat) {
17+
for (intj =0;j <n;j++) {
18+
maxVal =Math.max(maxVal,ints[j]);
19+
}
20+
}
21+
Map<Integer,Long>gcdWays =newHashMap<>();
22+
for (intg =maxVal;g >=1;g--) {
23+
longways =countWaysWithDivisor(mat,g,m,n);
24+
if (ways >0) {
25+
for (intmultiple =2 *g;multiple <=maxVal;multiple +=g) {
26+
if (gcdWays.containsKey(multiple)) {
27+
ways = (ways -gcdWays.get(multiple) +MOD) %MOD;
28+
}
29+
}
30+
gcdWays.put(g,ways);
31+
}
32+
}
33+
returngcdWays.getOrDefault(1,0L).intValue();
34+
}
35+
36+
privatelongcountWaysWithDivisor(int[][]matrix,intdivisor,introws,intcols) {
37+
longtotalWays =1;
38+
for (introw =0;row <rows;row++) {
39+
intvalidChoices =0;
40+
for (intcol =0;col <cols;col++) {
41+
if (matrix[row][col] %divisor ==0) {
42+
validChoices++;
43+
}
44+
}
45+
if (validChoices ==0) {
46+
return0;
47+
}
48+
totalWays = (totalWays *validChoices) %MOD;
49+
}
50+
returntotalWays;
51+
}
52+
}

0 commit comments

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