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

Commit7bf3e70

Browse files
authored
Added tasks 2546-2551
1 parentfa824d9 commit7bf3e70

File tree

15 files changed

+412
-0
lines changed

15 files changed

+412
-0
lines changed
Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
packageg2501_2600.s2546_apply_bitwise_operations_to_make_strings_equal;
2+
3+
// #Medium #String #Bit_Manipulation #2023_08_15_Time_0_ms_(100.00%)_Space_44.3_MB_(87.14%)
4+
5+
classSolution {
6+
publicbooleanmakeStringsEqual(Strings,Stringtarget) {
7+
returns.contains("1") ==target.contains("1");
8+
}
9+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
2546\. Apply Bitwise Operations to Make Strings Equal
2+
3+
Medium
4+
5+
You are given two**0-indexed binary** strings`s` and`target` of the same length`n`. You can do the following operation on`s`**any** number of times:
6+
7+
* Choose two**different** indices`i` and`j` where`0 <= i, j < n`.
8+
* Simultaneously, replace`s[i]` with (`s[i]`**OR**`s[j]`) and`s[j]` with (`s[i]`**XOR**`s[j]`).
9+
10+
For example, if`s = "0110"`, you can choose`i = 0` and`j = 2`, then simultaneously replace`s[0]` with (`s[0]`**OR**`s[2]` =`0`**OR**`1` =`1`), and`s[2]` with (`s[0]`**XOR**`s[2]` =`0`**XOR**`1` =`1`), so we will have`s = "1110"`.
11+
12+
Return`true`_if you can make the string_`s`_equal to_`target`_, or_`false`_otherwise_.
13+
14+
**Example 1:**
15+
16+
**Input:** s = "1010", target = "0110"
17+
18+
**Output:** true
19+
20+
**Explanation:** We can do the following operations:
21+
22+
- Choose i = 2 and j = 0. We have now s = "**<ins>0</ins>**0**<ins>1</ins>**0".
23+
24+
- Choose i = 2 and j = 1. We have now s = "0**<ins>11</ins>**0". Since we can make s equal to target, we return true.
25+
26+
**Example 2:**
27+
28+
**Input:** s = "11", target = "00"
29+
30+
**Output:** false
31+
32+
**Explanation:** It is not possible to make s equal to target with any number of operations.
33+
34+
**Constraints:**
35+
36+
*`n == s.length == target.length`
37+
* <code>2 <= n <= 10<sup>5</sup></code>
38+
*`s` and`target` consist of only the digits`0` and`1`.
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageg2501_2600.s2547_minimum_cost_to_split_an_array;
2+
3+
// #Hard #Array #Hash_Table #Dynamic_Programming #Counting
4+
// #2023_08_15_Time_32_ms_(98.70%)_Space_44.3_MB_(66.23%)
5+
6+
classSolution {
7+
publicintminCost(int[]nums,intk) {
8+
int[]dp =newint[nums.length +1];
9+
for (intstartPos =nums.length -1;startPos >=0;startPos--) {
10+
dp[startPos] =Integer.MAX_VALUE;
11+
int[]freq =newint[nums.length +1];
12+
intnRepeated =0;
13+
for (intpos =startPos;pos <nums.length;pos++) {
14+
intcurNum =nums[pos];
15+
if (freq[curNum] ==1) {
16+
nRepeated +=2;
17+
}elseif (freq[curNum] >0) {
18+
nRepeated++;
19+
}
20+
freq[curNum]++;
21+
dp[startPos] =Math.min(dp[startPos],k +nRepeated +dp[pos +1]);
22+
}
23+
}
24+
returndp[0];
25+
}
26+
}
Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
2547\. Minimum Cost to Split an Array
2+
3+
Hard
4+
5+
You are given an integer array`nums` and an integer`k`.
6+
7+
Split the array into some number of non-empty subarrays. The**cost** of a split is the sum of the**importance value** of each subarray in the split.
8+
9+
Let`trimmed(subarray)` be the version of the subarray where all numbers which appear only once are removed.
10+
11+
* For example,`trimmed([3,1,2,4,3,4]) = [3,4,3,4].`
12+
13+
The**importance value** of a subarray is`k + trimmed(subarray).length`.
14+
15+
* For example, if a subarray is`[1,2,3,3,3,4,4]`, then trimmed(`[1,2,3,3,3,4,4]) = [3,3,3,4,4].`The importance value of this subarray will be`k + 5`.
16+
17+
Return_the minimum possible cost of a split of_`nums`.
18+
19+
A**subarray** is a contiguous**non-empty** sequence of elements within an array.
20+
21+
**Example 1:**
22+
23+
**Input:** nums =[1,2,1,2,1,3,3], k = 2
24+
25+
**Output:** 8
26+
27+
**Explanation:** We split nums to have two subarrays:[1,2],[1,2,1,3,3]. '
28+
29+
The importance value of[1,2] is 2 + (0) = 2.
30+
31+
The importance value of[1,2,1,3,3] is 2 + (2 + 2) = 6.
32+
33+
The cost of the split is 2 + 6 = 8. It can be shown that this is the minimum possible cost among all the possible splits.
34+
35+
**Example 2:**
36+
37+
**Input:** nums =[1,2,1,2,1], k = 2
38+
39+
**Output:** 6
40+
41+
**Explanation:** We split nums to have two subarrays:[1,2],[1,2,1].
42+
43+
The importance value of[1,2] is 2 + (0) = 2.
44+
45+
The importance value of[1,2,1] is 2 + (2) = 4.
46+
47+
The cost of the split is 2 + 4 = 6. It can be shown that this is the minimum possible cost among all the possible splits.
48+
49+
**Example 3:**
50+
51+
**Input:** nums =[1,2,1,2,1], k = 5
52+
53+
**Output:** 10
54+
55+
**Explanation:** We split nums to have one subarray:[1,2,1,2,1].
56+
57+
The importance value of[1,2,1,2,1] is 5 + (3 + 2) = 10.
58+
59+
The cost of the split is 10. It can be shown that this is the minimum possible cost among all the possible splits.
60+
61+
**Constraints:**
62+
63+
*`1 <= nums.length <= 1000`
64+
*`0 <= nums[i] < nums.length`
65+
* <code>1 <= k <= 10<sup>9</sup></code>
Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
packageg2501_2600.s2549_count_distinct_numbers_on_board;
2+
3+
// #Easy #Array #Hash_Table #Math #Simulation #2023_08_15_Time_0_ms_(100.00%)_Space_39.2_MB_(75.23%)
4+
5+
classSolution {
6+
publicintdistinctIntegers(intn) {
7+
if (n ==1) {
8+
return1;
9+
}
10+
returnn -1;
11+
}
12+
}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
2549\. Count Distinct Numbers on Board
2+
3+
Easy
4+
5+
You are given a positive integer`n`, that is initially placed on a board. Every day, for <code>10<sup>9</sup></code> days, you perform the following procedure:
6+
7+
* For each number`x` present on the board, find all numbers`1 <= i <= n` such that`x % i == 1`.
8+
* Then, place those numbers on the board.
9+
10+
Return_the number of**distinct** integers present on the board after_ <code>10<sup>9</sup></code>_days have elapsed_.
11+
12+
**Note:**
13+
14+
* Once a number is placed on the board, it will remain on it until the end.
15+
*`%` stands for the modulo operation. For example,`14 % 3` is`2`.
16+
17+
**Example 1:**
18+
19+
**Input:** n = 5
20+
21+
**Output:** 4
22+
23+
**Explanation:** Initially, 5 is present on the board.
24+
25+
The next day, 2 and 4 will be added since 5 % 2 == 1 and 5 % 4 == 1.
26+
27+
After that day, 3 will be added to the board because 4 % 3 == 1.
28+
29+
At the end of a billion days, the distinct numbers on the board will be 2, 3, 4, and 5.
30+
31+
**Example 2:**
32+
33+
**Input:** n = 3
34+
35+
**Output:** 2
36+
37+
**Explanation:** Since 3 % 2 == 1, 2 will be added to the board. After a billion days, the only two distinct numbers on the board are 2 and 3.
38+
39+
**Constraints:**
40+
41+
*`1 <= n <= 100`
Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
packageg2501_2600.s2550_count_collisions_of_monkeys_on_a_polygon;
2+
3+
// #Medium #Math #Recursion #2023_08_15_Time_0_ms_(100.00%)_Space_39.3_MB_(62.81%)
4+
5+
classSolution {
6+
publicintmonkeyMove(intn) {
7+
return (int) ((((modPow2(n -2) -1) <<2) +2) %1000000007);
8+
}
9+
10+
privatelongmodPow2(intn) {
11+
if (n ==0) {
12+
return1;
13+
}
14+
longb =modPow2(n >>1);
15+
return ((b *b) << (n &1)) %1000000007;
16+
}
17+
}
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
2550\. Count Collisions of Monkeys on a Polygon
2+
3+
Medium
4+
5+
There is a regular convex polygon with`n` vertices. The vertices are labeled from`0` to`n - 1` in a clockwise direction, and each vertex has**exactly one monkey**. The following figure shows a convex polygon of`6` vertices.
6+
7+
![](https://assets.leetcode.com/uploads/2023/01/22/hexagon.jpg)
8+
9+
Each monkey moves simultaneously to a neighboring vertex. A neighboring vertex for a vertex`i` can be:
10+
11+
* the vertex`(i + 1) % n` in the clockwise direction, or
12+
* the vertex`(i - 1 + n) % n` in the counter-clockwise direction.
13+
14+
A**collision** happens if at least two monkeys reside on the same vertex after the movement or intersect on an edge.
15+
16+
Return_the number of ways the monkeys can move so that at least**one collision**__happens_. Since the answer may be very large, return it modulo <code>10<sup>9</sup> + 7</code>.
17+
18+
**Note** that each monkey can only move once.
19+
20+
**Example 1:**
21+
22+
**Input:** n = 3
23+
24+
**Output:** 6
25+
26+
**Explanation:** There are 8 total possible movements.
27+
28+
Two ways such that they collide at some point are:
29+
- Monkey 1 moves in a clockwise direction; monkey 2 moves in an anticlockwise direction; monkey 3 moves in a clockwise direction. Monkeys 1 and 2 collide.
30+
- Monkey 1 moves in an anticlockwise direction; monkey 2 moves in an anticlockwise direction; monkey 3 moves in a clockwise direction. Monkeys 1 and 3 collide. It can be shown 6 total movements result in a collision.
31+
32+
**Example 2:**
33+
34+
**Input:** n = 4
35+
36+
**Output:** 14
37+
38+
**Explanation:** It can be shown that there are 14 ways for the monkeys to collide.
39+
40+
**Constraints:**
41+
42+
* <code>3 <= n <= 10<sup>9</sup></code>
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2501_2600.s2551_put_marbles_in_bags;
2+
3+
// #Hard #Array #Sorting #Greedy #Heap_Priority_Queue
4+
// #2023_08_15_Time_33_ms_(99.82%)_Space_55.1_MB_(97.58%)
5+
6+
importjava.util.Arrays;
7+
8+
classSolution {
9+
publiclongputMarbles(int[]weights,intk) {
10+
longminAns =weights[0] + (long)weights[weights.length -1];
11+
longmaxAns =weights[0] + (long)weights[weights.length -1];
12+
long[]arr =newlong[weights.length -1];
13+
for (inti =1;i <weights.length;i++) {
14+
arr[i -1] =weights[i] + (long)weights[i -1];
15+
}
16+
Arrays.sort(arr);
17+
for (inti =0;i <k -1;i++) {
18+
minAns =minAns +arr[i];
19+
}
20+
for (inti =arr.length -1;i >arr.length -k;i--) {
21+
maxAns =maxAns +arr[i];
22+
}
23+
returnmaxAns -minAns;
24+
}
25+
}
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
2551\. Put Marbles in Bags
2+
3+
Hard
4+
5+
You have`k` bags. You are given a**0-indexed** integer array`weights` where`weights[i]` is the weight of the <code>i<sup>th</sup></code> marble. You are also given the integer`k.`
6+
7+
Divide the marbles into the`k` bags according to the following rules:
8+
9+
* No bag is empty.
10+
* If the <code>i<sup>th</sup></code> marble and <code>j<sup>th</sup></code> marble are in a bag, then all marbles with an index between the <code>i<sup>th</sup></code> and <code>j<sup>th</sup></code> indices should also be in that same bag.
11+
* If a bag consists of all the marbles with an index from`i` to`j` inclusively, then the cost of the bag is`weights[i] + weights[j]`.
12+
13+
The**score** after distributing the marbles is the sum of the costs of all the`k` bags.
14+
15+
Return_the**difference** between the**maximum** and**minimum** scores among marble distributions_.
16+
17+
**Example 1:**
18+
19+
**Input:** weights =[1,3,5,1], k = 2
20+
21+
**Output:** 4
22+
23+
**Explanation:**
24+
25+
The distribution[1],[3,5,1] results in the minimal score of (1+1) + (3+1) = 6.
26+
27+
The distribution[1,3],[5,1], results in the maximal score of (1+3) + (5+1) = 10.
28+
29+
Thus, we return their difference 10 - 6 = 4.
30+
31+
**Example 2:**
32+
33+
**Input:** weights =[1, 3], k = 2
34+
35+
**Output:** 0
36+
37+
**Explanation:** The only distribution possible is[1],[3]. Since both the maximal and minimal score are the same, we return 0.
38+
39+
**Constraints:**
40+
41+
* <code>1 <= k <= weights.length <= 10<sup>5</sup></code>
42+
* <code>1 <= weights[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+
packageg2501_2600.s2546_apply_bitwise_operations_to_make_strings_equal;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidmakeStringsEqual() {
11+
assertThat(newSolution().makeStringsEqual("1010","0110"),equalTo(true));
12+
}
13+
14+
@Test
15+
voidmakeStringsEqual2() {
16+
assertThat(newSolution().makeStringsEqual("11","00"),equalTo(false));
17+
}
18+
}
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
packageg2501_2600.s2547_minimum_cost_to_split_an_array;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidminCost() {
11+
assertThat(newSolution().minCost(newint[] {1,2,1,2,1,3,3},2),equalTo(8));
12+
}
13+
14+
@Test
15+
voidminCost2() {
16+
assertThat(newSolution().minCost(newint[] {1,2,1,2,1},2),equalTo(6));
17+
}
18+
19+
@Test
20+
voidminCost3() {
21+
assertThat(newSolution().minCost(newint[] {1,2,1,2,1},5),equalTo(10));
22+
}
23+
}
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg2501_2600.s2549_count_distinct_numbers_on_board;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voiddistinctIntegers() {
11+
assertThat(newSolution().distinctIntegers(5),equalTo(4));
12+
}
13+
14+
@Test
15+
voiddistinctIntegers2() {
16+
assertThat(newSolution().distinctIntegers(3),equalTo(2));
17+
}
18+
}

0 commit comments

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