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

Commit2a312d4

Browse files
authored
Added tasks 2602-2607
1 parent1341e85 commit2a312d4

File tree

15 files changed

+507
-0
lines changed

15 files changed

+507
-0
lines changed
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
packageg2601_2700.s2602_minimum_operations_to_make_all_array_elements_equal;
2+
3+
// #Medium #Array #Sorting #Binary_Search #Prefix_Sum
4+
// #2023_08_29_Time_41_ms_(97.39%)_Space_59.4_MB_(83.66%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
importjava.util.List;
9+
10+
publicclassSolution {
11+
publicList<Long>minOperations(int[]nums,int[]queries) {
12+
Arrays.sort(nums);
13+
long[]sum =newlong[nums.length];
14+
sum[0] =nums[0];
15+
for (inti =1;i <nums.length; ++i) {
16+
sum[i] =sum[i -1] +nums[i];
17+
}
18+
List<Long>res =newArrayList<>();
19+
for (intquery :queries) {
20+
res.add(getOperations(sum,nums,query));
21+
}
22+
returnres;
23+
}
24+
25+
privatelonggetOperations(long[]sum,int[]nums,inttarget) {
26+
longres =0;
27+
intindex =getIndex(nums,target);
28+
intrightCounts =nums.length -1 -index;
29+
if (index >0) {
30+
res += (long)index *target -sum[index -1];
31+
}
32+
if (rightCounts >0) {
33+
res +=sum[nums.length -1] -sum[index] - (long)rightCounts *target;
34+
}
35+
res +=Math.abs(target -nums[index]);
36+
returnres;
37+
}
38+
39+
privateintgetIndex(int[]nums,inttarget) {
40+
intindex =Arrays.binarySearch(nums,target);
41+
if (index <0) {
42+
index = -(index +1);
43+
}
44+
if (index ==nums.length) {
45+
--index;
46+
}
47+
returnindex;
48+
}
49+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
2602\. Minimum Operations to Make All Array Elements Equal
2+
3+
Medium
4+
5+
You are given an array`nums` consisting of positive integers.
6+
7+
You are also given an integer array`queries` of size`m`. For the <code>i<sup>th</sup></code> query, you want to make all of the elements of`nums` equal to`queries[i]`. You can perform the following operation on the array**any** number of times:
8+
9+
***Increase** or**decrease** an element of the array by`1`.
10+
11+
Return_an array_`answer`_of size_`m`_where_`answer[i]`_is the**minimum** number of operations to make all elements of_`nums`_equal to_`queries[i]`.
12+
13+
**Note** that after each query the array is reset to its original state.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[3,1,6,8], queries =[1,5]
18+
19+
**Output:**[14,10]
20+
21+
**Explanation:** For the first query we can do the following operations:
22+
- Decrease nums[0] 2 times, so that nums =[1,1,6,8].
23+
- Decrease nums[2] 5 times, so that nums =[1,1,1,8].
24+
- Decrease nums[3] 7 times, so that nums =[1,1,1,1].
25+
26+
So the total number of operations for the first query is 2 + 5 + 7 = 14.
27+
28+
For the second query we can do the following operations:
29+
- Increase nums[0] 2 times, so that nums =[5,1,6,8].
30+
- Increase nums[1] 4 times, so that nums =[5,5,6,8].
31+
- Decrease nums[2] 1 time, so that nums =[5,5,5,8].
32+
- Decrease nums[3] 3 times, so that nums =[5,5,5,5].
33+
34+
So the total number of operations for the second query is 2 + 4 + 1 + 3 = 10.
35+
36+
**Example 2:**
37+
38+
**Input:** nums =[2,9,6,3], queries =[10]
39+
40+
**Output:**[20]
41+
42+
**Explanation:** We can increase each value in the array to 10. The total number of operations will be 8 + 1 + 4 + 7 = 20.
43+
44+
**Constraints:**
45+
46+
*`n == nums.length`
47+
*`m == queries.length`
48+
* <code>1 <= n, m <= 10<sup>5</sup></code>
49+
* <code>1 <= nums[i], queries[i] <= 10<sup>9</sup></code>
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
packageg2601_2700.s2603_collect_coins_in_a_tree;
2+
3+
// #Hard #Array #Tree #Graph #Topological_Sort
4+
// #2023_08_29_Time_26_ms_(100.00%)_Space_66.3_MB_(32.97%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
privateint[]coins;
11+
privateList<Integer>[]graph;
12+
privateintsum;
13+
privateintret;
14+
15+
publicintcollectTheCoins(int[]coins,int[][]edges) {
16+
intn =coins.length;
17+
this.coins =coins;
18+
graph =newArrayList[n];
19+
for (inti =0;i <n;i++) {
20+
graph[i] =newArrayList<>();
21+
}
22+
for (int[]edge :edges) {
23+
graph[edge[0]].add(edge[1]);
24+
graph[edge[1]].add(edge[0]);
25+
}
26+
for (intcoin :coins) {
27+
sum +=coin;
28+
}
29+
dfs(0, -1);
30+
returnMath.max(2 * (ret -1),0);
31+
}
32+
33+
privateintdfs(intnode,intpre) {
34+
intcnt =0;
35+
ints =0;
36+
for (intnn :graph[node]) {
37+
if (nn !=pre) {
38+
intr =dfs(nn,node);
39+
if (r -coins[nn] >0) {
40+
cnt++;
41+
}
42+
s +=r;
43+
}
44+
}
45+
if (pre != -1 &&sum -s -coins[node] -coins[pre] >0) {
46+
cnt++;
47+
}
48+
if (cnt >=2) {
49+
ret++;
50+
}
51+
returns +coins[node];
52+
}
53+
}
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
2603\. Collect Coins in a Tree
2+
3+
Hard
4+
5+
There exists an undirected and unrooted tree with`n` nodes indexed from`0` to`n - 1`. You are given an 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. You are also given an array`coins` of size`n` where`coins[i]` can be either`0` or`1`, where`1` indicates the presence of a coin in the vertex`i`.
6+
7+
Initially, you choose to start at any vertex in the tree. Then, you can perform the following operations any number of times:
8+
9+
* Collect all the coins that are at a distance of at most`2` from the current vertex, or
10+
* Move to any adjacent vertex in the tree.
11+
12+
Find_the minimum number of edges you need to go through to collect all the coins and go back to the initial vertex_.
13+
14+
Note that if you pass an edge several times, you need to count it into the answer several times.
15+
16+
**Example 1:**
17+
18+
![](https://assets.leetcode.com/uploads/2023/03/01/graph-2.png)
19+
20+
**Input:** coins =[1,0,0,0,0,1], edges =[[0,1],[1,2],[2,3],[3,4],[4,5]]
21+
22+
**Output:** 2
23+
24+
**Explanation:** Start at vertex 2, collect the coin at vertex 0, move to vertex 3, collect the coin at vertex 5 then move back to vertex 2.
25+
26+
**Example 2:**
27+
28+
![](https://assets.leetcode.com/uploads/2023/03/02/graph-4.png)
29+
30+
**Input:** coins =[0,0,0,1,1,0,0,1], edges =[[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
31+
32+
**Output:** 2
33+
34+
**Explanation:** Start at vertex 0, collect the coins at vertices 4 and 3, move to vertex 2, collect the coin at vertex 7, then move back to vertex 0.
35+
36+
**Constraints:**
37+
38+
*`n == coins.length`
39+
* <code>1 <= n <= 3 * 10<sup>4</sup></code>
40+
*`0 <= coins[i] <= 1`
41+
*`edges.length == n - 1`
42+
*`edges[i].length == 2`
43+
* <code>0 <= a<sub>i</sub>, b<sub>i</sub> < n</code>
44+
* <code>a<sub>i</sub> != b<sub>i</sub></code>
45+
*`edges` represents a valid tree.
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageg2601_2700.s2605_form_smallest_number_from_two_digit_arrays;
2+
3+
// #Easy #Array #Hash_Table #Enumeration #2023_08_29_Time_1_ms_(95.34%)_Space_40.4_MB_(61.44%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publicintminNumber(int[]nums1,int[]nums2) {
9+
Arrays.sort(nums1);
10+
Arrays.sort(nums2);
11+
int[]temp =newint[Math.max(nums1[nums1.length -1],nums2[nums2.length -1]) +1];
12+
intn1 =nums1[0];
13+
intn2 =nums2[0];
14+
intk =Math.min(n1 *10 +n2,n2 *10 +n1);
15+
for (intvalue :nums1) {
16+
temp[value]++;
17+
}
18+
for (inti :nums2) {
19+
if (temp[i] >0) {
20+
k =Math.min(k,i);
21+
returnk;
22+
}
23+
}
24+
returnk;
25+
}
26+
}
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
2605\. Form Smallest Number From Two Digit Arrays
2+
3+
Easy
4+
5+
Given two arrays of**unique** digits`nums1` and`nums2`, return_the**smallest** number that contains**at least** one digit from each array_.
6+
7+
**Example 1:**
8+
9+
**Input:** nums1 =[4,1,3], nums2 =[5,7]
10+
11+
**Output:** 15
12+
13+
**Explanation:** The number 15 contains the digit 1 from nums1 and the digit 5 from nums2. It can be proven that 15 is the smallest number we can have.
14+
15+
**Example 2:**
16+
17+
**Input:** nums1 =[3,5,2,6], nums2 =[3,1,7]
18+
19+
**Output:** 3
20+
21+
**Explanation:** The number 3 contains the digit 3 which exists in both arrays.
22+
23+
**Constraints:**
24+
25+
*`1 <= nums1.length, nums2.length <= 9`
26+
*`1 <= nums1[i], nums2[i] <= 9`
27+
* All digits in each array are**unique**.
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageg2601_2700.s2606_find_the_substring_with_maximum_cost;
2+
3+
// #Medium #Array #String #Hash_Table #Dynamic_Programming
4+
// #2023_08_29_Time_3_ms_(100.00%)_Space_43.6_MB_(100.00%)
5+
6+
publicclassSolution {
7+
publicintmaximumCostSubstring(Strings,Stringchars,int[]vals) {
8+
int[]alphabetCost =newint[26];
9+
for (charch ='a';ch <='z';ch++) {
10+
alphabetCost[ch -'a'] = ((ch -'a') +1);
11+
}
12+
for (inti =0;i <chars.length();i++) {
13+
charchr =chars.charAt(i);
14+
intchrCost =vals[i];
15+
alphabetCost[chr -'a'] =chrCost;
16+
}
17+
intcurrCost =0;
18+
intmaxCost =Integer.MIN_VALUE;
19+
for (charch :s.toCharArray()) {
20+
intcost =alphabetCost[ch -'a'];
21+
currCost =Math.max(currCost +cost,cost);
22+
maxCost =Math.max(maxCost,currCost);
23+
}
24+
returnMath.max(maxCost,"".length());
25+
}
26+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2606\. Find the Substring With Maximum Cost
2+
3+
Medium
4+
5+
You are given a string`s`, a string`chars` of**distinct** characters and an integer array`vals` of the same length as`chars`.
6+
7+
The**cost of the substring** is the sum of the values of each character in the substring. The cost of an empty string is considered`0`.
8+
9+
The**value of the character** is defined in the following way:
10+
11+
* If the character is not in the string`chars`, then its value is its corresponding position**(1-indexed)** in the alphabet.
12+
* For example, the value of`'a'` is`1`, the value of`'b'` is`2`, and so on. The value of`'z'` is`26`.
13+
* Otherwise, assuming`i` is the index where the character occurs in the string`chars`, then its value is`vals[i]`.
14+
15+
Return_the maximum cost among all substrings of the string_`s`.
16+
17+
**Example 1:**
18+
19+
**Input:** s = "adaa", chars = "d", vals =[-1000]
20+
21+
**Output:** 2
22+
23+
**Explanation:** The value of the characters "a" and "d" is 1 and -1000 respectively. The substring with the maximum cost is "aa" and its cost is 1 + 1 = 2. It can be proven that 2 is the maximum cost.
24+
25+
**Example 2:**
26+
27+
**Input:** s = "abc", chars = "abc", vals =[-1,-1,-1]
28+
29+
**Output:** 0
30+
31+
**Explanation:** The value of the characters "a", "b" and "c" is -1, -1, and -1 respectively. The substring with the maximum cost is the empty substring "" and its cost is 0. It can be proven that 0 is the maximum cost.
32+
33+
**Constraints:**
34+
35+
* <code>1 <= s.length <= 10<sup>5</sup></code>
36+
*`s` consist of lowercase English letters.
37+
*`1 <= chars.length <= 26`
38+
*`chars` consist of**distinct** lowercase English letters.
39+
*`vals.length == chars.length`
40+
*`-1000 <= vals[i] <= 1000`
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
packageg2601_2700.s2607_make_k_subarray_sums_equal;
2+
3+
// #Medium #Array #Math #Sorting #Number_Theory
4+
// #2023_08_29_Time_24_ms_(99.15%)_Space_59.2_MB_(55.08%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publiclongmakeSubKSumEqual(int[]arr,intk) {
10+
intn =arr.length;
11+
inth =gcd(n,k);
12+
intq =n /h;
13+
longans =0;
14+
for (inti =0;i <h;i++) {
15+
int[]x =newint[q];
16+
for (intj =0;j <q;j++) {
17+
x[j] =arr[(h *j) +i];
18+
}
19+
Arrays.sort(x);
20+
intv =q /2;
21+
intu =q %2 ==0 ? (x[v] +x[v -1]) /2 :x[v];
22+
for (into =0;o <q;o++) {
23+
ans +=Math.abs(u -x[o]);
24+
}
25+
}
26+
returnans;
27+
}
28+
29+
privateintgcd(inta,intb) {
30+
if (b ==0) {
31+
returna;
32+
}else {
33+
returngcd(b,Math.abs(a -b));
34+
}
35+
}
36+
}

0 commit comments

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