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

Commitd47efe8

Browse files
authored
Added tasks 3602-3609
1 parenta2a3beb commitd47efe8

File tree

24 files changed

+1309
-0
lines changed

24 files changed

+1309
-0
lines changed
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
packageg3601_3700.s3602_hexadecimal_and_hexatrigesimal_conversion;
2+
3+
// #Easy #String #Math #2025_07_08_Time_2_ms_(100.00%)_Space_42.19_MB_(96.97%)
4+
5+
publicclassSolution {
6+
publicStringconcatHex36(intn) {
7+
intt =n *n;
8+
intk;
9+
StringBuilderst =newStringBuilder();
10+
StringBuildertmp =newStringBuilder();
11+
while (t >0) {
12+
k =t %16;
13+
t =t /16;
14+
if (k <=9) {
15+
tmp.append((char) ('0' +k));
16+
}else {
17+
tmp.append((char) ('A' + (k -10)));
18+
}
19+
}
20+
for (inti =tmp.length() -1;i >=0;i--) {
21+
st.append(tmp.charAt(i));
22+
}
23+
tmp =newStringBuilder();
24+
t =n *n *n;
25+
while (t >0) {
26+
k =t %36;
27+
t =t /36;
28+
if (k <=9) {
29+
tmp.append((char) ('0' +k));
30+
}else {
31+
tmp.append((char) ('A' + (k -10)));
32+
}
33+
}
34+
for (inti =tmp.length() -1;i >=0;i--) {
35+
st.append(tmp.charAt(i));
36+
}
37+
returnst.toString();
38+
}
39+
}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
3602\. Hexadecimal and Hexatrigesimal Conversion
2+
3+
Easy
4+
5+
You are given an integer`n`.
6+
7+
Return the concatenation of the**hexadecimal** representation of <code>n<sup>2</sup></code> and the**hexatrigesimal** representation of <code>n<sup>3</sup></code>.
8+
9+
A**hexadecimal** number is defined as a base-16 numeral system that uses the digits`0 – 9` and the uppercase letters`A - F` to represent values from 0 to 15.
10+
11+
A**hexatrigesimal** number is defined as a base-36 numeral system that uses the digits`0 – 9` and the uppercase letters`A - Z` to represent values from 0 to 35.
12+
13+
**Example 1:**
14+
15+
**Input:** n = 13
16+
17+
**Output:** "A91P1"
18+
19+
**Explanation:**
20+
21+
* <code>n<sup>2</sup> = 13 * 13 = 169</code>. In hexadecimal, it converts to`(10 * 16) + 9 = 169`, which corresponds to`"A9"`.
22+
* <code>n<sup>3</sup> = 13 * 13 * 13 = 2197</code>. In hexatrigesimal, it converts to <code>(1 * 36<sup>2</sup>) + (25 * 36) + 1 = 2197</code>, which corresponds to`"1P1"`.
23+
* Concatenating both results gives`"A9" + "1P1" = "A91P1"`.
24+
25+
**Example 2:**
26+
27+
**Input:** n = 36
28+
29+
**Output:** "5101000"
30+
31+
**Explanation:**
32+
33+
* <code>n<sup>2</sup> = 36 * 36 = 1296</code>. In hexadecimal, it converts to <code>(5 * 16<sup>2</sup>) + (1 * 16) + 0 = 1296</code>, which corresponds to`"510"`.
34+
* <code>n<sup>3</sup> = 36 * 36 * 36 = 46656</code>. In hexatrigesimal, it converts to <code>(1 * 36<sup>3</sup>) + (0 * 36<sup>2</sup>) + (0 * 36) + 0 = 46656</code>, which corresponds to`"1000"`.
35+
* Concatenating both results gives`"510" + "1000" = "5101000"`.
36+
37+
**Constraints:**
38+
39+
*`1 <= n <= 1000`
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
packageg3601_3700.s3603_minimum_cost_path_with_alternating_directions_ii;
2+
3+
// #Medium #Array #Dynamic_Programming #Matrix
4+
// #2025_07_08_Time_6_ms_(100.00%)_Space_64.48_MB_(99.27%)
5+
6+
publicclassSolution {
7+
publiclongminCost(intm,intn,int[][]waitCost) {
8+
long[]dp =newlong[n];
9+
dp[0] =1L;
10+
for (intj =1;j <n;j++) {
11+
longentry =j +1L;
12+
longwait =waitCost[0][j];
13+
dp[j] =dp[j -1] +entry +wait;
14+
}
15+
for (inti =1;i <m;i++) {
16+
longentry00 =i +1L;
17+
longwait00 =waitCost[i][0];
18+
dp[0] =dp[0] +entry00 +wait00;
19+
for (intj =1;j <n;j++) {
20+
longentry = (long) (i +1) * (j +1);
21+
longwait =waitCost[i][j];
22+
longfromAbove =dp[j];
23+
longfromLeft =dp[j -1];
24+
dp[j] =Math.min(fromAbove,fromLeft) +entry +wait;
25+
}
26+
}
27+
returndp[n -1] -waitCost[m -1][n -1];
28+
}
29+
}
Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
3603\. Minimum Cost Path with Alternating Directions II
2+
3+
Medium
4+
5+
You are given two integers`m` and`n` representing the number of rows and columns of a grid, respectively.
6+
7+
The cost to enter cell`(i, j)` is defined as`(i + 1) * (j + 1)`.
8+
9+
You are also given a 2D integer array`waitCost` where`waitCost[i][j]` defines the cost to**wait** on that cell.
10+
11+
You start at cell`(0, 0)` at second 1.
12+
13+
At each step, you follow an alternating pattern:
14+
15+
* On**odd-numbered** seconds, you must move**right** or**down** to an**adjacent** cell, paying its entry cost.
16+
* On**even-numbered** seconds, you must**wait** in place, paying`waitCost[i][j]`.
17+
18+
Return the**minimum** total cost required to reach`(m - 1, n - 1)`.
19+
20+
**Example 1:**
21+
22+
**Input:** m = 1, n = 2, waitCost =[[1,2]]
23+
24+
**Output:** 3
25+
26+
**Explanation:**
27+
28+
The optimal path is:
29+
30+
* Start at cell`(0, 0)` at second 1 with entry cost`(0 + 1) * (0 + 1) = 1`.
31+
***Second 1**: Move right to cell`(0, 1)` with entry cost`(0 + 1) * (1 + 1) = 2`.
32+
33+
Thus, the total cost is`1 + 2 = 3`.
34+
35+
**Example 2:**
36+
37+
**Input:** m = 2, n = 2, waitCost =[[3,5],[2,4]]
38+
39+
**Output:** 9
40+
41+
**Explanation:**
42+
43+
The optimal path is:
44+
45+
* Start at cell`(0, 0)` at second 1 with entry cost`(0 + 1) * (0 + 1) = 1`.
46+
***Second 1**: Move down to cell`(1, 0)` with entry cost`(1 + 1) * (0 + 1) = 2`.
47+
***Second 2**: Wait at cell`(1, 0)`, paying`waitCost[1][0] = 2`.
48+
***Second 3**: Move right to cell`(1, 1)` with entry cost`(1 + 1) * (1 + 1) = 4`.
49+
50+
Thus, the total cost is`1 + 2 + 2 + 4 = 9`.
51+
52+
**Example 3:**
53+
54+
**Input:** m = 2, n = 3, waitCost =[[6,1,4],[3,2,5]]
55+
56+
**Output:** 16
57+
58+
**Explanation:**
59+
60+
The optimal path is:
61+
62+
* Start at cell`(0, 0)` at second 1 with entry cost`(0 + 1) * (0 + 1) = 1`.
63+
***Second 1**: Move right to cell`(0, 1)` with entry cost`(0 + 1) * (1 + 1) = 2`.
64+
***Second 2**: Wait at cell`(0, 1)`, paying`waitCost[0][1] = 1`.
65+
***Second 3**: Move down to cell`(1, 1)` with entry cost`(1 + 1) * (1 + 1) = 4`.
66+
***Second 4**: Wait at cell`(1, 1)`, paying`waitCost[1][1] = 2`.
67+
***Second 5**: Move right to cell`(1, 2)` with entry cost`(1 + 1) * (2 + 1) = 6`.
68+
69+
Thus, the total cost is`1 + 2 + 1 + 4 + 2 + 6 = 16`.
70+
71+
**Constraints:**
72+
73+
* <code>1 <= m, n <= 10<sup>5</sup></code>
74+
* <code>2 <= m * n <= 10<sup>5</sup></code>
75+
*`waitCost.length == m`
76+
*`waitCost[0].length == n`
77+
* <code>0 <= waitCost[i][j] <= 10<sup>5</sup></code>
Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,106 @@
1+
packageg3601_3700.s3604_minimum_time_to_reach_destination_in_directed_graph;
2+
3+
// #Medium #Heap_Priority_Queue #Graph #Shortest_Path
4+
// #2025_07_08_Time_5_ms_(100.00%)_Space_102.82_MB_(98.27%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
privatestaticfinalintINF =Integer.MAX_VALUE;
10+
11+
publicintminTime(intn,int[][]edges) {
12+
int[]head =newint[n];
13+
int[]to =newint[edges.length];
14+
int[]start =newint[edges.length];
15+
int[]end =newint[edges.length];
16+
int[]next =newint[edges.length];
17+
Arrays.fill(head, -1);
18+
for (inti =0;i <edges.length;i++) {
19+
intu =edges[i][0];
20+
to[i] =edges[i][1];
21+
start[i] =edges[i][2];
22+
end[i] =edges[i][3];
23+
next[i] =head[u];
24+
head[u] =i;
25+
}
26+
int[]heap =newint[n];
27+
int[]time =newint[n];
28+
int[]pos =newint[n];
29+
boolean[]visited =newboolean[n];
30+
intsize =0;
31+
for (inti =0;i <n;i++) {
32+
time[i] =INF;
33+
pos[i] = -1;
34+
}
35+
time[0] =0;
36+
heap[size] =0;
37+
pos[0] =0;
38+
size++;
39+
while (size >0) {
40+
intu =heap[0];
41+
heap[0] =heap[--size];
42+
pos[heap[0]] =0;
43+
heapifyDown(heap,time,pos,size,0);
44+
if (visited[u]) {
45+
continue;
46+
}
47+
visited[u] =true;
48+
if (u ==n -1) {
49+
returntime[u];
50+
}
51+
for (inte =head[u];e != -1;e =next[e]) {
52+
intv =to[e];
53+
intt0 =time[u];
54+
if (t0 >end[e]) {
55+
continue;
56+
}
57+
intarrival =Math.max(t0,start[e]) +1;
58+
if (arrival <time[v]) {
59+
time[v] =arrival;
60+
if (pos[v] == -1) {
61+
heap[size] =v;
62+
pos[v] =size;
63+
heapifyUp(heap,time,pos,size);
64+
size++;
65+
}else {
66+
heapifyUp(heap,time,pos,pos[v]);
67+
}
68+
}
69+
}
70+
}
71+
return -1;
72+
}
73+
74+
privatevoidheapifyUp(int[]heap,int[]time,int[]pos,inti) {
75+
while (i >0) {
76+
intp = (i -1) /2;
77+
if (time[heap[p]] <=time[heap[i]]) {
78+
break;
79+
}
80+
swap(heap,pos,i,p);
81+
i =p;
82+
}
83+
}
84+
85+
privatevoidheapifyDown(int[]heap,int[]time,int[]pos,intsize,inti) {
86+
while (2 *i +1 <size) {
87+
intj =2 *i +1;
88+
if (j +1 <size &&time[heap[j +1]] <time[heap[j]]) {
89+
j++;
90+
}
91+
if (time[heap[i]] <=time[heap[j]]) {
92+
break;
93+
}
94+
swap(heap,pos,i,j);
95+
i =j;
96+
}
97+
}
98+
99+
privatevoidswap(int[]heap,int[]pos,inti,intj) {
100+
inttmp =heap[i];
101+
heap[i] =heap[j];
102+
heap[j] =tmp;
103+
pos[heap[i]] =i;
104+
pos[heap[j]] =j;
105+
}
106+
}
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
3604\. Minimum Time to Reach Destination in Directed Graph
2+
3+
Medium
4+
5+
You are given an integer`n` and a**directed** graph with`n` nodes labeled from 0 to`n - 1`. This is represented by a 2D array`edges`, where <code>edges[i] =[u<sub>i</sub>, v<sub>i</sub>, start<sub>i</sub>, end<sub>i</sub>]</code> indicates an edge from node <code>u<sub>i</sub></code> to <code>v<sub>i</sub></code> that can**only** be used at any integer time`t` such that <code>start<sub>i</sub> <= t <= end<sub>i</sub></code>.
6+
7+
You start at node 0 at time 0.
8+
9+
In one unit of time, you can either:
10+
11+
* Wait at your current node without moving, or
12+
* Travel along an outgoing edge from your current node if the current time`t` satisfies <code>start<sub>i</sub> <= t <= end<sub>i</sub></code>.
13+
14+
Return the**minimum** time required to reach node`n - 1`. If it is impossible, return`-1`.
15+
16+
**Example 1:**
17+
18+
**Input:** n = 3, edges =[[0,1,0,1],[1,2,2,5]]
19+
20+
**Output:** 3
21+
22+
**Explanation:**
23+
24+
![](https://assets.leetcode.com/uploads/2025/06/05/screenshot-2025-06-06-at-004535.png)
25+
26+
The optimal path is:
27+
28+
* At time`t = 0`, take the edge`(0 → 1)` which is available from 0 to 1. You arrive at node 1 at time`t = 1`, then wait until`t = 2`.
29+
* At time```t = `2````, take the edge`(1 → 2)` which is available from 2 to 5. You arrive at node 2 at time 3.
30+
31+
Hence, the minimum time to reach node 2 is 3.
32+
33+
**Example 2:**
34+
35+
**Input:** n = 4, edges =[[0,1,0,3],[1,3,7,8],[0,2,1,5],[2,3,4,7]]
36+
37+
**Output:** 5
38+
39+
**Explanation:**
40+
41+
![](https://assets.leetcode.com/uploads/2025/06/05/screenshot-2025-06-06-at-004757.png)
42+
43+
The optimal path is:
44+
45+
* Wait at node 0 until time`t = 1`, then take the edge`(0 → 2)` which is available from 1 to 5. You arrive at node 2 at`t = 2`.
46+
* Wait at node 2 until time`t = 4`, then take the edge`(2 → 3)` which is available from 4 to 7. You arrive at node 3 at`t = 5`.
47+
48+
Hence, the minimum time to reach node 3 is 5.
49+
50+
**Example 3:**
51+
52+
**Input:** n = 3, edges =[[1,0,1,3],[1,2,3,5]]
53+
54+
**Output:**\-1
55+
56+
**Explanation:**
57+
58+
![](https://assets.leetcode.com/uploads/2025/06/05/screenshot-2025-06-06-at-004914.png)
59+
60+
* Since there is no outgoing edge from node 0, it is impossible to reach node 2. Hence, the output is -1.
61+
62+
**Constraints:**
63+
64+
* <code>1 <= n <= 10<sup>5</sup></code>
65+
* <code>0 <= edges.length <= 10<sup>5</sup></code>
66+
* <code>edges[i] ==[u<sub>i</sub>, v<sub>i</sub>, start<sub>i</sub>, end<sub>i</sub>]</code>
67+
* <code>0 <= u<sub>i</sub>, v<sub>i</sub> <= n - 1</code>
68+
* <code>u<sub>i</sub> != v<sub>i</sub></code>
69+
* <code>0 <= start<sub>i</sub> <= end<sub>i</sub> <= 10<sup>9</sup></code>

0 commit comments

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