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

Commitfaf7911

Browse files
authored
Added tasks 2735-2741
1 parent6c6932c commitfaf7911

File tree

15 files changed

+479
-0
lines changed

15 files changed

+479
-0
lines changed
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2701_2800.s2735_collecting_chocolates;
2+
3+
// #Medium #Array #Enumeration #2023_09_22_Time_24_ms_(96.97%)_Space_43.5_MB_(92.12%)
4+
5+
publicclassSolution {
6+
publiclongminCost(int[]nums,intx) {
7+
intn =nums.length;
8+
int[]dp =newint[n];
9+
longres =0;
10+
for (inti =0;i <n;i++) {
11+
dp[i] =nums[i];
12+
res +=nums[i];
13+
}
14+
for (inti =1;i <n;i++) {
15+
longsum = (long)i *x;
16+
for (intj =0;j <n;j++) {
17+
intcurrIndex = (j +i >=n) ?j +i -n :j +i;
18+
dp[j] =Math.min(dp[j],nums[currIndex]);
19+
sum +=dp[j];
20+
}
21+
res =Math.min(res,sum);
22+
}
23+
returnres;
24+
}
25+
}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
2735\. Collecting Chocolates
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums` of size`n` representing the cost of collecting different chocolates. The cost of collecting the chocolate at the index`i` is`nums[i]`. Each chocolate is of a different type, and initially, the chocolate at the index`i` is of <code>i<sup>th</sup></code> type.
6+
7+
In one operation, you can do the following with an incurred**cost** of`x`:
8+
9+
* Simultaneously change the chocolate of <code>i<sup>th</sup></code> type to <code>((i + 1) mod n)<sup>th</sup></code> type for all chocolates.
10+
11+
Return_the minimum cost to collect chocolates of all types, given that you can perform as many operations as you would like._
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[20,1,15], x = 5
16+
17+
**Output:** 13
18+
19+
**Explanation:** Initially, the chocolate types are[0,1,2]. We will buy the 1<sup>st</sup> type of chocolate at a cost of 1.
20+
21+
Now, we will perform the operation at a cost of 5, and the types of chocolates will become[1,2,0]. We will buy the 2<sup>nd</sup> type of chocolate at a cost of 1.
22+
23+
Now, we will again perform the operation at a cost of 5, and the chocolate types will become[2,0,1]. We will buy the 0<sup>th</sup> type of chocolate at a cost of 1.
24+
25+
Thus, the total cost will become (1 + 5 + 1 + 5 + 1) = 13. We can prove that this is optimal.
26+
27+
**Example 2:**
28+
29+
**Input:** nums =[1,2,3], x = 4
30+
31+
**Output:** 6
32+
33+
**Explanation:** We will collect all three types of chocolates at their own price without performing any operations. Therefore, the total cost is 1 + 2 + 3 = 6.
34+
35+
**Constraints:**
36+
37+
*`1 <= nums.length <= 1000`
38+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
39+
* <code>1 <= x <= 10<sup>9</sup></code>
Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
packageg2701_2800.s2736_maximum_sum_queries;
2+
3+
// #Hard #Array #Sorting #Binary_Search #Stack #Monotonic_Stack #Segment_Tree #Binary_Indexed_Tree
4+
// #2023_09_23_Time_66_ms_(78.43%)_Space_84.1_MB_(94.12%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Comparator;
8+
importjava.util.List;
9+
importjava.util.Map;
10+
importjava.util.NavigableMap;
11+
importjava.util.TreeMap;
12+
13+
publicclassSolution {
14+
privatevoidupdate(NavigableMap<Integer,Integer>map,intnum,intsum) {
15+
Map.Entry<Integer,Integer>entry =map.floorEntry(num);
16+
while (entry !=null &&entry.getValue() <=sum) {
17+
map.remove(entry.getKey());
18+
intx =entry.getKey();
19+
entry =map.floorEntry(x);
20+
}
21+
entry =map.ceilingEntry(num);
22+
if (entry ==null ||entry.getValue() <sum) {
23+
map.put(num,sum);
24+
}
25+
}
26+
27+
privateintqueryVal(NavigableMap<Integer,Integer>map,intnum) {
28+
Map.Entry<Integer,Integer>entry =map.ceilingEntry(num);
29+
if (entry ==null) {
30+
return -1;
31+
}
32+
returnentry.getValue();
33+
}
34+
35+
publicint[]maximumSumQueries(int[]nums1,int[]nums2,int[][]queries) {
36+
intn =nums1.length;
37+
intm =queries.length;
38+
List<int[]>v =newArrayList<>();
39+
for (inti =0;i <n;i++) {
40+
v.add(newint[] {nums1[i],nums2[i]});
41+
}
42+
v.sort(Comparator.comparingInt(a ->a[0]));
43+
List<Integer>ind =newArrayList<>();
44+
for (inti =0;i <m;i++) {
45+
ind.add(i);
46+
}
47+
ind.sort((a,b) ->queries[b][0] -queries[a][0]);
48+
TreeMap<Integer,Integer>values =newTreeMap<>();
49+
intj =n -1;
50+
int[]ans =newint[m];
51+
for (inti :ind) {
52+
inta =queries[i][0];
53+
intb =queries[i][1];
54+
for (;j >=0 &&v.get(j)[0] >=a;j--) {
55+
update(values,v.get(j)[1],v.get(j)[0] +v.get(j)[1]);
56+
}
57+
ans[i] =queryVal(values,b);
58+
}
59+
returnans;
60+
}
61+
}
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
2736\. Maximum Sum Queries
2+
3+
Hard
4+
5+
You are given two**0-indexed** integer arrays`nums1` and`nums2`, each of length`n`, and a**1-indexed 2D array**`queries` where <code>queries[i] =[x<sub>i</sub>, y<sub>i</sub>]</code>.
6+
7+
For the <code>i<sup>th</sup></code> query, find the**maximum value** of`nums1[j] + nums2[j]` among all indices`j``(0 <= j < n)`, where <code>nums1[j] >= x<sub>i</sub></code> and <code>nums2[j] >= y<sub>i</sub></code>, or**\-1** if there is no`j` satisfying the constraints.
8+
9+
Return_an array_`answer`_where_`answer[i]`_is the answer to the_ <code>i<sup>th</sup></code>_query._
10+
11+
**Example 1:**
12+
13+
**Input:** nums1 =[4,3,1,2], nums2 =[2,4,9,5], queries =[[4,1],[1,3],[2,5]]
14+
15+
**Output:**[6,10,7]
16+
17+
**Explanation:**
18+
19+
For the 1st query <code>x<sub>i</sub> = 4</code> and <code>y<sub>i</sub> = 1</code>, we can select index`j = 0` since`nums1[j] >= 4` and`nums2[j] >= 1`. The sum`nums1[j] + nums2[j]` is 6, and we can show that 6 is the maximum we can obtain.
20+
21+
For the 2nd query <code>x<sub>i</sub> = 1</code> and <code>y<sub>i</sub> = 3</code>, we can select index`j = 2` since`nums1[j] >= 1` and`nums2[j] >= 3`. The sum`nums1[j] + nums2[j]` is 10, and we can show that 10 is the maximum we can obtain.
22+
23+
For the 3rd query <code>x<sub>i</sub> = 2</code> and <code>y<sub>i</sub> = 5</code>, we can select index`j = 3` since`nums1[j] >= 2` and`nums2[j] >= 5`. The sum`nums1[j] + nums2[j]` is 7, and we can show that 7 is the maximum we can obtain.
24+
25+
Therefore, we return`[6,10,7]`.
26+
27+
**Example 2:**
28+
29+
**Input:** nums1 =[3,2,5], nums2 =[2,3,4], queries =[[4,4],[3,2],[1,1]]
30+
31+
**Output:**[9,9,9]
32+
33+
**Explanation:** For this example, we can use index`j = 2` for all the queries since it satisfies the constraints for each query.
34+
35+
**Example 3:**
36+
37+
**Input:** nums1 =[2,1], nums2 =[2,3], queries =[[3,3]]
38+
39+
**Output:**[-1]
40+
41+
**Explanation:** There is one query in this example with <code>x<sub>i</sub></code> = 3 and <code>y<sub>i</sub></code> = 3. For every index, j, either nums1[j] < <code>x<sub>i</sub></code> or nums2[j] < <code>y<sub>i</sub></code>. Hence, there is no solution.
42+
43+
**Constraints:**
44+
45+
*`nums1.length == nums2.length`
46+
*`n == nums1.length`
47+
* <code>1 <= n <= 10<sup>5</sup></code>
48+
* <code>1 <= nums1[i], nums2[i] <= 10<sup>9</sup></code>
49+
* <code>1 <= queries.length <= 10<sup>5</sup></code>
50+
*`queries[i].length == 2`
51+
* <code>x<sub>i</sub> == queries[i][1]</code>
52+
* <code>y<sub>i</sub> == queries[i][2]</code>
53+
* <code>1 <= x<sub>i</sub>, y<sub>i</sub> <= 10<sup>9</sup></code>
Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
packageg2701_2800.s2739_total_distance_traveled;
2+
3+
// #Easy #Math #Simulation #2023_09_23_Time_4_ms_(100.00%)_Space_43.3_MB_(10.42%)
4+
5+
publicclassSolution {
6+
publicintdistanceTraveled(intmainTank,intadditionalTank) {
7+
inttransferableTimes = (mainTank -1) /4;
8+
inttransferredLiters =Math.min(transferableTimes,additionalTank);
9+
return (mainTank +transferredLiters) *10;
10+
}
11+
}
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
2739\. Total Distance Traveled
2+
3+
Easy
4+
5+
A truck has two fuel tanks. You are given two integers,`mainTank` representing the fuel present in the main tank in liters and`additionalTank` representing the fuel present in the additional tank in liters.
6+
7+
The truck has a mileage of`10` km per liter. Whenever`5` liters of fuel get used up in the main tank, if the additional tank has at least`1` liters of fuel,`1` liters of fuel will be transferred from the additional tank to the main tank.
8+
9+
Return_the maximum distance which can be traveled._
10+
11+
**Note:** Injection from the additional tank is not continuous. It happens suddenly and immediately for every 5 liters consumed.
12+
13+
**Example 1:**
14+
15+
**Input:** mainTank = 5, additionalTank = 10
16+
17+
**Output:** 60
18+
19+
**Explanation:**
20+
21+
After spending 5 litre of fuel, fuel remaining is (5 - 5 + 1) = 1 litre and distance traveled is 50km.
22+
23+
After spending another 1 litre of fuel, no fuel gets injected in the main tank and the main tank becomes empty.
24+
25+
Total distance traveled is 60km.
26+
27+
**Example 2:**
28+
29+
**Input:** mainTank = 1, additionalTank = 2
30+
31+
**Output:** 10
32+
33+
**Explanation:** After spending 1 litre of fuel, the main tank becomes empty. Total distance traveled is 10km.
34+
35+
**Constraints:**
36+
37+
*`1 <= mainTank, additionalTank <= 100`
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
packageg2701_2800.s2740_find_the_value_of_the_partition;
2+
3+
// #Medium #Array #Sorting #2023_09_23_Time_18_ms_(100.00%)_Space_54.6_MB_(33.05%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publicintfindValueOfPartition(int[]nums) {
9+
Arrays.sort(nums);
10+
intminDifference =Integer.MAX_VALUE;
11+
for (inti =1;i <nums.length;i++) {
12+
intdifference =nums[i] -nums[i -1];
13+
if (difference <minDifference) {
14+
minDifference =difference;
15+
}
16+
}
17+
returnminDifference;
18+
}
19+
}
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
2740\. Find the Value of the Partition
2+
3+
Medium
4+
5+
You are given a**positive** integer array`nums`.
6+
7+
Partition`nums` into two arrays,`nums1` and`nums2`, such that:
8+
9+
* Each element of the array`nums` belongs to either the array`nums1` or the array`nums2`.
10+
* Both arrays are**non-empty**.
11+
* The value of the partition is**minimized**.
12+
13+
The value of the partition is`|max(nums1) - min(nums2)|`.
14+
15+
Here,`max(nums1)` denotes the maximum element of the array`nums1`, and`min(nums2)` denotes the minimum element of the array`nums2`.
16+
17+
Return_the integer denoting the value of such partition_.
18+
19+
**Example 1:**
20+
21+
**Input:** nums =[1,3,2,4]
22+
23+
**Output:** 1
24+
25+
**Explanation:** We can partition the array nums into nums1 =[1,2] and nums2 =[3,4].
26+
- The maximum element of the array nums1 is equal to 2.
27+
- The minimum element of the array nums2 is equal to 3.
28+
29+
The value of the partition is |2 - 3| = 1.
30+
31+
It can be proven that 1 is the minimum value out of all partitions.
32+
33+
**Example 2:**
34+
35+
**Input:** nums =[100,1,10]
36+
37+
**Output:** 9
38+
39+
**Explanation:** We can partition the array nums into nums1 =[10] and nums2 =[100,1].
40+
- The maximum element of the array nums1 is equal to 10.
41+
- The minimum element of the array nums2 is equal to 1.
42+
43+
The value of the partition is |10 - 1| = 9.
44+
45+
It can be proven that 9 is the minimum value out of all partitions.
46+
47+
**Constraints:**
48+
49+
* <code>2 <= nums.length <= 10<sup>5</sup></code>
50+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
packageg2701_2800.s2741_special_permutations;
2+
3+
// #Medium #Array #Dynamic_Programming #Bit_Manipulation #Bitmask
4+
// #2023_09_23_Time_105_ms_(96.58%)_Space_49.6_MB_(55.48%)
5+
6+
publicclassSolution {
7+
privateintn;
8+
privateInteger[][]memo;
9+
privateint[]nums;
10+
11+
publicintspecialPerm(int[]nums) {
12+
this.n =nums.length;
13+
this.memo =newInteger[n][1 <<n];
14+
this.nums =nums;
15+
returnbacktrack(0,0);
16+
}
17+
18+
privateintbacktrack(intpreIndex,intmask) {
19+
if (mask == (1 <<n) -1) {
20+
return1;
21+
}
22+
if (memo[preIndex][mask] !=null) {
23+
returnmemo[preIndex][mask];
24+
}
25+
intcount =0;
26+
intmod = (int)1e9 +7;
27+
for (inti =0;i <n;i++) {
28+
if ((mask & (1 <<i)) ==0
29+
&& (mask ==0
30+
||nums[i] %nums[preIndex] ==0
31+
||nums[preIndex] %nums[i] ==0)) {
32+
count = (count +backtrack(i,mask | (1 <<i))) %mod;
33+
}
34+
}
35+
memo[preIndex][mask] =count;
36+
returnmemo[preIndex][mask];
37+
}
38+
}
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
2741\. Special Permutations
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums` containing`n`**distinct** positive integers. A permutation of`nums` is called special if:
6+
7+
* For all indexes`0 <= i < n - 1`, either`nums[i] % nums[i+1] == 0` or`nums[i+1] % nums[i] == 0`.
8+
9+
Return_the total number of special permutations._As the answer could be large, return it**modulo**<code>10<sup>9 </sup>+ 7</code>.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[2,3,6]
14+
15+
**Output:** 2
16+
17+
**Explanation:**[3,6,2] and[2,6,3] are the two special permutations of nums.
18+
19+
**Example 2:**
20+
21+
**Input:** nums =[1,4,3]
22+
23+
**Output:** 2
24+
25+
**Explanation:**[3,1,4] and[4,1,3] are the two special permutations of nums.
26+
27+
**Constraints:**
28+
29+
*`2 <= nums.length <= 14`
30+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg2701_2800.s2735_collecting_chocolates;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidminCost() {
11+
assertThat(newSolution().minCost(newint[] {20,1,15},5),equalTo(13L));
12+
}
13+
14+
@Test
15+
voidminCost2() {
16+
assertThat(newSolution().minCost(newint[] {1,2,3},4),equalTo(6L));
17+
}
18+
}

0 commit comments

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