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

Commita827c81

Browse files
authored
Added tasks 2762-2767
1 parent5b67071 commita827c81

File tree

15 files changed

+498
-0
lines changed

15 files changed

+498
-0
lines changed
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
packageg2701_2800.s2762_continuous_subarrays;
2+
3+
// #Medium #Array #Heap_Priority_Queue #Sliding_Window #Ordered_Set #Queue #Monotonic_Queue
4+
// #2023_09_24_Time_3_ms_(98.28%)_Space_56.8_MB_(61.59%)
5+
6+
publicclassSolution {
7+
publiclongcontinuousSubarrays(int[]nums) {
8+
longres =1;
9+
intlower =nums[0] -2;
10+
inthigher =nums[0] +2;
11+
intj =0;
12+
for (inti =1;i <nums.length;i++) {
13+
if (nums[i] >=lower &&nums[i] <=higher) {
14+
lower =Math.max(lower,nums[i] -2);
15+
higher =Math.min(higher,nums[i] +2);
16+
}else {
17+
j =i -1;
18+
lower =nums[i] -2;
19+
higher =nums[i] +2;
20+
while (j >=0 &&nums[j] >=lower &&nums[j] <=higher) {
21+
lower =Math.max(lower,nums[j] -2);
22+
higher =Math.min(higher,nums[j] +2);
23+
j--;
24+
}
25+
j++;
26+
}
27+
res +=i -j +1;
28+
}
29+
returnres;
30+
}
31+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
2762\. Continuous Subarrays
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums`. A subarray of`nums` is called**continuous** if:
6+
7+
* Let`i`,`i + 1`, ...,`j` be the indices in the subarray. Then, for each pair of indices <code>i <= i<sub>1</sub>, i<sub>2</sub> <= j</code>, <code>0 <= |nums[i<sub>1</sub>] - nums[i<sub>2</sub>]| <= 2</code>.
8+
9+
Return_the total number of**continuous** subarrays._
10+
11+
A subarray is a contiguous**non-empty** sequence of elements within an array.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[5,4,2,4]
16+
17+
**Output:** 8
18+
19+
**Explanation:**
20+
21+
Continuous subarray of size 1:[5],[4],[2],[4].
22+
23+
Continuous subarray of size 2:[5,4],[4,2],[2,4].
24+
25+
Continuous subarray of size 3:[4,2,4].
26+
27+
Thereare no subarrys of size 4.
28+
29+
Total continuous subarrays = 4 + 3 + 1 = 8.
30+
31+
It can be shown that there are no more continuous subarrays.
32+
33+
**Example 2:**
34+
35+
**Input:** nums =[1,2,3]
36+
37+
**Output:** 6
38+
39+
**Explanation:**
40+
41+
Continuous subarray of size 1:[1],[2],[3].
42+
43+
Continuous subarray of size 2:[1,2],[2,3].
44+
45+
Continuous subarray of size 3:[1,2,3].
46+
47+
Total continuous subarrays = 3 + 2 + 1 = 6.
48+
49+
**Constraints:**
50+
51+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
52+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2701_2800.s2763_sum_of_imbalance_numbers_of_all_subarrays;
2+
3+
// #Hard #Array #Hash_Table #Ordered_Set #2023_09_24_Time_1_ms_(100.00%)_Space_43.2_MB_(93.41%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publicintsumImbalanceNumbers(int[]nums) {
9+
intn =nums.length;
10+
ints =0;
11+
int[]left =newint[n];
12+
int[]seen =newint[n +2];
13+
Arrays.fill(seen, -1);
14+
for (inti =0;i <n;i++) {
15+
left[i] =Math.max(seen[nums[i]],seen[nums[i] +1]);
16+
seen[nums[i]] =i;
17+
}
18+
Arrays.fill(seen,n);
19+
for (inti =n -1;i >=0;i--) {
20+
s += (seen[nums[i] +1] -i) * (i -left[i]);
21+
seen[nums[i]] =i;
22+
}
23+
returns - (n +1) *n /2;
24+
}
25+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
2763\. Sum of Imbalance Numbers of All Subarrays
2+
3+
Hard
4+
5+
The**imbalance number** of a**0-indexed** integer array`arr` of length`n` is defined as the number of indices in`sarr = sorted(arr)` such that:
6+
7+
*`0 <= i < n - 1`, and
8+
*`sarr[i+1] - sarr[i] > 1`
9+
10+
Here,`sorted(arr)` is the function that returns the sorted version of`arr`.
11+
12+
Given a**0-indexed** integer array`nums`, return_the**sum of imbalance numbers** of all its**subarrays**_.
13+
14+
A**subarray** is a contiguous**non-empty** sequence of elements within an array.
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[2,3,1,4]
19+
20+
**Output:** 3
21+
22+
**Explanation:** There are 3 subarrays with non-zero imbalance numbers:
23+
- Subarray[3, 1] with an imbalance number of 1.
24+
- Subarray[3, 1, 4] with an imbalance number of 1.
25+
- Subarray[1, 4] with an imbalance number of 1.
26+
27+
The imbalance number of all other subarrays is 0. Hence, the sum of imbalance numbers of all the subarrays of nums is 3.
28+
29+
**Example 2:**
30+
31+
**Input:** nums =[1,3,3,3,5]
32+
33+
**Output:** 8
34+
35+
**Explanation:** There are 7 subarrays with non-zero imbalance numbers:
36+
- Subarray[1, 3] with an imbalance number of 1.
37+
- Subarray[1, 3, 3] with an imbalance number of 1.
38+
- Subarray[1, 3, 3, 3] with an imbalance number of 1.
39+
- Subarray[1, 3, 3, 3, 5] with an imbalance number of 2.
40+
- Subarray[3, 3, 3, 5] with an imbalance number of 1.
41+
- Subarray[3, 3, 5] with an imbalance number of 1.
42+
- Subarray[3, 5] with an imbalance number of 1.
43+
44+
The imbalance number of all other subarrays is 0. Hence, the sum of imbalance numbers of all the subarrays of nums is 8.
45+
46+
**Constraints:**
47+
48+
*`1 <= nums.length <= 1000`
49+
*`1 <= nums[i] <= nums.length`
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
packageg2701_2800.s2765_longest_alternating_subarray;
2+
3+
// #Easy #Array #Enumeration #2023_09_24_Time_2_ms_(82.60%)_Space_43_MB_(69.16%)
4+
5+
@SuppressWarnings("java:S135")
6+
publicclassSolution {
7+
publicintalternatingSubarray(int[]nums) {
8+
intresult = -1;
9+
intprevious =0;
10+
intsum =1;
11+
for (inti =1;i <nums.length;i++) {
12+
intdiff =nums[i] -nums[i -1];
13+
if (Math.abs(diff) !=1) {
14+
sum =1;
15+
continue;
16+
}
17+
if (diff ==previous) {
18+
sum =2;
19+
}
20+
if (diff !=previous) {
21+
if (diff != (sum %2 ==0 ? -1 :1)) {
22+
continue;
23+
}
24+
sum++;
25+
previous =diff;
26+
}
27+
result =Math.max(result,sum);
28+
}
29+
returnresult;
30+
}
31+
}
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
2765\. Longest Alternating Subarray
2+
3+
Easy
4+
5+
You are given a**0-indexed** integer array`nums`. A subarray`s` of length`m` is called**alternating** if:
6+
7+
*`m` is greater than`1`.
8+
* <code>s<sub>1</sub> = s<sub>0</sub> + 1</code>.
9+
* The**0-indexed** subarray`s` looks like <code>[s<sub>0</sub>, s<sub>1</sub>, s<sub>0</sub>, s<sub>1</sub>,...,s<sub>(m-1) % 2</sub>]</code>. In other words, <code>s<sub>1</sub> - s<sub>0</sub> = 1</code>, <code>s<sub>2</sub> - s<sub>1</sub> = -1</code>, <code>s<sub>3</sub> - s<sub>2</sub> = 1</code>, <code>s<sub>4</sub> - s<sub>3</sub> = -1</code>, and so on up to <code>s[m - 1] - s[m - 2] = (-1)<sup>m</sup></code>.
10+
11+
Return_the maximum length of all**alternating** subarrays present in_`nums`_or_`-1`_if no such subarray exists__._
12+
13+
A subarray is a contiguous**non-empty** sequence of elements within an array.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[2,3,4,3,4]
18+
19+
**Output:** 4
20+
21+
**Explanation:** The alternating subarrays are[3,4],[3,4,3], and[3,4,3,4]. The longest of these is[3,4,3,4], which is of length 4.
22+
23+
**Example 2:**
24+
25+
**Input:** nums =[4,5,6]
26+
27+
**Output:** 2
28+
29+
**Explanation:**[4,5] and[5,6] are the only two alternating subarrays. They are both of length 2.
30+
31+
**Constraints:**
32+
33+
*`2 <= nums.length <= 100`
34+
* <code>1 <= nums[i] <= 10<sup>4</sup></code>
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packageg2701_2800.s2766_relocate_marbles;
2+
3+
// #Medium #Array #Hash_Table #Sorting #Simulation
4+
// #2023_09_24_Time_47_ms_(91.67%)_Space_60.2_MB_(36.33%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.HashSet;
8+
importjava.util.List;
9+
importjava.util.Set;
10+
11+
publicclassSolution {
12+
publicList<Integer>relocateMarbles(int[]nums,int[]moveFrom,int[]moveTo) {
13+
Set<Integer>set =newHashSet<>();
14+
for (intnum :nums) {
15+
set.add(num);
16+
}
17+
for (inti =0;i <moveTo.length;i++) {
18+
if (set.contains(moveFrom[i])) {
19+
set.remove(moveFrom[i]);
20+
set.add(moveTo[i]);
21+
}
22+
}
23+
List<Integer>result =newArrayList<>(set);
24+
result.sort(null);
25+
returnresult;
26+
}
27+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
2766\. Relocate Marbles
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums` representing the initial positions of some marbles. You are also given two**0-indexed** integer arrays`moveFrom` and`moveTo` of**equal** length.
6+
7+
Throughout`moveFrom.length` steps, you will change the positions of the marbles. On the <code>i<sup>th</sup></code> step, you will move**all** marbles at position`moveFrom[i]` to position`moveTo[i]`.
8+
9+
After completing all the steps, return_the sorted list of**occupied** positions_.
10+
11+
**Notes:**
12+
13+
* We call a position**occupied** if there is at least one marble in that position.
14+
* There may be multiple marbles in a single position.
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[1,6,7,8], moveFrom =[1,7,2], moveTo =[2,9,5]
19+
20+
**Output:**[5,6,8,9]
21+
22+
**Explanation:** Initially, the marbles are at positions 1,6,7,8.
23+
24+
At the i = 0th step, we move the marbles at position 1 to position 2. Then, positions 2,6,7,8 are occupied.
25+
26+
At the i = 1st step, we move the marbles at position 7 to position 9. Then, positions 2,6,8,9 are occupied.
27+
28+
At the i = 2nd step, we move the marbles at position 2 to position 5. Then, positions 5,6,8,9 are occupied.
29+
30+
At the end, the final positions containing at least one marbles are[5,6,8,9].
31+
32+
**Example 2:**
33+
34+
**Input:** nums =[1,1,3,3], moveFrom =[1,3], moveTo =[2,2]
35+
36+
**Output:**[2]
37+
38+
**Explanation:** Initially, the marbles are at positions[1,1,3,3].
39+
40+
At the i = 0th step, we move all the marbles at position 1 to position 2. Then, the marbles are at positions[2,2,3,3].
41+
42+
At the i = 1st step, we move all the marbles at position 3 to position 2. Then, the marbles are at positions[2,2,2,2].
43+
44+
Since 2 is the only occupied position, we return[2].
45+
46+
**Constraints:**
47+
48+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
49+
* <code>1 <= moveFrom.length <= 10<sup>5</sup></code>
50+
*`moveFrom.length == moveTo.length`
51+
* <code>1 <= nums[i], moveFrom[i], moveTo[i] <= 10<sup>9</sup></code>
52+
* The test cases are generated such that there is at least a marble in`moveFrom[i]` at the moment we want to apply the <code>i<sup>th</sup></code> move.
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
packageg2701_2800.s2767_partition_string_into_minimum_beautiful_substrings;
2+
3+
// #Medium #String #Hash_Table #Dynamic_Programming #Backtracking
4+
// #2023_09_24_Time_1_ms_(100.00%)_Space_40.8_MB_(89.80%)
5+
6+
publicclassSolution {
7+
privatebooleanispower(intnum) {
8+
intpow =1;
9+
while (pow <num) {
10+
pow =pow *5;
11+
}
12+
returnpow ==num;
13+
}
14+
15+
privateintbacktrack(intind,Strings) {
16+
if (ind >=s.length()) {
17+
return0;
18+
}
19+
if (s.charAt(ind) =='0') {
20+
return999;
21+
}
22+
inttemp =999;
23+
intrunCount =0;
24+
for (inti =ind;i <s.length();i++) {
25+
runCount =runCount *2;
26+
if (s.charAt(i) =='1') {
27+
runCount++;
28+
}
29+
if (this.ispower(runCount)) {
30+
temp =Math.min(temp,1 +this.backtrack(i +1,s));
31+
}
32+
}
33+
returntemp;
34+
}
35+
36+
publicintminimumBeautifulSubstrings(Strings) {
37+
intres =this.backtrack(0,s);
38+
if (res <999) {
39+
returnres;
40+
}
41+
return -1;
42+
}
43+
}

0 commit comments

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