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

Commitee9366d

Browse files
authored
Added tasks 3184-3187
1 parent79f5664 commitee9366d

File tree

12 files changed

+428
-0
lines changed

12 files changed

+428
-0
lines changed
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg3101_3200.s3184_count_pairs_that_form_a_complete_day_i;
2+
3+
// #Easy #Array #Hash_Table #Counting #2024_06_21_Time_1_ms_(98.20%)_Space_42_MB_(83.72%)
4+
5+
publicclassSolution {
6+
publicintcountCompleteDayPairs(int[]hours) {
7+
int[]modular =newint[26];
8+
intans =0;
9+
for (inthour :hours) {
10+
intmod =hour %24;
11+
ans +=modular[24 -mod];
12+
if (mod ==0) {
13+
modular[24]++;
14+
}else {
15+
modular[mod]++;
16+
}
17+
}
18+
returnans;
19+
}
20+
}
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
3184\. Count Pairs That Form a Complete Day I
2+
3+
Easy
4+
5+
Given an integer array`hours` representing times in**hours**, return an integer denoting the number of pairs`i`,`j` where`i < j` and`hours[i] + hours[j]` forms a**complete day**.
6+
7+
A**complete day** is defined as a time duration that is an**exact****multiple** of 24 hours.
8+
9+
For example, 1 day is 24 hours, 2 days is 48 hours, 3 days is 72 hours, and so on.
10+
11+
**Example 1:**
12+
13+
**Input:** hours =[12,12,30,24,24]
14+
15+
**Output:** 2
16+
17+
**Explanation:**
18+
19+
The pairs of indices that form a complete day are`(0, 1)` and`(3, 4)`.
20+
21+
**Example 2:**
22+
23+
**Input:** hours =[72,48,24,3]
24+
25+
**Output:** 3
26+
27+
**Explanation:**
28+
29+
The pairs of indices that form a complete day are`(0, 1)`,`(0, 2)`, and`(1, 2)`.
30+
31+
**Constraints:**
32+
33+
*`1 <= hours.length <= 100`
34+
* <code>1 <= hours[i] <= 10<sup>9</sup></code>
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg3101_3200.s3185_count_pairs_that_form_a_complete_day_ii;
2+
3+
// #Medium #Array #Hash_Table #Counting #2024_06_21_Time_3_ms_(97.60%)_Space_97.1_MB_(14.69%)
4+
5+
publicclassSolution {
6+
publiclongcountCompleteDayPairs(int[]hours) {
7+
long[]hour =newlong[24];
8+
for (intj :hours) {
9+
hour[j %24]++;
10+
}
11+
longcounter =hour[0] * (hour[0] -1) /2;
12+
counter +=hour[12] * (hour[12] -1) /2;
13+
for (inti =1;i <12;i++) {
14+
counter +=hour[i] *hour[24 -i];
15+
}
16+
returncounter;
17+
}
18+
}
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
3185\. Count Pairs That Form a Complete Day II
2+
3+
Medium
4+
5+
Given an integer array`hours` representing times in**hours**, return an integer denoting the number of pairs`i`,`j` where`i < j` and`hours[i] + hours[j]` forms a**complete day**.
6+
7+
A**complete day** is defined as a time duration that is an**exact****multiple** of 24 hours.
8+
9+
For example, 1 day is 24 hours, 2 days is 48 hours, 3 days is 72 hours, and so on.
10+
11+
**Example 1:**
12+
13+
**Input:** hours =[12,12,30,24,24]
14+
15+
**Output:** 2
16+
17+
**Explanation:** The pairs of indices that form a complete day are`(0, 1)` and`(3, 4)`.
18+
19+
**Example 2:**
20+
21+
**Input:** hours =[72,48,24,3]
22+
23+
**Output:** 3
24+
25+
**Explanation:** The pairs of indices that form a complete day are`(0, 1)`,`(0, 2)`, and`(1, 2)`.
26+
27+
**Constraints:**
28+
29+
* <code>1 <= hours.length <= 5 * 10<sup>5</sup></code>
30+
* <code>1 <= hours[i] <= 10<sup>9</sup></code>
Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
packageg3101_3200.s3186_maximum_total_damage_with_spell_casting;
2+
3+
// #Medium #Array #Hash_Table #Dynamic_Programming #Sorting #Binary_Search #Two_Pointers #Counting
4+
// #2024_06_21_Time_51_ms_(99.29%)_Space_60.8_MB_(78.34%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publiclongmaximumTotalDamage(int[]power) {
10+
intmaxPower =0;
11+
for (intp :power) {
12+
if (p >maxPower) {
13+
maxPower =p;
14+
}
15+
}
16+
return (maxPower <=1_000_000) ?smallPower(power,maxPower) :bigPower(power);
17+
}
18+
19+
privatelongsmallPower(int[]power,intmaxPower) {
20+
int[]counts =newint[maxPower +6];
21+
for (intp :power) {
22+
counts[p]++;
23+
}
24+
long[]dp =newlong[maxPower +6];
25+
dp[1] =counts[1];
26+
dp[2] =Math.max(counts[2] *2L,dp[1]);
27+
for (inti =3;i <=maxPower;i++) {
28+
dp[i] =Math.max(counts[i] *i +dp[i -3],Math.max(dp[i -1],dp[i -2]));
29+
}
30+
returndp[maxPower];
31+
}
32+
33+
privatelongbigPower(int[]power) {
34+
Arrays.sort(power);
35+
intn =power.length;
36+
long[]prevs =newlong[4];
37+
intcurPower =power[0];
38+
intcount =1;
39+
longresult =0;
40+
for (inti =1;i <=n;i++) {
41+
intp = (i ==n) ?1_000_000_009 :power[i];
42+
if (p ==curPower) {
43+
count++;
44+
}else {
45+
longcurVal =
46+
Math.max((long)curPower *count +prevs[3],Math.max(prevs[1],prevs[2]));
47+
intdiff =Math.min(p -curPower,prevs.length -1);
48+
longnextCurVal = (diff ==1) ?0 :Math.max(prevs[3],Math.max(curVal,prevs[2]));
49+
// Shift the values in prevs[].
50+
intk =prevs.length -1;
51+
if (diff <prevs.length -1) {
52+
while (k >diff) {
53+
prevs[k] =prevs[k-- -diff];
54+
}
55+
prevs[k--] =curVal;
56+
}
57+
while (k >0) {
58+
prevs[k--] =nextCurVal;
59+
}
60+
curPower =p;
61+
count =1;
62+
}
63+
}
64+
for (longv :prevs) {
65+
if (v >result) {
66+
result =v;
67+
}
68+
}
69+
returnresult;
70+
}
71+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
3186\. Maximum Total Damage With Spell Casting
2+
3+
Medium
4+
5+
A magician has various spells.
6+
7+
You are given an array`power`, where each element represents the damage of a spell. Multiple spells can have the same damage value.
8+
9+
It is a known fact that if a magician decides to cast a spell with a damage of`power[i]`, they**cannot** cast any spell with a damage of`power[i] - 2`,`power[i] - 1`,`power[i] + 1`, or`power[i] + 2`.
10+
11+
Each spell can be cast**only once**.
12+
13+
Return the**maximum** possible_total damage_ that a magician can cast.
14+
15+
**Example 1:**
16+
17+
**Input:** power =[1,1,3,4]
18+
19+
**Output:** 6
20+
21+
**Explanation:**
22+
23+
The maximum possible damage of 6 is produced by casting spells 0, 1, 3 with damage 1, 1, 4.
24+
25+
**Example 2:**
26+
27+
**Input:** power =[7,1,6,6]
28+
29+
**Output:** 13
30+
31+
**Explanation:**
32+
33+
The maximum possible damage of 13 is produced by casting spells 1, 2, 3 with damage 1, 6, 6.
34+
35+
**Constraints:**
36+
37+
* <code>1 <= power.length <= 10<sup>5</sup></code>
38+
* <code>1 <= power[i] <= 10<sup>9</sup></code>
Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
packageg3101_3200.s3187_peaks_in_array;
2+
3+
// #Hard #Array #Segment_Tree #Binary_Indexed_Tree
4+
// #2024_06_21_Time_18_ms_(100.00%)_Space_137.7_MB_(31.34%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
publicList<Integer>countOfPeaks(int[]nums,int[][]queries) {
11+
boolean[]peaks =newboolean[nums.length];
12+
int[]binaryIndexedTree =newint[Integer.highestOneBit(peaks.length) *2 +1];
13+
for (inti =1;i <peaks.length -1; ++i) {
14+
if (nums[i] >Math.max(nums[i -1],nums[i +1])) {
15+
peaks[i] =true;
16+
update(binaryIndexedTree,i +1,1);
17+
}
18+
}
19+
20+
List<Integer>result =newArrayList<>();
21+
for (int[]query :queries) {
22+
if (query[0] ==1) {
23+
intleftIndex =query[1];
24+
intrightIndex =query[2];
25+
result.add(computeRangeSum(binaryIndexedTree,leftIndex +2,rightIndex));
26+
}else {
27+
intindex =query[1];
28+
intvalue =query[2];
29+
nums[index] =value;
30+
for (inti = -1;i <=1; ++i) {
31+
intaffected =index +i;
32+
if (affected >=1 &&affected <=nums.length -2) {
33+
booleanpeak =
34+
nums[affected] >Math.max(nums[affected -1],nums[affected +1]);
35+
if (peak !=peaks[affected]) {
36+
if (peak) {
37+
update(binaryIndexedTree,affected +1,1);
38+
}else {
39+
update(binaryIndexedTree,affected +1, -1);
40+
}
41+
peaks[affected] =peak;
42+
}
43+
}
44+
}
45+
}
46+
}
47+
returnresult;
48+
}
49+
50+
privateintcomputeRangeSum(int[]binaryIndexedTree,intbeginIndex,intendIndex) {
51+
return (beginIndex <=endIndex)
52+
? (query(binaryIndexedTree,endIndex) -query(binaryIndexedTree,beginIndex -1))
53+
:0;
54+
}
55+
56+
privateintquery(int[]binaryIndexedTree,intindex) {
57+
intresult =0;
58+
while (index !=0) {
59+
result +=binaryIndexedTree[index];
60+
index -=index & -index;
61+
}
62+
63+
returnresult;
64+
}
65+
66+
privatevoidupdate(int[]binaryIndexedTree,intindex,intdelta) {
67+
while (index <binaryIndexedTree.length) {
68+
binaryIndexedTree[index] +=delta;
69+
index +=index & -index;
70+
}
71+
}
72+
}
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
3187\. Peaks in Array
2+
3+
Hard
4+
5+
A**peak** in an array`arr` is an element that is**greater** than its previous and next element in`arr`.
6+
7+
You are given an integer array`nums` and a 2D integer array`queries`.
8+
9+
You have to process queries of two types:
10+
11+
* <code>queries[i] =[1, l<sub>i</sub>, r<sub>i</sub>]</code>, determine the count of**peak** elements in the subarray <code>nums[l<sub>i</sub>..r<sub>i</sub>]</code>.
12+
* <code>queries[i] =[2, index<sub>i</sub>, val<sub>i</sub>]</code>, change <code>nums[index<sub>i</sub>]</code> to <code>val<sub>i</sub></code>.
13+
14+
Return an array`answer` containing the results of the queries of the first type in order.
15+
16+
**Notes:**
17+
18+
* The**first** and the**last** element of an array or a subarray**cannot** be a peak.
19+
20+
**Example 1:**
21+
22+
**Input:** nums =[3,1,4,2,5], queries =[[2,3,4],[1,0,4]]
23+
24+
**Output:**[0]
25+
26+
**Explanation:**
27+
28+
First query: We change`nums[3]` to 4 and`nums` becomes`[3,1,4,4,5]`.
29+
30+
Second query: The number of peaks in the`[3,1,4,4,5]` is 0.
31+
32+
**Example 2:**
33+
34+
**Input:** nums =[4,1,4,2,1,5], queries =[[2,2,4],[1,0,2],[1,0,4]]
35+
36+
**Output:**[0,1]
37+
38+
**Explanation:**
39+
40+
First query:`nums[2]` should become 4, but it is already set to 4.
41+
42+
Second query: The number of peaks in the`[4,1,4]` is 0.
43+
44+
Third query: The second 4 is a peak in the`[4,1,4,2,1]`.
45+
46+
**Constraints:**
47+
48+
* <code>3 <= nums.length <= 10<sup>5</sup></code>
49+
* <code>1 <= nums[i] <= 10<sup>5</sup></code>
50+
* <code>1 <= queries.length <= 10<sup>5</sup></code>
51+
*`queries[i][0] == 1` or`queries[i][0] == 2`
52+
* For all`i` that:
53+
*`queries[i][0] == 1`:`0 <= queries[i][1] <= queries[i][2] <= nums.length - 1`
54+
*`queries[i][0] == 2`:`0 <= queries[i][1] <= nums.length - 1`, <code>1 <= queries[i][2] <= 10<sup>5</sup></code>
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
packageg3101_3200.s3184_count_pairs_that_form_a_complete_day_i;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidcountCompleteDayPairs() {
11+
assertThat(
12+
newSolution().countCompleteDayPairs(newint[] {12,12,30,24,24}),equalTo(2));
13+
}
14+
15+
@Test
16+
voidcountCompleteDayPairs2() {
17+
assertThat(newSolution().countCompleteDayPairs(newint[] {72,48,24,3}),equalTo(3));
18+
}
19+
}
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
packageg3101_3200.s3185_count_pairs_that_form_a_complete_day_ii;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidcountCompleteDayPairs() {
11+
assertThat(
12+
newSolution().countCompleteDayPairs(newint[] {12,12,30,24,24}),equalTo(2L));
13+
}
14+
15+
@Test
16+
voidcountCompleteDayPairs2() {
17+
assertThat(newSolution().countCompleteDayPairs(newint[] {72,48,24,3}),equalTo(3L));
18+
}
19+
}

0 commit comments

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