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

Commitbfdce7b

Browse files
authored
Added tasks 2608-2612
1 parent2a312d4 commitbfdce7b

File tree

15 files changed

+513
-0
lines changed

15 files changed

+513
-0
lines changed
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
packageg2601_2700.s2608_shortest_cycle_in_a_graph;
2+
3+
// #Hard #Breadth_First_Search #Graph #2023_08_30_Time_11_ms_(100.00%)_Space_44_MB_(76.40%)
4+
5+
importjava.util.ArrayList;
6+
importjava.util.List;
7+
8+
publicclassSolution {
9+
privateintoutput =1001;
10+
11+
publicintfindShortestCycle(intn,int[][]edges) {
12+
List<Integer>[]nexts =newArrayList[n];
13+
int[]ranks =newint[n];
14+
for (inti =0;i <n;i++) {
15+
nexts[i] =newArrayList<>();
16+
}
17+
for (int[]edge :edges) {
18+
for (inti =0;i <2;i++) {
19+
nexts[edge[i]].add(edge[1 -i]);
20+
}
21+
}
22+
for (inti =0;i <n;i++) {
23+
if (ranks[i] ==0) {
24+
findShortestCycle(nexts,i, -1, -1001,ranks);
25+
}
26+
}
27+
returnoutput ==1001 ? -1 :output;
28+
}
29+
30+
privatevoidfindShortestCycle(List<Integer>[]nexts,intc,intp,intr,int[]ranks) {
31+
ranks[c] =r;
32+
for (intn :nexts[c]) {
33+
if (n !=p) {
34+
if (ranks[n] >r +1) {
35+
findShortestCycle(nexts,n,c,r +1,ranks);
36+
}elseif (ranks[c] >ranks[n]) {
37+
output =Math.min(output,ranks[c] -ranks[n] +1);
38+
}
39+
}
40+
}
41+
}
42+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
2608\. Shortest Cycle in a Graph
2+
3+
Hard
4+
5+
There is a**bi-directional** graph with`n` vertices, where each vertex is labeled from`0` to`n - 1`. The edges in the graph are represented by a given 2D integer array`edges`, where <code>edges[i] =[u<sub>i</sub>, v<sub>i</sub>]</code> denotes an edge between vertex <code>u<sub>i</sub></code> and vertex <code>v<sub>i</sub></code>. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.
6+
7+
Return_the length of the**shortest** cycle in the graph_. If no cycle exists, return`-1`.
8+
9+
A cycle is a path that starts and ends at the same node, and each edge in the path is used only once.
10+
11+
**Example 1:**
12+
13+
![](https://assets.leetcode.com/uploads/2023/01/04/cropped.png)
14+
15+
**Input:** n = 7, edges =[[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
16+
17+
**Output:** 3
18+
19+
**Explanation:** The cycle with the smallest length is : 0 -> 1 -> 2 -> 0
20+
21+
**Example 2:**
22+
23+
![](https://assets.leetcode.com/uploads/2023/01/04/croppedagin.png)
24+
25+
**Input:** n = 4, edges =[[0,1],[0,2]]
26+
27+
**Output:** -1
28+
29+
**Explanation:** There are no cycles in this graph.
30+
31+
**Constraints:**
32+
33+
*`2 <= n <= 1000`
34+
*`1 <= edges.length <= 1000`
35+
*`edges[i].length == 2`
36+
* <code>0 <= u<sub>i</sub>, v<sub>i</sub> < n</code>
37+
* <code>u<sub>i</sub> != v<sub>i</sub></code>
38+
* There are no repeated edges.
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
packageg2601_2700.s2609_find_the_longest_balanced_substring_of_a_binary_string;
2+
3+
// #Easy #String #2023_08_30_Time_1_ms_(100.00%)_Space_42.5_MB_(18.86%)
4+
5+
publicclassSolution {
6+
publicintfindTheLongestBalancedSubstring(Strings) {
7+
char[]chars =s.toCharArray();
8+
intmax =0;
9+
intn =chars.length;
10+
intzero =0;
11+
intone =0;
12+
inti =0;
13+
while (i <n) {
14+
if (chars[i] =='0') {
15+
zero++;
16+
}else {
17+
while (i <n) {
18+
if (chars[i++] =='1') {
19+
one++;
20+
}else {
21+
i--;
22+
break;
23+
}
24+
}
25+
max =Math.max(max,2 *Math.min(one,zero));
26+
zero =1;
27+
one =0;
28+
}
29+
i++;
30+
}
31+
32+
returnmax;
33+
}
34+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2609\. Find the Longest Balanced Substring of a Binary String
2+
3+
Easy
4+
5+
You are given a binary string`s` consisting only of zeroes and ones.
6+
7+
A substring of`s` is considered balanced if**all zeroes are before ones** and the number of zeroes is equal to the number of ones inside the substring. Notice that the empty substring is considered a balanced substring.
8+
9+
Return_the length of the longest balanced substring of_`s`.
10+
11+
A**substring** is a contiguous sequence of characters within a string.
12+
13+
**Example 1:**
14+
15+
**Input:** s = "01000111"
16+
17+
**Output:** 6
18+
19+
**Explanation:** The longest balanced substring is "000111", which has length 6.
20+
21+
**Example 2:**
22+
23+
**Input:** s = "00111"
24+
25+
**Output:** 4
26+
27+
**Explanation:** The longest balanced substring is "0011", which has length 4.
28+
29+
**Example 3:**
30+
31+
**Input:** s = "111"
32+
33+
**Output:** 0
34+
35+
**Explanation:** There is no balanced substring except the empty substring, so the answer is 0.
36+
37+
**Constraints:**
38+
39+
*`1 <= s.length <= 50`
40+
*`'0' <= s[i] <= '1'`
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
packageg2601_2700.s2610_convert_an_array_into_a_2d_array_with_conditions;
2+
3+
// #Medium #Array #Hash_Table #2023_08_30_Time_2_ms_(97.24%)_Space_43.9_MB_(80.58%)
4+
5+
importjava.util.ArrayList;
6+
importjava.util.HashMap;
7+
importjava.util.List;
8+
importjava.util.Map;
9+
10+
publicclassSolution {
11+
publicList<List<Integer>>findMatrix(int[]nums) {
12+
List<List<Integer>>res =newArrayList<>();
13+
Map<Integer,Integer>map =newHashMap<>();
14+
for (intx :nums) {
15+
map.put(x,map.getOrDefault(x,0) +1);
16+
intidx =map.get(x);
17+
if (res.size() <idx) {
18+
res.add(newArrayList<>());
19+
}
20+
res.get(idx -1).add(x);
21+
}
22+
returnres;
23+
}
24+
}
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
2610\. Convert an Array Into a 2D Array With Conditions
2+
3+
Medium
4+
5+
You are given an integer array`nums`. You need to create a 2D array from`nums` satisfying the following conditions:
6+
7+
* The 2D array should contain**only** the elements of the array`nums`.
8+
* Each row in the 2D array contains**distinct** integers.
9+
* The number of rows in the 2D array should be**minimal**.
10+
11+
Return_the resulting array_. If there are multiple answers, return any of them.
12+
13+
**Note** that the 2D array can have a different number of elements on each row.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[1,3,4,1,2,3,1]
18+
19+
**Output:**[[1,3,4,2],[1,3],[1]]
20+
21+
**Explanation:** We can create a 2D array that contains the following rows: - 1,3,4,2 - 1,3 - 1 All elements of nums were used, and each row of the 2D array contains distinct integers, so it is a valid answer. It can be shown that we cannot have less than 3 rows in a valid array.
22+
23+
**Example 2:**
24+
25+
**Input:** nums =[1,2,3,4]
26+
27+
**Output:**[[4,3,2,1]]
28+
29+
**Explanation:** All elements of the array are distinct, so we can keep all of them in the first row of the 2D array.
30+
31+
**Constraints:**
32+
33+
*`1 <= nums.length <= 200`
34+
*`1 <= nums[i] <= nums.length`
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageg2601_2700.s2611_mice_and_cheese;
2+
3+
// #Medium #Array #Sorting #Greedy #Heap_Priority_Queue
4+
// #2023_08_30_Time_11_ms_(99.56%)_Space_55_MB_(81.66%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publicintmiceAndCheese(
10+
int[]firstReward,int[]seondReward,intnumberOfTypesOfCheeseForFirstMouse) {
11+
intmaximumPoints =0;
12+
finalinttotalTypesOfCheese =firstReward.length;
13+
int[]differenceInRewards =newint[totalTypesOfCheese];
14+
for (inti =0;i <totalTypesOfCheese; ++i) {
15+
differenceInRewards[i] =firstReward[i] -seondReward[i];
16+
maximumPoints +=seondReward[i];
17+
}
18+
Arrays.sort(differenceInRewards);
19+
for (inti =totalTypesOfCheese -1;
20+
i >totalTypesOfCheese -numberOfTypesOfCheeseForFirstMouse -1;
21+
--i) {
22+
maximumPoints +=differenceInRewards[i];
23+
}
24+
returnmaximumPoints;
25+
}
26+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2611\. Mice and Cheese
2+
3+
Medium
4+
5+
There are two mice and`n` different types of cheese, each type of cheese should be eaten by exactly one mouse.
6+
7+
A point of the cheese with index`i` (**0-indexed**) is:
8+
9+
*`reward1[i]` if the first mouse eats it.
10+
*`reward2[i]` if the second mouse eats it.
11+
12+
You are given a positive integer array`reward1`, a positive integer array`reward2`, and a non-negative integer`k`.
13+
14+
Return_**the maximum** points the mice can achieve if the first mouse eats exactly_`k`_types of cheese._
15+
16+
**Example 1:**
17+
18+
**Input:** reward1 =[1,1,3,4], reward2 =[4,4,1,1], k = 2
19+
20+
**Output:** 15
21+
22+
**Explanation:** In this example, the first mouse eats the 2<sup>nd</sup> (0-indexed) and the 3<sup>rd</sup> types of cheese, and the second mouse eats the 0<sup>th</sup> and the 1<sup>st</sup> types of cheese. The total points are 4 + 4 + 3 + 4 = 15. It can be proven that 15 is the maximum total points that the mice can achieve.
23+
24+
**Example 2:**
25+
26+
**Input:** reward1 =[1,1], reward2 =[1,1], k = 2
27+
28+
**Output:** 2
29+
30+
**Explanation:** In this example, the first mouse eats the 0<sup>th</sup> (0-indexed) and 1<sup>st</sup> types of cheese, and the second mouse does not eat any cheese. The total points are 1 + 1 = 2. It can be proven that 2 is the maximum total points that the mice can achieve.
31+
32+
**Constraints:**
33+
34+
* <code>1 <= n == reward1.length == reward2.length <= 10<sup>5</sup></code>
35+
*`1 <= reward1[i], reward2[i] <= 1000`
36+
*`0 <= k <= n`
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
packageg2601_2700.s2612_minimum_reverse_operations;
2+
3+
// #Hard #Array #Breadth_First_Search #Ordered_Set
4+
// #2023_08_30_Time_19_ms_(100.00%)_Space_59_MB_(78.00%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
publicint[]minReverseOperations(intn,intp,int[]banned,intk) {
11+
int[]out =newint[n];
12+
for (inti =0;i <n;i++) {
13+
out[i] = -1;
14+
}
15+
for (intnode :banned) {
16+
out[node] = -2;
17+
}
18+
List<Integer>nodes =newArrayList<>();
19+
nodes.add(p);
20+
intdepth =0;
21+
out[p] =depth;
22+
intstep =k -1;
23+
int[]nextNode2s =newint[n +1];
24+
for (inti =0;i <n +1;i++) {
25+
nextNode2s[i] =i +2;
26+
}
27+
while (!nodes.isEmpty()) {
28+
depth++;
29+
List<Integer>newNodes =newArrayList<>();
30+
for (intnode1 :nodes) {
31+
intloReverseStart =Math.max(node1 -step,0);
32+
inthiReverseStart =Math.min(node1,n -k);
33+
intloNode2 =2 *loReverseStart +k -1 -node1;
34+
inthiNode2 =2 *hiReverseStart +k -1 -node1;
35+
intpostHiNode2 =hiNode2 +2;
36+
intnode2 =loNode2;
37+
while (node2 <=hiNode2) {
38+
intnextNode2 =nextNode2s[node2];
39+
nextNode2s[node2] =postHiNode2;
40+
if (node2 <n &&out[node2] == -1) {
41+
newNodes.add(node2);
42+
out[node2] =depth;
43+
}
44+
node2 =nextNode2;
45+
}
46+
}
47+
nodes =newNodes;
48+
}
49+
for (inti =0;i <n;i++) {
50+
if (out[i] == -2) {
51+
out[i] = -1;
52+
}
53+
}
54+
returnout;
55+
}
56+
}
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
2612\. Minimum Reverse Operations
2+
3+
Hard
4+
5+
You are given an integer`n` and an integer`p` in the range`[0, n - 1]`. Representing a**0-indexed** array`arr` of length`n` where all positions are set to`0`'s, except position`p` which is set to`1`.
6+
7+
You are also given an integer array`banned` containing some positions from the array. For the**i**<sup>**th**</sup> position in`banned`,`arr[banned[i]] = 0`, and`banned[i] != p`.
8+
9+
You can perform**multiple** operations on`arr`. In an operation, you can choose a**subarray** with size`k` and**reverse** the subarray. However, the`1` in`arr` should never go to any of the positions in`banned`. In other words, after each operation`arr[banned[i]]`**remains**`0`.
10+
11+
_Return an array_`ans`_where__for each_`i`_from_`[0, n - 1]`,`ans[i]`_is the**minimum** number of reverse operations needed to bring the_`1`_to position_`i`_in arr_,_or_`-1`_if it is impossible_.
12+
13+
* A**subarray** is a contiguous**non-empty** sequence of elements within an array.
14+
* The values of`ans[i]` are independent for all`i`'s.
15+
* The**reverse** of an array is an array containing the values in**reverse order**.
16+
17+
**Example 1:**
18+
19+
**Input:** n = 4, p = 0, banned =[1,2], k = 4
20+
21+
**Output:**[0,-1,-1,1]
22+
23+
**Explanation:**
24+
25+
In this case`k = 4` so there is only one possible reverse operation we can perform, which is reversing the whole array. Initially, 1 is placed at position 0 so the amount of operations we need for position 0 is`0`. We can never place a 1 on the banned positions, so the answer for positions 1 and 2 is`-1`. Finally, with one reverse operation we can bring the 1 to index 3, so the answer for position 3 is`1`.
26+
27+
**Example 2:**
28+
29+
**Input:** n = 5, p = 0, banned =[2,4], k = 3
30+
31+
**Output:**[0,-1,-1,-1,-1]
32+
33+
**Explanation:**
34+
35+
In this case the 1 is initially at position 0, so the answer for that position is`0`. We can perform reverse operations of size 3. The 1 is currently located at position 0, so we need to reverse the subarray`[0, 2]` for it to leave that position, but reversing that subarray makes position 2 have a 1, which shouldn't happen. So, we can't move the 1 from position 0, making the result for all the other positions`-1`.
36+
37+
**Example 3:**
38+
39+
**Input:** n = 4, p = 2, banned =[0,1,3], k = 1
40+
41+
**Output:**[-1,-1,0,-1]
42+
43+
**Explanation:** In this case we can only perform reverse operations of size 1.So the 1 never changes its position.
44+
45+
**Constraints:**
46+
47+
* <code>1 <= n <= 10<sup>5</sup></code>
48+
*`0 <= p <= n - 1`
49+
*`0 <= banned.length <= n - 1`
50+
*`0 <= banned[i] <= n - 1`
51+
*`1 <= k <= n`
52+
*`banned[i] != p`
53+
* all values in`banned` are**unique**

0 commit comments

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