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

Commit2034528

Browse files
authored
Added tasks 2497, 2498, 2499, 2500
1 parent9017b49 commit2034528

File tree

13 files changed

+440
-0
lines changed

13 files changed

+440
-0
lines changed

‎README.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1848,6 +1848,10 @@ implementation 'com.github.javadev:leetcode-in-java:1.18'
18481848

18491849
| # | Title | Difficulty | Tag | Time, ms | Time, %
18501850
|------|----------------|-------------|-------------|----------|---------
1851+
| 2500 |[Delete Greatest Value in Each Row](src/main/java/g2401_2500/s2500_delete_greatest_value_in_each_row/Solution.java)| Easy | Array, Sorting, Matrix | 3 | 98.16
1852+
| 2499 |[Minimum Total Cost to Make Arrays Unequal](src/main/java/g2401_2500/s2499_minimum_total_cost_to_make_arrays_unequal/Solution.java)| Hard | Array, Hash_Table, Greedy, Counting | 3 | 100.00
1853+
| 2498 |[Frog Jump II](src/main/java/g2401_2500/s2498_frog_jump_ii/Solution.java)| Medium | Array, Greedy, Binary_Search | 1 | 100.00
1854+
| 2497 |[Maximum Star Sum of a Graph](src/main/java/g2401_2500/s2497_maximum_star_sum_of_a_graph/Solution.java)| Medium | Array, Sorting, Greedy, Heap_Priority_Queue, Graph | 36 | 97.50
18511855
| 2496 |[Maximum Value of a String in an Array](src/main/java/g2401_2500/s2496_maximum_value_of_a_string_in_an_array/Solution.java)| Easy | Array, String | 1 | 92.00
18521856
| 2493 |[Divide Nodes Into the Maximum Number of Groups](src/main/java/g2401_2500/s2493_divide_nodes_into_the_maximum_number_of_groups/Solution.java)| Hard | Breadth_First_Search, Graph, Union_Find | 443 | 77.02
18531857
| 2492 |[Minimum Score of a Path Between Two Cities](src/main/java/g2401_2500/s2492_minimum_score_of_a_path_between_two_cities/Solution.java)| Medium | Depth_First_Search, Breadth_First_Search, Graph, Union_Find | 13 | 92.82
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
packageg2401_2500.s2497_maximum_star_sum_of_a_graph;
2+
3+
// #Medium #Array #Sorting #Greedy #Heap_Priority_Queue #Graph
4+
// #2023_02_12_Time_36_ms_(97.50%)_Space_90.1_MB_(69.28%)
5+
6+
importjava.util.PriorityQueue;
7+
8+
publicclassSolution {
9+
privatePriorityQueue<Integer>[]graphNodeIdToNodeValues;
10+
11+
publicintmaxStarSum(int[]nodeValues,int[][]edges,intmaxNumberOfEdges) {
12+
finalinttotalNodes =nodeValues.length;
13+
graphNodeIdToNodeValues =newPriorityQueue[totalNodes];
14+
for (inti =0;i <totalNodes; ++i) {
15+
graphNodeIdToNodeValues[i] =newPriorityQueue<>();
16+
}
17+
for (int[]edge :edges) {
18+
addEdgeEndingWithValueOfNode(nodeValues,edge[0],edge[1],maxNumberOfEdges);
19+
addEdgeEndingWithValueOfNode(nodeValues,edge[1],edge[0],maxNumberOfEdges);
20+
}
21+
returncalculateMaxStarSum(nodeValues,totalNodes);
22+
}
23+
24+
privatevoidaddEdgeEndingWithValueOfNode(
25+
int[]nodeValues,intfromNode,inttoNode,intmaxNumberOfEdges) {
26+
if (nodeValues[toNode] >0 &&graphNodeIdToNodeValues[fromNode].size() <maxNumberOfEdges) {
27+
graphNodeIdToNodeValues[fromNode].add(nodeValues[toNode]);
28+
}elseif (!graphNodeIdToNodeValues[fromNode].isEmpty()
29+
&&graphNodeIdToNodeValues[fromNode].peek() <nodeValues[toNode]) {
30+
graphNodeIdToNodeValues[fromNode].poll();
31+
graphNodeIdToNodeValues[fromNode].add(nodeValues[toNode]);
32+
}
33+
}
34+
35+
privateintcalculateMaxStarSum(int[]nodeValues,inttotalNodes) {
36+
intmaxStarSum =Integer.MIN_VALUE;
37+
for (inti =0;i <totalNodes; ++i) {
38+
intsum =nodeValues[i];
39+
for (intvalue :graphNodeIdToNodeValues[i]) {
40+
sum +=value;
41+
}
42+
maxStarSum =Math.max(maxStarSum,sum);
43+
}
44+
returnmaxStarSum;
45+
}
46+
}
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
2497\. Maximum Star Sum of a Graph
2+
3+
Medium
4+
5+
There is an undirected graph consisting of`n` nodes numbered from`0` to`n - 1`. You are given a**0-indexed** integer array`vals` of length`n` where`vals[i]` denotes the value of the <code>i<sup>th</sup></code> node.
6+
7+
You are also given a 2D integer array`edges` where <code>edges[i] =[a<sub>i</sub>, b<sub>i</sub>]</code> denotes that there exists an**undirected** edge connecting nodes <code>a<sub>i</sub></code> and <code>b<sub>i.</sub></code>
8+
9+
A**star graph** is a subgraph of the given graph having a center node containing`0` or more neighbors. In other words, it is a subset of edges of the given graph such that there exists a common node for all edges.
10+
11+
The image below shows star graphs with`3` and`4` neighbors respectively, centered at the blue node.
12+
13+
![](https://assets.leetcode.com/uploads/2022/11/07/max-star-sum-descdrawio.png)
14+
15+
The**star sum** is the sum of the values of all the nodes present in the star graph.
16+
17+
Given an integer`k`, return_the**maximum star sum** of a star graph containing**at most**_`k`_edges._
18+
19+
**Example 1:**
20+
21+
![](https://assets.leetcode.com/uploads/2022/11/07/max-star-sum-example1drawio.png)
22+
23+
**Input:** vals =[1,2,3,4,10,-10,-20], edges =[[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]], k = 2
24+
25+
**Output:** 16
26+
27+
**Explanation:** The above diagram represents the input graph.
28+
29+
The star graph with the maximum star sum is denoted by blue.
30+
31+
It is centered at 3 and includes its neighbors 1 and 4. It can be shown it is not possible to get a star graph with a sum greater than 16.
32+
33+
**Example 2:**
34+
35+
**Input:** vals =[-5], edges =[], k = 0
36+
37+
**Output:** -5
38+
39+
**Explanation:** There is only one possible star graph, which is node 0 itself. Hence, we return -5.
40+
41+
**Constraints:**
42+
43+
*`n == vals.length`
44+
* <code>1 <= n <= 10<sup>5</sup></code>
45+
* <code>-10<sup>4</sup> <= vals[i] <= 10<sup>4</sup></code>
46+
*`0 <= edges.length <= min(n * (n - 1) / 2`<code>, 10<sup>5</sup>)</code>
47+
*`edges[i].length == 2`
48+
* <code>0 <= a<sub>i</sub>, b<sub>i</sub> <= n - 1</code>
49+
* <code>a<sub>i</sub> != b<sub>i</sub></code>
50+
*`0 <= k <= n - 1`
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
packageg2401_2500.s2498_frog_jump_ii;
2+
3+
// #Medium #Array #Greedy #Binary_Search #2023_02_12_Time_1_ms_(100.00%)_Space_55.8_MB_(66.50%)
4+
5+
publicclassSolution {
6+
publicintmaxJump(int[]stones) {
7+
intn =stones.length;
8+
intmax =0;
9+
for (inti =2;i <n;i++) {
10+
intgap =stones[i] -stones[i -2];
11+
if (gap >max) {
12+
max =gap;
13+
}
14+
}
15+
if (n >2) {
16+
returnmax;
17+
}else {
18+
returnstones[1] -stones[0];
19+
}
20+
}
21+
}
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
2498\. Frog Jump II
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`stones` sorted in**strictly increasing order** representing the positions of stones in a river.
6+
7+
A frog, initially on the first stone, wants to travel to the last stone and then return to the first stone. However, it can jump to any stone**at most once**.
8+
9+
The**length** of a jump is the absolute difference between the position of the stone the frog is currently on and the position of the stone to which the frog jumps.
10+
11+
* More formally, if the frog is at`stones[i]` and is jumping to`stones[j]`, the length of the jump is`|stones[i] - stones[j]|`.
12+
13+
The**cost** of a path is the**maximum length of a jump** among all jumps in the path.
14+
15+
Return_the**minimum** cost of a path for the frog_.
16+
17+
**Example 1:**
18+
19+
![](https://assets.leetcode.com/uploads/2022/11/14/example-1.png)
20+
21+
**Input:** stones =[0,2,5,6,7]
22+
23+
**Output:** 5
24+
25+
**Explanation:** The above figure represents one of the optimal paths the frog can take.
26+
27+
The cost of this path is 5, which is the maximum length of a jump.
28+
29+
Since it is not possible to achieve a cost of less than 5, we return it.
30+
31+
**Example 2:**
32+
33+
![](https://assets.leetcode.com/uploads/2022/11/14/example-2.png)
34+
35+
**Input:** stones =[0,3,9]
36+
37+
**Output:** 9
38+
39+
**Explanation:** The frog can jump directly to the last stone and come back to the first stone.
40+
41+
In this case, the length of each jump will be 9. The cost for the path will be max(9, 9) = 9.
42+
43+
It can be shown that this is the minimum achievable cost.
44+
45+
**Constraints:**
46+
47+
* <code>2 <= stones.length <= 10<sup>5</sup></code>
48+
* <code>0 <= stones[i] <= 10<sup>9</sup></code>
49+
*`stones[0] == 0`
50+
*`stones` is sorted in a strictly increasing order.
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
packageg2401_2500.s2499_minimum_total_cost_to_make_arrays_unequal;
2+
3+
// #Hard #Array #Hash_Table #Greedy #Counting #2023_02_12_Time_3_ms_(100.00%)_Space_59.5_MB_(76.40%)
4+
5+
publicclassSolution {
6+
publiclongminimumTotalCost(int[]nums1,int[]nums2) {
7+
intn =nums1.length;
8+
int[]bucket =newint[n +1];
9+
intmax =0;
10+
intmaxKey = -1;
11+
inttotalBucket =0;
12+
longcost =0;
13+
for (inti =0;i <n;i++) {
14+
if (nums1[i] ==nums2[i]) {
15+
if (++bucket[nums1[i]] >max) {
16+
max =bucket[nums1[i]];
17+
maxKey =nums1[i];
18+
}
19+
totalBucket++;
20+
cost +=i;
21+
}
22+
}
23+
intrequiredBucket =2 *max;
24+
if (requiredBucket >n) {
25+
return -1;
26+
}
27+
intlackBucket =requiredBucket -totalBucket;
28+
inti =0;
29+
while (i <n &&lackBucket >0) {
30+
if (nums1[i] ==maxKey ||nums2[i] ==maxKey ||nums1[i] ==nums2[i]) {
31+
i++;
32+
continue;
33+
}
34+
lackBucket--;
35+
cost +=i;
36+
i++;
37+
}
38+
if (lackBucket >0) {
39+
return -1;
40+
}
41+
returncost;
42+
}
43+
}
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
2499\. Minimum Total Cost to Make Arrays Unequal
2+
3+
Hard
4+
5+
You are given two**0-indexed** integer arrays`nums1` and`nums2`, of equal length`n`.
6+
7+
In one operation, you can swap the values of any two indices of`nums1`. The**cost** of this operation is the**sum** of the indices.
8+
9+
Find the**minimum** total cost of performing the given operation**any** number of times such that`nums1[i] != nums2[i]` for all`0 <= i <= n - 1` after performing all the operations.
10+
11+
Return_the**minimum total cost** such that_`nums1` and`nums2`_satisfy the above condition_. In case it is not possible, return`-1`.
12+
13+
**Example 1:**
14+
15+
**Input:** nums1 =[1,2,3,4,5], nums2 =[1,2,3,4,5]
16+
17+
**Output:** 10
18+
19+
**Explanation:** One of the ways we can perform the operations is:
20+
21+
- Swap values at indices 0 and 3, incurring cost = 0 + 3 = 3. Now, nums1 =[4,2,3,1,5]
22+
23+
- Swap values at indices 1 and 2, incurring cost = 1 + 2 = 3. Now, nums1 =[4,3,2,1,5].
24+
25+
- Swap values at indices 0 and 4, incurring cost = 0 + 4 = 4. Now, nums1 =[5,3,2,1,4].
26+
27+
We can see that for each index i, nums1[i] != nums2[i]. The cost required here is 10.
28+
29+
Note that there are other ways to swap values, but it can be proven that it is not possible to obtain a cost less than 10.
30+
31+
**Example 2:**
32+
33+
**Input:** nums1 =[2,2,2,1,3], nums2 =[1,2,2,3,3]
34+
35+
**Output:** 10
36+
37+
**Explanation:** One of the ways we can perform the operations is:
38+
39+
- Swap values at indices 2 and 3, incurring cost = 2 + 3 = 5. Now, nums1 =[2,2,1,2,3].
40+
41+
- Swap values at indices 1 and 4, incurring cost = 1 + 4 = 5. Now, nums1 =[2,3,1,2,2].
42+
43+
The total cost needed here is 10, which is the minimum possible.
44+
45+
**Example 3:**
46+
47+
**Input:** nums1 =[1,2,2], nums2 =[1,2,2]
48+
49+
**Output:** -1
50+
51+
**Explanation:** It can be shown that it is not possible to satisfy the given conditions irrespective of the number of operations we perform. Hence, we return -1.
52+
53+
**Constraints:**
54+
55+
*`n == nums1.length == nums2.length`
56+
* <code>1 <= n <= 10<sup>5</sup></code>
57+
*`1 <= nums1[i], nums2[i] <= n`
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
packageg2401_2500.s2500_delete_greatest_value_in_each_row;
2+
3+
// #Easy #Array #Sorting #Matrix #2023_02_12_Time_3_ms_(98.16%)_Space_42.6_MB_(34.09%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publicintdeleteGreatestValue(int[][]grid) {
9+
intsum =0;
10+
for (inti =0;i <grid.length;i++) {
11+
Arrays.sort(grid[i]);
12+
}
13+
for (intj =0;j <grid[0].length;j++) {
14+
intmax =Integer.MIN_VALUE;
15+
for (inti =0;i <grid.length;i++) {
16+
if (grid[i][j] >max) {
17+
max =grid[i][j];
18+
}
19+
}
20+
sum +=max;
21+
}
22+
returnsum;
23+
}
24+
}
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
2500\. Delete Greatest Value in Each Row
2+
3+
Easy
4+
5+
You are given an`m x n` matrix`grid` consisting of positive integers.
6+
7+
Perform the following operation until`grid` becomes empty:
8+
9+
* Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them.
10+
* Add the maximum of deleted elements to the answer.
11+
12+
**Note** that the number of columns decreases by one after each operation.
13+
14+
Return_the answer after performing the operations described above_.
15+
16+
**Example 1:**
17+
18+
![](https://assets.leetcode.com/uploads/2022/10/19/q1ex1.jpg)
19+
20+
**Input:** grid =[[1,2,4],[3,3,1]]
21+
22+
**Output:** 8
23+
24+
**Explanation:** The diagram above shows the removed values in each step.
25+
26+
- In the first operation, we remove 4 from the first row and 3 from the second row (notice that, there are two cells with value 3 and we can remove any of them). We add 4 to the answer.
27+
28+
- In the second operation, we remove 2 from the first row and 3 from the second row. We add 3 to the answer.
29+
30+
- In the third operation, we remove 1 from the first row and 1 from the second row. We add 1 to the answer.
31+
32+
The final answer = 4 + 3 + 1 = 8.
33+
34+
**Example 2:**
35+
36+
![](https://assets.leetcode.com/uploads/2022/10/19/q1ex2.jpg)
37+
38+
**Input:** grid =[[10]]
39+
40+
**Output:** 10
41+
42+
**Explanation:** The diagram above shows the removed values in each step.
43+
44+
- In the first operation, we remove 10 from the first row. We add 10 to the answer.
45+
46+
The final answer = 10.
47+
48+
**Constraints:**
49+
50+
*`m == grid.length`
51+
*`n == grid[i].length`
52+
*`1 <= m, n <= 50`
53+
*`1 <= grid[i][j] <= 100`
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
packageg2401_2500.s2497_maximum_star_sum_of_a_graph;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidmaxStarSum() {
11+
assertThat(
12+
newSolution()
13+
.maxStarSum(
14+
newint[] {1,2,3,4,10, -10, -20},
15+
newint[][] {{0,1}, {1,2}, {1,3}, {3,4}, {3,5}, {3,6}},
16+
2),
17+
equalTo(16));
18+
}
19+
20+
@Test
21+
voidmaxStarSum2() {
22+
assertThat(newSolution().maxStarSum(newint[] {-5},newint[][] {},0),equalTo(-5));
23+
}
24+
}

0 commit comments

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