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

Commitad89705

Browse files
authored
Added tasks 3648-3655
1 parent0ec11ba commitad89705

File tree

25 files changed

+1078
-1
lines changed

25 files changed

+1078
-1
lines changed
Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
packageg3601_3700.s3648_minimum_sensors_to_cover_grid;
2+
3+
// #Medium #Biweekly_Contest_163 #2025_08_17_Time_0_ms_(100.00%)_Space_41.03_MB_(100.00%)
4+
5+
publicclassSolution {
6+
publicintminSensors(intn,intm,intk) {
7+
intsize =k *2 +1;
8+
intx =n /size + (n %size ==0 ?0 :1);
9+
inty =m /size + (m %size ==0 ?0 :1);
10+
returnx *y;
11+
}
12+
}
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
3648\. Minimum Sensors to Cover Grid
2+
3+
Medium
4+
5+
You are given`n × m` grid and an integer`k`.
6+
7+
A sensor placed on cell`(r, c)` covers all cells whose**Chebyshev distance** from`(r, c)` is**at most**`k`.
8+
9+
The**Chebyshev distance** between two cells <code>(r<sub>1</sub>, c<sub>1</sub>)</code> and <code>(r<sub>2</sub>, c<sub>2</sub>)</code> is <code>max(|r<sub>1</sub> − r<sub>2</sub>|,|c<sub>1</sub> − c<sub>2</sub>|)</code>.
10+
11+
Your task is to return the**minimum** number of sensors required to cover every cell of the grid.
12+
13+
**Example 1:**
14+
15+
**Input:** n = 5, m = 5, k = 1
16+
17+
**Output:** 4
18+
19+
**Explanation:**
20+
21+
Placing sensors at positions`(0, 3)`,`(1, 0)`,`(3, 3)`, and`(4, 1)` ensures every cell in the grid is covered. Thus, the answer is 4.
22+
23+
**Example 2:**
24+
25+
**Input:** n = 2, m = 2, k = 2
26+
27+
**Output:** 1
28+
29+
**Explanation:**
30+
31+
With`k = 2`, a single sensor can cover the entire`2 * 2` grid regardless of its position. Thus, the answer is 1.
32+
33+
**Constraints:**
34+
35+
* <code>1 <= n <= 10<sup>3</sup></code>
36+
* <code>1 <= m <= 10<sup>3</sup></code>
37+
* <code>0 <= k <= 10<sup>3</sup></code>
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
packageg3601_3700.s3649_number_of_perfect_pairs;
2+
3+
// #Medium #Biweekly_Contest_163 #2025_08_17_Time_46_ms_(100.00%)_Space_60.00_MB_(100.00%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publiclongperfectPairs(int[]nums) {
9+
intn =nums.length;
10+
long[]arr =newlong[n];
11+
for (inti =0;i <n;i++) {
12+
arr[i] =Math.abs((long)nums[i]);
13+
}
14+
Arrays.sort(arr);
15+
longcnt =0;
16+
intr =0;
17+
for (inti =0;i <n;i++) {
18+
if (r <i) {
19+
r =i;
20+
}
21+
while (r +1 <n &&arr[r +1] <=2 *arr[i]) {
22+
r++;
23+
}
24+
cnt += (r -i);
25+
}
26+
returncnt;
27+
}
28+
}
Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
3649\. Number of Perfect Pairs
2+
3+
Medium
4+
5+
You are given an integer array`nums`.
6+
7+
A pair of indices`(i, j)` is called**perfect** if the following conditions are satisfied:
8+
9+
*`i < j`
10+
* Let`a = nums[i]`,`b = nums[j]`. Then:
11+
*`min(|a - b|, |a + b|) <= min(|a|, |b|)`
12+
*`max(|a - b|, |a + b|) >= max(|a|, |b|)`
13+
14+
Return the number of**distinct** perfect pairs.
15+
16+
**Note:** The absolute value`|x|` refers to the**non-negative** value of`x`.
17+
18+
**Example 1:**
19+
20+
**Input:** nums =[0,1,2,3]
21+
22+
**Output:** 2
23+
24+
**Explanation:**
25+
26+
There are 2 perfect pairs:
27+
28+
|`(i, j)`|`(a, b)`| `min(|a − b|,|a + b|)`| `min(|a|,|b|)`| `max(|a − b|,|a + b|)`| `max(|a|,|b|)`|
29+
|----------|-----------|-------------------------------------|-----------------|-------------------------------------|-----------------|
30+
| (1, 2)| (1, 2)| `min(|1 − 2|,|1 + 2|) = 1`| 1| `max(|1 − 2|,|1 + 2|) = 3`| 2|
31+
| (2, 3)| (2, 3)| `min(|2 − 3|,|2 + 3|) = 1`| 2| `max(|2 − 3|,|2 + 3|) = 5`| 3|
32+
33+
**Example 2:**
34+
35+
**Input:** nums =[-3,2,-1,4]
36+
37+
**Output:** 4
38+
39+
**Explanation:**
40+
41+
There are 4 perfect pairs:
42+
43+
|`(i, j)`|`(a, b)`| `min(|a − b|,|a + b|)`| `min(|a|,|b|)`| `max(|a − b|,|a + b|)`| `max(|a|,|b|)`|
44+
|----------|-----------|-----------------------------------------------|-----------------|-----------------------------------------------|-----------------|
45+
| (0, 1)| (-3, 2)| `min(|-3 - 2|,|-3 + 2|) = 1`| 2| `max(|-3 - 2|,|-3 + 2|) = 5`| 3|
46+
| (0, 3)| (-3, 4)| `min(|-3 - 4|,|-3 + 4|) = 1`| 3| `max(|-3 - 4|,|-3 + 4|) = 7`| 4|
47+
| (1, 2)| (2, -1)| `min(|2 - (-1)|,|2 + (-1)|) = 1`| 1| `max(|2 - (-1)|,|2 + (-1)|) = 3`| 2|
48+
| (1, 3)| (2, 4)| `min(|2 - 4|,|2 + 4|) = 2`| 2| `max(|2 - 4|,|2 + 4|) = 6`| 4|
49+
50+
**Example 3:**
51+
52+
**Input:** nums =[1,10,100,1000]
53+
54+
**Output:** 0
55+
56+
**Explanation:**
57+
58+
There are no perfect pairs. Thus, the answer is 0.
59+
60+
**Constraints:**
61+
62+
* <code>2 <= nums.length <= 10<sup>5</sup></code>
63+
* <code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
packageg3601_3700.s3650_minimum_cost_path_with_edge_reversals;
2+
3+
// #Medium #Biweekly_Contest_163 #2025_08_17_Time_51_ms_(99.85%)_Space_110.03_MB_(49.54%)
4+
5+
importjava.util.Arrays;
6+
importjava.util.PriorityQueue;
7+
8+
@SuppressWarnings({"java:S1210","java:S2234"})
9+
publicclassSolution {
10+
privatestaticfinalintINF =Integer.MAX_VALUE /2 -1;
11+
privateintcnt;
12+
privateint[]head;
13+
privateint[]next;
14+
privateint[]to;
15+
privateint[]weight;
16+
17+
privatestaticclassDistimplementsComparable<Dist> {
18+
intu;
19+
intd;
20+
21+
publicDist(intu,intd) {
22+
this.u =u;
23+
this.d =d;
24+
}
25+
26+
@Override
27+
publicintcompareTo(Disto) {
28+
returnLong.compare(d,o.d);
29+
}
30+
}
31+
32+
privatevoidinit(intn,intm) {
33+
head =newint[n];
34+
Arrays.fill(head, -1);
35+
next =newint[m];
36+
to =newint[m];
37+
weight =newint[m];
38+
}
39+
40+
privatevoidadd(intu,intv,intw) {
41+
to[cnt] =v;
42+
weight[cnt] =w;
43+
next[cnt] =head[u];
44+
head[u] =cnt++;
45+
}
46+
47+
privateintdist(ints,intt,intn) {
48+
PriorityQueue<Dist>queue =newPriorityQueue<>();
49+
int[]dist =newint[n];
50+
Arrays.fill(dist,INF);
51+
dist[s] =0;
52+
queue.add(newDist(s,dist[s]));
53+
while (!queue.isEmpty()) {
54+
Distd =queue.remove();
55+
intu =d.u;
56+
if (dist[u] <d.d) {
57+
continue;
58+
}
59+
if (u ==t) {
60+
returndist[t];
61+
}
62+
for (inti =head[u];i != -1;i =next[i]) {
63+
intv =to[i];
64+
intw =weight[i];
65+
if (dist[v] >dist[u] +w) {
66+
dist[v] =dist[u] +w;
67+
queue.add(newDist(v,dist[v]));
68+
}
69+
}
70+
}
71+
returnINF;
72+
}
73+
74+
publicintminCost(intn,int[][]edges) {
75+
intm =edges.length;
76+
init(n,2 *m);
77+
for (int[]edge :edges) {
78+
intu =edge[0];
79+
intv =edge[1];
80+
intw =edge[2];
81+
add(u,v,w);
82+
add(v,u,2 *w);
83+
}
84+
intans =dist(0,n -1,n);
85+
returnans ==INF ? -1 :ans;
86+
}
87+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
3650\. Minimum Cost Path with Edge Reversals
2+
3+
Medium
4+
5+
You are given a directed, weighted graph with`n` nodes labeled from 0 to`n - 1`, and an array`edges` where <code>edges[i] =[u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>]</code> represents a directed edge from node <code>u<sub>i</sub></code> to node <code>v<sub>i</sub></code> with cost <code>w<sub>i</sub></code>.
6+
7+
Each node <code>u<sub>i</sub></code> has a switch that can be used**at most once**: when you arrive at <code>u<sub>i</sub></code> and have not yet used its switch, you may activate it on one of its incoming edges <code>v<sub>i</sub> → u<sub>i</sub></code> reverse that edge to <code>u<sub>i</sub> → v<sub>i</sub></code> and**immediately** traverse it.
8+
9+
The reversal is only valid for that single move, and using a reversed edge costs <code>2 * w<sub>i</sub></code>.
10+
11+
Return the**minimum** total cost to travel from node 0 to node`n - 1`. If it is not possible, return -1.
12+
13+
**Example 1:**
14+
15+
**Input:** n = 4, edges =[[0,1,3],[3,1,1],[2,3,4],[0,2,2]]
16+
17+
**Output:** 5
18+
19+
**Explanation:**
20+
21+
**![](https://assets.leetcode.com/uploads/2025/05/07/e1drawio.png)**
22+
23+
* Use the path`0 → 1` (cost 3).
24+
* At node 1 reverse the original edge`3 → 1` into`1 → 3` and traverse it at cost`2 * 1 = 2`.
25+
* Total cost is`3 + 2 = 5`.
26+
27+
**Example 2:**
28+
29+
**Input:** n = 4, edges =[[0,2,1],[2,1,1],[1,3,1],[2,3,3]]
30+
31+
**Output:** 3
32+
33+
**Explanation:**
34+
35+
* No reversal is needed. Take the path`0 → 2` (cost 1), then`2 → 1` (cost 1), then`1 → 3` (cost 1).
36+
* Total cost is`1 + 1 + 1 = 3`.
37+
38+
**Constraints:**
39+
40+
* <code>2 <= n <= 5 * 10<sup>4</sup></code>
41+
* <code>1 <= edges.length <= 10<sup>5</sup></code>
42+
* <code>edges[i] =[u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>]</code>
43+
* <code>0 <= u<sub>i</sub>, v<sub>i</sub> <= n - 1</code>
44+
* <code>1 <= w<sub>i</sub> <= 1000</code>
Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
packageg3601_3700.s3651_minimum_cost_path_with_teleportations;
2+
3+
// #Hard #Biweekly_Contest_163 #2025_08_17_Time_78_ms_(100.00%)_Space_45.52_MB_(97.73%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publicintminCost(int[][]grid,intk) {
9+
intn =grid.length;
10+
intm =grid[0].length;
11+
intmax = -1;
12+
int[][]dp =newint[n][m];
13+
for (inti =n -1;i >=0;i--) {
14+
for (intj =m -1;j >=0;j--) {
15+
max =Math.max(grid[i][j],max);
16+
if (i ==n -1 &&j ==m -1) {
17+
continue;
18+
}
19+
if (i ==n -1) {
20+
dp[i][j] =grid[i][j +1] +dp[i][j +1];
21+
}elseif (j ==m -1) {
22+
dp[i][j] =grid[i +1][j] +dp[i +1][j];
23+
}else {
24+
dp[i][j] =
25+
Math.min(grid[i +1][j] +dp[i +1][j],grid[i][j +1] +dp[i][j +1]);
26+
}
27+
}
28+
}
29+
int[]prev =newint[max +1];
30+
Arrays.fill(prev,Integer.MAX_VALUE);
31+
for (inti =0;i <n;i++) {
32+
for (intj =0;j <m;j++) {
33+
prev[grid[i][j]] =Math.min(prev[grid[i][j]],dp[i][j]);
34+
}
35+
}
36+
// int currcost = prev[0];
37+
for (inti =1;i <=max;i++) {
38+
prev[i] =Math.min(prev[i],prev[i -1]);
39+
}
40+
for (inttr =1;tr <=k;tr++) {
41+
for (inti =n -1;i >=0;i--) {
42+
for (intj =m -1;j >=0;j--) {
43+
if (i ==n -1 &&j ==m -1) {
44+
continue;
45+
}
46+
dp[i][j] =prev[grid[i][j]];
47+
if (i ==n -1) {
48+
dp[i][j] =Math.min(dp[i][j],grid[i][j +1] +dp[i][j +1]);
49+
}elseif (j ==m -1) {
50+
dp[i][j] =Math.min(dp[i][j],grid[i +1][j] +dp[i +1][j]);
51+
}else {
52+
dp[i][j] =Math.min(dp[i][j],grid[i +1][j] +dp[i +1][j]);
53+
dp[i][j] =Math.min(dp[i][j],grid[i][j +1] +dp[i][j +1]);
54+
}
55+
}
56+
}
57+
Arrays.fill(prev,Integer.MAX_VALUE);
58+
for (inti =0;i <n;i++) {
59+
for (intj =0;j <m;j++) {
60+
prev[grid[i][j]] =Math.min(prev[grid[i][j]],dp[i][j]);
61+
}
62+
}
63+
// int currcost = prev[0];
64+
for (inti =1;i <=max;i++) {
65+
prev[i] =Math.min(prev[i],prev[i -1]);
66+
}
67+
}
68+
returndp[0][0];
69+
}
70+
}

0 commit comments

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