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

Commit2104c70

Browse files
authored
Added tasks 3254-3261
1 parent150a954 commit2104c70

File tree

25 files changed

+1066
-1
lines changed

25 files changed

+1066
-1
lines changed
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packageg3201_3300.s3254_find_the_power_of_k_size_subarrays_i;
2+
3+
// #Medium #Array #Sliding_Window #2024_08_20_Time_1_ms_(100.00%)_Space_45.2_MB_(95.96%)
4+
5+
publicclassSolution {
6+
publicint[]resultsArray(int[]nums,intk) {
7+
intn =nums.length;
8+
int[]arr =newint[n -k +1];
9+
intcount =0;
10+
for (inti =1;i <k;i++) {
11+
if (nums[i] ==nums[i -1] +1) {
12+
count++;
13+
}
14+
}
15+
arr[0] = (count ==k -1) ?nums[k -1] : -1;
16+
for (inti =1;i <=n -k;i++) {
17+
if (nums[i] ==nums[i -1] +1) {
18+
count--;
19+
}
20+
if (nums[i +k -1] ==nums[i +k -2] +1) {
21+
count++;
22+
}
23+
arr[i] = (count ==k -1) ?nums[i +k -1] : -1;
24+
}
25+
returnarr;
26+
}
27+
}
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
3254\. Find the Power of K-Size Subarrays I
2+
3+
Medium
4+
5+
You are given an array of integers`nums` of length`n` and a_positive_ integer`k`.
6+
7+
The**power** of an array is defined as:
8+
9+
* Its**maximum** element if_all_ of its elements are**consecutive** and**sorted** in**ascending** order.
10+
*\-1 otherwise.
11+
12+
You need to find the**power** of all subarrays of`nums` of size`k`.
13+
14+
Return an integer array`results` of size`n - k + 1`, where`results[i]` is the_power_ of`nums[i..(i + k - 1)]`.
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[1,2,3,4,3,2,5], k = 3
19+
20+
**Output:**[3,4,-1,-1,-1]
21+
22+
**Explanation:**
23+
24+
There are 5 subarrays of`nums` of size 3:
25+
26+
*`[1, 2, 3]` with the maximum element 3.
27+
*`[2, 3, 4]` with the maximum element 4.
28+
*`[3, 4, 3]` whose elements are**not** consecutive.
29+
*`[4, 3, 2]` whose elements are**not** sorted.
30+
*`[3, 2, 5]` whose elements are**not** consecutive.
31+
32+
**Example 2:**
33+
34+
**Input:** nums =[2,2,2,2,2], k = 4
35+
36+
**Output:**[-1,-1]
37+
38+
**Example 3:**
39+
40+
**Input:** nums =[3,2,3,2,3,2], k = 2
41+
42+
**Output:**[-1,3,-1,3,-1]
43+
44+
**Constraints:**
45+
46+
*`1 <= n == nums.length <= 500`
47+
* <code>1 <= nums[i] <= 10<sup>5</sup></code>
48+
*`1 <= k <= n`
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
packageg3201_3300.s3255_find_the_power_of_k_size_subarrays_ii;
2+
3+
// #Medium #Array #Sliding_Window #2024_08_20_Time_3_ms_(99.24%)_Space_64.1_MB_(67.44%)
4+
5+
publicclassSolution {
6+
publicint[]resultsArray(int[]nums,intk) {
7+
if (k ==1) {
8+
returnnums;
9+
}
10+
intstart =0;
11+
intn =nums.length;
12+
int[]output =newint[n -k +1];
13+
for (inti =1;i <n;i++) {
14+
if (nums[i] !=nums[i -1] +1) {
15+
start =i;
16+
}
17+
intindex =i -k +1;
18+
if (index >=0) {
19+
if (start >index) {
20+
output[index] = -1;
21+
}else {
22+
output[index] =nums[i];
23+
}
24+
}
25+
}
26+
returnoutput;
27+
}
28+
}
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
3255\. Find the Power of K-Size Subarrays II
2+
3+
Medium
4+
5+
You are given an array of integers`nums` of length`n` and a_positive_ integer`k`.
6+
7+
The**power** of an array is defined as:
8+
9+
* Its**maximum** element if_all_ of its elements are**consecutive** and**sorted** in**ascending** order.
10+
*\-1 otherwise.
11+
12+
You need to find the**power** of all subarrays of`nums` of size`k`.
13+
14+
Return an integer array`results` of size`n - k + 1`, where`results[i]` is the_power_ of`nums[i..(i + k - 1)]`.
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[1,2,3,4,3,2,5], k = 3
19+
20+
**Output:**[3,4,-1,-1,-1]
21+
22+
**Explanation:**
23+
24+
There are 5 subarrays of`nums` of size 3:
25+
26+
*`[1, 2, 3]` with the maximum element 3.
27+
*`[2, 3, 4]` with the maximum element 4.
28+
*`[3, 4, 3]` whose elements are**not** consecutive.
29+
*`[4, 3, 2]` whose elements are**not** sorted.
30+
*`[3, 2, 5]` whose elements are**not** consecutive.
31+
32+
**Example 2:**
33+
34+
**Input:** nums =[2,2,2,2,2], k = 4
35+
36+
**Output:**[-1,-1]
37+
38+
**Example 3:**
39+
40+
**Input:** nums =[3,2,3,2,3,2], k = 2
41+
42+
**Output:**[-1,3,-1,3,-1]
43+
44+
**Constraints:**
45+
46+
* <code>1 <= n == nums.length <= 10<sup>5</sup></code>
47+
* <code>1 <= nums[i] <= 10<sup>6</sup></code>
48+
*`1 <= k <= n`
Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
packageg3201_3300.s3256_maximum_value_sum_by_placing_three_rooks_i;
2+
3+
// #Hard #Array #Dynamic_Programming #Matrix #Enumeration
4+
// #2024_08_20_Time_7_ms_(100.00%)_Space_45.1_MB_(90.97%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publiclongmaximumValueSum(int[][]board) {
10+
intn =board.length;
11+
intm =board[0].length;
12+
int[][]tb =newint[n][m];
13+
tb[0] =Arrays.copyOf(board[0],m);
14+
for (inti =1;i <n;i++) {
15+
for (intj =0;j <m;j++) {
16+
tb[i][j] =Math.max(tb[i -1][j],board[i][j]);
17+
}
18+
}
19+
int[][]bt =newint[n][m];
20+
bt[n -1] =Arrays.copyOf(board[n -1],m);
21+
for (inti =n -2;i >=0;i--) {
22+
for (intj =0;j <m;j++) {
23+
bt[i][j] =Math.max(bt[i +1][j],board[i][j]);
24+
}
25+
}
26+
longans =Long.MIN_VALUE;
27+
for (inti =1;i <n -1;i++) {
28+
int[][]max3Top =getMax3(tb[i -1]);
29+
int[][]max3Cur =getMax3(board[i]);
30+
int[][]max3Bottom =getMax3(bt[i +1]);
31+
for (int[]topCand :max3Top) {
32+
for (int[]curCand :max3Cur) {
33+
for (int[]bottomCand :max3Bottom) {
34+
if (topCand[1] !=curCand[1]
35+
&&topCand[1] !=bottomCand[1]
36+
&&curCand[1] !=bottomCand[1]) {
37+
longcand = (long)topCand[0] +curCand[0] +bottomCand[0];
38+
ans =Math.max(ans,cand);
39+
}
40+
}
41+
}
42+
}
43+
}
44+
returnans;
45+
}
46+
47+
privateint[][]getMax3(int[]row) {
48+
intm =row.length;
49+
int[][]ans =newint[3][2];
50+
Arrays.fill(ans,newint[] {Integer.MIN_VALUE, -1});
51+
for (intj =0;j <m;j++) {
52+
if (row[j] >=ans[0][0]) {
53+
ans[2] =ans[1];
54+
ans[1] =ans[0];
55+
ans[0] =newint[] {row[j],j};
56+
}elseif (row[j] >=ans[1][0]) {
57+
ans[2] =ans[1];
58+
ans[1] =newint[] {row[j],j};
59+
}elseif (row[j] >ans[2][0]) {
60+
ans[2] =newint[] {row[j],j};
61+
}
62+
}
63+
returnans;
64+
}
65+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
3256\. Maximum Value Sum by Placing Three Rooks I
2+
3+
Hard
4+
5+
You are given a`m x n` 2D array`board` representing a chessboard, where`board[i][j]` represents the**value** of the cell`(i, j)`.
6+
7+
Rooks in the**same** row or column**attack** each other. You need to place_three_ rooks on the chessboard such that the rooks**do not****attack** each other.
8+
9+
Return the**maximum** sum of the cell**values** on which the rooks are placed.
10+
11+
**Example 1:**
12+
13+
**Input:** board =[[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]
14+
15+
**Output:** 4
16+
17+
**Explanation:**
18+
19+
![](https://assets.leetcode.com/uploads/2024/08/08/rooks2.png)
20+
21+
We can place the rooks in the cells`(0, 2)`,`(1, 3)`, and`(2, 1)` for a sum of`1 + 1 + 2 = 4`.
22+
23+
**Example 2:**
24+
25+
**Input:** board =[[1,2,3],[4,5,6],[7,8,9]]
26+
27+
**Output:** 15
28+
29+
**Explanation:**
30+
31+
We can place the rooks in the cells`(0, 0)`,`(1, 1)`, and`(2, 2)` for a sum of`1 + 5 + 9 = 15`.
32+
33+
**Example 3:**
34+
35+
**Input:** board =[[1,1,1],[1,1,1],[1,1,1]]
36+
37+
**Output:** 3
38+
39+
**Explanation:**
40+
41+
We can place the rooks in the cells`(0, 2)`,`(1, 1)`, and`(2, 0)` for a sum of`1 + 1 + 1 = 3`.
42+
43+
**Constraints:**
44+
45+
*`3 <= m == board.length <= 100`
46+
*`3 <= n == board[i].length <= 100`
47+
* <code>-10<sup>9</sup> <= board[i][j] <= 10<sup>9</sup></code>
Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
packageg3201_3300.s3257_maximum_value_sum_by_placing_three_rooks_ii;
2+
3+
// #Hard #Array #Dynamic_Programming #Matrix #Enumeration
4+
// #2024_08_20_Time_18_ms_(99.59%)_Space_74.2_MB_(66.81%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publiclongmaximumValueSum(int[][]board) {
10+
intn =board.length;
11+
intm =board[0].length;
12+
int[][]tb =newint[n][m];
13+
tb[0] =Arrays.copyOf(board[0],m);
14+
for (inti =1;i <n;i++) {
15+
for (intj =0;j <m;j++) {
16+
tb[i][j] =Math.max(tb[i -1][j],board[i][j]);
17+
}
18+
}
19+
int[][]bt =newint[n][m];
20+
bt[n -1] =Arrays.copyOf(board[n -1],m);
21+
for (inti =n -2;i >=0;i--) {
22+
for (intj =0;j <m;j++) {
23+
bt[i][j] =Math.max(bt[i +1][j],board[i][j]);
24+
}
25+
}
26+
longans =Long.MIN_VALUE;
27+
for (inti =1;i <n -1;i++) {
28+
int[][]max3Top =getMax3(tb[i -1]);
29+
int[][]max3Cur =getMax3(board[i]);
30+
int[][]max3Bottom =getMax3(bt[i +1]);
31+
for (int[]topCand :max3Top) {
32+
for (int[]curCand :max3Cur) {
33+
for (int[]bottomCand :max3Bottom) {
34+
if (topCand[1] !=curCand[1]
35+
&&topCand[1] !=bottomCand[1]
36+
&&curCand[1] !=bottomCand[1]) {
37+
longcand = (long)topCand[0] +curCand[0] +bottomCand[0];
38+
ans =Math.max(ans,cand);
39+
}
40+
}
41+
}
42+
}
43+
}
44+
returnans;
45+
}
46+
47+
privateint[][]getMax3(int[]row) {
48+
intm =row.length;
49+
int[][]ans =newint[3][2];
50+
Arrays.fill(ans,newint[] {Integer.MIN_VALUE, -1});
51+
for (intj =0;j <m;j++) {
52+
if (row[j] >=ans[0][0]) {
53+
ans[2] =ans[1];
54+
ans[1] =ans[0];
55+
ans[0] =newint[] {row[j],j};
56+
}elseif (row[j] >=ans[1][0]) {
57+
ans[2] =ans[1];
58+
ans[1] =newint[] {row[j],j};
59+
}elseif (row[j] >ans[2][0]) {
60+
ans[2] =newint[] {row[j],j};
61+
}
62+
}
63+
returnans;
64+
}
65+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
3257\. Maximum Value Sum by Placing Three Rooks II
2+
3+
Hard
4+
5+
You are given a`m x n` 2D array`board` representing a chessboard, where`board[i][j]` represents the**value** of the cell`(i, j)`.
6+
7+
Rooks in the**same** row or column**attack** each other. You need to place_three_ rooks on the chessboard such that the rooks**do not****attack** each other.
8+
9+
Return the**maximum** sum of the cell**values** on which the rooks are placed.
10+
11+
**Example 1:**
12+
13+
**Input:** board =[[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]
14+
15+
**Output:** 4
16+
17+
**Explanation:**
18+
19+
![](https://assets.leetcode.com/uploads/2024/08/08/rooks2.png)
20+
21+
We can place the rooks in the cells`(0, 2)`,`(1, 3)`, and`(2, 1)` for a sum of`1 + 1 + 2 = 4`.
22+
23+
**Example 2:**
24+
25+
**Input:** board =[[1,2,3],[4,5,6],[7,8,9]]
26+
27+
**Output:** 15
28+
29+
**Explanation:**
30+
31+
We can place the rooks in the cells`(0, 0)`,`(1, 1)`, and`(2, 2)` for a sum of`1 + 5 + 9 = 15`.
32+
33+
**Example 3:**
34+
35+
**Input:** board =[[1,1,1],[1,1,1],[1,1,1]]
36+
37+
**Output:** 3
38+
39+
**Explanation:**
40+
41+
We can place the rooks in the cells`(0, 2)`,`(1, 1)`, and`(2, 0)` for a sum of`1 + 1 + 1 = 3`.
42+
43+
**Constraints:**
44+
45+
*`3 <= m == board.length <= 500`
46+
*`3 <= n == board[i].length <= 500`
47+
* <code>-10<sup>9</sup> <= board[i][j] <= 10<sup>9</sup></code>

0 commit comments

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