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

Commita84d61a

Browse files
authored
Added tasks 2869-2873
1 parent2b6ef65 commita84d61a

File tree

15 files changed

+521
-0
lines changed

15 files changed

+521
-0
lines changed
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
packageg2801_2900.s2869_minimum_operations_to_collect_elements;
2+
3+
// #Easy #Array #Hash_Table #2023_12_21_Time_1_ms_(100.00%)_Space_42.4_MB_(5.72%)
4+
5+
importjava.util.List;
6+
7+
publicclassSolution {
8+
publicintminOperations(List<Integer>nums,intk) {
9+
Pair[]visited =newPair[k +1];
10+
visited[0] =newPair(true,0);
11+
intcount =0;
12+
for (inti =nums.size() -1;i >=0;i--) {
13+
count++;
14+
if (nums.get(i) <=k &&visited[nums.get(i)] ==null) {
15+
visited[nums.get(i)] =newPair(true,count);
16+
}
17+
}
18+
intfin = -1;
19+
for (Pairpair :visited) {
20+
if (pair !=null) {
21+
fin =Math.max(fin,pair.totalVisitedTillNow);
22+
}
23+
}
24+
returnfin;
25+
}
26+
27+
privatestaticclassPair {
28+
booleanisVisited;
29+
inttotalVisitedTillNow;
30+
31+
publicPair(booleanisVisited,inttotalVisitedTillNow) {
32+
this.isVisited =isVisited;
33+
this.totalVisitedTillNow =totalVisitedTillNow;
34+
}
35+
}
36+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2869\. Minimum Operations to Collect Elements
2+
3+
Easy
4+
5+
You are given an array`nums` of positive integers and an integer`k`.
6+
7+
In one operation, you can remove the last element of the array and add it to your collection.
8+
9+
Return_the**minimum number of operations** needed to collect elements_`1, 2, ..., k`.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[3,1,5,4,2], k = 2
14+
15+
**Output:** 4
16+
17+
**Explanation:** After 4 operations, we collect elements 2, 4, 5, and 1, in this order. Our collection contains elements 1 and 2. Hence, the answer is 4.
18+
19+
**Example 2:**
20+
21+
**Input:** nums =[3,1,5,4,2], k = 5
22+
23+
**Output:** 5
24+
25+
**Explanation:** After 5 operations, we collect elements 2, 4, 5, 1, and 3, in this order. Our collection contains elements 1 through 5. Hence, the answer is 5.
26+
27+
**Example 3:**
28+
29+
**Input:** nums =[3,2,5,3,1], k = 3
30+
31+
**Output:** 4
32+
33+
**Explanation:** After 4 operations, we collect elements 1, 3, 5, and 2, in this order. Our collection contains elements 1 through 3. Hence, the answer is 4.
34+
35+
**Constraints:**
36+
37+
*`1 <= nums.length <= 50`
38+
*`1 <= nums[i] <= nums.length`
39+
*`1 <= k <= nums.length`
40+
* The input is generated such that you can collect elements`1, 2, ..., k`.
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
packageg2801_2900.s2870_minimum_number_of_operations_to_make_array_empty;
2+
3+
// #Medium #Array #Hash_Table #Greedy #Counting
4+
// #2023_12_21_Time_6_ms_(98.16%)_Space_58.3_MB_(14.76%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publicintminOperations(int[]nums) {
10+
Arrays.sort(nums);
11+
intcount;
12+
intmin =0;
13+
intcurrent;
14+
inti =0;
15+
while (i <nums.length) {
16+
current =nums[i];
17+
count =0;
18+
while (i <nums.length &&current ==nums[i]) {
19+
count +=1;
20+
i++;
21+
}
22+
if (count ==1) {
23+
return -1;
24+
}
25+
min += (int)Math.ceil(count / (3 *1.0));
26+
}
27+
returnmin;
28+
}
29+
}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
2870\. Minimum Number of Operations to Make Array Empty
2+
3+
Medium
4+
5+
You are given a**0-indexed** array`nums` consisting of positive integers.
6+
7+
There are two types of operations that you can apply on the array**any** number of times:
8+
9+
* Choose**two** elements with**equal** values and**delete** them from the array.
10+
* Choose**three** elements with**equal** values and**delete** them from the array.
11+
12+
Return_the**minimum** number of operations required to make the array empty, or_`-1`_if it is not possible_.
13+
14+
**Example 1:**
15+
16+
**Input:** nums =[2,3,3,2,2,4,2,3,4]
17+
18+
**Output:** 4
19+
20+
**Explanation:** We can apply the following operations to make the array empty:
21+
- Apply the first operation on the elements at indices 0 and 3. The resulting array is nums =[3,3,2,4,2,3,4].
22+
- Apply the first operation on the elements at indices 2 and 4. The resulting array is nums =[3,3,4,3,4].
23+
- Apply the second operation on the elements at indices 0, 1, and 3. The resulting array is nums =[4,4].
24+
- Apply the first operation on the elements at indices 0 and 1. The resulting array is nums =[].
25+
26+
It can be shown that we cannot make the array empty in less than 4 operations.
27+
28+
**Example 2:**
29+
30+
**Input:** nums =[2,1,2,2,3,3]
31+
32+
**Output:** -1
33+
34+
**Explanation:** It is impossible to empty the array.
35+
36+
**Constraints:**
37+
38+
* <code>2 <= nums.length <= 10<sup>5</sup></code>
39+
* <code>1 <= nums[i] <= 10<sup>6</sup></code>
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
packageg2801_2900.s2871_split_array_into_maximum_number_of_subarrays;
2+
3+
// #Medium #Array #Greedy #Bit_Manipulation #2023_12_21_Time_3_ms_(100.00%)_Space_59.7_MB_(5.43%)
4+
5+
publicclassSolution {
6+
publicintmaxSubarrays(int[]nums) {
7+
if (nums.length ==1) {
8+
return1;
9+
}
10+
intandMax =nums[0];
11+
intcount =0;
12+
intcurrAnd =nums[0];
13+
intsum =0;
14+
for (intn :nums) {
15+
andMax &=n;
16+
}
17+
for (inti =1;i <nums.length;i++) {
18+
intn =nums[i];
19+
if (currAnd <=andMax) {
20+
count++;
21+
sum +=currAnd;
22+
currAnd =n;
23+
}
24+
currAnd &=n;
25+
}
26+
if (currAnd <=andMax) {
27+
count++;
28+
sum +=currAnd;
29+
}
30+
returnsum <=andMax ?count :1;
31+
}
32+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
2871\. Split Array Into Maximum Number of Subarrays
2+
3+
Medium
4+
5+
You are given an array`nums` consisting of**non-negative** integers.
6+
7+
We define the score of subarray`nums[l..r]` such that`l <= r` as`nums[l] AND nums[l + 1] AND ... AND nums[r]` where**AND** is the bitwise`AND` operation.
8+
9+
Consider splitting the array into one or more subarrays such that the following conditions are satisfied:
10+
11+
***E****ach** element of the array belongs to**exactly** one subarray.
12+
* The sum of scores of the subarrays is the**minimum** possible.
13+
14+
Return_the**maximum** number of subarrays in a split that satisfies the conditions above._
15+
16+
A**subarray** is a contiguous part of an array.
17+
18+
**Example 1:**
19+
20+
**Input:** nums =[1,0,2,0,1,2]
21+
22+
**Output:** 3
23+
24+
**Explanation:** We can split the array into the following subarrays:
25+
-[1,0]. The score of this subarray is 1 AND 0 = 0.
26+
-[2,0]. The score of this subarray is 2 AND 0 = 0.
27+
-[1,2]. The score of this subarray is 1 AND 2 = 0.
28+
29+
The sum of scores is 0 + 0 + 0 = 0, which is the minimum possible score that we can obtain.
30+
31+
It can be shown that we cannot split the array into more than 3 subarrays with a total score of 0. So we return 3.
32+
33+
**Example 2:**
34+
35+
**Input:** nums =[5,7,1,3]
36+
37+
**Output:** 1
38+
39+
**Explanation:** We can split the array into one subarray:[5,7,1,3] with a score of 1, which is the minimum possible score that we can obtain. It can be shown that we cannot split the array into more than 1 subarray with a total score of 1. So we return 1.
40+
41+
**Constraints:**
42+
43+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
44+
* <code>0 <= nums[i] <= 10<sup>6</sup></code>
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
packageg2801_2900.s2872_maximum_number_of_k_divisible_components;
2+
3+
// #Hard #Dynamic_Programming #Tree #Depth_First_Search
4+
// #2023_12_21_Time_24_ms_(93.51%)_Space_65.3_MB_(19.48%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
privateintans =0;
11+
12+
publicintmaxKDivisibleComponents(intn,int[][]edges,int[]values,intk) {
13+
List<List<Integer>>adj =newArrayList<>();
14+
for (inti =0;i <n;i++) {
15+
adj.add(newArrayList<>());
16+
}
17+
for (int[]edge :edges) {
18+
intstart =edge[0];
19+
intend =edge[1];
20+
adj.get(start).add(end);
21+
adj.get(end).add(start);
22+
}
23+
boolean[]isVis =newboolean[n];
24+
isVis[0] =true;
25+
get(0, -1,adj,isVis,values,k);
26+
returnans;
27+
}
28+
29+
privatelongget(
30+
intcurNode,
31+
intparent,
32+
List<List<Integer>>adj,
33+
boolean[]isVis,
34+
int[]values,
35+
longk) {
36+
longsum =values[curNode];
37+
for (intele :adj.get(curNode)) {
38+
if (ele !=parent && !isVis[ele]) {
39+
isVis[ele] =true;
40+
sum +=get(ele,curNode,adj,isVis,values,k);
41+
}
42+
}
43+
if (sum %k ==0) {
44+
ans++;
45+
return0;
46+
}else {
47+
returnsum;
48+
}
49+
}
50+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
2872\. Maximum Number of K-Divisible Components
2+
3+
Hard
4+
5+
There is an undirected tree with`n` nodes labeled from`0` to`n - 1`. You are given the integer`n` and a 2D integer array`edges` of length`n - 1`, where <code>edges[i] =[a<sub>i</sub>, b<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> in the tree.
6+
7+
You are also given a**0-indexed** integer array`values` of length`n`, where`values[i]` is the**value** associated with the <code>i<sup>th</sup></code> node, and an integer`k`.
8+
9+
A**valid split** of the tree is obtained by removing any set of edges, possibly empty, from the tree such that the resulting components all have values that are divisible by`k`, where the**value of a connected component** is the sum of the values of its nodes.
10+
11+
Return_the**maximum number of components** in any valid split_.
12+
13+
**Example 1:**
14+
15+
![](https://assets.leetcode.com/uploads/2023/08/07/example12-cropped2svg.jpg)
16+
17+
**Input:** n = 5, edges =[[0,2],[1,2],[1,3],[2,4]], values =[1,8,1,4,4], k = 6
18+
19+
**Output:** 2
20+
21+
**Explanation:** We remove the edge connecting node 1 with 2. The resulting split is valid because:
22+
- The value of the component containing nodes 1 and 3 is values[1] + values[3] = 12.
23+
- The value of the component containing nodes 0, 2, and 4 is values[0] + values[2] + values[4] = 6.
24+
25+
It can be shown that no other valid split has more than 2 connected components.
26+
27+
**Example 2:**
28+
29+
![](https://assets.leetcode.com/uploads/2023/08/07/example21svg-1.jpg)
30+
31+
**Input:** n = 7, edges =[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values =[3,0,6,1,5,2,1], k = 3
32+
33+
**Output:** 3
34+
35+
**Explanation:** We remove the edge connecting node 0 with 2, and the edge connecting node 0 with 1. The resulting split is valid because:
36+
- The value of the component containing node 0 is values[0] = 3.
37+
- The value of the component containing nodes 2, 5, and 6 is values[2] + values[5] + values[6] = 9.
38+
- The value of the component containing nodes 1, 3, and 4 is values[1] + values[3] + values[4] = 6.
39+
40+
It can be shown that no other valid split has more than 3 connected components.
41+
42+
**Constraints:**
43+
44+
* <code>1 <= n <= 3 * 10<sup>4</sup></code>
45+
*`edges.length == n - 1`
46+
*`edges[i].length == 2`
47+
* <code>0 <= a<sub>i</sub>, b<sub>i</sub> < n</code>
48+
*`values.length == n`
49+
* <code>0 <= values[i] <= 10<sup>9</sup></code>
50+
* <code>1 <= k <= 10<sup>9</sup></code>
51+
* Sum of`values` is divisible by`k`.
52+
* The input is generated such that`edges` represents a valid tree.
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packageg2801_2900.s2873_maximum_value_of_an_ordered_triplet_i;
2+
3+
// #Easy #Array #2023_12_21_Time_0_ms_(100.00%)_Space_42_MB_(10.64%)
4+
5+
publicclassSolution {
6+
publiclongmaximumTripletValue(int[]nums) {
7+
finalintn =nums.length;
8+
finalint[]iNumMaxs =newint[n];
9+
intprev =0;
10+
for (inti =0;i <n;i++) {
11+
if (nums[i] <=prev) {
12+
iNumMaxs[i] =prev;
13+
}else {
14+
prev =iNumMaxs[i] =nums[i];
15+
}
16+
}
17+
longresult =0;
18+
intkNumMax =nums[n -1];
19+
for (intj =n -2;j >0;j--) {
20+
result =Math.max(result, (long) (iNumMaxs[j -1] -nums[j]) *kNumMax);
21+
if (nums[j] >kNumMax) {
22+
kNumMax =nums[j];
23+
}
24+
}
25+
returnresult;
26+
}
27+
}

0 commit comments

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