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

Commitb2f1d39

Browse files
authored
Added tasks 2536, 2537, 2538, 2540, 2541
1 parentbd08265 commitb2f1d39

File tree

16 files changed

+558
-0
lines changed

16 files changed

+558
-0
lines changed

‎README.md

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

18491849
| # | Title | Difficulty | Tag | Time, ms | Time, %
18501850
|------|----------------|-------------|-------------|----------|---------
1851+
| 2541 |[Minimum Operations to Make Array Equal II](src/main/java/g2501_2600/s2541_minimum_operations_to_make_array_equal_ii/Solution.java)| Medium | Array, Math, Greedy | 3 | 100.00
1852+
| 2540 |[Minimum Common Value](src/main/java/g2501_2600/s2540_minimum_common_value/Solution.java)| Easy | Array, Hash_Table, Binary_Search, Two_Pointers | 0 | 100.00
1853+
| 2538 |[Difference Between Maximum and Minimum Price Sum](src/main/java/g2501_2600/s2538_difference_between_maximum_and_minimum_price_sum/Solution.java)| Hard | Array, Dynamic_Programming, Tree, Depth_First_Search | 43 | 95.19
1854+
| 2537 |[Count the Number of Good Subarrays](src/main/java/g2501_2600/s2537_count_the_number_of_good_subarrays/Solution.java)| Medium | Array, Hash_Table, Sliding_Window | 38 | 99.07
1855+
| 2536 |[Increment Submatrices by One](src/main/java/g2501_2600/s2536_increment_submatrices_by_one/Solution.java)| Medium | Array, Matrix, Prefix_Sum | 12 | 88.15
18511856
| 2535 |[Difference Between Element Sum and Digit Sum of an Array](src/main/java/g2501_2600/s2535_difference_between_element_sum_and_digit_sum_of_an_array/Solution.java)| Easy | Array, Math | 3 | 77.42
18521857
| 2532 |[Time to Cross a Bridge](src/main/java/g2501_2600/s2532_time_to_cross_a_bridge/Solution.java)| Hard | Array, Heap_Priority_Queue, Simulation | 67 | 72.50
18531858
| 2531 |[Make Number of Distinct Characters Equal](src/main/java/g2501_2600/s2531_make_number_of_distinct_characters_equal/Solution.java)| Medium | String, Hash_Table, Counting | 7 | 100.00
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
packageg2501_2600.s2536_increment_submatrices_by_one;
2+
3+
// #Medium #Array #Matrix #Prefix_Sum #2023_04_22_Time_12_ms_(88.15%)_Space_50.9_MB_(65.40%)
4+
5+
publicclassSolution {
6+
publicint[][]rangeAddQueries(intn,int[][]queries) {
7+
int[][]g =newint[n][n];
8+
for (int[]q :queries) {
9+
intr1 =q[0];
10+
intc1 =q[1];
11+
intr2 =q[2];
12+
intc2 =q[3];
13+
g[r1][c1]++;
14+
if (c2 <n -1) {
15+
g[r1][c2 +1]--;
16+
}
17+
if (r2 <n -1) {
18+
g[r2 +1][c1]--;
19+
}
20+
if (c2 <n -1 &&r2 <n -1) {
21+
g[r2 +1][c2 +1]++;
22+
}
23+
}
24+
25+
for (inti =0;i <n;i++) {
26+
for (intj =0;j <n;j++) {
27+
if (i >0) {
28+
g[i][j] +=g[i -1][j];
29+
}
30+
if (j >0) {
31+
g[i][j] +=g[i][j -1];
32+
}
33+
if (i >0 &&j >0) {
34+
g[i][j] -=g[i -1][j -1];
35+
}
36+
}
37+
}
38+
39+
returng;
40+
}
41+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
2536\. Increment Submatrices by One
2+
3+
Medium
4+
5+
You are given a positive integer`n`, indicating that we initially have an`n x n`**0-indexed** integer matrix`mat` filled with zeroes.
6+
7+
You are also given a 2D integer array`query`. For each <code>query[i] =[row1<sub>i</sub>, col1<sub>i</sub>, row2<sub>i</sub>, col2<sub>i</sub>]</code>, you should do the following operation:
8+
9+
* Add`1` to**every element** in the submatrix with the**top left** corner <code>(row1<sub>i</sub>, col1<sub>i</sub>)</code> and the**bottom right** corner <code>(row2<sub>i</sub>, col2<sub>i</sub>)</code>. That is, add`1` to`mat[x][y]` for all <code>row1<sub>i</sub> <= x <= row2<sub>i</sub></code> and <code>col1<sub>i</sub> <= y <= col2<sub>i</sub></code>.
10+
11+
Return_the matrix_`mat`_after performing every query._
12+
13+
**Example 1:**
14+
15+
![](https://assets.leetcode.com/uploads/2022/11/24/p2example11.png)
16+
17+
**Input:** n = 3, queries =[[1,1,2,2],[0,0,1,1]]
18+
19+
**Output:**[[1,1,0],[1,2,1],[0,1,1]]
20+
21+
**Explanation:** The diagram above shows the initial matrix, the matrix after the first query, and the matrix after the second query.
22+
23+
- In the first query, we add 1 to every element in the submatrix with the top left corner (1, 1) and bottom right corner (2, 2).
24+
25+
- In the second query, we add 1 to every element in the submatrix with the top left corner (0, 0) and bottom right corner (1, 1).
26+
27+
**Example 2:**
28+
29+
![](https://assets.leetcode.com/uploads/2022/11/24/p2example22.png)
30+
31+
**Input:** n = 2, queries =[[0,0,1,1]]
32+
33+
**Output:**[[1,1],[1,1]]
34+
35+
**Explanation:** The diagram above shows the initial matrix and the matrix after the first query.
36+
37+
- In the first query we add 1 to every element in the matrix.
38+
39+
**Constraints:**
40+
41+
*`1 <= n <= 500`
42+
* <code>1 <= queries.length <= 10<sup>4</sup></code>
43+
* <code>0 <= row1<sub>i</sub> <= row2<sub>i</sub> < n</code>
44+
* <code>0 <= col1<sub>i</sub> <= col2<sub>i</sub> < n</code>
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
packageg2501_2600.s2537_count_the_number_of_good_subarrays;
2+
3+
// #Medium #Array #Hash_Table #Sliding_Window #2023_04_22_Time_38_ms_(99.07%)_Space_60.8_MB_(16.67%)
4+
5+
importjava.util.HashMap;
6+
importjava.util.Map;
7+
8+
publicclassSolution {
9+
publiclongcountGood(int[]nums,intk) {
10+
if (nums.length <2) {
11+
return0L;
12+
}
13+
14+
Map<Integer,Integer>countMap =newHashMap<>(nums.length,0.99f);
15+
longgoodSubArrays =0L;
16+
longcurrent =0L;
17+
intleft =0;
18+
intright = -1;
19+
while (left <nums.length) {
20+
if (current <k) {
21+
if (++right ==nums.length) {
22+
break;
23+
}
24+
Integernum =nums[right];
25+
Integercount =countMap.get(num);
26+
if (count ==null) {
27+
count =1;
28+
}else {
29+
current +=count;
30+
if (current >=k) {
31+
goodSubArrays +=nums.length -right;
32+
}
33+
count =count +1;
34+
}
35+
countMap.put(num,count);
36+
}else {
37+
Integernum =nums[left++];
38+
intcount =countMap.get(num) -1;
39+
if (count >0) {
40+
countMap.put(num,count);
41+
current -=count;
42+
}else {
43+
countMap.remove(num);
44+
}
45+
if (current >=k) {
46+
goodSubArrays +=nums.length -right;
47+
}
48+
}
49+
}
50+
51+
returngoodSubArrays;
52+
}
53+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
2537\. Count the Number of Good Subarrays
2+
3+
Medium
4+
5+
Given an integer array`nums` and an integer`k`, return_the number of**good** subarrays of_`nums`.
6+
7+
A subarray`arr` is**good** if it there are**at least**`k` pairs of indices`(i, j)` such that`i < j` and`arr[i] == arr[j]`.
8+
9+
A**subarray** is a contiguous**non-empty** sequence of elements within an array.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[1,1,1,1,1], k = 10
14+
15+
**Output:** 1
16+
17+
**Explanation:** The only good subarray is the array nums itself.
18+
19+
**Example 2:**
20+
21+
**Input:** nums =[3,1,4,3,2,2,4], k = 2
22+
23+
**Output:** 4
24+
25+
**Explanation:** There are 4 different good subarrays:
26+
27+
-[3,1,4,3,2,2] that has 2 pairs.
28+
29+
-[3,1,4,3,2,2,4] that has 3 pairs.
30+
31+
-[1,4,3,2,2,4] that has 2 pairs.
32+
33+
-[4,3,2,2,4] that has 2 pairs.
34+
35+
**Constraints:**
36+
37+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
38+
* <code>1 <= nums[i], k <= 10<sup>9</sup></code>
Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
packageg2501_2600.s2538_difference_between_maximum_and_minimum_price_sum;
2+
3+
// #Hard #Array #Dynamic_Programming #Tree #Depth_First_Search
4+
// #2023_04_22_Time_43_ms_(95.19%)_Space_86.2_MB_(57.69%)
5+
6+
importjava.util.ArrayList;
7+
8+
publicclassSolution {
9+
privateArrayList<Integer>[]tree;
10+
privateint[]price;
11+
privatelongres;
12+
privateboolean[]visited;
13+
14+
publiclongmaxOutput(intn,int[][]edges,int[]price) {
15+
if (n ==1) {
16+
return0;
17+
}
18+
19+
this.price =price;
20+
tree =newArrayList[n];
21+
for (inti =0;i <n;i++) {
22+
tree[i] =newArrayList<>();
23+
}
24+
for (int[]e :edges) {
25+
tree[e[0]].add(e[1]);
26+
tree[e[1]].add(e[0]);
27+
}
28+
29+
visited =newboolean[n];
30+
visited[0] =true;
31+
dfs(0);
32+
33+
returnres;
34+
}
35+
36+
// return long[]{longest path with leaf, longest path without leaf}
37+
privatelong[]dfs(intnode) {
38+
if (tree[node].size() ==1 &&node !=0) {
39+
returnnewlong[] {price[node],0};
40+
}
41+
inti0 = -1;
42+
inti1 = -1;
43+
longl0 =0;
44+
longl1 =0;
45+
longs0 =0;
46+
longs1 =0;
47+
for (intchild :tree[node]) {
48+
if (visited[child]) {
49+
continue;
50+
}
51+
visited[child] =true;
52+
long[]sub =dfs(child);
53+
if (sub[0] >=l0) {
54+
s0 =l0;
55+
l0 =sub[0];
56+
i0 =child;
57+
}elseif (sub[0] >s0) {
58+
s0 =sub[0];
59+
}
60+
61+
if (sub[1] >=l1) {
62+
s1 =l1;
63+
l1 =sub[1];
64+
i1 =child;
65+
}elseif (sub[1] >s1) {
66+
s1 =sub[1];
67+
}
68+
}
69+
70+
if (s0 ==0) {
71+
// only one child. case: example 2
72+
res =Math.max(res,Math.max(l0,l1 +price[node]));
73+
}else {
74+
longpath =i0 !=i1 ?price[node] +l0 +l1 :price[node] +Math.max(l0 +s1,s0 +l1);
75+
res =Math.max(res,path);
76+
}
77+
returnnewlong[] {l0 +price[node],l1 +price[node]};
78+
}
79+
}
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
2538\. Difference Between Maximum and Minimum Price Sum
2+
3+
Hard
4+
5+
There exists an undirected and initially unrooted tree with`n` nodes indexed 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+
Each node has an associated price. You are given an integer array`price`, where`price[i]` is the price of the <code>i<sup>th</sup></code> node.
8+
9+
The**price sum** of a given path is the sum of the prices of all nodes lying on that path.
10+
11+
The tree can be rooted at any node`root` of your choice. The incurred**cost** after choosing`root` is the difference between the maximum and minimum**price sum** amongst all paths starting at`root`.
12+
13+
Return_the**maximum** possible**cost**__amongst all possible root choices_.
14+
15+
**Example 1:**
16+
17+
![](https://assets.leetcode.com/uploads/2022/12/01/example14.png)
18+
19+
**Input:** n = 6, edges =[[0,1],[1,2],[1,3],[3,4],[3,5]], price =[9,8,7,6,10,5]
20+
21+
**Output:** 24
22+
23+
**Explanation:** The diagram above denotes the tree after rooting it at node 2. The first part (colored in red) shows the path with the maximum price sum. The second part (colored in blue) shows the path with the minimum price sum.
24+
25+
- The first path contains nodes[2,1,3,4]: the prices are[7,8,6,10], and the sum of the prices is 31.
26+
27+
- The second path contains the node[2] with the price[7].
28+
29+
The difference between the maximum and minimum price sum is 24. It can be proved that 24 is the maximum cost.
30+
31+
**Example 2:**
32+
33+
![](https://assets.leetcode.com/uploads/2022/11/24/p1_example2.png)
34+
35+
**Input:** n = 3, edges =[[0,1],[1,2]], price =[1,1,1]
36+
37+
**Output:** 2
38+
39+
**Explanation:** The diagram above denotes the tree after rooting it at node 0. The first part (colored in red) shows the path with the maximum price sum. The second part (colored in blue) shows the path with the minimum price sum.
40+
41+
- The first path contains nodes[0,1,2]: the prices are[1,1,1], and the sum of the prices is 3.
42+
43+
- The second path contains node[0] with a price[1].
44+
45+
The difference between the maximum and minimum price sum is 2. It can be proved that 2 is the maximum cost.
46+
47+
**Constraints:**
48+
49+
* <code>1 <= n <= 10<sup>5</sup></code>
50+
*`edges.length == n - 1`
51+
* <code>0 <= a<sub>i</sub>, b<sub>i</sub> <= n - 1</code>
52+
*`edges` represents a valid tree.
53+
*`price.length == n`
54+
* <code>1 <= price[i] <= 10<sup>5</sup></code>
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2501_2600.s2540_minimum_common_value;
2+
3+
// #Easy #Array #Hash_Table #Binary_Search #Two_Pointers
4+
// #2023_04_22_Time_0_ms_(100.00%)_Space_58.9_MB_(33.19%)
5+
6+
publicclassSolution {
7+
publicintgetCommon(int[]nums1,int[]nums2) {
8+
inti =0;
9+
intj =0;
10+
if (nums1[0] >nums2[nums2.length -1] ||nums1[nums1.length -1] <nums2[0]) {
11+
return -1;
12+
}
13+
while (i <nums1.length &&j <nums2.length) {
14+
if (nums1[i] ==nums2[j]) {
15+
returnnums1[i];
16+
}
17+
if (nums1[i] >nums2[j]) {
18+
j++;
19+
}else {
20+
i++;
21+
}
22+
}
23+
return -1;
24+
}
25+
}
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
2540\. Minimum Common Value
2+
3+
Easy
4+
5+
Given two integer arrays`nums1` and`nums2`, sorted in non-decreasing order, return_the**minimum integer common** to both arrays_. If there is no common integer amongst`nums1` and`nums2`, return`-1`.
6+
7+
Note that an integer is said to be**common** to`nums1` and`nums2` if both arrays have**at least one** occurrence of that integer.
8+
9+
**Example 1:**
10+
11+
**Input:** nums1 =[1,2,3], nums2 =[2,4]
12+
13+
**Output:** 2
14+
15+
**Explanation:** The smallest element common to both arrays is 2, so we return 2.
16+
17+
**Example 2:**
18+
19+
**Input:** nums1 =[1,2,3,6], nums2 =[2,3,4,5]
20+
21+
**Output:** 2
22+
23+
**Explanation:** There are two common elements in the array 2 and 3 out of which 2 is the smallest, so 2 is returned.
24+
25+
**Constraints:**
26+
27+
* <code>1 <= nums1.length, nums2.length <= 10<sup>5</sup></code>
28+
* <code>1 <= nums1[i], nums2[j] <= 10<sup>9</sup></code>
29+
* Both`nums1` and`nums2` are sorted in**non-decreasing** order.

0 commit comments

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