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

Commit6bfd733

Browse files
authored
Added tasks 3190-3197
1 parent4ea5777 commit6bfd733

File tree

24 files changed

+865
-0
lines changed

24 files changed

+865
-0
lines changed
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
packageg3101_3200.s3190_find_minimum_operations_to_make_all_elements_divisible_by_three;
2+
3+
// #Easy #Array #Math #2024_06_26_Time_0_ms_(100.00%)_Space_41.6_MB_(78.56%)
4+
5+
publicclassSolution {
6+
publicintminimumOperations(int[]nums) {
7+
intcount =0;
8+
for (inti =0;i <nums.length;i++) {
9+
if (nums[i] %3 !=0) {
10+
count++;
11+
}
12+
}
13+
returncount;
14+
}
15+
}
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
3190\. Find Minimum Operations to Make All Elements Divisible by Three
2+
3+
Easy
4+
5+
You are given an integer array`nums`. In one operation, you can add or subtract 1 from**any** element of`nums`.
6+
7+
Return the**minimum** number of operations to make all elements of`nums` divisible by 3.
8+
9+
**Example 1:**
10+
11+
**Input:** nums =[1,2,3,4]
12+
13+
**Output:** 3
14+
15+
**Explanation:**
16+
17+
All array elements can be made divisible by 3 using 3 operations:
18+
19+
* Subtract 1 from 1.
20+
* Add 1 to 2.
21+
* Subtract 1 from 4.
22+
23+
**Example 2:**
24+
25+
**Input:** nums =[3,6,9]
26+
27+
**Output:** 0
28+
29+
**Constraints:**
30+
31+
*`1 <= nums.length <= 50`
32+
*`1 <= nums[i] <= 50`
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
packageg3101_3200.s3191_minimum_operations_to_make_binary_array_elements_equal_to_one_i;
2+
3+
// #Medium #Array #Bit_Manipulation #Prefix_Sum #Sliding_Window #Queue
4+
// #2024_06_26_Time_6_ms_(99.99%)_Space_57.2_MB_(62.07%)
5+
6+
publicclassSolution {
7+
publicintminOperations(int[]nums) {
8+
intans =0;
9+
// Iterate through the array up to the third-last element
10+
for (inti =0;i <nums.length -2;i++) {
11+
// If the current element is 0, perform an operation
12+
if (nums[i] ==0) {
13+
ans++;
14+
// Flip the current element and the next two elements
15+
nums[i] =1;
16+
nums[i +1] =nums[i +1] ==0 ?1 :0;
17+
nums[i +2] =nums[i +2] ==0 ?1 :0;
18+
}
19+
}
20+
// Check the last two elements if they are 0, return -1 as they cannot be flipped
21+
for (inti =nums.length -2;i <nums.length;i++) {
22+
if (nums[i] ==0) {
23+
return -1;
24+
}
25+
}
26+
returnans;
27+
}
28+
}
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
3191\. Minimum Operations to Make Binary Array Elements Equal to One I
2+
3+
Medium
4+
5+
You are given a binary array`nums`.
6+
7+
You can do the following operation on the array**any** number of times (possibly zero):
8+
9+
* Choose**any** 3**consecutive** elements from the array and**flip****all** of them.
10+
11+
**Flipping** an element means changing its value from 0 to 1, and from 1 to 0.
12+
13+
Return the**minimum** number of operations required to make all elements in`nums` equal to 1. If it is impossible, return -1.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[0,1,1,1,0,0]
18+
19+
**Output:** 3
20+
21+
**Explanation:**
22+
We can do the following operations:
23+
24+
* Choose the elements at indices 0, 1 and 2. The resulting array is <code>nums =[<ins>**1**</ins>,<ins>**0**</ins>,<ins>**0**</ins>,1,0,0]</code>.
25+
* Choose the elements at indices 1, 2 and 3. The resulting array is <code>nums =[1,<ins>**1**</ins>,<ins>**1**</ins>,**<ins>0</ins>**,0,0]</code>.
26+
* Choose the elements at indices 3, 4 and 5. The resulting array is <code>nums =[1,1,1,**<ins>1</ins>**,<ins>**1**</ins>,<ins>**1**</ins>]</code>.
27+
28+
**Example 2:**
29+
30+
**Input:** nums =[0,1,1,1]
31+
32+
**Output:**\-1
33+
34+
**Explanation:**
35+
It is impossible to make all elements equal to 1.
36+
37+
**Constraints:**
38+
39+
* <code>3 <= nums.length <= 10<sup>5</sup></code>
40+
*`0 <= nums[i] <= 1`
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
packageg3101_3200.s3192_minimum_operations_to_make_binary_array_elements_equal_to_one_ii;
2+
3+
// #Medium #Array #Dynamic_Programming #Greedy #2024_06_26_Time_6_ms_(99.64%)_Space_62.9_MB_(17.52%)
4+
5+
publicclassSolution {
6+
publicintminOperations(int[]nums) {
7+
inta =0;
8+
intc =1;
9+
for (intx :nums) {
10+
if (x !=c) {
11+
a++;
12+
c ^=1;
13+
}
14+
}
15+
returna;
16+
}
17+
}
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
3192\. Minimum Operations to Make Binary Array Elements Equal to One II
2+
3+
Medium
4+
5+
You are given a binary array`nums`.
6+
7+
You can do the following operation on the array**any** number of times (possibly zero):
8+
9+
* Choose**any** index`i` from the array and**flip****all** the elements from index`i` to the end of the array.
10+
11+
**Flipping** an element means changing its value from 0 to 1, and from 1 to 0.
12+
13+
Return the**minimum** number of operations required to make all elements in`nums` equal to 1.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[0,1,1,0,1]
18+
19+
**Output:** 4
20+
21+
**Explanation:**
22+
We can do the following operations:
23+
24+
* Choose the index`i = 1`. The resulting array will be <code>nums =[0,<ins>**0**</ins>,<ins>**0**</ins>,<ins>**1**</ins>,<ins>**0**</ins>]</code>.
25+
* Choose the index`i = 0`. The resulting array will be <code>nums =[<ins>**1**</ins>,<ins>**1**</ins>,<ins>**1**</ins>,<ins>**0**</ins>,<ins>**1**</ins>]</code>.
26+
* Choose the index`i = 4`. The resulting array will be <code>nums =[1,1,1,0,<ins>**0**</ins>]</code>.
27+
* Choose the index`i = 3`. The resulting array will be <code>nums =[1,1,1,<ins>**1**</ins>,<ins>**1**</ins>]</code>.
28+
29+
**Example 2:**
30+
31+
**Input:** nums =[1,0,0,0]
32+
33+
**Output:** 1
34+
35+
**Explanation:**
36+
We can do the following operation:
37+
38+
* Choose the index`i = 1`. The resulting array will be <code>nums =[1,<ins>**1**</ins>,<ins>**1**</ins>,<ins>**1**</ins>]</code>.
39+
40+
**Constraints:**
41+
42+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
43+
*`0 <= nums[i] <= 1`
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
packageg3101_3200.s3193_count_the_number_of_inversions;
2+
3+
// #Hard #Array #Dynamic_Programming #2024_06_26_Time_11_ms_(96.54%)_Space_45.5_MB_(37.54%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
privatestaticfinalintMOD =1_000_000_007;
9+
10+
publicintnumberOfPermutations(intn,int[][]r) {
11+
Arrays.sort(r, (o1,o2) ->o1[0] -o2[0]);
12+
if (r[0][0] ==0 &&r[0][1] >0) {
13+
return0;
14+
}
15+
intri =r[0][0] ==0 ?1 :0;
16+
longa =1;
17+
longt;
18+
int[][]m =newint[n][401];
19+
m[0][0] =1;
20+
for (inti =1;i <m.length;i++) {
21+
m[i][0] =m[i -1][0];
22+
for (intj =1;j <=i;j++) {
23+
m[i][j] = (m[i][j] +m[i][j -1]) %MOD;
24+
m[i][j] = (m[i][j] +m[i -1][j]) %MOD;
25+
}
26+
for (intj =i +1;j <=r[ri][1];j++) {
27+
m[i][j] = (m[i][j] +m[i][j -1]) %MOD;
28+
m[i][j] = (m[i][j] +m[i -1][j]) %MOD;
29+
m[i][j] = (m[i][j] -m[i -1][j -i -1]);
30+
if (m[i][j] <0) {
31+
m[i][j] +=MOD;
32+
}
33+
}
34+
if (r[ri][0] ==i) {
35+
t =m[i][r[ri][1]];
36+
if (t ==0) {
37+
return0;
38+
}
39+
Arrays.fill(m[i],0);
40+
m[i][r[ri][1]] =1;
41+
a = (a *t) %MOD;
42+
ri++;
43+
}
44+
}
45+
return (int)a;
46+
}
47+
}
Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
3193\. Count the Number of Inversions
2+
3+
Hard
4+
5+
You are given an integer`n` and a 2D array`requirements`, where <code>requirements[i] =[end<sub>i</sub>, cnt<sub>i</sub>]</code> represents the end index and the**inversion** count of each requirement.
6+
7+
A pair of indices`(i, j)` from an integer array`nums` is called an**inversion** if:
8+
9+
*`i < j` and`nums[i] > nums[j]`
10+
11+
Return the number of permutations`perm` of`[0, 1, 2, ..., n - 1]` such that for**all**`requirements[i]`, <code>perm[0..end<sub>i</sub>]</code> has exactly <code>cnt<sub>i</sub></code> inversions.
12+
13+
Since the answer may be very large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
14+
15+
**Example 1:**
16+
17+
**Input:** n = 3, requirements =[[2,2],[0,0]]
18+
19+
**Output:** 2
20+
21+
**Explanation:**
22+
23+
The two permutations are:
24+
25+
*`[2, 0, 1]`
26+
* Prefix`[2, 0, 1]` has inversions`(0, 1)` and`(0, 2)`.
27+
* Prefix`[2]` has 0 inversions.
28+
*`[1, 2, 0]`
29+
* Prefix`[1, 2, 0]` has inversions`(0, 2)` and`(1, 2)`.
30+
* Prefix`[1]` has 0 inversions.
31+
32+
**Example 2:**
33+
34+
**Input:** n = 3, requirements =[[2,2],[1,1],[0,0]]
35+
36+
**Output:** 1
37+
38+
**Explanation:**
39+
40+
The only satisfying permutation is`[2, 0, 1]`:
41+
42+
* Prefix`[2, 0, 1]` has inversions`(0, 1)` and`(0, 2)`.
43+
* Prefix`[2, 0]` has an inversion`(0, 1)`.
44+
* Prefix`[2]` has 0 inversions.
45+
46+
**Example 3:**
47+
48+
**Input:** n = 2, requirements =[[0,0],[1,0]]
49+
50+
**Output:** 1
51+
52+
**Explanation:**
53+
54+
The only satisfying permutation is`[0, 1]`:
55+
56+
* Prefix`[0]` has 0 inversions.
57+
* Prefix`[0, 1]` has an inversion`(0, 1)`.
58+
59+
**Constraints:**
60+
61+
*`2 <= n <= 300`
62+
*`1 <= requirements.length <= n`
63+
* <code>requirements[i] =[end<sub>i</sub>, cnt<sub>i</sub>]</code>
64+
* <code>0 <= end<sub>i</sub> <= n - 1</code>
65+
* <code>0 <= cnt<sub>i</sub> <= 400</code>
66+
* The input is generated such that there is at least one`i` such that <code>end<sub>i</sub> == n - 1</code>.
67+
* The input is generated such that all <code>end<sub>i</sub></code> are unique.
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
packageg3101_3200.s3194_minimum_average_of_smallest_and_largest_elements;
2+
3+
// #Easy #Array #Sorting #Two_Pointers #2024_06_26_Time_2_ms_(98.88%)_Space_43.5_MB_(88.12%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publicdoubleminimumAverage(int[]nums) {
9+
Arrays.sort(nums);
10+
doublem =102.0;
11+
for (inti =0,l =nums.length;i <l /2;i++) {
12+
m =Math.min(m,nums[i] + (double)nums[l -i -1]);
13+
}
14+
returnm /2.0;
15+
}
16+
}
Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
3194\. Minimum Average of Smallest and Largest Elements
2+
3+
Easy
4+
5+
You have an array of floating point numbers`averages` which is initially empty. You are given an array`nums` of`n` integers where`n` is even.
6+
7+
You repeat the following procedure`n / 2` times:
8+
9+
* Remove the**smallest** element,`minElement`, and the**largest** element`maxElement`, from`nums`.
10+
* Add`(minElement + maxElement) / 2` to`averages`.
11+
12+
Return the**minimum** element in`averages`.
13+
14+
**Example 1:**
15+
16+
**Input:** nums =[7,8,3,4,15,13,4,1]
17+
18+
**Output:** 5.5
19+
20+
**Explanation:**
21+
22+
| Step| nums| averages|
23+
|------|------------------|------------|
24+
| 0|[7,8,3,4,15,13,4,1]|[]|
25+
| 1|[7,8,3,4,13,4]|[8]|
26+
| 2|[7,8,4,4]|[8, 8]|
27+
| 3|[7,4]|[8, 8, 6]|
28+
| 4|[]|[8, 8, 6, 5.5]|
29+
30+
The smallest element of averages, 5.5, is returned.
31+
32+
**Example 2:**
33+
34+
**Input:** nums =[1,9,8,3,10,5]
35+
36+
**Output:** 5.5
37+
38+
**Explanation:**
39+
40+
| Step| nums| averages|
41+
|------|----------------|------------|
42+
| 0|[1,9,8,3,10,5]|[]|
43+
| 1|[9,8,3,5]|[5.5]|
44+
| 2|[8,5]|[5.5, 6]|
45+
| 3|[]|[5.5, 6, 6.5]|
46+
47+
**Example 3:**
48+
49+
**Input:** nums =[1,2,3,7,8,9]
50+
51+
**Output:** 5.0
52+
53+
**Explanation:**
54+
55+
| Step| nums| averages|
56+
|------|----------------|------------|
57+
| 0|[1,2,3,7,8,9]|[]|
58+
| 1|[2,3,7,8]|[5]|
59+
| 2|[3,7]|[5, 5]|
60+
| 3|[]|[5, 5, 5]|
61+
62+
**Constraints:**
63+
64+
*`2 <= n == nums.length <= 50`
65+
*`n` is even.
66+
*`1 <= nums[i] <= 50`

0 commit comments

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