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

Commit6835a51

Browse files
authored
Added tasks 3248-3251
1 parent7f41811 commit6835a51

File tree

14 files changed

+508
-0
lines changed

14 files changed

+508
-0
lines changed
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
packageg3201_3300.s3248_snake_in_matrix;
2+
3+
// #Easy #Array #String #Simulation #2024_08_13_Time_2_ms_(98.05%)_Space_44.4_MB_(66.96%)
4+
5+
importjava.util.List;
6+
7+
publicclassSolution {
8+
publicintfinalPositionOfSnake(intn,List<String>commands) {
9+
intx =0;
10+
inty =0;
11+
for (Stringcommand :commands) {
12+
switch (command) {
13+
case"UP":
14+
if (x >0) {
15+
x--;
16+
}
17+
break;
18+
case"DOWN":
19+
if (x <n -1) {
20+
x++;
21+
}
22+
break;
23+
case"LEFT":
24+
if (y >0) {
25+
y--;
26+
}
27+
break;
28+
case"RIGHT":
29+
if (y <n -1) {
30+
y++;
31+
}
32+
break;
33+
default:
34+
break;
35+
}
36+
}
37+
return (x *n) +y;
38+
}
39+
}
Loading
Loading
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
3248\. Snake in Matrix
2+
3+
Easy
4+
5+
There is a snake in an`n x n` matrix`grid` and can move in**four possible directions**. Each cell in the`grid` is identified by the position:`grid[i][j] = (i * n) + j`.
6+
7+
The snake starts at cell 0 and follows a sequence of commands.
8+
9+
You are given an integer`n` representing the size of the`grid` and an array of strings`commands` where each`command[i]` is either`"UP"`,`"RIGHT"`,`"DOWN"`, and`"LEFT"`. It's guaranteed that the snake will remain within the`grid` boundaries throughout its movement.
10+
11+
Return the position of the final cell where the snake ends up after executing`commands`.
12+
13+
**Example 1:**
14+
15+
**Input:** n = 2, commands =["RIGHT","DOWN"]
16+
17+
**Output:** 3
18+
19+
**Explanation:**
20+
21+
![image](image01.png)
22+
23+
**Example 2:**
24+
25+
**Input:** n = 3, commands =["DOWN","RIGHT","UP"]
26+
27+
**Output:** 1
28+
29+
**Explanation:**
30+
31+
![image](image02.png)
32+
33+
**Constraints:**
34+
35+
*`2 <= n <= 10`
36+
*`1 <= commands.length <= 100`
37+
*`commands` consists only of`"UP"`,`"RIGHT"`,`"DOWN"`, and`"LEFT"`.
38+
* The input is generated such the snake will not move outside of the boundaries.
Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
packageg3201_3300.s3249_count_the_number_of_good_nodes;
2+
3+
// #Medium #Tree #Depth_First_Search #2024_08_13_Time_34_ms_(100.00%)_Space_113.9_MB_(90.70%)
4+
5+
importjava.util.ArrayList;
6+
importjava.util.List;
7+
8+
publicclassSolution {
9+
privateintcount =0;
10+
11+
publicintcountGoodNodes(int[][]edges) {
12+
intn =edges.length +1;
13+
TNode[]nodes =newTNode[n];
14+
nodes[0] =newTNode(0);
15+
for (int[]edge :edges) {
16+
inta =edge[0];
17+
intb =edge[1];
18+
if (nodes[b] !=null &&nodes[a] ==null) {
19+
nodes[a] =newTNode(a);
20+
nodes[b].children.add(nodes[a]);
21+
}else {
22+
if (nodes[a] ==null) {
23+
nodes[a] =newTNode(a);
24+
}
25+
if (nodes[b] ==null) {
26+
nodes[b] =newTNode(b);
27+
}
28+
nodes[a].children.add(nodes[b]);
29+
}
30+
}
31+
sizeOfTree(nodes[0]);
32+
returncount;
33+
}
34+
35+
privateintsizeOfTree(TNodenode) {
36+
if (node.size >0) {
37+
returnnode.size;
38+
}
39+
List<TNode>children =node.children;
40+
if (children.isEmpty()) {
41+
count++;
42+
node.size =1;
43+
return1;
44+
}
45+
intsize =sizeOfTree(children.get(0));
46+
intsum =size;
47+
booleangoodNode =true;
48+
for (inti =1;i <children.size(); ++i) {
49+
TNodechild =children.get(i);
50+
if (size !=sizeOfTree(child)) {
51+
goodNode =false;
52+
}
53+
sum +=sizeOfTree(child);
54+
}
55+
if (goodNode) {
56+
count++;
57+
}
58+
sum++;
59+
node.size =sum;
60+
returnsum;
61+
}
62+
63+
privatestaticclassTNode {
64+
intval;
65+
intsize;
66+
List<TNode>children;
67+
68+
TNode(intval) {
69+
this.val =val;
70+
this.size = -1;
71+
this.children =newArrayList<>();
72+
}
73+
}
74+
}
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
3249\. Count the Number of Good Nodes
2+
3+
Medium
4+
5+
There is an**undirected** tree with`n` nodes labeled from`0` to`n - 1`, and rooted at node`0`. You are given a 2D integer array`edges` of length`n - 1`, where <code>edges[i] =[a<sub>i</sub>, b<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> in the tree.
6+
7+
A node is**good** if all the subtrees rooted at its children have the same size.
8+
9+
Return the number of**good** nodes in the given tree.
10+
11+
A**subtree** of`treeName` is a tree consisting of a node in`treeName` and all of its descendants.
12+
13+
**Example 1:**
14+
15+
**Input:** edges =[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
16+
17+
**Output:** 7
18+
19+
**Explanation:**
20+
21+
![](https://assets.leetcode.com/uploads/2024/05/26/tree1.png)
22+
23+
All of the nodes of the given tree are good.
24+
25+
**Example 2:**
26+
27+
**Input:** edges =[[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]]
28+
29+
**Output:** 6
30+
31+
**Explanation:**
32+
33+
![](https://assets.leetcode.com/uploads/2024/06/03/screenshot-2024-06-03-193552.png)
34+
35+
There are 6 good nodes in the given tree. They are colored in the image above.
36+
37+
**Example 3:**
38+
39+
**Input:** edges =[[0,1],[1,2],[1,3],[1,4],[0,5],[5,6],[6,7],[7,8],[0,9],[9,10],[9,12],[10,11]]
40+
41+
**Output:** 12
42+
43+
**Explanation:**
44+
45+
![](https://assets.leetcode.com/uploads/2024/08/08/rob.jpg)
46+
47+
All nodes except node 9 are good.
48+
49+
**Constraints:**
50+
51+
* <code>2 <= n <= 10<sup>5</sup></code>
52+
*`edges.length == n - 1`
53+
*`edges[i].length == 2`
54+
* <code>0 <= a<sub>i</sub>, b<sub>i</sub> < n</code>
55+
* The input is generated such that`edges` represents a valid tree.
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
packageg3201_3300.s3250_find_the_count_of_monotonic_pairs_i;
2+
3+
// #Hard #Array #Dynamic_Programming #Math #Prefix_Sum #Combinatorics
4+
// #2024_08_13_Time_3_ms_(100.00%)_Space_44.7_MB_(99.34%)
5+
6+
publicclassSolution {
7+
publicintcountOfPairs(int[]nums) {
8+
int[]maxShift =newint[nums.length];
9+
maxShift[0] =nums[0];
10+
intcurrShift =0;
11+
for (inti =1;i <nums.length;i++) {
12+
currShift =Math.max(currShift,nums[i] -maxShift[i -1]);
13+
maxShift[i] =Math.min(maxShift[i -1],nums[i] -currShift);
14+
if (maxShift[i] <0) {
15+
return0;
16+
}
17+
}
18+
int[][]cases =getAllCases(nums,maxShift);
19+
returncases[nums.length -1][maxShift[nums.length -1]];
20+
}
21+
22+
privateint[][]getAllCases(int[]nums,int[]maxShift) {
23+
int[]currCases;
24+
int[][]cases =newint[nums.length][];
25+
cases[0] =newint[maxShift[0] +1];
26+
for (inti =0;i <cases[0].length;i++) {
27+
cases[0][i] =i +1;
28+
}
29+
for (inti =1;i <nums.length;i++) {
30+
currCases =newint[maxShift[i] +1];
31+
currCases[0] =1;
32+
for (intj =1;j <currCases.length;j++) {
33+
intprevCases =
34+
j <cases[i -1].length
35+
?cases[i -1][j]
36+
:cases[i -1][cases[i -1].length -1];
37+
currCases[j] = (currCases[j -1] +prevCases) % (1_000_000_000 +7);
38+
}
39+
cases[i] =currCases;
40+
}
41+
returncases;
42+
}
43+
}
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
3250\. Find the Count of Monotonic Pairs I
2+
3+
Hard
4+
5+
You are given an array of**positive** integers`nums` of length`n`.
6+
7+
We call a pair of**non-negative** integer arrays`(arr1, arr2)`**monotonic** if:
8+
9+
* The lengths of both arrays are`n`.
10+
*`arr1` is monotonically**non-decreasing**, in other words,`arr1[0] <= arr1[1] <= ... <= arr1[n - 1]`.
11+
*`arr2` is monotonically**non-increasing**, in other words,`arr2[0] >= arr2[1] >= ... >= arr2[n - 1]`.
12+
*`arr1[i] + arr2[i] == nums[i]` for all`0 <= i <= n - 1`.
13+
14+
Return the count of**monotonic** pairs.
15+
16+
Since the answer may be very large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
17+
18+
**Example 1:**
19+
20+
**Input:** nums =[2,3,2]
21+
22+
**Output:** 4
23+
24+
**Explanation:**
25+
26+
The good pairs are:
27+
28+
1.`([0, 1, 1], [2, 2, 1])`
29+
2.`([0, 1, 2], [2, 2, 0])`
30+
3.`([0, 2, 2], [2, 1, 0])`
31+
4.`([1, 2, 2], [1, 1, 0])`
32+
33+
**Example 2:**
34+
35+
**Input:** nums =[5,5,5,5]
36+
37+
**Output:** 126
38+
39+
**Constraints:**
40+
41+
*`1 <= n == nums.length <= 2000`
42+
*`1 <= nums[i] <= 50`
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
packageg3201_3300.s3251_find_the_count_of_monotonic_pairs_ii;
2+
3+
// #Hard #Array #Dynamic_Programming #Math #Prefix_Sum #Combinatorics
4+
// #2024_08_13_Time_24_ms_(100.00%)_Space_44.7_MB_(97.70%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
privatestaticfinalintMOD =1000000007;
10+
11+
publicintcountOfPairs(int[]nums) {
12+
intprefixZeros =0;
13+
intn =nums.length;
14+
// Calculate prefix zeros
15+
for (inti =1;i <n;i++) {
16+
prefixZeros +=Math.max(nums[i] -nums[i -1],0);
17+
}
18+
introw =n +1;
19+
intcol =nums[n -1] +1 -prefixZeros;
20+
if (col <=0) {
21+
return0;
22+
}
23+
// Initialize dp array
24+
int[]dp =newint[col];
25+
Arrays.fill(dp,1);
26+
// Fill dp array
27+
for (intr =1;r <row;r++) {
28+
for (intc =1;c <col;c++) {
29+
dp[c] = (dp[c] +dp[c -1]) %MOD;
30+
}
31+
}
32+
returndp[col -1];
33+
}
34+
}
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
3251\. Find the Count of Monotonic Pairs II
2+
3+
Hard
4+
5+
You are given an array of**positive** integers`nums` of length`n`.
6+
7+
We call a pair of**non-negative** integer arrays`(arr1, arr2)`**monotonic** if:
8+
9+
* The lengths of both arrays are`n`.
10+
*`arr1` is monotonically**non-decreasing**, in other words,`arr1[0] <= arr1[1] <= ... <= arr1[n - 1]`.
11+
*`arr2` is monotonically**non-increasing**, in other words,`arr2[0] >= arr2[1] >= ... >= arr2[n - 1]`.
12+
*`arr1[i] + arr2[i] == nums[i]` for all`0 <= i <= n - 1`.
13+
14+
Return the count of**monotonic** pairs.
15+
16+
Since the answer may be very large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
17+
18+
**Example 1:**
19+
20+
**Input:** nums =[2,3,2]
21+
22+
**Output:** 4
23+
24+
**Explanation:**
25+
26+
The good pairs are:
27+
28+
1.`([0, 1, 1], [2, 2, 1])`
29+
2.`([0, 1, 2], [2, 2, 0])`
30+
3.`([0, 2, 2], [2, 1, 0])`
31+
4.`([1, 2, 2], [1, 1, 0])`
32+
33+
**Example 2:**
34+
35+
**Input:** nums =[5,5,5,5]
36+
37+
**Output:** 126
38+
39+
**Constraints:**
40+
41+
*`1 <= n == nums.length <= 2000`
42+
*`1 <= nums[i] <= 1000`

0 commit comments

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