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

Commit6c6932c

Browse files
authored
Added tasks 2730-2734
1 parentc31be13 commit6c6932c

File tree

15 files changed

+498
-0
lines changed

15 files changed

+498
-0
lines changed
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg2701_2800.s2730_find_the_longest_semi_repetitive_substring;
2+
3+
// #Medium #String #Sliding_Window #2023_09_22_Time_5_ms_(100.00%)_Space_44.5_MB_(13.68%)
4+
5+
publicclassSolution {
6+
publicintlongestSemiRepetitiveSubstring(Strings) {
7+
inti =0;
8+
intcur =0;
9+
intn =s.length();
10+
for (intj =1;j <n;j++) {
11+
cur += (s.charAt(j) ==s.charAt(j -1)) ?1 :0;
12+
if (cur >1) {
13+
cur -= (s.charAt(++i) ==s.charAt(i -1)) ?1 :0;
14+
}
15+
}
16+
returnn -i;
17+
}
18+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2730\. Find the Longest Semi-Repetitive Substring
2+
3+
Medium
4+
5+
You are given a**0-indexed** string`s` that consists of digits from`0` to`9`.
6+
7+
A string`t` is called a**semi-repetitive** if there is at most one consecutive pair of the same digits inside`t`. For example,`0010`,`002020`,`0123`,`2002`, and`54944` are semi-repetitive while`00101022`, and`1101234883` are not.
8+
9+
Return_the length of the longest semi-repetitive substring inside_`s`.
10+
11+
A**substring** is a contiguous**non-empty** sequence of characters within a string.
12+
13+
**Example 1:**
14+
15+
**Input:** s = "52233"
16+
17+
**Output:** 4
18+
19+
**Explanation:** The longest semi-repetitive substring is "5223", which starts at i = 0 and ends at j = 3.
20+
21+
**Example 2:**
22+
23+
**Input:** s = "5494"
24+
25+
**Output:** 4
26+
27+
**Explanation:** s is a semi-reptitive string, so the answer is 4.
28+
29+
**Example 3:**
30+
31+
**Input:** s = "1111111"
32+
33+
**Output:** 2
34+
35+
**Explanation:** The longest semi-repetitive substring is "11", which starts at i = 0 and ends at j = 1.
36+
37+
**Constraints:**
38+
39+
*`1 <= s.length <= 50`
40+
*`'0' <= s[i] <= '9'`
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
packageg2701_2800.s2731_movement_of_robots;
2+
3+
// #Medium #Array #Sorting #Prefix_Sum #Brainteaser
4+
// #2023_09_22_Time_9_ms_(100.00%)_Space_54.7_MB_(63.56%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publicintsumDistance(int[]nums,Strings,intd) {
10+
intn =nums.length;
11+
intmod = (int) (1e9 +7);
12+
for (inti =0;i <n;i++) {
13+
nums[i] += (s.charAt(i) =='R') ?d : -d;
14+
}
15+
Arrays.sort(nums);
16+
longres =0;
17+
for (inti =0;i <n;i++) {
18+
res = (res + (1L +i +i -n) *nums[i]) %mod;
19+
}
20+
return (int) ((res +mod) %mod);
21+
}
22+
}
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
2731\. Movement of Robots
2+
3+
Medium
4+
5+
Some robots are standing on an infinite number line with their initial coordinates given by a**0-indexed** integer array`nums` and will start moving once given the command to move. The robots will move a unit distance each second.
6+
7+
You are given a string`s` denoting the direction in which robots will move on command.`'L'` means the robot will move towards the left side or negative side of the number line, whereas`'R'` means the robot will move towards the right side or positive side of the number line.
8+
9+
If two robots collide, they will start moving in opposite directions.
10+
11+
Return_the sum of distances between all the pairs of robots_`d`_seconds after the command._ Since the sum can be very large, return it modulo <code>10<sup>9</sup> + 7</code>.
12+
13+
**Note:**
14+
15+
* For two robots at the index`i` and`j`, pair`(i,j)` and pair`(j,i)` are considered the same pair.
16+
* When robots collide, they**instantly change** their directions without wasting any time.
17+
* Collision happens when two robots share the same place in a moment.
18+
* For example, if a robot is positioned in 0 going to the right and another is positioned in 2 going to the left, the next second they'll be both in 1 and they will change direction and the next second the first one will be in 0, heading left, and another will be in 2, heading right.
19+
* For example, if a robot is positioned in 0 going to the right and another is positioned in 1 going to the left, the next second the first one will be in 0, heading left, and another will be in 1, heading right.
20+
21+
**Example 1:**
22+
23+
**Input:** nums =[-2,0,2], s = "RLL", d = 3
24+
25+
**Output:** 8
26+
27+
**Explanation:**
28+
29+
After 1 second, the positions are[-1,-1,1]. Now, the robot at index 0 will move left, and the robot at index 1 will move right.
30+
31+
After 2 seconds, the positions are[-2,0,0]. Now, the robot at index 1 will move left, and the robot at index 2 will move right.
32+
33+
After 3 seconds, the positions are[-3,-1,1].
34+
35+
The distance between the robot at index 0 and 1 is abs(-3 - (-1)) = 2.
36+
37+
The distance between the robot at index 0 and 2 is abs(-3 - 1) = 4.
38+
39+
The distance between the robot at index 1 and 2 is abs(-1 - 1) = 2.
40+
41+
The sum of the pairs of all distances = 2 + 4 + 2 = 8.
42+
43+
**Example 2:**
44+
45+
**Input:** nums =[1,0], s = "RL", d = 2
46+
47+
**Output:** 5
48+
49+
**Explanation:**
50+
51+
After 1 second, the positions are[2,-1].
52+
53+
After 2 seconds, the positions are[3,-2].
54+
55+
The distance between the two robots is abs(-2 - 3) = 5.
56+
57+
**Constraints:**
58+
59+
* <code>2 <= nums.length <= 10<sup>5</sup></code>
60+
* <code>-2 * 10<sup>9</sup> <= nums[i] <= 2 * 10<sup>9</sup></code>
61+
* <code>0 <= d <= 10<sup>9</sup></code>
62+
*`nums.length == s.length`
63+
*`s` consists of 'L' and 'R' only
64+
*`nums[i]` will be unique.
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
packageg2701_2800.s2732_find_a_good_subset_of_the_matrix;
2+
3+
// #Hard #Array #Greedy #Matrix #Bit_Manipulation
4+
// #2023_09_22_Time_7_ms_(70.65%)_Space_57.2_MB_(5.43%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.HashMap;
8+
importjava.util.List;
9+
importjava.util.Map;
10+
11+
publicclassSolution {
12+
publicList<Integer>goodSubsetofBinaryMatrix(int[][]grid) {
13+
intm =grid.length;
14+
intn =grid[0].length;
15+
if (m ==1 &&sumArray(grid[0]) ==0) {
16+
returnList.of(0);
17+
}
18+
Map<Integer,Integer>pos =newHashMap<>();
19+
for (inti =0;i <m;i++) {
20+
for (intmask =0;mask < (1 <<n);mask++) {
21+
booleanvalid =true;
22+
for (intj =0;j <n;j++) {
23+
if ((mask & (1 <<j)) !=0 &&grid[i][j] +1 >1) {
24+
valid =false;
25+
break;
26+
}
27+
}
28+
if (valid &&pos.containsKey(mask)) {
29+
returnList.of(pos.get(mask),i);
30+
}
31+
}
32+
intcurr =0;
33+
for (intj =0;j <n;j++) {
34+
if (grid[i][j] ==1) {
35+
curr =curr | (1 <<j);
36+
}
37+
}
38+
pos.put(curr,i);
39+
}
40+
returnnewArrayList<>();
41+
}
42+
43+
privateintsumArray(int[]arr) {
44+
intsum =0;
45+
for (intnum :arr) {
46+
sum +=num;
47+
}
48+
returnsum;
49+
}
50+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
2732\. Find a Good Subset of the Matrix
2+
3+
Hard
4+
5+
You are given a**0-indexed**`m x n` binary matrix`grid`.
6+
7+
Let us call a**non-empty** subset of rows**good** if the sum of each column of the subset is at most half of the length of the subset.
8+
9+
More formally, if the length of the chosen subset of rows is`k`, then the sum of each column should be at most`floor(k / 2)`.
10+
11+
Return_an integer array that contains row indices of a good subset sorted in**ascending** order._
12+
13+
If there are multiple good subsets, you can return any of them. If there are no good subsets, return an empty array.
14+
15+
A**subset** of rows of the matrix`grid` is any matrix that can be obtained by deleting some (possibly none or all) rows from`grid`.
16+
17+
**Example 1:**
18+
19+
**Input:** grid =[[0,1,1,0],[0,0,0,1],[1,1,1,1]]
20+
21+
**Output:**[0,1]
22+
23+
**Explanation:** We can choose the 0<sup>th</sup> and 1<sup>st</sup> rows to create a good subset of rows. The length of the chosen subset is 2.
24+
- The sum of the 0<sup>th</sup> column is 0 + 0 = 0, which is at most half of the length of the subset.
25+
- The sum of the 1<sup>st</sup> column is 1 + 0 = 1, which is at most half of the length of the subset.
26+
- The sum of the 2<sup>nd</sup> column is 1 + 0 = 1, which is at most half of the length of the subset.
27+
- The sum of the 3<sup>rd</sup> column is 0 + 1 = 1, which is at most half of the length of the subset.
28+
29+
**Example 2:**
30+
31+
**Input:** grid =[[0]]
32+
33+
**Output:**[0]
34+
35+
**Explanation:** We can choose the 0<sup>th</sup> row to create a good subset of rows. The length of the chosen subset is 1.
36+
- The sum of the 0<sup>th</sup> column is 0, which is at most half of the length of the subset.
37+
38+
**Example 3:**
39+
40+
**Input:** grid =[[1,1,1],[1,1,1]]
41+
42+
**Output:**[]
43+
44+
**Explanation:** It is impossible to choose any subset of rows to create a good subset.
45+
46+
**Constraints:**
47+
48+
*`m == grid.length`
49+
*`n == grid[i].length`
50+
* <code>1 <= m <= 10<sup>4</sup></code>
51+
*`1 <= n <= 5`
52+
*`grid[i][j]` is either`0` or`1`.
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg2701_2800.s2733_neither_minimum_nor_maximum;
2+
3+
// #Easy #Array #Sorting #2023_09_22_Time_4_ms_(99.76%)_Space_43.9_MB_(27.58%)
4+
5+
publicclassSolution {
6+
publicintfindNonMinOrMax(int[]nums) {
7+
intmn =999;
8+
intmx = -1;
9+
for (intnum :nums) {
10+
mn =Math.min(num,mn);
11+
mx =Math.max(num,mx);
12+
}
13+
for (intnum :nums) {
14+
if (num !=mn &&num !=mx) {
15+
returnnum;
16+
}
17+
}
18+
return -1;
19+
}
20+
}
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
2733\. Neither Minimum nor Maximum
2+
3+
Easy
4+
5+
Given an integer array`nums` containing**distinct****positive** integers, find and return**any** number from the array that is neither the**minimum** nor the**maximum** value in the array, or**`-1`** if there is no such number.
6+
7+
Return_the selected integer._
8+
9+
**Example 1:**
10+
11+
**Input:** nums =[3,2,1,4]
12+
13+
**Output:** 2
14+
15+
**Explanation:** In this example, the minimum value is 1 and the maximum value is 4. Therefore, either 2 or 3 can be valid answers.
16+
17+
**Example 2:**
18+
19+
**Input:** nums =[1,2]
20+
21+
**Output:** -1
22+
23+
**Explanation:** Since there is no number in nums that is neither the maximum nor the minimum, we cannot select a number that satisfies the given condition. Therefore, there is no answer.
24+
25+
**Example 3:**
26+
27+
**Input:** nums =[2,1,3]
28+
29+
**Output:** 2
30+
31+
**Explanation:** Since 2 is neither the maximum nor the minimum value in nums, it is the only valid answer.
32+
33+
**Constraints:**
34+
35+
*`1 <= nums.length <= 100`
36+
*`1 <= nums[i] <= 100`
37+
* All values in`nums` are distinct
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
packageg2701_2800.s2734_lexicographically_smallest_string_after_substring_operation;
2+
3+
// #Medium #String #Greedy #2023_09_22_Time_12_ms_(86.26%)_Space_48.4_MB_(70.88%)
4+
5+
publicclassSolution {
6+
publicStringsmallestString(Strings) {
7+
inti =0;
8+
intn =s.length();
9+
char[]a =s.toCharArray();
10+
while (i <n &&a[i] =='a') {
11+
i++;
12+
if (i ==n) {
13+
a[n -1] ='z';
14+
}
15+
}
16+
while (i <n &&a[i] !='a') {
17+
--a[i++];
18+
}
19+
returnString.valueOf(a);
20+
}
21+
}
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
2734\. Lexicographically Smallest String After Substring Operation
2+
3+
Medium
4+
5+
You are given a string`s` consisting of only lowercase English letters. In one operation, you can do the following:
6+
7+
* Select any non-empty substring of`s`, possibly the entire string, then replace each one of its characters with the previous character of the English alphabet. For example, 'b' is converted to 'a', and 'a' is converted to 'z'.
8+
9+
Return_the**lexicographically smallest** string you can obtain after performing the above operation**exactly once**._
10+
11+
A**substring** is a contiguous sequence of characters in a string.
12+
13+
A string`x` is**lexicographically smaller** than a string`y` of the same length if`x[i]` comes before`y[i]` in alphabetic order for the first position`i` such that`x[i] != y[i]`.
14+
15+
**Example 1:**
16+
17+
**Input:** s = "cbabc"
18+
19+
**Output:** "baabc"
20+
21+
**Explanation:** We apply the operation on the substring starting at index 0, and ending at index 1 inclusive. It can be proven that the resulting string is the lexicographically smallest.
22+
23+
**Example 2:**
24+
25+
**Input:** s = "acbbc"
26+
27+
**Output:** "abaab"
28+
29+
**Explanation:** We apply the operation on the substring starting at index 1, and ending at index 4 inclusive. It can be proven that the resulting string is the lexicographically smallest.
30+
31+
**Example 3:**
32+
33+
**Input:** s = "leetcode"
34+
35+
**Output:** "kddsbncd"
36+
37+
**Explanation:** We apply the operation on the entire string. It can be proven that the resulting string is the lexicographically smallest.
38+
39+
**Constraints:**
40+
41+
* <code>1 <= s.length <= 3 * 10<sup>5</sup></code>
42+
*`s` consists of lowercase English letters

0 commit comments

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