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

Commitec8429c

Browse files
authored
Added tasks 2830-2835
1 parent5b74f8e commitec8429c

File tree

15 files changed

+482
-0
lines changed

15 files changed

+482
-0
lines changed
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
packageg2801_2900.s2830_maximize_the_profit_as_the_salesman;
2+
3+
// #Medium #Array #Dynamic_Programming #Sorting #Binary_Search
4+
// #2023_12_11_Time_36_ms_(80.00%)_Space_76.3_MB_(73.13%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.HashMap;
8+
importjava.util.List;
9+
10+
publicclassSolution {
11+
publicintmaximizeTheProfit(intn,List<List<Integer>>offers) {
12+
int[]dp =newint[n];
13+
HashMap<Integer,List<List<Integer>>>range =newHashMap<>();
14+
for (List<Integer>l :offers) {
15+
if (range.containsKey(l.get(0))) {
16+
range.get(l.get(0)).add(l);
17+
}else {
18+
List<List<Integer>>r =newArrayList<>();
19+
r.add(l);
20+
range.put(l.get(0),r);
21+
}
22+
}
23+
inti =0;
24+
while (i <n) {
25+
List<List<Integer>>temp =newArrayList<>();
26+
if (range.containsKey(i)) {
27+
temp =range.get(i);
28+
}
29+
dp[i] = (i !=0) ?Math.max(dp[i],dp[i -1]) :dp[i];
30+
for (List<Integer>l :temp) {
31+
dp[l.get(1)] =
32+
(i !=0)
33+
?Math.max(dp[l.get(1)],dp[i -1] +l.get(2))
34+
:Math.max(dp[l.get(1)],l.get(2));
35+
}
36+
i++;
37+
}
38+
returndp[n -1];
39+
}
40+
}
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
2830\. Maximize the Profit as the Salesman
2+
3+
Medium
4+
5+
You are given an integer`n` representing the number of houses on a number line, numbered from`0` to`n - 1`.
6+
7+
Additionally, you are given a 2D integer array`offers` where <code>offers[i] =[start<sub>i</sub>, end<sub>i</sub>, gold<sub>i</sub>]</code>, indicating that <code>i<sup>th</sup></code> buyer wants to buy all the houses from <code>start<sub>i</sub></code> to <code>end<sub>i</sub></code> for <code>gold<sub>i</sub></code> amount of gold.
8+
9+
As a salesman, your goal is to**maximize** your earnings by strategically selecting and selling houses to buyers.
10+
11+
Return_the maximum amount of gold you can earn_.
12+
13+
**Note** that different buyers can't buy the same house, and some houses may remain unsold.
14+
15+
**Example 1:**
16+
17+
**Input:** n = 5, offers =[[0,0,1],[0,2,2],[1,3,2]]
18+
19+
**Output:** 3
20+
21+
**Explanation:** There are 5 houses numbered from 0 to 4 and there are 3 purchase offers.
22+
23+
We sell houses in the range[0,0] to 1<sup>st</sup> buyer for 1 gold and houses in the range[1,3] to 3<sup>rd</sup> buyer for 2 golds.
24+
25+
It can be proven that 3 is the maximum amount of gold we can achieve.
26+
27+
**Example 2:**
28+
29+
**Input:** n = 5, offers =[[0,0,1],[0,2,10],[1,3,2]]
30+
31+
**Output:** 10
32+
33+
**Explanation:** There are 5 houses numbered from 0 to 4 and there are 3 purchase offers.
34+
35+
We sell houses in the range[0,2] to 2<sup>nd</sup> buyer for 10 golds.
36+
37+
It can be proven that 10 is the maximum amount of gold we can achieve.
38+
39+
**Constraints:**
40+
41+
* <code>1 <= n <= 10<sup>5</sup></code>
42+
* <code>1 <= offers.length <= 10<sup>5</sup></code>
43+
*`offers[i].length == 3`
44+
* <code>0 <= start<sub>i</sub> <= end<sub>i</sub> <= n - 1</code>
45+
* <code>1 <= gold<sub>i</sub> <= 10<sup>3</sup></code>
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
packageg2801_2900.s2831_find_the_longest_equal_subarray;
2+
3+
// #Medium #Array #Hash_Table #Binary_Search #Sliding_Window
4+
// #2023_12_11_Time_15_ms_(96.81%)_Space_57.6_MB_(92.02%)
5+
6+
importjava.util.List;
7+
8+
publicclassSolution {
9+
publicintlongestEqualSubarray(List<Integer>nums,intk) {
10+
int[]count =newint[nums.size() +1];
11+
inti =0;
12+
intmaxCount =0;
13+
for (intj =0;j <nums.size();j++) {
14+
count[nums.get(j)]++;
15+
maxCount =Math.max(maxCount,count[nums.get(j)]);
16+
if ((j -i +1) -maxCount >k) {
17+
count[nums.get(i)]--;
18+
i++;
19+
}
20+
}
21+
returnmaxCount;
22+
}
23+
}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
2831\. Find the Longest Equal Subarray
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums` and an integer`k`.
6+
7+
A subarray is called**equal** if all of its elements are equal. Note that the empty subarray is an**equal** subarray.
8+
9+
Return_the length of the**longest** possible equal subarray after deleting**at most**_`k`_elements from_`nums`.
10+
11+
A**subarray** is a contiguous, possibly empty sequence of elements within an array.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[1,3,2,3,1,3], k = 3
16+
17+
**Output:** 3
18+
19+
**Explanation:** It's optimal to delete the elements at index 2 and index 4.
20+
21+
After deleting them, nums becomes equal to[1, 3, 3, 3]. The longest equal subarray starts at i = 1 and ends at j = 3 with length equal to 3.
22+
23+
It can be proven that no longer equal subarrays can be created.
24+
25+
**Example 2:**
26+
27+
**Input:** nums =[1,1,2,2,1,1], k = 2
28+
29+
**Output:** 4
30+
31+
**Explanation:** It's optimal to delete the elements at index 2 and index 3.
32+
33+
After deleting them, nums becomes equal to[1, 1, 1, 1]. The array itself is an equal subarray, so the answer is 4.
34+
35+
It can be proven that no longer equal subarrays can be created.
36+
37+
**Constraints:**
38+
39+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
40+
*`1 <= nums[i] <= nums.length`
41+
*`0 <= k <= nums.length`
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg2801_2900.s2833_furthest_point_from_origin;
2+
3+
// #Easy #Array #Counting #2023_12_11_Time_1_ms_(100.00%)_Space_41.4_MB_(50.89%)
4+
5+
publicclassSolution {
6+
publicintfurthestDistanceFromOrigin(Stringm) {
7+
intcount =0;
8+
intres =0;
9+
for (inti =0;i <m.length();i++) {
10+
if (m.charAt(i) =='L') {
11+
res -=1;
12+
}elseif (m.charAt(i) =='R') {
13+
res +=1;
14+
}else {
15+
count++;
16+
}
17+
}
18+
returnMath.abs(res) +count;
19+
}
20+
}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
2833\. Furthest Point From Origin
2+
3+
Easy
4+
5+
You are given a string`moves` of length`n` consisting only of characters`'L'`,`'R'`, and`'_'`. The string represents your movement on a number line starting from the origin`0`.
6+
7+
In the <code>i<sup>th</sup></code> move, you can choose one of the following directions:
8+
9+
* move to the left if`moves[i] = 'L'` or`moves[i] = '_'`
10+
* move to the right if`moves[i] = 'R'` or`moves[i] = '_'`
11+
12+
Return_the**distance from the origin** of the**furthest** point you can get to after_`n`_moves_.
13+
14+
**Example 1:**
15+
16+
**Input:** moves = "L\_RL\_\_R"
17+
18+
**Output:** 3
19+
20+
**Explanation:** The furthest point we can reach from the origin 0 is point -3 through the following sequence of moves "LLRLLLR".
21+
22+
**Example 2:**
23+
24+
**Input:** moves = "\_R\_\_LL\_"
25+
26+
**Output:** 5
27+
28+
**Explanation:** The furthest point we can reach from the origin 0 is point -5 through the following sequence of moves "LRLLLLL".
29+
30+
**Example 3:**
31+
32+
**Input:** moves = "\_\_\_\_\_\_\_"
33+
34+
**Output:** 7
35+
36+
**Explanation:** The furthest point we can reach from the origin 0 is point 7 through the following sequence of moves "RRRRRRR".
37+
38+
**Constraints:**
39+
40+
*`1 <= moves.length == n <= 50`
41+
*`moves` consists only of characters`'L'`,`'R'` and`'_'`.
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
packageg2801_2900.s2834_find_the_minimum_possible_sum_of_a_beautiful_array;
2+
3+
// #Medium #Math #Greedy #2023_12_11_Time_0_ms_(100.00%)_Space_39.6_MB_(48.53%)
4+
5+
publicclassSolution {
6+
publicintminimumPossibleSum(intn,intk) {
7+
longmod = (long)1e9 +7;
8+
if (k > (n +n -1)) {
9+
return (int) ((long)n * (n +1) %mod /2);
10+
}
11+
longtoChange =n - (long) (k /2);
12+
longsum = ((n * ((long)n +1)) /2) %mod;
13+
longremain = (long)k - ((k /2) +1);
14+
return (int) ((sum + (toChange *remain) %mod) %mod);
15+
}
16+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
2834\. Find the Minimum Possible Sum of a Beautiful Array
2+
3+
Medium
4+
5+
You are given positive integers`n` and`target`.
6+
7+
An array`nums` is**beautiful** if it meets the following conditions:
8+
9+
*`nums.length == n`.
10+
*`nums` consists of pairwise**distinct****positive** integers.
11+
* There doesn't exist two**distinct** indices,`i` and`j`, in the range`[0, n - 1]`, such that`nums[i] + nums[j] == target`.
12+
13+
Return_the**minimum** possible sum that a beautiful array could have modulo_ <code>10<sup>9</sup> + 7</code>.
14+
15+
**Example 1:**
16+
17+
**Input:** n = 2, target = 3
18+
19+
**Output:** 4
20+
21+
**Explanation:** We can see that nums =[1,3] is beautiful.
22+
- The array nums has length n = 2.
23+
- The array nums consists of pairwise distinct positive integers.
24+
- There doesn't exist two distinct indices, i and j, with nums[i] + nums[j] == 3.
25+
26+
It can be proven that 4 is the minimum possible sum that a beautiful array could have.
27+
28+
**Example 2:**
29+
30+
**Input:** n = 3, target = 3
31+
32+
**Output:** 8
33+
34+
**Explanation:** We can see that nums =[1,3,4] is beautiful.
35+
- The array nums has length n = 3.
36+
- The array nums consists of pairwise distinct positive integers.
37+
- There doesn't exist two distinct indices, i and j, with nums[i] + nums[j] == 3.
38+
39+
It can be proven that 8 is the minimum possible sum that a beautiful array could have.
40+
41+
**Example 3:**
42+
43+
**Input:** n = 1, target = 1
44+
45+
**Output:** 1
46+
47+
**Explanation:** We can see, that nums =[1] is beautiful.
48+
49+
**Constraints:**
50+
51+
* <code>1 <= n <= 10<sup>9</sup></code>
52+
* <code>1 <= target <= 10<sup>9</sup></code>
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
packageg2801_2900.s2835_minimum_operations_to_form_subsequence_with_target_sum;
2+
3+
// #Hard #Array #Greedy #Bit_Manipulation #2023_12_11_Time_2_ms_(94.66%)_Space_43.3_MB_(39.69%)
4+
5+
importjava.util.List;
6+
importjava.util.PriorityQueue;
7+
8+
publicclassSolution {
9+
publicintminOperations(List<Integer>nums,inttarget) {
10+
PriorityQueue<Integer>pq =newPriorityQueue<>((a,b) ->b -a);
11+
longsum =0;
12+
longcount =0;
13+
for (intx :nums) {
14+
pq.offer(x);
15+
sum +=x;
16+
}
17+
if (sum <target) {
18+
return -1;
19+
}
20+
while (!pq.isEmpty()) {
21+
intval =pq.poll();
22+
sum -=val;
23+
if (val <=target) {
24+
target -=val;
25+
}elseif (sum <target) {
26+
count++;
27+
pq.offer(val /2);
28+
pq.offer(val /2);
29+
sum +=val;
30+
}
31+
}
32+
return (int)count;
33+
}
34+
}
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
2835\. Minimum Operations to Form Subsequence With Target Sum
2+
3+
Hard
4+
5+
You are given a**0-indexed** array`nums` consisting of**non-negative** powers of`2`, and an integer`target`.
6+
7+
In one operation, you must apply the following changes to the array:
8+
9+
* Choose any element of the array`nums[i]` such that`nums[i] > 1`.
10+
* Remove`nums[i]` from the array.
11+
* Add**two** occurrences of`nums[i] / 2` to the**end** of`nums`.
12+
13+
Return the_**minimum number of operations** you need to perform so that_`nums`_contains a**subsequence** whose elements sum to_`target`. If it is impossible to obtain such a subsequence, return`-1`.
14+
15+
A**subsequence** is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
16+
17+
**Example 1:**
18+
19+
**Input:** nums =[1,2,8], target = 7
20+
21+
**Output:** 1
22+
23+
**Explanation:** In the first operation, we choose element nums[2]. The array becomes equal to nums =[1,2,4,4].
24+
25+
At this stage, nums contains the subsequence[1,2,4] which sums up to 7.
26+
27+
It can be shown that there is no shorter sequence of operations that results in a subsequnce that sums up to 7.
28+
29+
**Example 2:**
30+
31+
**Input:** nums =[1,32,1,2], target = 12
32+
33+
**Output:** 2
34+
35+
**Explanation:** In the first operation, we choose element nums[1]. The array becomes equal to nums =[1,1,2,16,16].
36+
37+
In the second operation, we choose element nums[3]. The array becomes equal to nums =[1,1,2,16,8,8]
38+
39+
At this stage, nums contains the subsequence[1,1,2,8] which sums up to 12.
40+
41+
It can be shown that there is no shorter sequence of operations that results in a subsequence that sums up to 12.
42+
43+
**Example 3:**
44+
45+
**Input:** nums =[1,32,1], target = 35
46+
47+
**Output:** -1
48+
49+
**Explanation:** It can be shown that no sequence of operations results in a subsequence that sums up to 35.
50+
51+
**Constraints:**
52+
53+
*`1 <= nums.length <= 1000`
54+
* <code>1 <= nums[i] <= 2<sup>30</sup></code>
55+
*`nums` consists only of non-negative powers of two.
56+
* <code>1 <= target < 2<sup>31</sup></code>

0 commit comments

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