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

Commitda6ac41

Browse files
authored
Added tasks 2585-2589
1 parent8800c47 commitda6ac41

File tree

15 files changed

+476
-0
lines changed

15 files changed

+476
-0
lines changed
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
packageg2501_2600.s2585_number_of_ways_to_earn_points;
2+
3+
// #Hard #Array #Dynamic_Programming #2023_08_22_Time_56_ms_(76.40%)_Space_43.9_MB_(21.91%)
4+
5+
publicclassSolution {
6+
privatestaticfinalintMOD =1000000007;
7+
privateInteger[][]memo;
8+
9+
privateinthelper(int[][]types,inttarget,inttypeIndex) {
10+
intn =types.length;
11+
if (typeIndex >=n) {
12+
returntarget ==0 ?1 :0;
13+
}
14+
if (memo[typeIndex][target] !=null) {
15+
returnmemo[typeIndex][target];
16+
}
17+
intways =0;
18+
ways = (ways +helper(types,target,typeIndex +1)) %MOD;
19+
intcurrQuestCount =types[typeIndex][0];
20+
intcurrQuestPoint =types[typeIndex][1];
21+
intpointsEarned;
22+
for (intquest =1;quest <=currQuestCount;quest++) {
23+
pointsEarned =quest *currQuestPoint;
24+
if (pointsEarned >target) {
25+
break;
26+
}
27+
ways = (ways +helper(types,target -pointsEarned,typeIndex +1)) %MOD;
28+
}
29+
memo[typeIndex][target] =ways;
30+
returnmemo[typeIndex][target];
31+
}
32+
33+
publicintwaysToReachTarget(inttarget,int[][]types) {
34+
intn =types.length;
35+
memo =newInteger[n +1][target +1];
36+
returnhelper(types,target,0);
37+
}
38+
}
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
2585\. Number of Ways to Earn Points
2+
3+
Hard
4+
5+
There is a test that has`n` types of questions. You are given an integer`target` and a**0-indexed** 2D integer array`types` where <code>types[i] =[count<sub>i</sub>, marks<sub>i</sub>]</code> indicates that there are <code>count<sub>i</sub></code> questions of the <code>i<sup>th</sup></code> type, and each one of them is worth <code>marks<sub>i</sub></code> points.
6+
7+
Return_the number of ways you can earn**exactly**_`target`_points in the exam_. Since the answer may be too large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
8+
9+
**Note** that questions of the same type are indistinguishable.
10+
11+
* For example, if there are`3` questions of the same type, then solving the <code>1<sup>st</sup></code> and <code>2<sup>nd</sup></code> questions is the same as solving the <code>1<sup>st</sup></code> and <code>3<sup>rd</sup></code> questions, or the <code>2<sup>nd</sup></code> and <code>3<sup>rd</sup></code> questions.
12+
13+
**Example 1:**
14+
15+
**Input:** target = 6, types =[[6,1],[3,2],[2,3]]
16+
17+
**Output:** 7
18+
19+
**Explanation:** You can earn 6 points in one of the seven ways:
20+
21+
- Solve 6 questions of the 0<sup>th</sup> type: 1 + 1 + 1 + 1 + 1 + 1 = 6
22+
- Solve 4 questions of the 0<sup>th</sup> type and 1 question of the 1<sup>st</sup> type: 1 + 1 + 1 + 1 + 2 = 6
23+
- Solve 2 questions of the 0<sup>th</sup> type and 2 questions of the 1<sup>st</sup> type: 1 + 1 + 2 + 2 = 6
24+
- Solve 3 questions of the 0<sup>th</sup> type and 1 question of the 2<sup>nd</sup> type: 1 + 1 + 1 + 3 = 6
25+
- Solve 1 question of the 0<sup>th</sup> type, 1 question of the 1<sup>st</sup> type and 1 question of the 2<sup>nd</sup> type: 1 + 2 + 3 = 6
26+
- Solve 3 questions of the 1<sup>st</sup> type: 2 + 2 + 2 = 6 - Solve 2 questions of the 2<sup>nd</sup> type: 3 + 3 = 6
27+
28+
**Example 2:**
29+
30+
**Input:** target = 5, types =[[50,1],[50,2],[50,5]]
31+
32+
**Output:** 4
33+
34+
**Explanation:** You can earn 5 points in one of the four ways:
35+
36+
- Solve 5 questions of the 0<sup>th</sup> type: 1 + 1 + 1 + 1 + 1 = 5
37+
- Solve 3 questions of the 0<sup>th</sup> type and 1 question of the 1<sup>st</sup> type: 1 + 1 + 1 + 2 = 5
38+
- Solve 1 questions of the 0<sup>th</sup> type and 2 questions of the 1<sup>st</sup> type: 1 + 2 + 2 = 5
39+
- Solve 1 question of the 2<sup>nd</sup> type: 5
40+
41+
**Example 3:**
42+
43+
**Input:** target = 18, types =[[6,1],[3,2],[2,3]]
44+
45+
**Output:** 1
46+
47+
**Explanation:** You can only earn 18 points by answering all questions.
48+
49+
**Constraints:**
50+
51+
*`1 <= target <= 1000`
52+
*`n == types.length`
53+
*`1 <= n <= 50`
54+
*`types[i].length == 2`
55+
* <code>1 <= count<sub>i</sub>, marks<sub>i</sub> <= 50</code>
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg2501_2600.s2586_count_the_number_of_vowel_strings_in_range;
2+
3+
// #Easy #Array #String #2023_08_22_Time_1_ms_(100.00%)_Space_43.1_MB_(79.90%)
4+
5+
publicclassSolution {
6+
publicintvowelStrings(String[]words,intleft,intright) {
7+
intcount =0;
8+
for (inti =left;i <=right;i++) {
9+
if (isVowel(words[i].charAt(0)) &&isVowel(words[i].charAt(words[i].length() -1))) {
10+
count++;
11+
}
12+
}
13+
returncount;
14+
}
15+
16+
privatebooleanisVowel(charch) {
17+
Stringstr ="aeiou";
18+
returnstr.indexOf(ch) != -1;
19+
}
20+
}
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
2586\. Count the Number of Vowel Strings in Range
2+
3+
Easy
4+
5+
You are given a**0-indexed** array of string`words` and two integers`left` and`right`.
6+
7+
A string is called a**vowel string** if it starts with a vowel character and ends with a vowel character where vowel characters are`'a'`,`'e'`,`'i'`,`'o'`, and`'u'`.
8+
9+
Return_the number of vowel strings_`words[i]`_where_`i`_belongs to the inclusive range_`[left, right]`.
10+
11+
**Example 1:**
12+
13+
**Input:** words =["are","amy","u"], left = 0, right = 2
14+
15+
**Output:** 2
16+
17+
**Explanation:**
18+
19+
- "are" is a vowel string because it starts with 'a' and ends with 'e'.
20+
21+
- "amy" is not a vowel string because it does not end with a vowel.
22+
23+
- "u" is a vowel string because it starts with 'u' and ends with 'u'. The number of vowel strings in the mentioned range is 2.
24+
25+
**Example 2:**
26+
27+
**Input:** words =["hey","aeo","mu","ooo","artro"], left = 1, right = 4
28+
29+
**Output:** 3
30+
31+
**Explanation:**
32+
33+
- "aeo" is a vowel string because it starts with 'a' and ends with 'o'.
34+
35+
- "mu" is not a vowel string because it does not start with a vowel.
36+
37+
- "ooo" is a vowel string because it starts with 'o' and ends with 'o'.
38+
39+
- "artro" is a vowel string because it starts with 'a' and ends with 'o'.
40+
41+
The number of vowel strings in the mentioned range is 3.
42+
43+
**Constraints:**
44+
45+
*`1 <= words.length <= 1000`
46+
*`1 <= words[i].length <= 10`
47+
*`words[i]` consists of only lowercase English letters.
48+
*`0 <= left <= right < words.length`
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
packageg2501_2600.s2587_rearrange_array_to_maximize_prefix_score;
2+
3+
// #Medium #Array #Sorting #Greedy #Prefix_Sum
4+
// #2023_08_22_Time_28_ms_(92.55%)_Space_57.7_MB_(77.66%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publicintmaxScore(int[]nums) {
10+
Arrays.sort(nums);
11+
intcount =0;
12+
longsum =0;
13+
for (inti =nums.length -1;i >=0;i--) {
14+
sum +=nums[i];
15+
if (sum >0) {
16+
count++;
17+
}
18+
}
19+
returncount;
20+
}
21+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2587\. Rearrange Array to Maximize Prefix Score
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums`. You can rearrange the elements of`nums` to**any order** (including the given order).
6+
7+
Let`prefix` be the array containing the prefix sums of`nums` after rearranging it. In other words,`prefix[i]` is the sum of the elements from`0` to`i` in`nums` after rearranging it. The**score** of`nums` is the number of positive integers in the array`prefix`.
8+
9+
Return_the maximum score you can achieve_.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[2,-1,0,1,-3,3,-3]
14+
15+
**Output:** 6
16+
17+
**Explanation:**
18+
19+
We can rearrange the array into nums =[2,3,1,-1,-3,0,-3].
20+
21+
prefix =[2,5,6,5,2,2,-1], so the score is 6.
22+
23+
It can be shown that 6 is the maximum score we can obtain.
24+
25+
**Example 2:**
26+
27+
**Input:** nums =[-2,-3,0]
28+
29+
**Output:** 0
30+
31+
**Explanation:** Any rearrangement of the array will result in a score of 0.
32+
33+
**Constraints:**
34+
35+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
36+
* <code>-10<sup>6</sup> <= nums[i] <= 10<sup>6</sup></code>
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
packageg2501_2600.s2588_count_the_number_of_beautiful_subarrays;
2+
3+
// #Medium #Array #Hash_Table #Bit_Manipulation #Prefix_Sum
4+
// #2023_08_22_Time_38_ms_(96.52%)_Space_58_MB_(52.17%)
5+
6+
importjava.util.HashMap;
7+
importjava.util.Map;
8+
9+
publicclassSolution {
10+
publiclongbeautifulSubarrays(int[]nums) {
11+
longcount =0;
12+
intxor =0;
13+
Map<Integer,Integer>map =newHashMap<>();
14+
map.put(0,1);
15+
for (intnum :nums) {
16+
xor ^=num;
17+
count +=map.merge(xor,1,Integer::sum) -1;
18+
}
19+
returncount;
20+
}
21+
}
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
2588\. Count the Number of Beautiful Subarrays
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums`. In one operation, you can:
6+
7+
* Choose two different indices`i` and`j` such that`0 <= i, j < nums.length`.
8+
* Choose a non-negative integer`k` such that the <code>k<sup>th</sup></code> bit (**0-indexed**) in the binary representation of`nums[i]` and`nums[j]` is`1`.
9+
* Subtract <code>2<sup>k</sup></code> from`nums[i]` and`nums[j]`.
10+
11+
A subarray is**beautiful** if it is possible to make all of its elements equal to`0` after applying the above operation any number of times.
12+
13+
Return_the number of**beautiful subarrays** in the array_`nums`.
14+
15+
A subarray is a contiguous**non-empty** sequence of elements within an array.
16+
17+
**Example 1:**
18+
19+
**Input:** nums =[4,3,1,2,4]
20+
21+
**Output:** 2
22+
23+
**Explanation:** There are 2 beautiful subarrays in nums:[4,<ins>3,1,2</ins>,4] and[<ins>4,3,1,2,4</ins>].
24+
- We can make all elements in the subarray[3,1,2] equal to 0 in the following way:
25+
- Choose[<ins>3</ins>, 1, <ins>2</ins>] and k = 1. Subtract 2<sup>1</sup> from both numbers. The subarray becomes[1, 1, 0].
26+
- Choose[<ins>1</ins>, <ins>1</ins>, 0] and k = 0. Subtract 2<sup>0</sup> from both numbers. The subarray becomes[0, 0, 0].
27+
- We can make all elements in the subarray[4,3,1,2,4] equal to 0 in the following way:
28+
- Choose[<ins>4</ins>, 3, 1, 2, <ins>4</ins>] and k = 2. Subtract 2<sup>2</sup> from both numbers. The subarray becomes[0, 3, 1, 2, 0].
29+
- Choose[0, <ins>3</ins>, <ins>1</ins>, 2, 0] and k = 0. Subtract 2<sup>0</sup> from both numbers. The subarray becomes[0, 2, 0, 2, 0].
30+
- Choose[0, <ins>2</ins>, 0, <ins>2</ins>, 0] and k = 1. Subtract 2<sup>1</sup> from both numbers. The subarray becomes[0, 0, 0, 0, 0].
31+
32+
**Example 2:**
33+
34+
**Input:** nums =[1,10,4]
35+
36+
**Output:** 0
37+
38+
**Explanation:** There are no beautiful subarrays in nums.
39+
40+
**Constraints:**
41+
42+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
43+
* <code>0 <= nums[i] <= 10<sup>6</sup></code>
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
packageg2501_2600.s2589_minimum_time_to_complete_all_tasks;
2+
3+
// #Hard #Array #Sorting #Greedy #Binary_Search #Stack
4+
// #2023_08_22_Time_19_ms_(97.26%)_Space_43.9_MB_(72.60%)
5+
6+
importjava.util.Arrays;
7+
importjava.util.Comparator;
8+
9+
publicclassSolution {
10+
publicintfindMinimumTime(int[][]tasks) {
11+
Arrays.sort(tasks,Comparator.comparingInt(a ->a[1]));
12+
boolean[]visited =newboolean[2001];
13+
intoutput =0;
14+
for (int[]row :tasks) {
15+
intnum =0;
16+
for (inti =row[0];i <=row[1];i++) {
17+
if (visited[i]) {
18+
num++;
19+
}
20+
}
21+
intj =row[1];
22+
while (num <row[2]) {
23+
if (!visited[j]) {
24+
visited[j] =true;
25+
num++;
26+
output++;
27+
}
28+
j--;
29+
}
30+
}
31+
returnoutput;
32+
}
33+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2589\. Minimum Time to Complete All Tasks
2+
3+
Hard
4+
5+
There is a computer that can run an unlimited number of tasks**at the same time**. You are given a 2D integer array`tasks` where <code>tasks[i] =[start<sub>i</sub>, end<sub>i</sub>, duration<sub>i</sub>]</code> indicates that the <code>i<sup>th</sup></code> task should run for a total of <code>duration<sub>i</sub></code> seconds (not necessarily continuous) within the**inclusive** time range <code>[start<sub>i</sub>, end<sub>i</sub>]</code>.
6+
7+
You may turn on the computer only when it needs to run a task. You can also turn it off if it is idle.
8+
9+
Return_the minimum time during which the computer should be turned on to complete all tasks_.
10+
11+
**Example 1:**
12+
13+
**Input:** tasks =[[2,3,1],[4,5,1],[1,5,2]]
14+
15+
**Output:** 2
16+
17+
**Explanation:**
18+
- The first task can be run in the inclusive time range[2, 2].
19+
- The second task can be run in the inclusive time range[5, 5].
20+
- The third task can be run in the two inclusive time ranges[2, 2] and[5, 5]. The computer will be on for a total of 2 seconds.
21+
22+
**Example 2:**
23+
24+
**Input:** tasks =[[1,3,2],[2,5,3],[5,6,2]]
25+
26+
**Output:** 4
27+
28+
**Explanation:**
29+
- The first task can be run in the inclusive time range[2, 3].
30+
- The second task can be run in the inclusive time ranges[2, 3] and[5, 5].
31+
- The third task can be run in the two inclusive time range[5, 6].
32+
33+
The computer will be on for a total of 4 seconds.
34+
35+
**Constraints:**
36+
37+
*`1 <= tasks.length <= 2000`
38+
*`tasks[i].length == 3`
39+
* <code>1 <= start<sub>i</sub>, end<sub>i</sub> <= 2000</code>
40+
* <code>1 <= duration<sub>i</sub> <= end<sub>i</sub> - start<sub>i</sub> + 1</code>

0 commit comments

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