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

Commit3cbf8af

Browse files
authored
Added tasks 2718-2723
1 parent72a7ad4 commit3cbf8af

File tree

15 files changed

+538
-0
lines changed

15 files changed

+538
-0
lines changed
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
packageg2701_2800.s2718_sum_of_matrix_after_queries;
2+
3+
// #Medium #Array #Hash_Table #2023_09_18_Time_3_ms_(100.00%)_Space_61.2_MB_(84.49%)
4+
5+
publicclassSolution {
6+
publiclongmatrixSumQueries(intn,int[][]queries) {
7+
boolean[]queriedRow =newboolean[n];
8+
boolean[]queriedCol =newboolean[n];
9+
longsum =0;
10+
intremainingRows =n;
11+
intremainingCols =n;
12+
for (inti =queries.length -1;i >=0;i--) {
13+
inttype =queries[i][0];
14+
intindex =queries[i][1];
15+
intvalue =queries[i][2];
16+
if ((type ==0 && !queriedRow[index]) || (type ==1 && !queriedCol[index])) {
17+
sum += (long)value * (type ==0 ?remainingCols :remainingRows);
18+
if (type ==0) {
19+
remainingRows--;
20+
queriedRow[index] =true;
21+
}else {
22+
remainingCols--;
23+
queriedCol[index] =true;
24+
}
25+
}
26+
}
27+
returnsum;
28+
}
29+
}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
2718\. Sum of Matrix After Queries
2+
3+
Medium
4+
5+
You are given an integer`n` and a**0-indexed****2D array**`queries` where <code>queries[i] =[type<sub>i</sub>, index<sub>i</sub>, val<sub>i</sub>]</code>.
6+
7+
Initially, there is a**0-indexed**`n x n` matrix filled with`0`'s. For each query, you must apply one of the following changes:
8+
9+
* if <code>type<sub>i</sub> == 0</code>, set the values in the row with <code>index<sub>i</sub></code> to <code>val<sub>i</sub></code>, overwriting any previous values.
10+
* if <code>type<sub>i</sub> == 1</code>, set the values in the column with <code>index<sub>i</sub></code> to <code>val<sub>i</sub></code>, overwriting any previous values.
11+
12+
Return_the sum of integers in the matrix after all queries are applied_.
13+
14+
**Example 1:**
15+
16+
![](https://assets.leetcode.com/uploads/2023/05/11/exm1.png)
17+
18+
**Input:** n = 3, queries =[[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
19+
20+
**Output:** 23
21+
22+
**Explanation:** The image above describes the matrix after each query. The sum of the matrix after all queries are applied is 23.
23+
24+
**Example 2:**
25+
26+
![](https://assets.leetcode.com/uploads/2023/05/11/exm2.png)
27+
28+
**Input:** n = 3, queries =[[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2,1]]
29+
30+
**Output:** 17
31+
32+
**Explanation:** The image above describes the matrix after each query. The sum of the matrix after all queries are applied is 17.
33+
34+
**Constraints:**
35+
36+
* <code>1 <= n <= 10<sup>4</sup></code>
37+
* <code>1 <= queries.length <= 5 * 10<sup>4</sup></code>
38+
*`queries[i].length == 3`
39+
* <code>0 <= type<sub>i</sub> <= 1</code>
40+
* <code>0 <= index<sub>i</sub> < n</code>
41+
* <code>0 <= val<sub>i</sub> <= 10<sup>5</sup></code>
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
packageg2701_2800.s2719_count_of_integers;
2+
3+
// #Hard #String #Dynamic_Programming #Math #2023_09_18_Time_15_ms_(97.70%)_Space_44.2_MB_(82.18%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
privateint[][][][]dp;
9+
privatestaticfinalintMOD = (int) (1e9 +7);
10+
11+
privateintcountStrings(
12+
inti,booleantight1,booleantight2,intsum,Stringnum1,Stringnum2) {
13+
if (sum <0) {
14+
return0;
15+
}
16+
if (i ==num2.length()) {
17+
return1;
18+
}
19+
if (dp[i][tight1 ?1 :0][tight2 ?1 :0][sum] != -1) {
20+
returndp[i][tight1 ?1 :0][tight2 ?1 :0][sum];
21+
}
22+
intlo =tight1 ? (num1.charAt(i) -'0') :0;
23+
inthi =tight2 ? (num2.charAt(i) -'0') :9;
24+
intcount =0;
25+
for (intidx =lo;idx <=hi;idx++) {
26+
count =
27+
(count %MOD
28+
+countStrings(
29+
i +1,
30+
tight1 && (idx ==lo),
31+
tight2 && (idx ==hi),
32+
sum -idx,
33+
num1,
34+
num2)
35+
%MOD)
36+
%MOD;
37+
}
38+
39+
dp[i][tight1 ?1 :0][tight2 ?1 :0][sum] =count;
40+
returncount;
41+
}
42+
43+
publicintcount(Stringnum1,Stringnum2,intminSum,intmaxSum) {
44+
intmaxLength =num2.length();
45+
intminLength =num1.length();
46+
intleadingZeroes =maxLength -minLength;
47+
Stringnum1extended ="0".repeat(leadingZeroes) +num1;
48+
dp =newint[maxLength][2][2][401];
49+
for (inti =0;i <maxLength;i++) {
50+
for (intj =0;j <2;j++) {
51+
for (intk =0;k <2;k++) {
52+
Arrays.fill(dp[i][j][k], -1);
53+
}
54+
}
55+
}
56+
inttotal =countStrings(0,true,true,maxSum,num1extended,num2);
57+
intunnecessary =countStrings(0,true,true,minSum -1,num1extended,num2);
58+
intans = (total -unnecessary) %MOD;
59+
if (ans <0) {
60+
ans +=MOD;
61+
}
62+
returnans;
63+
}
64+
}
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
2719\. Count of Integers
2+
3+
Hard
4+
5+
You are given two numeric strings`num1` and`num2` and two integers`max_sum` and`min_sum`. We denote an integer`x` to be_good_ if:
6+
7+
*`num1 <= x <= num2`
8+
*`min_sum <= digit_sum(x) <= max_sum`.
9+
10+
Return_the number of good integers_. Since the answer may be large, return it modulo <code>10<sup>9</sup> + 7</code>.
11+
12+
Note that`digit_sum(x)` denotes the sum of the digits of`x`.
13+
14+
**Example 1:**
15+
16+
**Input:** num1 = "1", num2 = "12",`min_sum` = 1, max\_sum = 8
17+
18+
**Output:** 11
19+
20+
**Explanation:** There are 11 integers whose sum of digits lies between 1 and 8 are 1,2,3,4,5,6,7,8,10,11, and 12. Thus, we return 11.
21+
22+
**Example 2:**
23+
24+
**Input:** num1 = "1", num2 = "5",`min_sum` = 1, max\_sum = 5
25+
26+
**Output:** 5
27+
28+
**Explanation:** The 5 integers whose sum of digits lies between 1 and 5 are 1,2,3,4, and 5. Thus, we return 5.
29+
30+
**Constraints:**
31+
32+
* <code>1 <= num1 <= num2 <= 10<sup>22</sup></code>
33+
*`1 <= min_sum <= max_sum <= 400`
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
2721\. Execute Asynchronous Functions in Parallel
2+
3+
Medium
4+
5+
Given an array of asynchronous functions`functions`, return a new promise`promise`. Each function in the array accepts no arguments and returns a promise.
6+
7+
`promise` resolves:
8+
9+
* When all the promises returned from`functions` were resolved successfully. The resolved value of`promise` should be an array of all the resolved values of promises in the same order as they were in the`functions`.
10+
11+
`promise` rejects:
12+
13+
* When any of the promises returned from`functions` were rejected.`promise` should also reject with the reason of the first rejection.
14+
15+
Please solve it without using the built-in`Promise.all` function.
16+
17+
**Example 1:**
18+
19+
**Input:**
20+
21+
functions = [
22+
() => new Promise(resolve => setTimeout(() => resolve(5), 200))
23+
]
24+
25+
**Output:** {"t": 200, "resolved":[5]}
26+
27+
**Explanation:** promiseAll(functions).then(console.log); //[5] The single function was resolved at 200ms with a value of 5.
28+
29+
**Example 2:**
30+
31+
**Input:**
32+
33+
functions =[
34+
() => new Promise(resolve => setTimeout(() => resolve(1), 200)),
35+
() => new Promise((resolve, reject) => setTimeout(() => reject("Error"), 100))
36+
]
37+
38+
**Output:** {"t": 100, "rejected": "Error"}
39+
40+
**Explanation:** Since one of the promises rejected, the returned promise also rejected with the same error at the same time.
41+
42+
**Example 3:**
43+
44+
**Input:**
45+
46+
functions =[
47+
() => new Promise(resolve => setTimeout(() => resolve(4), 50)),
48+
() => new Promise(resolve => setTimeout(() => resolve(10), 150)),
49+
() => new Promise(resolve => setTimeout(() => resolve(16), 100))
50+
]
51+
52+
**Output:** {"t": 150, "resolved":[4, 10, 16]}
53+
54+
**Explanation:** All the promises resolved with a value. The returned promise resolved when the last promise resolved.
55+
56+
**Constraints:**
57+
58+
*`functions is an array of functions that returns promises`
59+
*`1 <= functions.length <= 10`
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
// #Medium #2023_09_18_Time_67_ms_(84.73%)_Space_43.6_MB_(15.83%)
2+
3+
asyncfunctionpromiseAll<T>(functions:(()=>Promise<T>)[]):Promise<T[]>{
4+
constresolved=[]
5+
letcounter=0
6+
7+
returnnewPromise((resolve,reject)=>{
8+
for(leti=0;i<functions.length;i++){
9+
functions[i]()
10+
.then((res)=>{
11+
// must specify index of array
12+
resolved[i]=res
13+
counter++
14+
if(counter===functions.length){
15+
resolve(resolved)
16+
}
17+
})
18+
.catch((err)=>{
19+
reject(err)
20+
})
21+
}
22+
})
23+
}
24+
25+
/*
26+
* const promise = promiseAll([() => new Promise(res => res(42))])
27+
* promise.then(console.log); // [42]
28+
*/
29+
30+
export{promiseAll}
31+
Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
2722\. Join Two Arrays by ID
2+
3+
Medium
4+
5+
Given two arrays`arr1` and`arr2`, return a new array`joinedArray`. All the objects in each of the two inputs arrays will contain an`id` field that has an integer value.`joinedArray` is an array formed by merging`arr1` and`arr2` based on their`id` key. The length of`joinedArray` should be the length of unique values of`id`. The returned array should be sorted in**ascending** order based on the`id` key.
6+
7+
If a given`id` exists in one array but not the other, the single object with that`id` should be included in the result array without modification.
8+
9+
If two objects share an`id`, their properties should be merged into a single object:
10+
11+
* If a key only exists in one object, that single key-value pair should be included in the object.
12+
* If a key is included in both objects, the value in the object from`arr2` should override the value from`arr1`.
13+
14+
**Example 1:**
15+
16+
**Input:**
17+
18+
arr1 = [
19+
{"id": 1, "x": 1},
20+
{"id": 2, "x": 9}
21+
],
22+
arr2 = [
23+
{"id": 3, "x": 5}
24+
]
25+
26+
**Output:**
27+
28+
[
29+
{"id": 1, "x": 1},
30+
{"id": 2, "x": 9},
31+
{"id": 3, "x": 5}
32+
]
33+
34+
**Explanation:** There are no duplicate ids so arr1 is simply concatenated with arr2.
35+
36+
**Example 2:**
37+
38+
**Input:**
39+
40+
arr1 = [
41+
{"id": 1, "x": 2, "y": 3},
42+
{"id": 2, "x": 3, "y": 6}
43+
],
44+
arr2 = [
45+
{"id": 2, "x": 10, "y": 20},
46+
{"id": 3, "x": 0, "y": 0}
47+
]
48+
49+
**Output:**
50+
51+
[
52+
{"id": 1, "x": 2, "y": 3},
53+
{"id": 2, "x": 10, "y": 20},
54+
{"id": 3, "x": 0, "y": 0}
55+
]
56+
57+
**Explanation:** The two objects with id=1 and id=3 are included in the result array without modifiction. The two objects with id=2 are merged together. The keys from arr2 override the values in arr1.
58+
59+
**Example 3:**
60+
61+
**Input:**
62+
63+
arr1 = [
64+
{"id": 1, "b": {"b": 94},"v": [4, 3], "y": 48}
65+
]
66+
arr2 = [
67+
{"id": 1, "b": {"c": 84}, "v": [1, 3]}
68+
]
69+
70+
**Output:**
71+
72+
[
73+
{"id": 1, "b": {"c": 84}, "v": [1, 3], "y": 48}
74+
]
75+
76+
**Explanation:** The two objects with id=1 are merged together. For the keys "b" and "v" the values from arr2 are used. Since the key "y" only exists in arr1, that value is taken form arr1.
77+
78+
**Constraints:**
79+
80+
*`arr1 and arr2 are valid JSON arrays`
81+
*`Each object in arr1 and arr2 has a unique integer id key`
82+
* <code>2 <= JSON.stringify(arr1).length <= 10<sup>6</sup></code>
83+
* <code>2 <= JSON.stringify(arr2).length <= 10<sup>6</sup></code>
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
// #Medium #2023_09_18_Time_246_ms_(96.81%)_Space_106_MB_(70.44%)
2+
3+
functionjoin(arr1:any[],arr2:any[]):any[]{
4+
constresult:any={}
5+
for(letobjofarr1){
6+
result[obj.id]=obj
7+
}
8+
for(letobjofarr2){
9+
if(result[obj.id]){
10+
for(letkeyinobj){
11+
result[obj.id][key]=obj[key]
12+
}
13+
}else{
14+
result[obj.id]=obj
15+
}
16+
}
17+
returnObject.values(result)
18+
}
19+
20+
export{join}
21+

0 commit comments

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