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

Commit0e343eb

Browse files
authored
Added tasks 3417-3420
1 parent302f471 commit0e343eb

File tree

12 files changed

+556
-0
lines changed

12 files changed

+556
-0
lines changed
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
packageg3401_3500.s3417_zigzag_grid_traversal_with_skip;
2+
3+
// #Easy #Array #Matrix #Simulation #2025_01_15_Time_1_(100.00%)_Space_45.56_(84.25%)
4+
5+
importjava.util.ArrayList;
6+
importjava.util.List;
7+
8+
publicclassSolution {
9+
publicList<Integer>zigzagTraversal(int[][]grid) {
10+
List<Integer>ans =newArrayList<>();
11+
intm =grid.length;
12+
intn =grid[0].length;
13+
inti =0;
14+
booleanflag =true;
15+
booleanskip =false;
16+
while (i <m) {
17+
if (flag) {
18+
for (intj =0;j <n;j++) {
19+
if (!skip) {
20+
ans.add(grid[i][j]);
21+
}
22+
skip = !skip;
23+
}
24+
}else {
25+
for (intj =n -1;j >=0;j--) {
26+
if (!skip) {
27+
ans.add(grid[i][j]);
28+
}
29+
skip = !skip;
30+
}
31+
}
32+
flag = !flag;
33+
i++;
34+
}
35+
returnans;
36+
}
37+
}
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
3417\. Zigzag Grid Traversal With Skip
2+
3+
Easy
4+
5+
You are given an`m x n` 2D array`grid` of**positive** integers.
6+
7+
Your task is to traverse`grid` in a**zigzag** pattern while skipping every**alternate** cell.
8+
9+
Zigzag pattern traversal is defined as following the below actions:
10+
11+
* Start at the top-left cell`(0, 0)`.
12+
* Move_right_ within a row until the end of the row is reached.
13+
* Drop down to the next row, then traverse_left_ until the beginning of the row is reached.
14+
* Continue**alternating** between right and left traversal until every row has been traversed.
15+
16+
**Note** that you**must skip** every_alternate_ cell during the traversal.
17+
18+
Return an array of integers`result` containing,**in order**, the value of the cells visited during the zigzag traversal with skips.
19+
20+
**Example 1:**
21+
22+
**Input:** grid =[[1,2],[3,4]]
23+
24+
**Output:**[1,4]
25+
26+
**Explanation:**
27+
28+
**![](https://assets.leetcode.com/uploads/2024/11/23/4012_example0.png)**
29+
30+
**Example 2:**
31+
32+
**Input:** grid =[[2,1],[2,1],[2,1]]
33+
34+
**Output:**[2,1,2]
35+
36+
**Explanation:**
37+
38+
![](https://assets.leetcode.com/uploads/2024/11/23/4012_example1.png)
39+
40+
**Example 3:**
41+
42+
**Input:** grid =[[1,2,3],[4,5,6],[7,8,9]]
43+
44+
**Output:**[1,3,5,7,9]
45+
46+
**Explanation:**
47+
48+
![](https://assets.leetcode.com/uploads/2024/11/23/4012_example2.png)
49+
50+
**Constraints:**
51+
52+
*`2 <= n == grid.length <= 50`
53+
*`2 <= m == grid[i].length <= 50`
54+
*`1 <= grid[i][j] <= 2500`
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
packageg3401_3500.s3418_maximum_amount_of_money_robot_can_earn;
2+
3+
// #Medium #Array #Dynamic_Programming #Matrix #2025_01_15_Time_12_(99.86%)_Space_72.43_(98.47%)
4+
5+
publicclassSolution {
6+
publicintmaximumAmount(int[][]coins) {
7+
intm =coins.length;
8+
intn =coins[0].length;
9+
int[][]dp =newint[m][n];
10+
int[][]dp1 =newint[m][n];
11+
int[][]dp2 =newint[m][n];
12+
dp[0][0] =coins[0][0];
13+
for (intj =1;j <n;j++) {
14+
dp[0][j] =dp[0][j -1] +coins[0][j];
15+
}
16+
for (inti =1;i <m;i++) {
17+
dp[i][0] =dp[i -1][0] +coins[i][0];
18+
}
19+
for (inti =1;i <m;i++) {
20+
for (intj =1;j <n;j++) {
21+
dp[i][j] =Math.max(dp[i][j -1],dp[i -1][j]) +coins[i][j];
22+
}
23+
}
24+
dp1[0][0] =Math.max(coins[0][0],0);
25+
for (intj =1;j <n;j++) {
26+
dp1[0][j] =Math.max(dp[0][j -1],dp1[0][j -1] +coins[0][j]);
27+
}
28+
for (inti =1;i <m;i++) {
29+
dp1[i][0] =Math.max(dp[i -1][0],dp1[i -1][0] +coins[i][0]);
30+
}
31+
for (inti =1;i <m;i++) {
32+
for (intj =1;j <n;j++) {
33+
dp1[i][j] =
34+
Math.max(
35+
Math.max(dp[i][j -1],dp[i -1][j]),
36+
Math.max(dp1[i][j -1],dp1[i -1][j]) +coins[i][j]);
37+
}
38+
}
39+
dp2[0][0] =Math.max(coins[0][0],0);
40+
for (intj =1;j <n;j++) {
41+
dp2[0][j] =Math.max(dp1[0][j -1],dp2[0][j -1] +coins[0][j]);
42+
}
43+
for (inti =1;i <m;i++) {
44+
dp2[i][0] =Math.max(dp1[i -1][0],dp2[i -1][0] +coins[i][0]);
45+
}
46+
for (inti =1;i <m;i++) {
47+
for (intj =1;j <n;j++) {
48+
dp2[i][j] =
49+
Math.max(
50+
Math.max(dp1[i][j -1],dp1[i -1][j]),
51+
Math.max(dp2[i][j -1],dp2[i -1][j]) +coins[i][j]);
52+
}
53+
}
54+
returndp2[m -1][n -1];
55+
}
56+
}
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
3418\. Maximum Amount of Money Robot Can Earn
2+
3+
Medium
4+
5+
You are given an`m x n` grid. A robot starts at the top-left corner of the grid`(0, 0)` and wants to reach the bottom-right corner`(m - 1, n - 1)`. The robot can move either right or down at any point in time.
6+
7+
The grid contains a value`coins[i][j]` in each cell:
8+
9+
* If`coins[i][j] >= 0`, the robot gains that many coins.
10+
* If`coins[i][j] < 0`, the robot encounters a robber, and the robber steals the**absolute** value of`coins[i][j]` coins.
11+
12+
The robot has a special ability to**neutralize robbers** in at most**2 cells** on its path, preventing them from stealing coins in those cells.
13+
14+
**Note:** The robot's total coins can be negative.
15+
16+
Return the**maximum** profit the robot can gain on the route.
17+
18+
**Example 1:**
19+
20+
**Input:** coins =[[0,1,-1],[1,-2,3],[2,-3,4]]
21+
22+
**Output:** 8
23+
24+
**Explanation:**
25+
26+
An optimal path for maximum coins is:
27+
28+
1. Start at`(0, 0)` with`0` coins (total coins =`0`).
29+
2. Move to`(0, 1)`, gaining`1` coin (total coins =`0 + 1 = 1`).
30+
3. Move to`(1, 1)`, where there's a robber stealing`2` coins. The robot uses one neutralization here, avoiding the robbery (total coins =`1`).
31+
4. Move to`(1, 2)`, gaining`3` coins (total coins =`1 + 3 = 4`).
32+
5. Move to`(2, 2)`, gaining`4` coins (total coins =`4 + 4 = 8`).
33+
34+
**Example 2:**
35+
36+
**Input:** coins =[[10,10,10],[10,10,10]]
37+
38+
**Output:** 40
39+
40+
**Explanation:**
41+
42+
An optimal path for maximum coins is:
43+
44+
1. Start at`(0, 0)` with`10` coins (total coins =`10`).
45+
2. Move to`(0, 1)`, gaining`10` coins (total coins =`10 + 10 = 20`).
46+
3. Move to`(0, 2)`, gaining another`10` coins (total coins =`20 + 10 = 30`).
47+
4. Move to`(1, 2)`, gaining the final`10` coins (total coins =`30 + 10 = 40`).
48+
49+
**Constraints:**
50+
51+
*`m == coins.length`
52+
*`n == coins[i].length`
53+
*`1 <= m, n <= 500`
54+
*`-1000 <= coins[i][j] <= 1000`
Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
packageg3401_3500.s3419_minimize_the_maximum_edge_weight_of_graph;
2+
3+
// #Medium #Binary_Search #Graph #Shortest_Path #Depth_First_Search #Breadth_First_Search
4+
// #2025_01_15_Time_64_(99.28%)_Space_110.17_(57.63%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
importjava.util.LinkedList;
9+
importjava.util.Queue;
10+
11+
@SuppressWarnings({"unchecked","unused","java:S1172"})
12+
publicclassSolution {
13+
privateArrayList<ArrayList<Pair>>revadj;
14+
15+
privatestaticclassPair {
16+
intnode;
17+
intweight;
18+
19+
publicPair(intnode,intweight) {
20+
this.node =node;
21+
this.weight =weight;
22+
}
23+
}
24+
25+
publicintminMaxWeight(intn,int[][]edges,intthreshold) {
26+
ArrayList<ArrayList<Pair>>adj =newArrayList<>();
27+
revadj =newArrayList<>();
28+
for (inti =0;i <=n +1;i++) {
29+
adj.add(newArrayList<>());
30+
revadj.add(newArrayList<>());
31+
}
32+
for (int[]edge :edges) {
33+
intu =edge[0];
34+
intv =edge[1];
35+
intwt =edge[2];
36+
adj.get(u).add(newPair(v,wt));
37+
revadj.get(v).add(newPair(u,wt));
38+
}
39+
if (!check(n)) {
40+
return -1;
41+
}
42+
int[]dist =newint[n +1];
43+
Arrays.fill(dist, (int) (1e9));
44+
dist[0] =0;
45+
Queue<Pair>q =newLinkedList<>();
46+
q.offer(newPair(0,0));
47+
while (!q.isEmpty()) {
48+
intu =q.peek().node;
49+
intcurrMax =q.peek().weight;
50+
q.poll();
51+
for (inti =0;i <revadj.get(u).size();i++) {
52+
intv =revadj.get(u).get(i).node;
53+
intwt =revadj.get(u).get(i).weight;
54+
if (dist[v] >Math.max(wt,currMax)) {
55+
dist[v] =Math.max(wt,currMax);
56+
q.offer(newPair(v,dist[v]));
57+
}
58+
}
59+
}
60+
intmaxi =dist[0];
61+
for (inti =0;i <n;i++) {
62+
maxi =Math.max(maxi,dist[i]);
63+
}
64+
returnmaxi;
65+
}
66+
67+
privatebooleancheck(intn) {
68+
int[]vis =newint[n];
69+
ArrayList<Integer>nodes =newArrayList<>();
70+
dfs(0,vis,nodes);
71+
returnnodes.size() ==n;
72+
}
73+
74+
privatevoiddfs(intu,int[]vis,ArrayList<Integer>nodes) {
75+
nodes.add(u);
76+
vis[u] =1;
77+
for (inti =0;i <revadj.get(u).size();i++) {
78+
intv =revadj.get(u).get(i).node;
79+
if (vis[v] ==0) {
80+
dfs(v,vis,nodes);
81+
}
82+
}
83+
}
84+
}
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
3419\. Minimize the Maximum Edge Weight of Graph
2+
3+
Medium
4+
5+
You are given two integers,`n` and`threshold`, as well as a**directed** weighted graph of`n` nodes numbered from 0 to`n - 1`. The graph is represented by a**2D** integer array`edges`, where <code>edges[i] =[A<sub>i</sub>, B<sub>i</sub>, W<sub>i</sub>]</code> indicates that there is an edge going from node <code>A<sub>i</sub></code> to node <code>B<sub>i</sub></code> with weight <code>W<sub>i</sub></code>.
6+
7+
You have to remove some edges from this graph (possibly**none**), so that it satisfies the following conditions:
8+
9+
* Node 0 must be reachable from all other nodes.
10+
* The**maximum** edge weight in the resulting graph is**minimized**.
11+
* Each node has**at most**`threshold` outgoing edges.
12+
13+
Return the**minimum** possible value of the**maximum** edge weight after removing the necessary edges. If it is impossible for all conditions to be satisfied, return -1.
14+
15+
**Example 1:**
16+
17+
**Input:** n = 5, edges =[[1,0,1],[2,0,2],[3,0,1],[4,3,1],[2,1,1]], threshold = 2
18+
19+
**Output:** 1
20+
21+
**Explanation:**
22+
23+
![](https://assets.leetcode.com/uploads/2024/12/09/s-1.png)
24+
25+
Remove the edge`2 -> 0`. The maximum weight among the remaining edges is 1.
26+
27+
**Example 2:**
28+
29+
**Input:** n = 5, edges =[[0,1,1],[0,2,2],[0,3,1],[0,4,1],[1,2,1],[1,4,1]], threshold = 1
30+
31+
**Output:**\-1
32+
33+
**Explanation:**
34+
35+
It is impossible to reach node 0 from node 2.
36+
37+
**Example 3:**
38+
39+
**Input:** n = 5, edges =[[1,2,1],[1,3,3],[1,4,5],[2,3,2],[3,4,2],[4,0,1]], threshold = 1
40+
41+
**Output:** 2
42+
43+
**Explanation:**
44+
45+
![](https://assets.leetcode.com/uploads/2024/12/09/s2-1.png)
46+
47+
Remove the edges`1 -> 3` and`1 -> 4`. The maximum weight among the remaining edges is 2.
48+
49+
**Example 4:**
50+
51+
**Input:** n = 5, edges =[[1,2,1],[1,3,3],[1,4,5],[2,3,2],[4,0,1]], threshold = 1
52+
53+
**Output:**\-1
54+
55+
**Constraints:**
56+
57+
* <code>2 <= n <= 10<sup>5</sup></code>
58+
*`1 <= threshold <= n - 1`
59+
* <code>1 <= edges.length <= min(10<sup>5</sup>, n * (n - 1) / 2).</code>
60+
*`edges[i].length == 3`
61+
* <code>0 <= A<sub>i</sub>, B<sub>i</sub> < n</code>
62+
* <code>A<sub>i</sub> != B<sub>i</sub></code>
63+
* <code>1 <= W<sub>i</sub> <= 10<sup>6</sup></code>
64+
* There**may be** multiple edges between a pair of nodes, but they must have unique weights.
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
packageg3401_3500.s3420_count_non_decreasing_subarrays_after_k_operations;
2+
3+
// #Hard #Array #Two_Pointers #Stack #Monotonic_Stack #Queue #Segment_Tree #Monotonic_Queue
4+
// #2025_01_15_Time_29_(83.94%)_Space_62.04_(56.93%)
5+
6+
importjava.util.ArrayDeque;
7+
importjava.util.Deque;
8+
9+
publicclassSolution {
10+
publiclongcountNonDecreasingSubarrays(int[]nums,longk) {
11+
intn =nums.length;
12+
for (inti =0;i <n /2; ++i) {
13+
inttemp =nums[i];
14+
nums[i] =nums[n -1 -i];
15+
nums[n -1 -i] =temp;
16+
}
17+
longres =0;
18+
Deque<Integer>q =newArrayDeque<>();
19+
inti =0;
20+
for (intj =0;j <nums.length; ++j) {
21+
while (!q.isEmpty() &&nums[q.peekLast()] <nums[j]) {
22+
intr =q.pollLast();
23+
intl =q.isEmpty() ?i -1 :q.peekLast();
24+
k -= (long) (r -l) * (nums[j] -nums[r]);
25+
}
26+
q.addLast(j);
27+
while (k <0) {
28+
k +=nums[q.peekFirst()] -nums[i];
29+
if (q.peekFirst() ==i) {
30+
q.pollFirst();
31+
}
32+
++i;
33+
}
34+
res +=j -i +1;
35+
}
36+
returnres;
37+
}
38+
}

0 commit comments

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