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

Commit87b2837

Browse files
authored
Added tasks 3536-3539
1 parent81c1a86 commit87b2837

File tree

13 files changed

+548
-1
lines changed

13 files changed

+548
-1
lines changed
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packageg3501_3600.s3536_maximum_product_of_two_digits;
2+
3+
// #Easy #Math #Sorting #2025_05_06_Time_1_ms_(95.82%)_Space_40.95_MB_(91.71%)
4+
5+
publicclassSolution {
6+
publicintmaxProduct(intn) {
7+
intm1 =n %10;
8+
n /=10;
9+
intm2 =n %10;
10+
n /=10;
11+
while (n >0) {
12+
inta =n %10;
13+
if (a >m1) {
14+
if (m1 >m2) {
15+
m2 =m1;
16+
}
17+
m1 =a;
18+
}else {
19+
if (a >m2) {
20+
m2 =a;
21+
}
22+
}
23+
n /=10;
24+
}
25+
returnm1 *m2;
26+
}
27+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
3536\. Maximum Product of Two Digits
2+
3+
Easy
4+
5+
You are given a positive integer`n`.
6+
7+
Return the**maximum** product of any two digits in`n`.
8+
9+
**Note:** You may use the**same** digit twice if it appears more than once in`n`.
10+
11+
**Example 1:**
12+
13+
**Input:** n = 31
14+
15+
**Output:** 3
16+
17+
**Explanation:**
18+
19+
* The digits of`n` are`[3, 1]`.
20+
* The possible products of any two digits are:`3 * 1 = 3`.
21+
* The maximum product is 3.
22+
23+
**Example 2:**
24+
25+
**Input:** n = 22
26+
27+
**Output:** 4
28+
29+
**Explanation:**
30+
31+
* The digits of`n` are`[2, 2]`.
32+
* The possible products of any two digits are:`2 * 2 = 4`.
33+
* The maximum product is 4.
34+
35+
**Example 3:**
36+
37+
**Input:** n = 124
38+
39+
**Output:** 8
40+
41+
**Explanation:**
42+
43+
* The digits of`n` are`[1, 2, 4]`.
44+
* The possible products of any two digits are:`1 * 2 = 2`,`1 * 4 = 4`,`2 * 4 = 8`.
45+
* The maximum product is 8.
46+
47+
**Constraints:**
48+
49+
* <code>10 <= n <= 10<sup>9</sup></code>
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
packageg3501_3600.s3537_fill_a_special_grid;
2+
3+
// #Medium #Array #Matrix #Divide_and_Conquer
4+
// #2025_05_06_Time_2_ms_(100.00%)_Space_87.14_MB_(16.42%)
5+
6+
publicclassSolution {
7+
publicint[][]specialGrid(intn) {
8+
if (n ==0) {
9+
returnnewint[][] {{0}};
10+
}
11+
intlen = (int)Math.pow(2,n);
12+
int[][]ans =newint[len][len];
13+
int[]num =newint[] {(int)Math.pow(2,2D *n) -1};
14+
backtrack(ans,len,len,0,0,num);
15+
returnans;
16+
}
17+
18+
privatevoidbacktrack(int[][]ans,intm,intn,intx,inty,int[]num) {
19+
if (m ==2 &&n ==2) {
20+
ans[x][y] =num[0];
21+
ans[x +1][y] =num[0] -1;
22+
ans[x +1][y +1] =num[0] -2;
23+
ans[x][y +1] =num[0] -3;
24+
num[0] -=4;
25+
return;
26+
}
27+
backtrack(ans,m /2,n /2,x,y,num);
28+
backtrack(ans,m /2,n /2,x +m /2,y,num);
29+
backtrack(ans,m /2,n /2,x +m /2,y +n /2,num);
30+
backtrack(ans,m /2,n /2,x,y +n /2,num);
31+
}
32+
}
Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
3537\. Fill a Special Grid
2+
3+
Medium
4+
5+
You are given a non-negative integer`n` representing a <code>2<sup>n</sup> x 2<sup>n</sup></code> grid. You must fill the grid with integers from 0 to <code>2<sup>2n</sup> - 1</code> to make it**special**. A grid is**special** if it satisfies**all** the following conditions:
6+
7+
* All numbers in the top-right quadrant are smaller than those in the bottom-right quadrant.
8+
* All numbers in the bottom-right quadrant are smaller than those in the bottom-left quadrant.
9+
* All numbers in the bottom-left quadrant are smaller than those in the top-left quadrant.
10+
* Each of its quadrants is also a special grid.
11+
12+
Return the**special** <code>2<sup>n</sup> x 2<sup>n</sup></code> grid.
13+
14+
**Note**: Any 1x1 grid is special.
15+
16+
**Example 1:**
17+
18+
**Input:** n = 0
19+
20+
**Output:**[[0]]
21+
22+
**Explanation:**
23+
24+
The only number that can be placed is 0, and there is only one possible position in the grid.
25+
26+
**Example 2:**
27+
28+
**Input:** n = 1
29+
30+
**Output:**[[3,0],[2,1]]
31+
32+
**Explanation:**
33+
34+
The numbers in each quadrant are:
35+
36+
* Top-right: 0
37+
* Bottom-right: 1
38+
* Bottom-left: 2
39+
* Top-left: 3
40+
41+
Since`0 < 1 < 2 < 3`, this satisfies the given constraints.
42+
43+
**Example 3:**
44+
45+
**Input:** n = 2
46+
47+
**Output:**[[15,12,3,0],[14,13,2,1],[11,8,7,4],[10,9,6,5]]
48+
49+
**Explanation:**
50+
51+
![](https://assets.leetcode.com/uploads/2025/03/05/4123example3p1drawio.png)
52+
53+
The numbers in each quadrant are:
54+
55+
* Top-right: 3, 0, 2, 1
56+
* Bottom-right: 7, 4, 6, 5
57+
* Bottom-left: 11, 8, 10, 9
58+
* Top-left: 15, 12, 14, 13
59+
*`max(3, 0, 2, 1) < min(7, 4, 6, 5)`
60+
*`max(7, 4, 6, 5) < min(11, 8, 10, 9)`
61+
*`max(11, 8, 10, 9) < min(15, 12, 14, 13)`
62+
63+
This satisfies the first three requirements. Additionally, each quadrant is also a special grid. Thus, this is a special grid.
64+
65+
**Constraints:**
66+
67+
*`0 <= n <= 10`
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
packageg3501_3600.s3538_merge_operations_for_minimum_travel_time;
2+
3+
// #Hard #Array #Dynamic_Programming #Prefix_Sum
4+
// #2025_05_06_Time_7_ms_(99.32%)_Space_45.14_MB_(87.16%)
5+
6+
@SuppressWarnings({"unused","java:S1172"})
7+
publicclassSolution {
8+
publicintminTravelTime(intl,intn,intk,int[]position,int[]time) {
9+
int[][][]dp =newint[n][k +1][k +1];
10+
for (inti =0;i <n;i++) {
11+
for (intj =0;j <=k;j++) {
12+
for (intm =0;m <=k;m++) {
13+
dp[i][j][m] =Integer.MAX_VALUE;
14+
}
15+
}
16+
}
17+
dp[0][0][0] =0;
18+
for (inti =0;i <n -1;i++) {
19+
intcurrTime =0;
20+
for (intcurr =0;curr <=k &&curr <=i;curr++) {
21+
currTime +=time[i -curr];
22+
for (intused =0;used <=k;used++) {
23+
if (dp[i][curr][used] ==Integer.MAX_VALUE) {
24+
continue;
25+
}
26+
for (intnext =0;next <=k -used &&next <=n -i -2;next++) {
27+
intnextI =i +next +1;
28+
dp[nextI][next][next +used] =
29+
Math.min(
30+
dp[nextI][next][next +used],
31+
dp[i][curr][used]
32+
+ (position[nextI] -position[i]) *currTime);
33+
}
34+
}
35+
}
36+
}
37+
intans =Integer.MAX_VALUE;
38+
for (intcurr =0;curr <=k;curr++) {
39+
ans =Math.min(ans,dp[n -1][curr][k]);
40+
}
41+
returnans;
42+
}
43+
}
Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
3538\. Merge Operations for Minimum Travel Time
2+
3+
Hard
4+
5+
You are given a straight road of length`l` km, an integer`n`, an integer`k`**,** and**two** integer arrays,`position` and`time`, each of length`n`.
6+
7+
The array`position` lists the positions (in km) of signs in**strictly** increasing order (with`position[0] = 0` and`position[n - 1] = l`).
8+
9+
Each`time[i]` represents the time (in minutes) required to travel 1 km between`position[i]` and`position[i + 1]`.
10+
11+
You**must** perform**exactly**`k` merge operations. In one merge, you can choose any**two** adjacent signs at indices`i` and`i + 1` (with`i > 0` and`i + 1 < n`) and:
12+
13+
* Update the sign at index`i + 1` so that its time becomes`time[i] + time[i + 1]`.
14+
* Remove the sign at index`i`.
15+
16+
Return the**minimum****total****travel time** (in minutes) to travel from 0 to`l` after**exactly**`k` merges.
17+
18+
**Example 1:**
19+
20+
**Input:** l = 10, n = 4, k = 1, position =[0,3,8,10], time =[5,8,3,6]
21+
22+
**Output:** 62
23+
24+
**Explanation:**
25+
26+
* Merge the signs at indices 1 and 2. Remove the sign at index 1, and change the time at index 2 to`8 + 3 = 11`.
27+
28+
* After the merge:
29+
*`position` array:`[0, 8, 10]`
30+
*`time` array:`[5, 11, 6]`
31+
32+
| Segment| Distance (km)| Time per km (min)| Segment Travel Time (min)|
33+
|-----------|---------------|-------------------|----------------------------|
34+
| 0 → 8| 8| 5| 8 × 5 = 40|
35+
| 8 → 10| 2| 11| 2 × 11 = 22|
36+
37+
38+
* Total Travel Time:`40 + 22 = 62`, which is the minimum possible time after exactly 1 merge.
39+
40+
**Example 2:**
41+
42+
**Input:** l = 5, n = 5, k = 1, position =[0,1,2,3,5], time =[8,3,9,3,3]
43+
44+
**Output:** 34
45+
46+
**Explanation:**
47+
48+
* Merge the signs at indices 1 and 2. Remove the sign at index 1, and change the time at index 2 to`3 + 9 = 12`.
49+
* After the merge:
50+
*`position` array:`[0, 2, 3, 5]`
51+
*`time` array:`[8, 12, 3, 3]`
52+
53+
| Segment| Distance (km)| Time per km (min)| Segment Travel Time (min)|
54+
|-----------|---------------|-------------------|----------------------------|
55+
| 0 → 2| 2| 8| 2 × 8 = 16|
56+
| 2 → 3| 1| 12| 1 × 12 = 12|
57+
| 3 → 5| 2| 3| 2 × 3 = 6|
58+
59+
* Total Travel Time:`16 + 12 + 6 = 34`**,** which is the minimum possible time after exactly 1 merge.
60+
61+
**Constraints:**
62+
63+
* <code>1 <= l <= 10<sup>5</sup></code>
64+
*`2 <= n <= min(l + 1, 50)`
65+
*`0 <= k <= min(n - 2, 10)`
66+
*`position.length == n`
67+
*`position[0] = 0` and`position[n - 1] = l`
68+
*`position` is sorted in strictly increasing order.
69+
*`time.length == n`
70+
*`1 <= time[i] <= 100`
71+
*`1 <= sum(time) <= 100`
Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
packageg3501_3600.s3539_find_sum_of_array_product_of_magical_sequences;
2+
3+
// #Hard #Array #Dynamic_Programming #Math #Bit_Manipulation #Bitmask #Combinatorics
4+
// #2025_05_06_Time_39_ms_(95.71%)_Space_44.58_MB_(98.57%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
privatestaticfinalintMOD =1_000_000_007;
10+
privatestaticfinalint[][]C =precomputeBinom(31);
11+
privatestaticfinalint[]P =precomputePop(31);
12+
13+
publicintmagicalSum(intm,intk,int[]nums) {
14+
intn =nums.length;
15+
long[][]pow =newlong[n][m +1];
16+
for (intj =0;j <n;j++) {
17+
pow[j][0] =1L;
18+
for (intc =1;c <=m;c++) {
19+
pow[j][c] =pow[j][c -1] *nums[j] %MOD;
20+
}
21+
}
22+
long[][][]dp =newlong[m +1][k +1][m +1];
23+
long[][][]next =newlong[m +1][k +1][m +1];
24+
dp[0][0][0] =1L;
25+
for (inti =0;i <n;i++) {
26+
for (intt =0;t <=m;t++) {
27+
for (into =0;o <=k;o++) {
28+
Arrays.fill(next[t][o],0L);
29+
}
30+
}
31+
for (intt =0;t <=m;t++) {
32+
for (into =0;o <=k;o++) {
33+
for (intc =0;c <=m;c++) {
34+
if (dp[t][o][c] ==0) {
35+
continue;
36+
}
37+
for (intcc =0;cc <=m -t;cc++) {
38+
inttotal =c +cc;
39+
if (o + (total &1) >k) {
40+
continue;
41+
}
42+
next[t +cc][o + (total &1)][total >>>1] =
43+
(next[t +cc][o + (total &1)][total >>>1]
44+
+dp[t][o][c]
45+
*C[m -t][cc]
46+
%MOD
47+
*pow[i][cc]
48+
%MOD)
49+
%MOD;
50+
}
51+
}
52+
}
53+
}
54+
long[][][]tmp =dp;
55+
dp =next;
56+
next =tmp;
57+
}
58+
longres =0;
59+
for (into =0;o <=k;o++) {
60+
for (intc =0;c <=m;c++) {
61+
if (o +P[c] ==k) {
62+
res = (res +dp[m][o][c]) %MOD;
63+
}
64+
}
65+
}
66+
return (int)res;
67+
}
68+
69+
privatestaticint[][]precomputeBinom(intmax) {
70+
int[][]res =newint[max][max];
71+
for (inti =0;i <max;i++) {
72+
res[i][0] =res[i][i] =1;
73+
for (intj =1;j <i;j++) {
74+
res[i][j] = (res[i -1][j -1] +res[i -1][j]) %MOD;
75+
}
76+
}
77+
returnres;
78+
}
79+
80+
privatestaticint[]precomputePop(intmax) {
81+
int[]res =newint[max];
82+
for (inti =1;i <max;i++) {
83+
res[i] =res[i >>1] + (i &1);
84+
}
85+
returnres;
86+
}
87+
}

0 commit comments

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