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

Commit113ad95

Browse files
authored
Added tasks 3354-3357
1 parent0131b3c commit113ad95

File tree

12 files changed

+465
-0
lines changed

12 files changed

+465
-0
lines changed
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
packageg3301_3400.s3354_make_array_elements_equal_to_zero;
2+
3+
// #Easy #Array #Simulation #Prefix_Sum #2024_11_19_Time_1_ms_(95.09%)_Space_41.9_MB_(92.55%)
4+
5+
publicclassSolution {
6+
publicintcountValidSelections(int[]nums) {
7+
int[]rightSum =newint[nums.length];
8+
int[]leftSum =newint[nums.length];
9+
intresult =0;
10+
leftSum[0] =0;
11+
rightSum[nums.length -1] =0;
12+
for (inti =1;i <nums.length;i++) {
13+
leftSum[i] =leftSum[i -1] +nums[i -1];
14+
}
15+
for (intj =nums.length -2;j >=0;j--) {
16+
rightSum[j] =rightSum[j +1] +nums[j +1];
17+
}
18+
for (intk =0;k <nums.length;k++) {
19+
if (nums[k] ==0 &&Math.abs(rightSum[k] -leftSum[k]) ==1) {
20+
result++;
21+
}
22+
if (nums[k] ==0 &&Math.abs(rightSum[k] -leftSum[k]) ==0) {
23+
result +=2;
24+
}
25+
}
26+
returnresult;
27+
}
28+
}
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
3354\. Make Array Elements Equal to Zero
2+
3+
Easy
4+
5+
You are given an integer array`nums`.
6+
7+
Start by selecting a starting position`curr` such that`nums[curr] == 0`, and choose a movement**direction** of either left or right.
8+
9+
After that, you repeat the following process:
10+
11+
* If`curr` is out of the range`[0, n - 1]`, this process ends.
12+
* If`nums[curr] == 0`, move in the current direction by**incrementing**`curr` if you are moving right, or**decrementing**`curr` if you are moving left.
13+
* Else if`nums[curr] > 0`:
14+
* Decrement`nums[curr]` by 1.
15+
***Reverse** your movement direction (left becomes right and vice versa).
16+
* Take a step in your new direction.
17+
18+
A selection of the initial position`curr` and movement direction is considered**valid** if every element in`nums` becomes 0 by the end of the process.
19+
20+
Return the number of possible**valid** selections.
21+
22+
**Example 1:**
23+
24+
**Input:** nums =[1,0,2,0,3]
25+
26+
**Output:** 2
27+
28+
**Explanation:**
29+
30+
The only possible valid selections are the following:
31+
32+
* Choose`curr = 3`, and a movement direction to the left.
33+
* <code>[1,0,2,**<ins>0</ins>**,3] ->[1,0,**<ins>2</ins>**,0,3] ->[1,0,1,**<ins>0</ins>**,3] ->[1,0,1,0,**<ins>3</ins>**] ->[1,0,1,**<ins>0</ins>**,2] ->[1,0,**<ins>1</ins>**,0,2] ->[1,0,0,**<ins>0</ins>**,2] ->[1,0,0,0,**<ins>2</ins>**] ->[1,0,0,**<ins>0</ins>**,1] ->[1,0,**<ins>0</ins>**,0,1] ->[1,**<ins>0</ins>**,0,0,1] ->[**<ins>1</ins>**,0,0,0,1] ->[0,**<ins>0</ins>**,0,0,1] ->[0,0,**<ins>0</ins>**,0,1] ->[0,0,0,**<ins>0</ins>**,1] ->[0,0,0,0,**<ins>1</ins>**] ->[0,0,0,0,0]</code>.
34+
* Choose`curr = 3`, and a movement direction to the right.
35+
* <code>[1,0,2,**<ins>0</ins>**,3] ->[1,0,2,0,**<ins>3</ins>**] ->[1,0,2,**<ins>0</ins>**,2] ->[1,0,**<ins>2</ins>**,0,2] ->[1,0,1,**<ins>0</ins>**,2] ->[1,0,1,0,**<ins>2</ins>**] ->[1,0,1,**<ins>0</ins>**,1] ->[1,0,**<ins>1</ins>**,0,1] ->[1,0,0,**<ins>0</ins>**,1] ->[1,0,0,0,**<ins>1</ins>**] ->[1,0,0,**<ins>0</ins>**,0] ->[1,0,**<ins>0</ins>**,0,0] ->[1,**<ins>0</ins>**,0,0,0] ->[**<ins>1</ins>**,0,0,0,0] ->[0,0,0,0,0].</code>
36+
37+
**Example 2:**
38+
39+
**Input:** nums =[2,3,4,0,4,1,0]
40+
41+
**Output:** 0
42+
43+
**Explanation:**
44+
45+
There are no possible valid selections.
46+
47+
**Constraints:**
48+
49+
*`1 <= nums.length <= 100`
50+
*`0 <= nums[i] <= 100`
51+
* There is at least one element`i` where`nums[i] == 0`.
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
packageg3301_3400.s3355_zero_array_transformation_i;
2+
3+
// #Medium #Array #Prefix_Sum #2024_11_19_Time_3_ms_(91.34%)_Space_96_MB_(17.22%)
4+
5+
publicclassSolution {
6+
publicbooleanisZeroArray(int[]nums,int[][]queries) {
7+
intn =nums.length;
8+
intsum =0;
9+
for (intnum :nums) {
10+
sum +=num;
11+
}
12+
if (sum ==0) {
13+
returntrue;
14+
}
15+
int[]diff =newint[n +1];
16+
for (int[]q :queries) {
17+
intlow =q[0];
18+
inthigh =q[1];
19+
diff[low] -=1;
20+
if (high +1 <n) {
21+
diff[high +1] +=1;
22+
}
23+
}
24+
for (inti =0;i <n;i++) {
25+
if (i >0) {
26+
diff[i] +=diff[i -1];
27+
}
28+
nums[i] +=diff[i];
29+
sum +=diff[i];
30+
if (nums[i] >0) {
31+
returnfalse;
32+
}
33+
}
34+
returnsum <=0;
35+
}
36+
}
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
3355\. Zero Array Transformation I
2+
3+
Medium
4+
5+
You are given an integer array`nums` of length`n` and a 2D array`queries`, where <code>queries[i] =[l<sub>i</sub>, r<sub>i</sub>]</code>.
6+
7+
For each`queries[i]`:
8+
9+
* Select a subset of indices within the range <code>[l<sub>i</sub>, r<sub>i</sub>]</code> in`nums`.
10+
* Decrement the values at the selected indices by 1.
11+
12+
A**Zero Array** is an array where all elements are equal to 0.
13+
14+
Return`true` if it is_possible_ to transform`nums` into a**Zero Array** after processing all the queries sequentially, otherwise return`false`.
15+
16+
A**subset** of an array is a selection of elements (possibly none) of the array.
17+
18+
**Example 1:**
19+
20+
**Input:** nums =[1,0,1], queries =[[0,2]]
21+
22+
**Output:** true
23+
24+
**Explanation:**
25+
26+
***For i = 0:**
27+
* Select the subset of indices as`[0, 2]` and decrement the values at these indices by 1.
28+
* The array will become`[0, 0, 0]`, which is a Zero Array.
29+
30+
**Example 2:**
31+
32+
**Input:** nums =[4,3,2,1], queries =[[1,3],[0,2]]
33+
34+
**Output:** false
35+
36+
**Explanation:**
37+
38+
***For i = 0:**
39+
* Select the subset of indices as`[1, 2, 3]` and decrement the values at these indices by 1.
40+
* The array will become`[4, 2, 1, 0]`.
41+
***For i = 1:**
42+
* Select the subset of indices as`[0, 1, 2]` and decrement the values at these indices by 1.
43+
* The array will become`[3, 1, 0, 0]`, which is not a Zero Array.
44+
45+
**Constraints:**
46+
47+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
48+
* <code>0 <= nums[i] <= 10<sup>5</sup></code>
49+
* <code>1 <= queries.length <= 10<sup>5</sup></code>
50+
*`queries[i].length == 2`
51+
* <code>0 <= l<sub>i</sub> <= r<sub>i</sub> < nums.length</code>
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
packageg3301_3400.s3356_zero_array_transformation_ii;
2+
3+
// #Medium #Array #Binary_Search #Prefix_Sum #2024_11_19_Time_4_ms_(93.46%)_Space_118.5_MB_(13.87%)
4+
5+
publicclassSolution {
6+
publicintminZeroArray(int[]nums,int[][]queries) {
7+
int[]diff =newint[nums.length];
8+
intidx =0;
9+
intd =0;
10+
for (inti =0;i <nums.length;i++) {
11+
d +=diff[i];
12+
while (nums[i] +d >0 &&idx <queries.length) {
13+
int[]q =queries[idx];
14+
if (i >=q[0] &&i <=q[1]) {
15+
d -=q[2];
16+
}
17+
diff[q[0]] -=q[2];
18+
if (q[1] +1 <nums.length) {
19+
diff[q[1] +1] +=q[2];
20+
}
21+
idx++;
22+
}
23+
if (nums[i] +d >0) {
24+
return -1;
25+
}
26+
}
27+
returnidx;
28+
}
29+
}
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
3356\. Zero Array Transformation II
2+
3+
Medium
4+
5+
You are given an integer array`nums` of length`n` and a 2D array`queries` where <code>queries[i] =[l<sub>i</sub>, r<sub>i</sub>, val<sub>i</sub>]</code>.
6+
7+
Each`queries[i]` represents the following action on`nums`:
8+
9+
* Decrement the value at each index in the range <code>[l<sub>i</sub>, r<sub>i</sub>]</code> in`nums` by**at most** <code>val<sub>i</sub></code>.
10+
* The amount by which each value is decremented can be chosen**independently** for each index.
11+
12+
A**Zero Array** is an array with all its elements equal to 0.
13+
14+
Return the**minimum** possible**non-negative** value of`k`, such that after processing the first`k` queries in**sequence**,`nums` becomes a**Zero Array**. If no such`k` exists, return -1.
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[2,0,2], queries =[[0,2,1],[0,2,1],[1,1,3]]
19+
20+
**Output:** 2
21+
22+
**Explanation:**
23+
24+
***For i = 0 (l = 0, r = 2, val = 1):**
25+
* Decrement values at indices`[0, 1, 2]` by`[1, 0, 1]` respectively.
26+
* The array will become`[1, 0, 1]`.
27+
***For i = 1 (l = 0, r = 2, val = 1):**
28+
* Decrement values at indices`[0, 1, 2]` by`[1, 0, 1]` respectively.
29+
* The array will become`[0, 0, 0]`, which is a Zero Array. Therefore, the minimum value of`k` is 2.
30+
31+
**Example 2:**
32+
33+
**Input:** nums =[4,3,2,1], queries =[[1,3,2],[0,2,1]]
34+
35+
**Output:**\-1
36+
37+
**Explanation:**
38+
39+
***For i = 0 (l = 1, r = 3, val = 2):**
40+
* Decrement values at indices`[1, 2, 3]` by`[2, 2, 1]` respectively.
41+
* The array will become`[4, 1, 0, 0]`.
42+
***For i = 1 (l = 0, r = 2, val\= 1):**
43+
* Decrement values at indices`[0, 1, 2]` by`[1, 1, 0]` respectively.
44+
* The array will become`[3, 0, 0, 0]`, which is not a Zero Array.
45+
46+
**Constraints:**
47+
48+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
49+
* <code>0 <= nums[i] <= 5 * 10<sup>5</sup></code>
50+
* <code>1 <= queries.length <= 10<sup>5</sup></code>
51+
*`queries[i].length == 3`
52+
* <code>0 <= l<sub>i</sub> <= r<sub>i</sub> < nums.length</code>
53+
* <code>1 <= val<sub>i</sub> <= 5</code>
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
packageg3301_3400.s3357_minimize_the_maximum_adjacent_element_difference;
2+
3+
// #Hard #Array #Greedy #Binary_Search #2024_11_19_Time_5_ms_(100.00%)_Space_59.2_MB_(29.41%)
4+
5+
publicclassSolution {
6+
publicintminDifference(int[]nums) {
7+
intn =nums.length;
8+
intmaxAdj =0;
9+
intmina =Integer.MAX_VALUE;
10+
intmaxb =Integer.MIN_VALUE;
11+
for (inti =0;i <n -1; ++i) {
12+
inta =nums[i];
13+
intb =nums[i +1];
14+
if (a >0 &&b >0) {
15+
maxAdj =Math.max(maxAdj,Math.abs(a -b));
16+
}elseif (a >0 ||b >0) {
17+
mina =Math.min(mina,Math.max(a,b));
18+
maxb =Math.max(maxb,Math.max(a,b));
19+
}
20+
}
21+
intres =0;
22+
for (inti =0;i <n; ++i) {
23+
if ((i >0 &&nums[i -1] == -1) ||nums[i] >0) {
24+
continue;
25+
}
26+
intj =i;
27+
while (j <n &&nums[j] == -1) {
28+
j++;
29+
}
30+
inta =Integer.MAX_VALUE;
31+
intb =Integer.MIN_VALUE;
32+
if (i >0) {
33+
a =Math.min(a,nums[i -1]);
34+
b =Math.max(b,nums[i -1]);
35+
}
36+
if (j <n) {
37+
a =Math.min(a,nums[j]);
38+
b =Math.max(b,nums[j]);
39+
}
40+
if (a <=b) {
41+
if (j -i ==1) {
42+
res =Math.max(res,Math.min(maxb -a,b -mina));
43+
}else {
44+
res =
45+
Math.max(
46+
res,
47+
Math.min(
48+
maxb -a,
49+
Math.min(b -mina, (maxb -mina +2) /3 *2)));
50+
}
51+
}
52+
}
53+
returnMath.max(maxAdj, (res +1) /2);
54+
}
55+
}
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
3357\. Minimize the Maximum Adjacent Element Difference
2+
3+
Hard
4+
5+
You are given an array of integers`nums`. Some values in`nums` are**missing** and are denoted by -1.
6+
7+
You can choose a pair of**positive** integers`(x, y)`**exactly once** and replace each**missing** element with_either_`x` or`y`.
8+
9+
You need to**minimize** the**maximum****absolute difference** between_adjacent_ elements of`nums` after replacements.
10+
11+
Return the**minimum** possible difference.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[1,2,-1,10,8]
16+
17+
**Output:** 4
18+
19+
**Explanation:**
20+
21+
By choosing the pair as`(6, 7)`, nums can be changed to`[1, 2, 6, 10, 8]`.
22+
23+
The absolute differences between adjacent elements are:
24+
25+
*`|1 - 2| == 1`
26+
*`|2 - 6| == 4`
27+
*`|6 - 10| == 4`
28+
*`|10 - 8| == 2`
29+
30+
**Example 2:**
31+
32+
**Input:** nums =[-1,-1,-1]
33+
34+
**Output:** 0
35+
36+
**Explanation:**
37+
38+
By choosing the pair as`(4, 4)`, nums can be changed to`[4, 4, 4]`.
39+
40+
**Example 3:**
41+
42+
**Input:** nums =[-1,10,-1,8]
43+
44+
**Output:** 1
45+
46+
**Explanation:**
47+
48+
By choosing the pair as`(11, 9)`, nums can be changed to`[11, 10, 9, 8]`.
49+
50+
**Constraints:**
51+
52+
* <code>2 <= nums.length <= 10<sup>5</sup></code>
53+
*`nums[i]` is either -1 or in the range <code>[1, 10<sup>9</sup>]</code>.
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packageg3301_3400.s3354_make_array_elements_equal_to_zero;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidcountValidSelections() {
11+
assertThat(newSolution().countValidSelections(newint[] {1,0,2,0,3}),equalTo(2));
12+
}
13+
14+
@Test
15+
voidcountValidSelections2() {
16+
assertThat(
17+
newSolution().countValidSelections(newint[] {2,3,4,0,4,1,0}),equalTo(0));
18+
}
19+
20+
@Test
21+
voidcountValidSelections3() {
22+
assertThat(
23+
newSolution()
24+
.countValidSelections(newint[] {16,13,10,0,0,0,10,6,7,8,7}),
25+
equalTo(3));
26+
}
27+
}

0 commit comments

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