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

Commit08e8cec

Browse files
authored
Added tasks 2570-2574
1 parentdfad59e commit08e8cec

File tree

15 files changed

+552
-0
lines changed

15 files changed

+552
-0
lines changed
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
packageg2501_2600.s2570_merge_two_2d_arrays_by_summing_values;
2+
3+
// #Easy #Array #Hash_Table #Two_Pointers #2023_08_21_Time_0_ms_(100.00%)_Space_44.2_MB_(83.67%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publicint[][]mergeArrays(int[][]nums1,int[][]nums2) {
9+
intn1 =nums1.length;
10+
intn2 =nums2.length;
11+
int[][]res =newint[n1 +n2][2];
12+
inti =0;
13+
intj =0;
14+
intidx =0;
15+
while (i <n1 &&j <n2) {
16+
if (nums1[i][0] ==nums2[j][0]) {
17+
res[idx][0] =nums1[i][0];
18+
res[idx][1] =nums1[i][1] +nums2[j][1];
19+
i++;
20+
j++;
21+
}elseif (nums1[i][0] <nums2[j][0]) {
22+
res[idx][0] =nums1[i][0];
23+
res[idx][1] =nums1[i][1];
24+
i++;
25+
}else {
26+
res[idx][0] =nums2[j][0];
27+
res[idx][1] =nums2[j][1];
28+
j++;
29+
}
30+
idx++;
31+
}
32+
while (i <n1) {
33+
res[idx][0] =nums1[i][0];
34+
res[idx][1] =nums1[i][1];
35+
i++;
36+
idx++;
37+
}
38+
while (j <n2) {
39+
res[idx][0] =nums2[j][0];
40+
res[idx][1] =nums2[j][1];
41+
j++;
42+
idx++;
43+
}
44+
45+
returnArrays.copyOf(res,idx);
46+
}
47+
}
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
2570\. Merge Two 2D Arrays by Summing Values
2+
3+
Easy
4+
5+
You are given two**2D** integer arrays`nums1` and`nums2.`
6+
7+
* <code>nums1[i] =[id<sub>i</sub>, val<sub>i</sub>]</code> indicate that the number with the id <code>id<sub>i</sub></code> has a value equal to <code>val<sub>i</sub></code>.
8+
* <code>nums2[i] =[id<sub>i</sub>, val<sub>i</sub>]</code> indicate that the number with the id <code>id<sub>i</sub></code> has a value equal to <code>val<sub>i</sub></code>.
9+
10+
Each array contains**unique** ids and is sorted in**ascending** order by id.
11+
12+
Merge the two arrays into one array that is sorted in ascending order by id, respecting the following conditions:
13+
14+
* Only ids that appear in at least one of the two arrays should be included in the resulting array.
15+
* Each id should be included**only once** and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays then its value in that array is considered to be`0`.
16+
17+
Return_the resulting array_. The returned array must be sorted in ascending order by id.
18+
19+
**Example 1:**
20+
21+
**Input:** nums1 =[[1,2],[2,3],[4,5]], nums2 =[[1,4],[3,2],[4,1]]
22+
23+
**Output:**[[1,6],[2,3],[3,2],[4,6]]
24+
25+
**Explanation:** The resulting array contains the following:
26+
27+
- id = 1, the value of this id is 2 + 4 = 6.
28+
- id = 2, the value of this id is 3.
29+
- id = 3, the value of this id is 2.
30+
- id = 4, the value of this id is 5 + 1 = 6.
31+
32+
**Example 2:**
33+
34+
**Input:** nums1 =[[2,4],[3,6],[5,5]], nums2 =[[1,3],[4,3]]
35+
36+
**Output:**[[1,3],[2,4],[3,6],[4,3],[5,5]]
37+
38+
**Explanation:** There are no common ids, so we just include each id with its value in the resulting list.
39+
40+
**Constraints:**
41+
42+
*`1 <= nums1.length, nums2.length <= 200`
43+
*`nums1[i].length == nums2[j].length == 2`
44+
* <code>1 <= id<sub>i</sub>, val<sub>i</sub> <= 1000</code>
45+
* Both arrays contain unique ids.
46+
* Both arrays are in strictly ascending order by id.
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
packageg2501_2600.s2571_minimum_operations_to_reduce_an_integer_to_0;
2+
3+
// #Medium #Dynamic_Programming #Greedy #Bit_Manipulation
4+
// #2023_08_21_Time_0_ms_(100.00%)_Space_39.4_MB_(38.98%)
5+
6+
publicclassSolution {
7+
publicintminOperations(intn) {
8+
intcnt =1;
9+
while (n !=0) {
10+
intnum =1;
11+
while (num <=n) {
12+
if (num ==n) {
13+
returncnt;
14+
}
15+
num *=2;
16+
}
17+
n =Math.min(num -n,n -num /2);
18+
cnt++;
19+
}
20+
returncnt;
21+
}
22+
}
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
2571\. Minimum Operations to Reduce an Integer to 0
2+
3+
Medium
4+
5+
You are given a positive integer`n`, you can do the following operation**any** number of times:
6+
7+
* Add or subtract a**power** of`2` from`n`.
8+
9+
Return_the**minimum** number of operations to make_`n`_equal to_`0`.
10+
11+
A number`x` is power of`2` if <code>x == 2<sup>i</sup></code> where`i >= 0`_._
12+
13+
**Example 1:**
14+
15+
**Input:** n = 39
16+
17+
**Output:** 3
18+
19+
**Explanation:** We can do the following operations:
20+
21+
- Add 2<sup>0</sup> = 1 to n, so now n = 40.
22+
23+
- Subtract 2<sup>3</sup> = 8 from n, so now n = 32.
24+
25+
- Subtract 2<sup>5</sup> = 32 from n, so now n = 0. It can be shown that 3 is the minimum number of operations we need to make n equal to 0.
26+
27+
**Example 2:**
28+
29+
**Input:** n = 54
30+
31+
**Output:** 3
32+
33+
**Explanation:** We can do the following operations:
34+
35+
- Add 2<sup>1</sup> = 2 to n, so now n = 56.
36+
37+
- Add 2<sup>3</sup> = 8 to n, so now n = 64.
38+
39+
- Subtract 2<sup>6</sup> = 64 from n, so now n = 0. So the minimum number of operations is 3.
40+
41+
**Constraints:**
42+
43+
* <code>1 <= n <= 10<sup>5</sup></code>
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
packageg2501_2600.s2572_count_the_number_of_square_free_subsets;
2+
3+
// #Medium #Array #Dynamic_Programming #Math #Bit_Manipulation #Bitmask
4+
// #2023_08_21_Time_1_ms_(100.00%)_Space_41.5_MB_(79.12%)
5+
6+
publicclassSolution {
7+
privatefinalint[]count =newint[31];
8+
privatefinalint[]masks =newint[31];
9+
privatefinallong[][]cache =newlong[31][1 <<6];
10+
privatestaticfinallongMOD =1_000_000_007;
11+
12+
publicintsquareFreeSubsets(int[]nums) {
13+
int[]p = {1,2,3,5,7,11,13};
14+
for (inti =0;i <7; ++i) {
15+
intmask =i ==0 ?0 :1 << (i -1);
16+
for (intj =i +1;j <7; ++j) {
17+
if (p[i] *p[j] >30) {
18+
break;
19+
}
20+
masks[p[i] *p[j]] =mask | (1 << (j -1));
21+
}
22+
}
23+
masks[30] =7;
24+
for (intk :nums) {
25+
if (k %4 !=0 &&k %9 !=0 &&k %25 !=0) {
26+
++count[k];
27+
}
28+
}
29+
count[1] =powof2(count[1]);
30+
return (int) ((dfs(30,0) +MOD -1) %MOD);
31+
}
32+
33+
privatelongdfs(intk,intmask) {
34+
if (k ==1) {
35+
returncount[1];
36+
}
37+
if (cache[k][mask] !=0) {
38+
returncache[k][mask];
39+
}
40+
longres =dfs(k -1,mask);
41+
if (count[k] >0 && (masks[k] &mask) ==0) {
42+
res = (res + (count[k] *dfs(k -1,mask |masks[k])) %MOD) %MOD;
43+
}
44+
cache[k][mask] =res;
45+
returncache[k][mask];
46+
}
47+
48+
privateintpowof2(intk) {
49+
longpow2 =2;
50+
longres =1;
51+
while (k >0) {
52+
if (k %2 ==1) {
53+
res = (res *pow2) %MOD;
54+
}
55+
pow2 = (pow2 *pow2) %MOD;
56+
k >>=1;
57+
}
58+
return (int)res;
59+
}
60+
}
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
2572\. Count the Number of Square-Free Subsets
2+
3+
Medium
4+
5+
You are given a positive integer**0-indexed** array`nums`.
6+
7+
A subset of the array`nums` is**square-free** if the product of its elements is a**square-free integer**.
8+
9+
A**square-free integer** is an integer that is divisible by no square number other than`1`.
10+
11+
Return_the number of square-free non-empty subsets of the array_**nums**. Since the answer may be too large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
12+
13+
A**non-empty****subset** of`nums` is an array that can be obtained by deleting some (possibly none but not all) elements from`nums`. Two subsets are different if and only if the chosen indices to delete are different.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[3,4,4,5]
18+
19+
**Output:** 3
20+
21+
**Explanation:** There are 3 square-free subsets in this example:
22+
23+
- The subset consisting of the 0<sup>th</sup> element[3]. The product of its elements is 3, which is a square-free integer.
24+
25+
- The subset consisting of the 3<sup>rd</sup> element[5]. The product of its elements is 5, which is a square-free integer.
26+
27+
- The subset consisting of 0<sup>th</sup> and 3<sup>rd</sup> elements[3,5]. The product of its elements is 15, which is a square-free integer.
28+
29+
It can be proven that there are no more than 3 square-free subsets in the given array.
30+
31+
**Example 2:**
32+
33+
**Input:** nums =[1]
34+
35+
**Output:** 1
36+
37+
**Explanation:** There is 1 square-free subset in this example:
38+
39+
- The subset consisting of the 0<sup>th</sup> element[1]. The product of its elements is 1, which is a square-free integer.
40+
41+
It can be proven that there is no more than 1 square-free subset in the given array.
42+
43+
**Constraints:**
44+
45+
*`1 <= nums.length <= 1000`
46+
*`1 <= nums[i] <= 30`
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
packageg2501_2600.s2573_find_the_string_with_lcp;
2+
3+
// #Hard #String #Dynamic_Programming #Greedy #Union_Find
4+
// #2023_08_21_Time_5_ms_(100.00%)_Space_142.3_MB_(10.34%)
5+
6+
publicclassSolution {
7+
publicStringfindTheString(int[][]lcp) {
8+
intn =lcp.length;
9+
char[]arr =newchar[n];
10+
arr[0] ='a';
11+
chartest;
12+
booleanfound;
13+
for (inti =1;i <n; ++i) {
14+
test ='a';
15+
found =false;
16+
for (intj =0;j <i; ++j) {
17+
test = (char)Math.max(test,arr[j]);
18+
if (lcp[i][j] !=0) {
19+
found =true;
20+
arr[i] =arr[j];
21+
break;
22+
}
23+
}
24+
if (found) {
25+
continue;
26+
}
27+
++test;
28+
arr[i] =test;
29+
if (test >'z') {
30+
return"";
31+
}
32+
}
33+
int[][]dp =newint[n +1][n +1];
34+
intval;
35+
for (inti =n -1;i >=0; --i) {
36+
for (intj =n -1;j >=0; --j) {
37+
if (arr[i] !=arr[j]) {
38+
val =0;
39+
}else {
40+
val =1 +dp[i +1][j +1];
41+
}
42+
dp[i][j] =val;
43+
}
44+
}
45+
for (inti =n -1;i >=0; --i) {
46+
for (intj =n -1;j >=0; --j) {
47+
if (dp[i][j] !=lcp[i][j]) {
48+
return"";
49+
}
50+
}
51+
}
52+
returnString.valueOf(arr);
53+
}
54+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2573\. Find the String with LCP
2+
3+
Hard
4+
5+
We define the`lcp` matrix of any**0-indexed** string`word` of`n` lowercase English letters as an`n x n` grid such that:
6+
7+
*`lcp[i][j]` is equal to the length of the**longest common prefix** between the substrings`word[i,n-1]` and`word[j,n-1]`.
8+
9+
Given an`n x n` matrix`lcp`, return the alphabetically smallest string`word` that corresponds to`lcp`. If there is no such string, return an empty string.
10+
11+
A string`a` is lexicographically smaller than a string`b` (of the same length) if in the first position where`a` and`b` differ, string`a` has a letter that appears earlier in the alphabet than the corresponding letter in`b`. For example,`"aabd"` is lexicographically smaller than`"aaca"` because the first position they differ is at the third letter, and`'b'` comes before`'c'`.
12+
13+
**Example 1:**
14+
15+
**Input:** lcp =[[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]
16+
17+
**Output:** "abab"
18+
19+
**Explanation:** lcp corresponds to any 4 letter string with two alternating letters. The lexicographically smallest of them is "abab".
20+
21+
**Example 2:**
22+
23+
**Input:** lcp =[[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]
24+
25+
**Output:** "aaaa"
26+
27+
**Explanation:** lcp corresponds to any 4 letter string with a single distinct letter. The lexicographically smallest of them is "aaaa".
28+
29+
**Example 3:**
30+
31+
**Input:** lcp =[[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]
32+
33+
**Output:** ""
34+
35+
**Explanation:** lcp[3][3] cannot be equal to 3 since word[3,...,3] consists of only a single letter; Thus, no answer exists.
36+
37+
**Constraints:**
38+
39+
*`1 <= n == ``lcp.length ==``lcp[i].length``<= 1000`
40+
*`0 <= lcp[i][j] <= n`
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
packageg2501_2600.s2574_left_and_right_sum_differences;
2+
3+
// #Easy #Array #Prefix_Sum #2023_08_21_Time_2_ms_(74.57%)_Space_43.7_MB_(76.84%)
4+
5+
publicclassSolution {
6+
publicint[]leftRightDifference(int[]nums) {
7+
intls =0;
8+
intrs =0;
9+
for (inti :nums) {
10+
rs +=i;
11+
}
12+
for (inti =0;i <nums.length; ++i) {
13+
ls +=nums[i];
14+
rs -=nums[i];
15+
nums[i] =Math.abs(rs - (ls -nums[i]));
16+
}
17+
returnnums;
18+
}
19+
}

0 commit comments

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