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

Commit2c09a3e

Browse files
authored
Added tasks 2919-2925
1 parentbdeec5e commit2c09a3e

File tree

15 files changed

+582
-0
lines changed

15 files changed

+582
-0
lines changed
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
packageg2901_3000.s2919_minimum_increment_operations_to_make_array_beautiful;
2+
3+
// #Medium #Array #Dynamic_Programming #2023_12_29_Time_4_ms_(64.62%)_Space_56.2_MB_(98.28%)
4+
5+
publicclassSolution {
6+
publiclongminIncrementOperations(int[]nums,intk) {
7+
long[]dp =newlong[nums.length];
8+
dp[0] =Math.max(0,k -nums[0]);
9+
dp[1] =Math.max(0,k -nums[1]);
10+
dp[2] =Math.max(0,k -nums[2]);
11+
for (inti =3;i <nums.length;i++) {
12+
dp[i] =Math.max(0,k -nums[i]) +Math.min(Math.min(dp[i -3],dp[i -2]),dp[i -1]);
13+
}
14+
returnMath.min(Math.min(dp[nums.length -3],dp[nums.length -2]),dp[nums.length -1]);
15+
}
16+
}
Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
2919\. Minimum Increment Operations to Make Array Beautiful
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums` having length`n`, and an integer`k`.
6+
7+
You can perform the following**increment** operation**any** number of times (**including zero**):
8+
9+
* Choose an index`i` in the range`[0, n - 1]`, and increase`nums[i]` by`1`.
10+
11+
An array is considered**beautiful** if, for any**subarray** with a size of`3` or**more**, its**maximum** element is**greater than or equal** to`k`.
12+
13+
Return_an integer denoting the**minimum** number of increment operations needed to make_`nums`_**beautiful**._
14+
15+
A subarray is a contiguous**non-empty** sequence of elements within an array.
16+
17+
**Example 1:**
18+
19+
**Input:** nums =[2,3,0,0,2], k = 4
20+
21+
**Output:** 3
22+
23+
**Explanation:** We can perform the following increment operations to make nums beautiful:
24+
25+
Choose index i = 1 and increase nums[1] by 1 ->[2,4,0,0,2].
26+
27+
Choose index i = 4 and increase nums[4] by 1 ->[2,4,0,0,3].
28+
29+
Choose index i = 4 and increase nums[4] by 1 ->[2,4,0,0,4].
30+
31+
The subarrays with a size of 3 or more are:[2,4,0],[4,0,0],[0,0,4],[2,4,0,0],[4,0,0,4],[2,4,0,0,4].
32+
33+
In all the subarrays, the maximum element is equal to k = 4, so nums is now beautiful.
34+
35+
It can be shown that nums cannot be made beautiful with fewer than 3 increment operations.
36+
37+
Hence, the answer is 3.
38+
39+
**Example 2:**
40+
41+
**Input:** nums =[0,1,3,3], k = 5
42+
43+
**Output:** 2
44+
45+
**Explanation:** We can perform the following increment operations to make nums beautiful:
46+
47+
Choose index i = 2 and increase nums[2] by 1 ->[0,1,4,3].
48+
49+
Choose index i = 2 and increase nums[2] by 1 ->[0,1,5,3].
50+
51+
The subarrays with a size of 3 or more are:[0,1,5],[1,5,3],[0,1,5,3].
52+
53+
In all the subarrays, the maximum element is equal to k = 5, so nums is now beautiful.
54+
55+
It can be shown that nums cannot be made beautiful with fewer than 2 increment operations.
56+
57+
Hence, the answer is 2.
58+
59+
**Example 3:**
60+
61+
**Input:** nums =[1,1,2], k = 1
62+
63+
**Output:** 0
64+
65+
**Explanation:** The only subarray with a size of 3 or more in this example is[1,1,2]. The maximum element, 2, is already greater than k = 1, so we don't need any increment operation. Hence, the answer is 0.
66+
67+
**Constraints:**
68+
69+
* <code>3 <= n == nums.length <= 10<sup>5</sup></code>
70+
* <code>0 <= nums[i] <= 10<sup>9</sup></code>
71+
* <code>0 <= k <= 10<sup>9</sup></code>
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
packageg2901_3000.s2920_maximum_points_after_collecting_coins_from_all_nodes;
2+
3+
// #Hard #Array #Dynamic_Programming #Tree #Bit_Manipulation #Depth_First_Search
4+
// #2023_12_29_Time_113_ms_(77.94%)_Space_111.3_MB_(91.50%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
privateList<Integer>[]adjList;
11+
privateint[]coins;
12+
privateintk;
13+
privateint[][]dp;
14+
15+
privatevoidinit(int[][]edges,int[]coins,intk) {
16+
intn =coins.length;
17+
adjList =newList[n];
18+
for (intv =0;v <n; ++v) {
19+
adjList[v] =newArrayList<>();
20+
}
21+
for (int[]edge :edges) {
22+
intu =edge[0];
23+
intv =edge[1];
24+
adjList[u].add(v);
25+
adjList[v].add(u);
26+
}
27+
this.coins =coins;
28+
this.k =k;
29+
dp =newint[n][14];
30+
for (intv =0;v <n; ++v) {
31+
for (intnumOfWay2Parents =0;numOfWay2Parents <14; ++numOfWay2Parents) {
32+
dp[v][numOfWay2Parents] = -1;
33+
}
34+
}
35+
}
36+
37+
privateintrec(intv,intp,intnumOfWay2Parents) {
38+
if (numOfWay2Parents >=14) {
39+
return0;
40+
}
41+
if (dp[v][numOfWay2Parents] == -1) {
42+
intcoinsV =coins[v] / (1 <<numOfWay2Parents);
43+
ints0 =coinsV -k;
44+
ints1 =coinsV /2;
45+
for (intchild :adjList[v]) {
46+
if (child !=p) {
47+
s0 +=rec(child,v,numOfWay2Parents);
48+
s1 +=rec(child,v,numOfWay2Parents +1);
49+
}
50+
}
51+
dp[v][numOfWay2Parents] =Math.max(s0,s1);
52+
}
53+
returndp[v][numOfWay2Parents];
54+
}
55+
56+
publicintmaximumPoints(int[][]edges,int[]coins,intk) {
57+
init(edges,coins,k);
58+
returnrec(0, -1,0);
59+
}
60+
}
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
2920\. Maximum Points After Collecting Coins From All Nodes
2+
3+
Hard
4+
5+
There exists an undirected tree rooted at node`0` with`n` nodes labeled from`0` to`n - 1`. You are given 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. You are also given a**0-indexed** array`coins` of size`n` where`coins[i]` indicates the number of coins in the vertex`i`, and an integer`k`.
6+
7+
Starting from the root, you have to collect all the coins such that the coins at a node can only be collected if the coins of its ancestors have been already collected.
8+
9+
Coins at <code>node<sub>i</sub></code> can be collected in one of the following ways:
10+
11+
* Collect all the coins, but you will get`coins[i] - k` points. If`coins[i] - k` is negative then you will lose`abs(coins[i] - k)` points.
12+
* Collect all the coins, but you will get`floor(coins[i] / 2)` points. If this way is used, then for all the <code>node<sub>j</sub></code> present in the subtree of <code>node<sub>i</sub></code>,`coins[j]` will get reduced to`floor(coins[j] / 2)`.
13+
14+
Return_the**maximum points** you can get after collecting the coins from**all** the tree nodes._
15+
16+
**Example 1:**
17+
18+
![](https://assets.leetcode.com/uploads/2023/09/18/ex1-copy.png)
19+
20+
**Input:** edges =[[0,1],[1,2],[2,3]], coins =[10,10,3,3], k = 5
21+
22+
**Output:** 11
23+
24+
**Explanation:**
25+
26+
Collect all the coins from node 0 using the first way. Total points = 10 - 5 = 5.
27+
28+
Collect all the coins from node 1 using the first way. Total points = 5 + (10 - 5) = 10.
29+
30+
Collect all the coins from node 2 using the second way so coins left at node 3 will be floor(3 / 2) = 1. Total points = 10 + floor(3 / 2) = 11.
31+
32+
Collect all the coins from node 3 using the second way. Total points = 11 + floor(1 / 2) = 11.
33+
34+
It can be shown that the maximum points we can get after collecting coins from all the nodes is 11.
35+
36+
**Example 2:**
37+
38+
**![](https://assets.leetcode.com/uploads/2023/09/18/ex2.png)**
39+
40+
**Input:** edges =[[0,1],[0,2]], coins =[8,4,4], k = 0
41+
42+
**Output:** 16
43+
44+
**Explanation:** Coins will be collected from all the nodes using the first way. Therefore, total points = (8 - 0) + (4 - 0) + (4 - 0) = 16.
45+
46+
**Constraints:**
47+
48+
*`n == coins.length`
49+
* <code>2 <= n <= 10<sup>5</sup></code>
50+
* <code>0 <= coins[i] <= 10<sup>4</sup></code>
51+
*`edges.length == n - 1`
52+
*`0 <= edges[i][0], edges[i][1] < n`
53+
* <code>0 <= k <= 10<sup>4</sup></code>
Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
packageg2901_3000.s2923_find_champion_i;
2+
3+
// #Easy #Array #Matrix #2023_12_29_Time_1_ms_(96.00%)_Space_45.2_MB_(6.05%)
4+
5+
publicclassSolution {
6+
publicintfindChampion(int[][]grid) {
7+
intchampion =grid[1][0];
8+
for (intopponent =2;opponent <grid.length;opponent++) {
9+
if (grid[opponent][champion] !=0) {
10+
champion =opponent;
11+
}
12+
}
13+
returnchampion;
14+
}
15+
}
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
2923\. Find Champion I
2+
3+
Easy
4+
5+
There are`n` teams numbered from`0` to`n - 1` in a tournament.
6+
7+
Given a**0-indexed** 2D boolean matrix`grid` of size`n * n`. For all`i, j` that`0 <= i, j <= n - 1` and`i != j` team`i` is**stronger** than team`j` if`grid[i][j] == 1`, otherwise, team`j` is**stronger** than team`i`.
8+
9+
Team`a` will be the**champion** of the tournament if there is no team`b` that is stronger than team`a`.
10+
11+
Return_the team that will be the champion of the tournament._
12+
13+
**Example 1:**
14+
15+
**Input:** grid =[[0,1],[0,0]]
16+
17+
**Output:** 0
18+
19+
**Explanation:** There are two teams in this tournament.
20+
21+
grid[0][1] == 1 means that team 0 is stronger than team 1. So team 0 will be the champion.
22+
23+
**Example 2:**
24+
25+
**Input:** grid =[[0,0,1],[1,0,1],[0,0,0]]
26+
27+
**Output:** 1
28+
29+
**Explanation:** There are three teams in this tournament.
30+
31+
grid[1][0] == 1 means that team 1 is stronger than team 0.
32+
33+
grid[1][2] == 1 means that team 1 is stronger than team 2.
34+
35+
So team 1 will be the champion.
36+
37+
**Constraints:**
38+
39+
*`n == grid.length`
40+
*`n == grid[i].length`
41+
*`2 <= n <= 100`
42+
*`grid[i][j]` is either`0` or`1`.
43+
* For all`i grid[i][i]` is`0.`
44+
* For all`i, j` that`i != j`,`grid[i][j] != grid[j][i]`.
45+
* The input is generated such that if team`a` is stronger than team`b` and team`b` is stronger than team`c`, then team`a` is stronger than team`c`.
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2901_3000.s2924_find_champion_ii;
2+
3+
// #Medium #Graph #2023_12_29_Time_1_ms_(100.00%)_Space_46_MB_(5.87%)
4+
5+
publicclassSolution {
6+
publicintfindChampion(intn,int[][]edges) {
7+
int[]arr =newint[n];
8+
for (int[]adj :edges) {
9+
arr[adj[1]]++;
10+
}
11+
intcnt =0;
12+
intans = -1;
13+
for (inti =0;i <n;i++) {
14+
if (arr[i] ==0) {
15+
cnt++;
16+
ans =i;
17+
}
18+
}
19+
if (cnt ==1) {
20+
returnans;
21+
}else {
22+
return -1;
23+
}
24+
}
25+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
2924\. Find Champion II
2+
3+
Medium
4+
5+
There are`n` teams numbered from`0` to`n - 1` in a tournament; each team is also a node in a**DAG**.
6+
7+
You are given the integer`n` and a**0-indexed** 2D integer array`edges` of length`m` representing the**DAG**, where <code>edges[i] =[u<sub>i</sub>, v<sub>i</sub>]</code> indicates that there is a directed edge from team <code>u<sub>i</sub></code> to team <code>v<sub>i</sub></code> in the graph.
8+
9+
A directed edge from`a` to`b` in the graph means that team`a` is**stronger** than team`b` and team`b` is**weaker** than team`a`.
10+
11+
Team`a` will be the**champion** of the tournament if there is no team`b` that is**stronger** than team`a`.
12+
13+
Return_the team that will be the**champion** of the tournament if there is a**unique** champion, otherwise, return_`-1`_._
14+
15+
**Notes**
16+
17+
* A**cycle** is a series of nodes <code>a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>, a<sub>n+1</sub></code> such that node <code>a<sub>1</sub></code> is the same node as node <code>a<sub>n+1</sub></code>, the nodes <code>a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub></code> are distinct, and there is a directed edge from the node <code>a<sub>i</sub></code> to node <code>a<sub>i+1</sub></code> for every`i` in the range`[1, n]`.
18+
* A**DAG** is a directed graph that does not have any**cycle**.
19+
20+
**Example 1:**
21+
22+
![](https://assets.leetcode.com/uploads/2023/10/19/graph-3.png)
23+
24+
**Input:** n = 3, edges =[[0,1],[1,2]]
25+
26+
**Output:** 0
27+
28+
**Explanation:** Team 1 is weaker than team 0. Team 2 is weaker than team 1. So the champion is team 0.
29+
30+
**Example 2:**
31+
32+
![](https://assets.leetcode.com/uploads/2023/10/19/graph-4.png)
33+
34+
**Input:** n = 4, edges =[[0,2],[1,3],[1,2]]
35+
36+
**Output:** -1
37+
38+
**Explanation:** Team 2 is weaker than team 0 and team 1. Team 3 is weaker than team 1. But team 1 and team 0 are not weaker than any other teams. So the answer is -1.
39+
40+
**Constraints:**
41+
42+
*`1 <= n <= 100`
43+
*`m == edges.length`
44+
*`0 <= m <= n * (n - 1) / 2`
45+
*`edges[i].length == 2`
46+
*`0 <= edge[i][j] <= n - 1`
47+
*`edges[i][0] != edges[i][1]`
48+
* The input is generated such that if team`a` is stronger than team`b`, team`b` is not stronger than team`a`.
49+
* The input is generated such that if team`a` is stronger than team`b` and team`b` is stronger than team`c`, then team`a` is stronger than team`c`.
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
packageg2901_3000.s2925_maximum_score_after_applying_operations_on_a_tree;
2+
3+
// #Medium #Dynamic_Programming #Tree #Depth_First_Search
4+
// #2023_12_29_Time_22_ms_(79.74%)_Space_57.1_MB_(70.30%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
publiclongmaximumScoreAfterOperations(int[][]edges,int[]values) {
11+
longsum =0;
12+
intn =values.length;
13+
List<List<Integer>>adj =newArrayList<>();
14+
for (inti =0;i <n; ++i) {
15+
adj.add(newArrayList<>());
16+
}
17+
for (int[]edge :edges) {
18+
adj.get(edge[0]).add(edge[1]);
19+
adj.get(edge[1]).add(edge[0]);
20+
}
21+
for (intvalue :values) {
22+
sum +=value;
23+
}
24+
longx =dfs(0, -1,adj,values);
25+
returnsum -x;
26+
}
27+
28+
privatelongdfs(intnode,intparent,List<List<Integer>>adj,int[]values) {
29+
if (adj.get(node).size() ==1 &&node !=0) {
30+
returnvalues[node];
31+
}
32+
longsum =0;
33+
for (intchild :adj.get(node)) {
34+
if (child !=parent) {
35+
sum +=dfs(child,node,adj,values);
36+
}
37+
}
38+
returnMath.min(sum,values[node]);
39+
}
40+
}

0 commit comments

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