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

Commitaca8642

Browse files
authored
Added tasks 2554-2559
1 parent35468ca commitaca8642

File tree

15 files changed

+485
-0
lines changed

15 files changed

+485
-0
lines changed
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2501_2600.s2554_maximum_number_of_integers_to_choose_from_a_range_i;
2+
3+
// #Medium #Array #Hash_Table #Sorting #Greedy #Binary_Search
4+
// #2023_08_19_Time_4_ms_(100.00%)_Space_44.9_MB_(17.88%)
5+
6+
publicclassSolution {
7+
publicintmaxCount(int[]banned,intn,intmaxSum) {
8+
boolean[]arr =newboolean[10002];
9+
for (intj :banned) {
10+
arr[j] =true;
11+
}
12+
intsum =0;
13+
intcount =0;
14+
for (inti =1;i <=n;i++) {
15+
if (!arr[i]) {
16+
sum +=i;
17+
if (sum >maxSum) {
18+
returncount;
19+
}
20+
count++;
21+
}
22+
}
23+
returncount;
24+
}
25+
}
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
2554\. Maximum Number of Integers to Choose From a Range I
2+
3+
Medium
4+
5+
You are given an integer array`banned` and two integers`n` and`maxSum`. You are choosing some number of integers following the below rules:
6+
7+
* The chosen integers have to be in the range`[1, n]`.
8+
* Each integer can be chosen**at most once**.
9+
* The chosen integers should not be in the array`banned`.
10+
* The sum of the chosen integers should not exceed`maxSum`.
11+
12+
Return_the**maximum** number of integers you can choose following the mentioned rules_.
13+
14+
**Example 1:**
15+
16+
**Input:** banned =[1,6,5], n = 5, maxSum = 6
17+
18+
**Output:** 2
19+
20+
**Explanation:**
21+
22+
You can choose the integers 2 and 4.
23+
24+
2 and 4 are from the range[1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.
25+
26+
**Example 2:**
27+
28+
**Input:** banned =[1,2,3,4,5,6,7], n = 8, maxSum = 1
29+
30+
**Output:** 0
31+
32+
**Explanation:**
33+
34+
You cannot choose any integer while following the mentioned conditions.
35+
36+
**Example 3:**
37+
38+
**Input:** banned =[11], n = 7, maxSum = 50
39+
40+
**Output:** 7
41+
42+
**Explanation:**
43+
44+
You can choose the integers 1, 2, 3, 4, 5, 6, and 7. They are from the range[1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.
45+
46+
**Constraints:**
47+
48+
* <code>1 <= banned.length <= 10<sup>4</sup></code>
49+
* <code>1 <= banned[i], n <= 10<sup>4</sup></code>
50+
* <code>1 <= maxSum <= 10<sup>9</sup></code>
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
packageg2501_2600.s2555_maximize_win_from_two_segments;
2+
3+
// #Medium #Array #Binary_Search #Sliding_Window
4+
// #2023_08_19_Time_5_ms_(90.10%)_Space_55.4_MB_(45.54%)
5+
6+
publicclassSolution {
7+
publicintmaximizeWin(int[]a,intk) {
8+
intj =0;
9+
inti;
10+
intn =a.length;
11+
int[]dp =newint[n +1];
12+
intans =0;
13+
for (i =0;i <a.length;i++) {
14+
while (a[i] -a[j] >k) {
15+
j++;
16+
}
17+
dp[i +1] =Math.max(dp[i],i -j +1);
18+
ans =Math.max(ans,dp[j] +i -j +1);
19+
}
20+
returnans;
21+
}
22+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
2555\. Maximize Win From Two Segments
2+
3+
Medium
4+
5+
There are some prizes on the**X-axis**. You are given an integer array`prizePositions` that is**sorted in non-decreasing order**, where`prizePositions[i]` is the position of the <code>i<sup>th</sup></code> prize. There could be different prizes at the same position on the line. You are also given an integer`k`.
6+
7+
You are allowed to select two segments with integer endpoints. The length of each segment must be`k`. You will collect all prizes whose position falls within at least one of the two selected segments (including the endpoints of the segments). The two selected segments may intersect.
8+
9+
* For example if`k = 2`, you can choose segments`[1, 3]` and`[2, 4]`, and you will win any prize i that satisfies`1 <= prizePositions[i] <= 3` or`2 <= prizePositions[i] <= 4`.
10+
11+
Return_the**maximum** number of prizes you can win if you choose the two segments optimally_.
12+
13+
**Example 1:**
14+
15+
**Input:** prizePositions =[1,1,2,2,3,3,5], k = 2
16+
17+
**Output:** 7
18+
19+
**Explanation:**
20+
21+
In this example, you can win all 7 prizes by selecting two segments[1, 3] and[3, 5].
22+
23+
**Example 2:**
24+
25+
**Input:** prizePositions =[1,2,3,4], k = 0
26+
27+
**Output:** 2
28+
29+
**Explanation:**
30+
31+
For this example,**one choice** for the segments is`[3, 3]` and`[4, 4],` and you will be able to get`2` prizes.
32+
33+
**Constraints:**
34+
35+
* <code>1 <= prizePositions.length <= 10<sup>5</sup></code>
36+
* <code>1 <= prizePositions[i] <= 10<sup>9</sup></code>
37+
* <code>0 <= k <= 10<sup>9</sup></code>
38+
*`prizePositions` is sorted in non-decreasing order.
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
packageg2501_2600.s2556_disconnect_path_in_a_binary_matrix_by_at_most_one_flip;
2+
3+
// #Medium #Array #Dynamic_Programming #Depth_First_Search #Breadth_First_Search #Matrix
4+
// #2023_08_19_Time_0_ms_(100.00%)_Space_54.4_MB_(97.73%)
5+
6+
publicclassSolution {
7+
privateintn;
8+
privateintm;
9+
10+
publicbooleanisPossibleToCutPath(int[][]g) {
11+
n =g.length;
12+
m =g[0].length;
13+
if (!dfs(0,0,g)) {
14+
returntrue;
15+
}
16+
g[0][0] =1;
17+
return !dfs(0,0,g);
18+
}
19+
20+
privatebooleandfs(intr,intc,int[][]g) {
21+
if (r ==n -1 &&c ==m -1) {
22+
returntrue;
23+
}
24+
if (r ==n ||c ==m ||g[r][c] ==0) {
25+
returnfalse;
26+
}
27+
g[r][c] =0;
28+
returndfs(r,c +1,g) ||dfs(r +1,c,g);
29+
}
30+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
2556\. Disconnect Path in a Binary Matrix by at Most One Flip
2+
3+
Medium
4+
5+
You are given a**0-indexed**`m x n`**binary** matrix`grid`. You can move from a cell`(row, col)` to any of the cells`(row + 1, col)` or`(row, col + 1)` that has the value`1`. The matrix is**disconnected** if there is no path from`(0, 0)` to`(m - 1, n - 1)`.
6+
7+
You can flip the value of**at most one** (possibly none) cell. You**cannot flip** the cells`(0, 0)` and`(m - 1, n - 1)`.
8+
9+
Return`true`_if it is possible to make the matrix disconnect or_`false`_otherwise_.
10+
11+
**Note** that flipping a cell changes its value from`0` to`1` or from`1` to`0`.
12+
13+
**Example 1:**
14+
15+
![](https://assets.leetcode.com/uploads/2022/12/07/yetgrid2drawio.png)
16+
17+
**Input:** grid =[[1,1,1],[1,0,0],[1,1,1]]
18+
19+
**Output:** true
20+
21+
**Explanation:**
22+
23+
We can change the cell shown in the diagram above. There is no path from (0, 0) to (2, 2) in the resulting grid.
24+
25+
**Example 2:**
26+
27+
![](https://assets.leetcode.com/uploads/2022/12/07/yetgrid3drawio.png)
28+
29+
**Input:** grid =[[1,1,1],[1,0,1],[1,1,1]]
30+
31+
**Output:** false
32+
33+
**Explanation:**
34+
35+
It is not possible to change at most one cell such that there is not path from (0, 0) to (2, 2).
36+
37+
**Constraints:**
38+
39+
*`m == grid.length`
40+
*`n == grid[i].length`
41+
*`1 <= m, n <= 1000`
42+
* <code>1 <= m * n <= 10<sup>5</sup></code>
43+
*`grid[i][j]` is either`0` or`1`.
44+
*`grid[0][0] == grid[m - 1][n - 1] == 1`
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageg2501_2600.s2558_take_gifts_from_the_richest_pile;
2+
3+
// #Easy #Array #Heap_Priority_Queue #Simulation
4+
// #2023_08_19_Time_5_ms_(97.80%)_Space_41.8_MB_(25.67%)
5+
6+
importjava.util.PriorityQueue;
7+
8+
publicclassSolution {
9+
publiclongpickGifts(int[]gifts,intk) {
10+
PriorityQueue<Integer>pq =newPriorityQueue<>((a,b) -> (b -a));
11+
longres =0;
12+
for (intgift :gifts) {
13+
pq.add(gift);
14+
}
15+
while (!pq.isEmpty() &&k >0) {
16+
longval =pq.poll();
17+
intnewVal = (int)Math.sqrt(val);
18+
pq.add(newVal);
19+
k--;
20+
}
21+
while (!pq.isEmpty()) {
22+
res +=pq.poll();
23+
}
24+
returnres;
25+
}
26+
}
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
2558\. Take Gifts From the Richest Pile
2+
3+
Easy
4+
5+
You are given an integer array`gifts` denoting the number of gifts in various piles. Every second, you do the following:
6+
7+
* Choose the pile with the maximum number of gifts.
8+
* If there is more than one pile with the maximum number of gifts, choose any.
9+
* Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.
10+
11+
Return_the number of gifts remaining after_`k`_seconds._
12+
13+
**Example 1:**
14+
15+
**Input:** gifts =[25,64,9,4,100], k = 4
16+
17+
**Output:** 29
18+
19+
**Explanation:** The gifts are taken in the following way:
20+
21+
- In the first second, the last pile is chosen and 10 gifts are left behind.
22+
- Then the second pile is chosen and 8 gifts are left behind.
23+
- After that the first pile is chosen and 5 gifts are left behind.
24+
- Finally, the last pile is chosen again and 3 gifts are left behind.
25+
26+
The final remaining gifts are[5,8,9,4,3], so the total number of gifts remaining is 29.
27+
28+
**Example 2:**
29+
30+
**Input:** gifts =[1,1,1,1], k = 4
31+
32+
**Output:** 4
33+
34+
**Explanation:**
35+
36+
In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile.
37+
38+
That is, you can't take any pile with you.
39+
40+
So, the total gifts remaining are 4.
41+
42+
**Constraints:**
43+
44+
* <code>1 <= gifts.length <= 10<sup>3</sup></code>
45+
* <code>1 <= gifts[i] <= 10<sup>9</sup></code>
46+
* <code>1 <= k <= 10<sup>3</sup></code>
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
packageg2501_2600.s2559_count_vowel_strings_in_ranges;
2+
3+
// #Medium #Array #String #Prefix_Sum #2023_08_19_Time_4_ms_(99.59%)_Space_85.6_MB_(78.46%)
4+
5+
publicclassSolution {
6+
privatebooleanvalidWord(Strings) {
7+
charcStart =s.charAt(0);
8+
charcEnd =s.charAt(s.length() -1);
9+
booleanflag1 =
10+
cStart =='a' ||cStart =='e' ||cStart =='i' ||cStart =='o' ||cStart =='u';
11+
booleanflag2 =cEnd =='a' ||cEnd =='e' ||cEnd =='i' ||cEnd =='o' ||cEnd =='u';
12+
returnflag1 &&flag2;
13+
}
14+
15+
publicint[]vowelStrings(String[]words,int[][]queries) {
16+
int[]prefixArr =newint[words.length];
17+
prefixArr[0] =validWord(words[0]) ?1 :0;
18+
for (inti =1;i <words.length; ++i) {
19+
if (validWord(words[i])) {
20+
prefixArr[i] =prefixArr[i -1] +1;
21+
}else {
22+
prefixArr[i] =prefixArr[i -1];
23+
}
24+
}
25+
int[]res =newint[queries.length];
26+
for (inti =0;i <queries.length; ++i) {
27+
intupperBound =queries[i][1];
28+
intlowerBound =queries[i][0];
29+
intval =
30+
(lowerBound ==0)
31+
?prefixArr[upperBound]
32+
:prefixArr[upperBound] -prefixArr[lowerBound -1];
33+
res[i] =val;
34+
}
35+
returnres;
36+
}
37+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
2559\. Count Vowel Strings in Ranges
2+
3+
Medium
4+
5+
You are given a**0-indexed** array of strings`words` and a 2D array of integers`queries`.
6+
7+
Each query <code>queries[i] =[l<sub>i</sub>, r<sub>i</sub>]</code> asks us to find the number of strings present in the range <code>l<sub>i</sub></code> to <code>r<sub>i</sub></code> (both**inclusive**) of`words` that start and end with a vowel.
8+
9+
Return_an array_`ans`_of size_`queries.length`_, where_`ans[i]`_is the answer to the_`i`<sup>th</sup>_query_.
10+
11+
**Note** that the vowel letters are`'a'`,`'e'`,`'i'`,`'o'`, and`'u'`.
12+
13+
**Example 1:**
14+
15+
**Input:** words =["aba","bcb","ece","aa","e"], queries =[[0,2],[1,4],[1,1]]
16+
17+
**Output:**[2,3,0]
18+
19+
**Explanation:** The strings starting and ending with a vowel are "aba", "ece", "aa" and "e".
20+
21+
The answer to the query[0,2] is 2 (strings "aba" and "ece").
22+
23+
to query[1,4] is 3 (strings "ece", "aa", "e").
24+
25+
to query[1,1] is 0.
26+
27+
We return[2,3,0].
28+
29+
**Example 2:**
30+
31+
**Input:** words =["a","e","i"], queries =[[0,2],[0,1],[2,2]]
32+
33+
**Output:**[3,2,1]
34+
35+
**Explanation:** Every string satisfies the conditions, so we return[3,2,1].
36+
37+
**Constraints:**
38+
39+
* <code>1 <= words.length <= 10<sup>5</sup></code>
40+
*`1 <= words[i].length <= 40`
41+
*`words[i]` consists only of lowercase English letters.
42+
* <code>sum(words[i].length) <= 3 * 10<sup>5</sup></code>
43+
* <code>1 <= queries.length <= 10<sup>5</sup></code>
44+
* <code>0 <= l<sub>i</sub> <= r<sub>i</sub> < words.length</code>

0 commit comments

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