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

Commit76a46a6

Browse files
authored
Added tasks 3200-3203
1 parent8ce41cb commit76a46a6

File tree

12 files changed

+438
-0
lines changed

12 files changed

+438
-0
lines changed
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
packageg3101_3200.s3200_maximum_height_of_a_triangle;
2+
3+
// #Easy #Array #Enumeration #2024_07_04_Time_1_ms_(86.34%)_Space_40.5_MB_(90.34%)
4+
5+
@SuppressWarnings("java:S135")
6+
publicclassSolution {
7+
privateintcount(intv1,intv2) {
8+
intct =1;
9+
booleanflag =true;
10+
while (true) {
11+
if (flag) {
12+
if (ct <=v1) {
13+
v1 -=ct;
14+
}else {
15+
break;
16+
}
17+
}else {
18+
if (ct <=v2) {
19+
v2 -=ct;
20+
}else {
21+
break;
22+
}
23+
}
24+
ct++;
25+
flag = !flag;
26+
}
27+
returnct -1;
28+
}
29+
30+
publicintmaxHeightOfTriangle(intred,intblue) {
31+
returnMath.max(count(red,blue),count(blue,red));
32+
}
33+
}
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
3200\. Maximum Height of a Triangle
2+
3+
Easy
4+
5+
You are given two integers`red` and`blue` representing the count of red and blue colored balls. You have to arrange these balls to form a triangle such that the 1<sup>st</sup> row will have 1 ball, the 2<sup>nd</sup> row will have 2 balls, the 3<sup>rd</sup> row will have 3 balls, and so on.
6+
7+
All the balls in a particular row should be the**same** color, and adjacent rows should have**different** colors.
8+
9+
Return the**maximum**_height of the triangle_ that can be achieved.
10+
11+
**Example 1:**
12+
13+
**Input:** red = 2, blue = 4
14+
15+
**Output:** 3
16+
17+
**Explanation:**
18+
19+
![](https://assets.leetcode.com/uploads/2024/06/16/brb.png)
20+
21+
The only possible arrangement is shown above.
22+
23+
**Example 2:**
24+
25+
**Input:** red = 2, blue = 1
26+
27+
**Output:** 2
28+
29+
**Explanation:**
30+
31+
![](https://assets.leetcode.com/uploads/2024/06/16/br.png)
32+
The only possible arrangement is shown above.
33+
34+
**Example 3:**
35+
36+
**Input:** red = 1, blue = 1
37+
38+
**Output:** 1
39+
40+
**Example 4:**
41+
42+
**Input:** red = 10, blue = 1
43+
44+
**Output:** 2
45+
46+
**Explanation:**
47+
48+
![](https://assets.leetcode.com/uploads/2024/06/16/br.png)
49+
The only possible arrangement is shown above.
50+
51+
**Constraints:**
52+
53+
*`1 <= red, blue <= 100`
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
packageg3201_3300.s3201_find_the_maximum_length_of_valid_subsequence_i;
2+
3+
// #Medium #Array #Dynamic_Programming #2024_07_04_Time_5_ms_(82.23%)_Space_61.7_MB_(91.46%)
4+
5+
classSolution {
6+
publicintmaximumLength(int[]nums) {
7+
intn =nums.length;
8+
intalter =1;
9+
intodd =0;
10+
inteven =0;
11+
if (nums[0] %2 ==0) {
12+
even++;
13+
}else {
14+
odd++;
15+
}
16+
booleanlastodd =nums[0] %2 !=0;
17+
for (inti =1;i <n;i++) {
18+
booleanflag =nums[i] %2 ==0;
19+
if (flag) {
20+
if (lastodd) {
21+
alter++;
22+
lastodd =false;
23+
}
24+
even++;
25+
}else {
26+
if (!lastodd) {
27+
alter++;
28+
lastodd =true;
29+
}
30+
odd++;
31+
}
32+
}
33+
returnMath.max(alter,Math.max(odd,even));
34+
}
35+
}
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
3201\. Find the Maximum Length of Valid Subsequence I
2+
3+
Medium
4+
5+
You are given an integer array`nums`.
6+
7+
A subsequence`sub` of`nums` with length`x` is called**valid** if it satisfies:
8+
9+
*`(sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2.`
10+
11+
Return the length of the**longest****valid** subsequence of`nums`.
12+
13+
A**subsequence** is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[1,2,3,4]
18+
19+
**Output:** 4
20+
21+
**Explanation:**
22+
23+
The longest valid subsequence is`[1, 2, 3, 4]`.
24+
25+
**Example 2:**
26+
27+
**Input:** nums =[1,2,1,1,2,1,2]
28+
29+
**Output:** 6
30+
31+
**Explanation:**
32+
33+
The longest valid subsequence is`[1, 2, 1, 2, 1, 2]`.
34+
35+
**Example 3:**
36+
37+
**Input:** nums =[1,3]
38+
39+
**Output:** 2
40+
41+
**Explanation:**
42+
43+
The longest valid subsequence is`[1, 3]`.
44+
45+
**Constraints:**
46+
47+
* <code>2 <= nums.length <= 2 * 10<sup>5</sup></code>
48+
* <code>1 <= nums[i] <= 10<sup>7</sup></code>
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg3201_3300.s3202_find_the_maximum_length_of_valid_subsequence_ii;
2+
3+
// #Medium #Array #Dynamic_Programming #2024_07_04_Time_34_ms_(92.46%)_Space_51_MB_(45.95%)
4+
5+
publicclassSolution {
6+
publicintmaximumLength(int[]nums,intk) {
7+
// dp array to store the index against each possible modulo
8+
int[][]dp =newint[nums.length +1][k +1];
9+
intlongest =0;
10+
for (inti =0;i <nums.length;i++) {
11+
for (intj =0;j <i;j++) {
12+
// Checking the modulo with each previous number
13+
intval = (nums[i] +nums[j]) %k;
14+
// storing the number of pairs that have the same modulo.
15+
// it would be one more than the number of pairs with the same modulo at the last
16+
// index
17+
dp[i][val] =dp[j][val] +1;
18+
// Calculating the max seen till now
19+
longest =Math.max(longest,dp[i][val]);
20+
}
21+
}
22+
// total number of elements in the subsequence would be 1 more than the number of pairs
23+
returnlongest +1;
24+
}
25+
}
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
3202\. Find the Maximum Length of Valid Subsequence II
2+
3+
Medium
4+
5+
You are given an integer array`nums` and a**positive** integer`k`.
6+
7+
A subsequence`sub` of`nums` with length`x` is called**valid** if it satisfies:
8+
9+
*`(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k.`
10+
11+
Return the length of the**longest****valid** subsequence of`nums`.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[1,2,3,4,5], k = 2
16+
17+
**Output:** 5
18+
19+
**Explanation:**
20+
21+
The longest valid subsequence is`[1, 2, 3, 4, 5]`.
22+
23+
**Example 2:**
24+
25+
**Input:** nums =[1,4,2,3,1,4], k = 3
26+
27+
**Output:** 4
28+
29+
**Explanation:**
30+
31+
The longest valid subsequence is`[1, 4, 1, 4]`.
32+
33+
**Constraints:**
34+
35+
* <code>2 <= nums.length <= 10<sup>3</sup></code>
36+
* <code>1 <= nums[i] <= 10<sup>7</sup></code>
37+
* <code>1 <= k <= 10<sup>3</sup></code>
Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
packageg3201_3300.s3203_find_minimum_diameter_after_merging_two_trees;
2+
3+
// #Hard #Tree #Graph #Depth_First_Search #Breadth_First_Search
4+
// #2024_07_04_Time_29_ms_(99.83%)_Space_110.9_MB_(86.36%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publicintminimumDiameterAfterMerge(int[][]edges1,int[][]edges2) {
10+
intn =edges1.length +1;
11+
int[][]g =packU(n,edges1);
12+
intm =edges2.length +1;
13+
int[][]h =packU(m,edges2);
14+
int[]d1 =diameter(g);
15+
int[]d2 =diameter(h);
16+
intans =Math.max(d1[0],d2[0]);
17+
ans =Math.max((d1[0] +1) /2 + (d2[0] +1) /2 +1,ans);
18+
returnans;
19+
}
20+
21+
publicstaticint[]diameter(int[][]g) {
22+
intn =g.length;
23+
intf0;
24+
intf1;
25+
intd01;
26+
int[]q =newint[n];
27+
boolean[]ved =newboolean[n];
28+
intqp =0;
29+
q[qp++] =0;
30+
ved[0] =true;
31+
for (inti =0;i <qp;i++) {
32+
intcur =q[i];
33+
for (inte :g[cur]) {
34+
if (!ved[e]) {
35+
ved[e] =true;
36+
q[qp++] =e;
37+
}
38+
}
39+
}
40+
f0 =q[n -1];
41+
int[]d =newint[n];
42+
qp =0;
43+
Arrays.fill(ved,false);
44+
q[qp++] =f0;
45+
ved[f0] =true;
46+
for (inti =0;i <qp;i++) {
47+
intcur =q[i];
48+
for (inte :g[cur]) {
49+
if (!ved[e]) {
50+
ved[e] =true;
51+
q[qp++] =e;
52+
d[e] =d[cur] +1;
53+
}
54+
}
55+
}
56+
f1 =q[n -1];
57+
d01 =d[f1];
58+
returnnewint[] {d01,f0,f1};
59+
}
60+
61+
publicstaticint[][]packU(intn,int[][]ft) {
62+
int[][]g =newint[n][];
63+
int[]p =newint[n];
64+
for (int[]u :ft) {
65+
p[u[0]]++;
66+
p[u[1]]++;
67+
}
68+
for (inti =0;i <n;i++) {
69+
g[i] =newint[p[i]];
70+
}
71+
for (int[]u :ft) {
72+
g[u[0]][--p[u[0]]] =u[1];
73+
g[u[1]][--p[u[1]]] =u[0];
74+
}
75+
returng;
76+
}
77+
}
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
3203\. Find Minimum Diameter After Merging Two Trees
2+
3+
Hard
4+
5+
There exist two**undirected** trees with`n` and`m` nodes, numbered from`0` to`n - 1` and from`0` to`m - 1`, respectively. You are given two 2D integer arrays`edges1` and`edges2` of lengths`n - 1` and`m - 1`, respectively, where <code>edges1[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 first tree and <code>edges2[i] =[u<sub>i</sub>, v<sub>i</sub>]</code> indicates that there is an edge between nodes <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code> in the second tree.
6+
7+
You must connect one node from the first tree with another node from the second tree with an edge.
8+
9+
Return the**minimum** possible**diameter** of the resulting tree.
10+
11+
The**diameter** of a tree is the length of the_longest_ path between any two nodes in the tree.
12+
13+
**Example 1:**![](https://assets.leetcode.com/uploads/2024/04/22/example11-transformed.png)
14+
15+
**Input:** edges1 =[[0,1],[0,2],[0,3]], edges2 =[[0,1]]
16+
17+
**Output:** 3
18+
19+
**Explanation:**
20+
21+
We can obtain a tree of diameter 3 by connecting node 0 from the first tree with any node from the second tree.
22+
23+
**Example 2:**
24+
25+
![](https://assets.leetcode.com/uploads/2024/04/22/example211.png)
26+
27+
**Input:** edges1 =[[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]], edges2 =[[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]]
28+
29+
**Output:** 5
30+
31+
**Explanation:**
32+
33+
We can obtain a tree of diameter 5 by connecting node 0 from the first tree with node 0 from the second tree.
34+
35+
**Constraints:**
36+
37+
* <code>1 <= n, m <= 10<sup>5</sup></code>
38+
*`edges1.length == n - 1`
39+
*`edges2.length == m - 1`
40+
*`edges1[i].length == edges2[i].length == 2`
41+
* <code>edges1[i] =[a<sub>i</sub>, b<sub>i</sub>]</code>
42+
* <code>0 <= a<sub>i</sub>, b<sub>i</sub> < n</code>
43+
* <code>edges2[i] =[u<sub>i</sub>, v<sub>i</sub>]</code>
44+
* <code>0 <= u<sub>i</sub>, v<sub>i</sub> < m</code>
45+
* The input is generated such that`edges1` and`edges2` represent valid trees.
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg3101_3200.s3200_maximum_height_of_a_triangle;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidmaxHeightOfTriangle() {
11+
assertThat(newSolution().maxHeightOfTriangle(2,4),equalTo(3));
12+
}
13+
14+
@Test
15+
voidmaxHeightOfTriangle2() {
16+
assertThat(newSolution().maxHeightOfTriangle(2,1),equalTo(2));
17+
}
18+
}

0 commit comments

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