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

Commit71acd89

Browse files
authored
Added tasks 3285-3292
1 parent862f069 commit71acd89

File tree

24 files changed

+966
-0
lines changed

24 files changed

+966
-0
lines changed
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
packageg3201_3300.s3285_find_indices_of_stable_mountains;
2+
3+
// #Easy #Array #2024_09_15_Time_1_ms_(100.00%)_Space_44.5_MB_(100.00%)
4+
5+
importjava.util.ArrayList;
6+
importjava.util.List;
7+
8+
publicclassSolution {
9+
publicList<Integer>stableMountains(int[]height,intthreshold) {
10+
intn =height.length;
11+
List<Integer>list =newArrayList<>();
12+
for (inti =0;i <n -1;i++) {
13+
if (height[i] >threshold) {
14+
list.add(i +1);
15+
}
16+
}
17+
returnlist;
18+
}
19+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
3285\. Find Indices of Stable Mountains
2+
3+
Easy
4+
5+
There are`n` mountains in a row, and each mountain has a height. You are given an integer array`height` where`height[i]` represents the height of mountain`i`, and an integer`threshold`.
6+
7+
A mountain is called**stable** if the mountain just before it (**if it exists**) has a height**strictly greater** than`threshold`.**Note** that mountain 0 is**not** stable.
8+
9+
Return an array containing the indices of_all_**stable** mountains in**any** order.
10+
11+
**Example 1:**
12+
13+
**Input:** height =[1,2,3,4,5], threshold = 2
14+
15+
**Output:**[3,4]
16+
17+
**Explanation:**
18+
19+
* Mountain 3 is stable because`height[2] == 3` is greater than`threshold == 2`.
20+
* Mountain 4 is stable because`height[3] == 4` is greater than`threshold == 2`.
21+
22+
**Example 2:**
23+
24+
**Input:** height =[10,1,10,1,10], threshold = 3
25+
26+
**Output:**[1,3]
27+
28+
**Example 3:**
29+
30+
**Input:** height =[10,1,10,1,10], threshold = 10
31+
32+
**Output:**[]
33+
34+
**Constraints:**
35+
36+
*`2 <= n == height.length <= 100`
37+
*`1 <= height[i] <= 100`
38+
*`1 <= threshold <= 100`
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
packageg3201_3300.s3286_find_a_safe_walk_through_a_grid;
2+
3+
// #Medium #Array #Matrix #Heap_Priority_Queue #Graph #Shortest_Path #Breadth_First_Search
4+
// #2024_09_15_Time_90_ms_(100.00%)_Space_46.6_MB_(100.00%)
5+
6+
importjava.util.LinkedList;
7+
importjava.util.List;
8+
importjava.util.Objects;
9+
importjava.util.Queue;
10+
11+
publicclassSolution {
12+
publicbooleanfindSafeWalk(List<List<Integer>>grid,inthealth) {
13+
intn =grid.size();
14+
intm =grid.get(0).size();
15+
int[]dr =newint[] {0,0,1, -1};
16+
int[]dc =newint[] {1, -1,0,0};
17+
boolean[][][]visited =newboolean[n][m][health +1];
18+
Queue<int[]>bfs =newLinkedList<>();
19+
bfs.add(newint[] {0,0,health -grid.get(0).get(0)});
20+
visited[0][0][health -grid.get(0).get(0)] =true;
21+
while (!bfs.isEmpty()) {
22+
intsize =bfs.size();
23+
while (size-- >0) {
24+
int[]currNode =bfs.poll();
25+
intr =Objects.requireNonNull(currNode)[0];
26+
intc =currNode[1];
27+
inth =currNode[2];
28+
if (r ==n -1 &&c ==m -1 &&h >0) {
29+
returntrue;
30+
}
31+
for (intk =0;k <4;k++) {
32+
intnr =r +dr[k];
33+
intnc =c +dc[k];
34+
if (isValidMove(nr,nc,n,m)) {
35+
intnh =h -grid.get(nr).get(nc);
36+
if (nh >=0 && !visited[nr][nc][nh]) {
37+
visited[nr][nc][nh] =true;
38+
bfs.add(newint[] {nr,nc,nh});
39+
}
40+
}
41+
}
42+
}
43+
}
44+
returnfalse;
45+
}
46+
47+
privatebooleanisValidMove(intr,intc,intn,intm) {
48+
returnr >=0 &&c >=0 &&r <n &&c <m;
49+
}
50+
}
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
3286\. Find a Safe Walk Through a Grid
2+
3+
Medium
4+
5+
You are given an`m x n` binary matrix`grid` and an integer`health`.
6+
7+
You start on the upper-left corner`(0, 0)` and would like to get to the lower-right corner`(m - 1, n - 1)`.
8+
9+
You can move up, down, left, or right from one cell to another adjacent cell as long as your health_remains_**positive**.
10+
11+
Cells`(i, j)` with`grid[i][j] = 1` are considered**unsafe** and reduce your health by 1.
12+
13+
Return`true` if you can reach the final cell with a health value of 1 or more, and`false` otherwise.
14+
15+
**Example 1:**
16+
17+
**Input:** grid =[[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1
18+
19+
**Output:** true
20+
21+
**Explanation:**
22+
23+
The final cell can be reached safely by walking along the gray cells below.
24+
25+
![](https://assets.leetcode.com/uploads/2024/08/04/3868_examples_1drawio.png)
26+
27+
**Example 2:**
28+
29+
**Input:** grid =[[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health = 3
30+
31+
**Output:** false
32+
33+
**Explanation:**
34+
35+
A minimum of 4 health points is needed to reach the final cell safely.
36+
37+
![](https://assets.leetcode.com/uploads/2024/08/04/3868_examples_2drawio.png)
38+
39+
**Example 3:**
40+
41+
**Input:** grid =[[1,1,1],[1,0,1],[1,1,1]], health = 5
42+
43+
**Output:** true
44+
45+
**Explanation:**
46+
47+
The final cell can be reached safely by walking along the gray cells below.
48+
49+
![](https://assets.leetcode.com/uploads/2024/08/04/3868_examples_3drawio.png)
50+
51+
Any path that does not go through the cell`(1, 1)` is unsafe since your health will drop to 0 when reaching the final cell.
52+
53+
**Constraints:**
54+
55+
*`m == grid.length`
56+
*`n == grid[i].length`
57+
*`1 <= m, n <= 50`
58+
*`2 <= m * n`
59+
*`1 <= health <= m + n`
60+
*`grid[i][j]` is either 0 or 1.
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
packageg3201_3300.s3287_find_the_maximum_sequence_value_of_array;
2+
3+
// #Hard #Array #Dynamic_Programming #Bit_Manipulation
4+
// #2024_09_15_Time_1140_ms_(100.00%)_Space_285.4_MB_(100.00%)
5+
6+
importjava.util.HashSet;
7+
importjava.util.Set;
8+
9+
@SuppressWarnings("unchecked")
10+
publicclassSolution {
11+
publicintmaxValue(int[]nums,intk) {
12+
intn =nums.length;
13+
Set<Integer>[][]left =newSet[n][k +1];
14+
Set<Integer>[][]right =newSet[n][k +1];
15+
for (inti =0;i <n;i++) {
16+
for (intj =0;j <=k;j++) {
17+
left[i][j] =newHashSet<>();
18+
right[i][j] =newHashSet<>();
19+
}
20+
}
21+
left[0][0].add(0);
22+
left[0][1].add(nums[0]);
23+
for (inti =1;i <n -k;i++) {
24+
left[i][0].add(0);
25+
for (intj =1;j <=k;j++) {
26+
left[i][j].addAll(left[i -1][j]);
27+
for (intv :left[i -1][j -1]) {
28+
left[i][j].add(v |nums[i]);
29+
}
30+
}
31+
}
32+
right[n -1][0].add(0);
33+
right[n -1][1].add(nums[n -1]);
34+
intresult =0;
35+
if (k ==1) {
36+
for (intl :left[n -2][k]) {
37+
result =Math.max(result,l ^nums[n -1]);
38+
}
39+
}
40+
for (inti =n -2;i >=k;i--) {
41+
right[i][0].add(0);
42+
for (intj =1;j <=k;j++) {
43+
right[i][j].addAll(right[i +1][j]);
44+
for (intv :right[i +1][j -1]) {
45+
right[i][j].add(v |nums[i]);
46+
}
47+
}
48+
for (intl :left[i -1][k]) {
49+
for (intr :right[i][k]) {
50+
result =Math.max(result,l ^r);
51+
}
52+
}
53+
}
54+
returnresult;
55+
}
56+
}
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
3287\. Find the Maximum Sequence Value of Array
2+
3+
Hard
4+
5+
You are given an integer array`nums` and a**positive** integer`k`.
6+
7+
The**value** of a sequence`seq` of size`2 * x` is defined as:
8+
9+
*`(seq[0] OR seq[1] OR ... OR seq[x - 1]) XOR (seq[x] OR seq[x + 1] OR ... OR seq[2 * x - 1])`.
10+
11+
Return the**maximum****value** of any subsequence of`nums` having size`2 * k`.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[2,6,7], k = 1
16+
17+
**Output:** 5
18+
19+
**Explanation:**
20+
21+
The subsequence`[2, 7]` has the maximum value of`2 XOR 7 = 5`.
22+
23+
**Example 2:**
24+
25+
**Input:** nums =[4,2,5,6,7], k = 2
26+
27+
**Output:** 2
28+
29+
**Explanation:**
30+
31+
The subsequence`[4, 5, 6, 7]` has the maximum value of`(4 OR 5) XOR (6 OR 7) = 2`.
32+
33+
**Constraints:**
34+
35+
*`2 <= nums.length <= 400`
36+
* <code>1 <= nums[i] < 2<sup>7</sup></code>
37+
*`1 <= k <= nums.length / 2`
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
packageg3201_3300.s3288_length_of_the_longest_increasing_path;
2+
3+
// #Hard #Array #Sorting #Binary_Search #2024_09_15_Time_34_ms_(100.00%)_Space_106.2_MB_(50.00%)
4+
5+
importjava.util.ArrayList;
6+
importjava.util.List;
7+
8+
publicclassSolution {
9+
publicintmaxPathLength(int[][]coordinates,intk) {
10+
List<int[]>upper =newArrayList<>();
11+
List<int[]>lower =newArrayList<>();
12+
for (int[]pair :coordinates) {
13+
if (pair[0] >coordinates[k][0] &&pair[1] >coordinates[k][1]) {
14+
upper.add(pair);
15+
}
16+
if (pair[0] <coordinates[k][0] &&pair[1] <coordinates[k][1]) {
17+
lower.add(pair);
18+
}
19+
}
20+
upper.sort(
21+
(a,b) -> {
22+
if (a[0] ==b[0]) {
23+
returnb[1] -a[1];
24+
}else {
25+
returna[0] -b[0];
26+
}
27+
});
28+
lower.sort(
29+
(a,b) -> {
30+
if (a[0] ==b[0]) {
31+
returnb[1] -a[1];
32+
}else {
33+
returna[0] -b[0];
34+
}
35+
});
36+
returnlongestIncreasingLength(upper) +longestIncreasingLength(lower) +1;
37+
}
38+
39+
privateintlongestIncreasingLength(List<int[]>array) {
40+
List<Integer>list =newArrayList<>();
41+
for (int[]pair :array) {
42+
intm =list.size();
43+
if (m ==0 ||list.get(m -1) <pair[1]) {
44+
list.add(pair[1]);
45+
}else {
46+
intidx =binarySearch(list,pair[1]);
47+
list.set(idx,pair[1]);
48+
}
49+
}
50+
returnlist.size();
51+
}
52+
53+
privateintbinarySearch(List<Integer>list,inttarget) {
54+
intn =list.size();
55+
intleft =0;
56+
intright =n -1;
57+
while (left <right) {
58+
intmid = (left +right) /2;
59+
if (list.get(mid) ==target) {
60+
returnmid;
61+
}elseif (list.get(mid) >target) {
62+
right =mid;
63+
}else {
64+
left =mid +1;
65+
}
66+
}
67+
returnleft;
68+
}
69+
}
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
3288\. Length of the Longest Increasing Path
2+
3+
Hard
4+
5+
You are given a 2D array of integers`coordinates` of length`n` and an integer`k`, where`0 <= k < n`.
6+
7+
<code>coordinates[i] =[x<sub>i</sub>, y<sub>i</sub>]</code> indicates the point <code>(x<sub>i</sub>, y<sub>i</sub>)</code> in a 2D plane.
8+
9+
An**increasing path** of length`m` is defined as a list of points <code>(x<sub>1</sub>, y<sub>1</sub>)</code>, <code>(x<sub>2</sub>, y<sub>2</sub>)</code>, <code>(x<sub>3</sub>, y<sub>3</sub>)</code>, ..., <code>(x<sub>m</sub>, y<sub>m</sub>)</code> such that:
10+
11+
* <code>x<sub>i</sub> < x<sub>i + 1</sub></code> and <code>y<sub>i</sub> < y<sub>i + 1</sub></code> for all`i` where`1 <= i < m`.
12+
* <code>(x<sub>i</sub>, y<sub>i</sub>)</code> is in the given coordinates for all`i` where`1 <= i <= m`.
13+
14+
Return the**maximum** length of an**increasing path** that contains`coordinates[k]`.
15+
16+
**Example 1:**
17+
18+
**Input:** coordinates =[[3,1],[2,2],[4,1],[0,0],[5,3]], k = 1
19+
20+
**Output:** 3
21+
22+
**Explanation:**
23+
24+
`(0, 0)`,`(2, 2)`,`(5, 3)` is the longest increasing path that contains`(2, 2)`.
25+
26+
**Example 2:**
27+
28+
**Input:** coordinates =[[2,1],[7,0],[5,6]], k = 2
29+
30+
**Output:** 2
31+
32+
**Explanation:**
33+
34+
`(2, 1)`,`(5, 6)` is the longest increasing path that contains`(5, 6)`.
35+
36+
**Constraints:**
37+
38+
* <code>1 <= n == coordinates.length <= 10<sup>5</sup></code>
39+
*`coordinates[i].length == 2`
40+
* <code>0 <= coordinates[i][0], coordinates[i][1] <= 10<sup>9</sup></code>
41+
* All elements in`coordinates` are**distinct**.
42+
*`0 <= k <= n - 1`

0 commit comments

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