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

Commit952c5da

Browse files
authored
Added tasks 3360-3373
1 parent818ed59 commit952c5da

File tree

36 files changed

+1462
-0
lines changed

36 files changed

+1462
-0
lines changed
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg3301_3400.s3360_stone_removal_game;
2+
3+
// #Easy #Math #Simulation #2024_12_03_Time_0_ms_(100.00%)_Space_40.3_MB_(80.86%)
4+
5+
publicclassSolution {
6+
publicbooleancanAliceWin(intn) {
7+
if (n <10) {
8+
returnfalse;
9+
}
10+
intstonesRemaining =n -10;
11+
intstonesToBeRemoved =9;
12+
inti =1;
13+
while (stonesRemaining >=stonesToBeRemoved) {
14+
stonesRemaining -=stonesToBeRemoved;
15+
i++;
16+
stonesToBeRemoved--;
17+
}
18+
returni %2 !=0;
19+
}
20+
}
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
3360\. Stone Removal Game
2+
3+
Easy
4+
5+
Alice and Bob are playing a game where they take turns removing stones from a pile, with_Alice going first_.
6+
7+
* Alice starts by removing**exactly** 10 stones on her first turn.
8+
* For each subsequent turn, each player removes**exactly** 1 fewer stone than the previous opponent.
9+
10+
The player who cannot make a move loses the game.
11+
12+
Given a positive integer`n`, return`true` if Alice wins the game and`false` otherwise.
13+
14+
**Example 1:**
15+
16+
**Input:** n = 12
17+
18+
**Output:** true
19+
20+
**Explanation:**
21+
22+
* Alice removes 10 stones on her first turn, leaving 2 stones for Bob.
23+
* Bob cannot remove 9 stones, so Alice wins.
24+
25+
**Example 2:**
26+
27+
**Input:** n = 1
28+
29+
**Output:** false
30+
31+
**Explanation:**
32+
33+
* Alice cannot remove 10 stones, so Alice loses.
34+
35+
**Constraints:**
36+
37+
*`1 <= n <= 50`
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
packageg3301_3400.s3361_shift_distance_between_two_strings;
2+
3+
// #Medium #Array #String #Prefix_Sum #2024_12_03_Time_9_ms_(100.00%)_Space_45.8_MB_(36.02%)
4+
5+
publicclassSolution {
6+
publiclongshiftDistance(Strings,Stringt,int[]nextCost,int[]previousCost) {
7+
long[][]costs =newlong[26][26];
8+
longcost;
9+
for (inti =0;i <26;i++) {
10+
cost =nextCost[i];
11+
intj =i ==25 ?0 :i +1;
12+
while (j !=i) {
13+
costs[i][j] =cost;
14+
cost +=nextCost[j];
15+
if (j ==25) {
16+
j = -1;
17+
}
18+
j++;
19+
}
20+
}
21+
for (inti =0;i <26;i++) {
22+
cost =previousCost[i];
23+
intj =i ==0 ?25 :i -1;
24+
while (j !=i) {
25+
costs[i][j] =Math.min(costs[i][j],cost);
26+
cost +=previousCost[j];
27+
if (j ==0) {
28+
j =26;
29+
}
30+
j--;
31+
}
32+
}
33+
intn =s.length();
34+
longans =0;
35+
for (inti =0;i <n;i++) {
36+
ans +=costs[s.charAt(i) -'a'][t.charAt(i) -'a'];
37+
}
38+
returnans;
39+
}
40+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
3361\. Shift Distance Between Two Strings
2+
3+
Medium
4+
5+
You are given two strings`s` and`t` of the same length, and two integer arrays`nextCost` and`previousCost`.
6+
7+
In one operation, you can pick any index`i` of`s`, and perform**either one** of the following actions:
8+
9+
* Shift`s[i]` to the next letter in the alphabet. If`s[i] == 'z'`, you should replace it with`'a'`. This operation costs`nextCost[j]` where`j` is the index of`s[i]` in the alphabet.
10+
* Shift`s[i]` to the previous letter in the alphabet. If`s[i] == 'a'`, you should replace it with`'z'`. This operation costs`previousCost[j]` where`j` is the index of`s[i]` in the alphabet.
11+
12+
The**shift distance** is the**minimum** total cost of operations required to transform`s` into`t`.
13+
14+
Return the**shift distance** from`s` to`t`.
15+
16+
**Example 1:**
17+
18+
**Input:** s = "abab", t = "baba", nextCost =[100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], previousCost =[1,100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
19+
20+
**Output:** 2
21+
22+
**Explanation:**
23+
24+
* We choose index`i = 0` and shift`s[0]` 25 times to the previous character for a total cost of 1.
25+
* We choose index`i = 1` and shift`s[1]` 25 times to the next character for a total cost of 0.
26+
* We choose index`i = 2` and shift`s[2]` 25 times to the previous character for a total cost of 1.
27+
* We choose index`i = 3` and shift`s[3]` 25 times to the next character for a total cost of 0.
28+
29+
**Example 2:**
30+
31+
**Input:** s = "leet", t = "code", nextCost =[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], previousCost =[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
32+
33+
**Output:** 31
34+
35+
**Explanation:**
36+
37+
* We choose index`i = 0` and shift`s[0]` 9 times to the previous character for a total cost of 9.
38+
* We choose index`i = 1` and shift`s[1]` 10 times to the next character for a total cost of 10.
39+
* We choose index`i = 2` and shift`s[2]` 1 time to the previous character for a total cost of 1.
40+
* We choose index`i = 3` and shift`s[3]` 11 times to the next character for a total cost of 11.
41+
42+
**Constraints:**
43+
44+
* <code>1 <= s.length == t.length <= 10<sup>5</sup></code>
45+
*`s` and`t` consist only of lowercase English letters.
46+
*`nextCost.length == previousCost.length == 26`
47+
* <code>0 <= nextCost[i], previousCost[i] <= 10<sup>9</sup></code>
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
packageg3301_3400.s3362_zero_array_transformation_iii;
2+
3+
// #Medium #Array #Sorting #Greedy #Heap_Priority_Queue #Prefix_Sum
4+
// #2024_12_03_Time_68_ms_(91.99%)_Space_93.6_MB_(45.88%)
5+
6+
importjava.util.Arrays;
7+
importjava.util.PriorityQueue;
8+
9+
publicclassSolution {
10+
publicintmaxRemoval(int[]nums,int[][]queries) {
11+
Arrays.sort(queries, (a,b) ->a[0] -b[0]);
12+
PriorityQueue<Integer>last =newPriorityQueue<>((a,b) ->b -a);
13+
int[]diffs =newint[nums.length +1];
14+
intidx =0;
15+
intcur =0;
16+
for (inti =0;i <nums.length;i++) {
17+
while (idx <queries.length &&queries[idx][0] ==i) {
18+
last.add(queries[idx][1]);
19+
idx++;
20+
}
21+
cur +=diffs[i];
22+
while (cur <nums[i] && !last.isEmpty() &&last.peek() >=i) {
23+
cur++;
24+
diffs[last.poll() +1]--;
25+
}
26+
if (cur <nums[i]) {
27+
return -1;
28+
}
29+
}
30+
returnlast.size();
31+
}
32+
}
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
3362\. Zero Array Transformation III
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+
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** 1.
10+
* The amount by which the 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**maximum** number of elements that can be removed from`queries`, such that`nums` can still be converted to a**zero array** using the_remaining_ queries. If it is not possible to convert`nums` to a**zero array**, return -1.
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[2,0,2], queries =[[0,2],[0,2],[1,1]]
19+
20+
**Output:** 1
21+
22+
**Explanation:**
23+
24+
After removing`queries[2]`,`nums` can still be converted to a zero array.
25+
26+
* Using`queries[0]`, decrement`nums[0]` and`nums[2]` by 1 and`nums[1]` by 0.
27+
* Using`queries[1]`, decrement`nums[0]` and`nums[2]` by 1 and`nums[1]` by 0.
28+
29+
**Example 2:**
30+
31+
**Input:** nums =[1,1,1,1], queries =[[1,3],[0,2],[1,3],[1,2]]
32+
33+
**Output:** 2
34+
35+
**Explanation:**
36+
37+
We can remove`queries[2]` and`queries[3]`.
38+
39+
**Example 3:**
40+
41+
**Input:** nums =[1,2,3,4], queries =[[0,3]]
42+
43+
**Output:**\-1
44+
45+
**Explanation:**
46+
47+
`nums` cannot be converted to a zero array even after using all the queries.
48+
49+
**Constraints:**
50+
51+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
52+
* <code>0 <= nums[i] <= 10<sup>5</sup></code>
53+
* <code>1 <= queries.length <= 10<sup>5</sup></code>
54+
*`queries[i].length == 2`
55+
* <code>0 <= l<sub>i</sub> <= r<sub>i</sub> < nums.length</code>
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
packageg3301_3400.s3363_find_the_maximum_number_of_fruits_collected;
2+
3+
// #Hard #Array #Dynamic_Programming #Matrix #2024_12_03_Time_12_ms_(91.34%)_Space_142.1_MB_(88.96%)
4+
5+
publicclassSolution {
6+
publicintmaxCollectedFruits(int[][]fruits) {
7+
intn =fruits.length;
8+
// Set inaccessible cells to 0
9+
for (inti =0;i <n; ++i) {
10+
for (intj =0;j <n; ++j) {
11+
if (i <j &&j <n -1 -i) {
12+
fruits[i][j] =0;
13+
}
14+
if (j <i &&i <n -1 -j) {
15+
fruits[i][j] =0;
16+
}
17+
}
18+
}
19+
intres =0;
20+
for (inti =0;i <n; ++i) {
21+
res +=fruits[i][i];
22+
}
23+
for (inti =1;i <n; ++i) {
24+
for (intj =i +1;j <n; ++j) {
25+
fruits[i][j] +=
26+
Math.max(
27+
fruits[i -1][j -1],
28+
Math.max(fruits[i -1][j], (j +1 <n) ?fruits[i -1][j +1] :0));
29+
}
30+
}
31+
for (intj =1;j <n; ++j) {
32+
for (inti =j +1;i <n; ++i) {
33+
fruits[i][j] +=
34+
Math.max(
35+
fruits[i -1][j -1],
36+
Math.max(fruits[i][j -1], (i +1 <n) ?fruits[i +1][j -1] :0));
37+
}
38+
}
39+
returnres +fruits[n -1][n -2] +fruits[n -2][n -1];
40+
}
41+
}
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
3363\. Find the Maximum Number of Fruits Collected
2+
3+
Hard
4+
5+
There is a game dungeon comprised of`n x n` rooms arranged in a grid.
6+
7+
You are given a 2D array`fruits` of size`n x n`, where`fruits[i][j]` represents the number of fruits in the room`(i, j)`. Three children will play in the game dungeon, with**initial** positions at the corner rooms`(0, 0)`,`(0, n - 1)`, and`(n - 1, 0)`.
8+
9+
The children will make**exactly**`n - 1` moves according to the following rules to reach the room`(n - 1, n - 1)`:
10+
11+
* The child starting from`(0, 0)` must move from their current room`(i, j)` to one of the rooms`(i + 1, j + 1)`,`(i + 1, j)`, and`(i, j + 1)` if the target room exists.
12+
* The child starting from`(0, n - 1)` must move from their current room`(i, j)` to one of the rooms`(i + 1, j - 1)`,`(i + 1, j)`, and`(i + 1, j + 1)` if the target room exists.
13+
* The child starting from`(n - 1, 0)` must move from their current room`(i, j)` to one of the rooms`(i - 1, j + 1)`,`(i, j + 1)`, and`(i + 1, j + 1)` if the target room exists.
14+
15+
When a child enters a room, they will collect all the fruits there. If two or more children enter the same room, only one child will collect the fruits, and the room will be emptied after they leave.
16+
17+
Return the**maximum** number of fruits the children can collect from the dungeon.
18+
19+
**Example 1:**
20+
21+
**Input:** fruits =[[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]
22+
23+
**Output:** 100
24+
25+
**Explanation:**
26+
27+
![](https://assets.leetcode.com/uploads/2024/10/15/example_1.gif)
28+
29+
In this example:
30+
31+
* The 1<sup>st</sup> child (green) moves on the path`(0,0) -> (1,1) -> (2,2) -> (3, 3)`.
32+
* The 2<sup>nd</sup> child (red) moves on the path`(0,3) -> (1,2) -> (2,3) -> (3, 3)`.
33+
* The 3<sup>rd</sup> child (blue) moves on the path`(3,0) -> (3,1) -> (3,2) -> (3, 3)`.
34+
35+
In total they collect`1 + 6 + 11 + 1 + 4 + 8 + 12 + 13 + 14 + 15 = 100` fruits.
36+
37+
**Example 2:**
38+
39+
**Input:** fruits =[[1,1],[1,1]]
40+
41+
**Output:** 4
42+
43+
**Explanation:**
44+
45+
In this example:
46+
47+
* The 1<sup>st</sup> child moves on the path`(0,0) -> (1,1)`.
48+
* The 2<sup>nd</sup> child moves on the path`(0,1) -> (1,1)`.
49+
* The 3<sup>rd</sup> child moves on the path`(1,0) -> (1,1)`.
50+
51+
In total they collect`1 + 1 + 1 + 1 = 4` fruits.
52+
53+
**Constraints:**
54+
55+
*`2 <= n == fruits.length == fruits[i].length <= 1000`
56+
*`0 <= fruits[i][j] <= 1000`
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg3301_3400.s3364_minimum_positive_sum_subarray;
2+
3+
// #Easy #Array #Prefix_Sum #Sliding_Window #2024_12_03_Time_1_ms_(100.00%)_Space_44.5_MB_(38.75%)
4+
5+
importjava.util.List;
6+
7+
publicclassSolution {
8+
publicintminimumSumSubarray(List<Integer>li,intl,intr) {
9+
intn =li.size();
10+
intmin =Integer.MAX_VALUE;
11+
int[]a =newint[n +1];
12+
for (inti =1;i <=n;i++) {
13+
a[i] =a[i -1] +li.get(i -1);
14+
}
15+
for (intsize =l;size <=r;size++) {
16+
for (inti =size -1;i <n;i++) {
17+
intsum =a[i +1] -a[i +1 -size];
18+
if (sum >0) {
19+
min =Math.min(min,sum);
20+
}
21+
}
22+
}
23+
returnmin ==Integer.MAX_VALUE ? -1 :min;
24+
}
25+
}

0 commit comments

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