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

Commit2bb2ef4

Browse files
authored
Added tasks 2490, 2491, 2492, 2493, 2496
1 parentb2986d0 commit2bb2ef4

File tree

16 files changed

+529
-0
lines changed

16 files changed

+529
-0
lines changed

‎README.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1848,6 +1848,11 @@ implementation 'com.github.javadev:leetcode-in-java:1.17'
18481848

18491849
| # | Title | Difficulty | Tag | Time, ms | Time, %
18501850
|------|----------------|-------------|-------------|----------|---------
1851+
| 2496 |[Maximum Value of a String in an Array](src/main/java/g2401_2500/s2496_maximum_value_of_a_string_in_an_array/Solution.java)| Easy | Array, String | 1 | 92.00
1852+
| 2493 |[Divide Nodes Into the Maximum Number of Groups](src/main/java/g2401_2500/s2493_divide_nodes_into_the_maximum_number_of_groups/Solution.java)| Hard | Graph, Union_Find, Breadth_First_Search | 443 | 77.02
1853+
| 2492 |[Minimum Score of a Path Between Two Cities](src/main/java/g2401_2500/s2492_minimum_score_of_a_path_between_two_cities/Solution.java)| Medium | Graph, Union_Find, Depth_First_Search, Breadth_First_Search | 13 | 92.82
1854+
| 2491 |[Divide Players Into Teams of Equal Skill](src/main/java/g2401_2500/s2491_divide_players_into_teams_of_equal_skill/Solution.java)| Medium | Array, Hash_Table, Sorting, Two_Pointers | 21 | 70.31
1855+
| 2490 |[Circular Sentence](src/main/java/g2401_2500/s2490_circular_sentence/Solution.java)| Easy | String | 1 | 99.85
18511856
| 2488 |[Count Subarrays With Median K](src/main/java/g2401_2500/s2488_count_subarrays_with_median_k/Solution.java)| Hard | Array, Hash_Table, Prefix_Sum | 24 | 72.25
18521857
| 2487 |[Remove Nodes From Linked List](src/main/java/g2401_2500/s2487_remove_nodes_from_linked_list/Solution.java)| Medium | Stack, Linked_List, Monotonic_Stack, Recursion | 5 | 99.79
18531858
| 2486 |[Append Characters to String to Make Subsequence](src/main/java/g2401_2500/s2486_append_characters_to_string_to_make_subsequence/Solution.java)| Medium | String, Greedy, Two_Pointers | 2 | 99.89
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
packageg2401_2500.s2490_circular_sentence;
2+
3+
// #Easy #String #2023_01_27_Time_1_ms_(99.85%)_Space_42.6_MB_(55.63%)
4+
5+
publicclassSolution {
6+
publicbooleanisCircularSentence(Stringsentence) {
7+
char[]letters =sentence.toCharArray();
8+
intlen =letters.length;
9+
for (inti =0;i <len -1; ++i) {
10+
if (letters[i] ==' ' &&letters[i -1] !=letters[i +1]) {
11+
returnfalse;
12+
}
13+
}
14+
returnletters[0] ==letters[len -1];
15+
}
16+
}
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
2490\. Circular Sentence
2+
3+
Easy
4+
5+
A**sentence** is a list of words that are separated by a**single** space with no leading or trailing spaces.
6+
7+
* For example,`"Hello World"`,`"HELLO"`,`"hello world hello world"` are all sentences.
8+
9+
Words consist of**only** uppercase and lowercase English letters. Uppercase and lowercase English letters are considered different.
10+
11+
A sentence is**circular** if:
12+
13+
* The last character of a word is equal to the first character of the next word.
14+
* The last character of the last word is equal to the first character of the first word.
15+
16+
For example,`"leetcode exercises sound delightful"`,`"eetcode"`,`"leetcode eats soul"` are all circular sentences. However,`"Leetcode is cool"`,`"happy Leetcode"`,`"Leetcode"` and`"I like Leetcode"` are**not** circular sentences.
17+
18+
Given a string`sentence`, return`true`_if it is circular_. Otherwise, return`false`.
19+
20+
**Example 1:**
21+
22+
**Input:** sentence = "leetcode exercises sound delightful"
23+
24+
**Output:** true
25+
26+
**Explanation:** The words in sentence are["leetcode", "exercises", "sound", "delightful"].
27+
- leetcod<ins>e</ins>'s last character is equal to <ins>e</ins>xercises's first character.
28+
- exercise<ins>s</ins>'s last character is equal to <ins>s</ins>ound's first character.
29+
- soun<ins>d</ins>'s last character is equal to <ins>d</ins>elightful's first character.
30+
- delightfu<ins>l</ins>'s last character is equal to <ins>l</ins>eetcode's first character.
31+
32+
The sentence is circular.
33+
34+
**Example 2:**
35+
36+
**Input:** sentence = "eetcode"
37+
38+
**Output:** true
39+
40+
**Explanation:** The words in sentence are["eetcode"].
41+
- eetcod<ins>e</ins>'s last character is equal to <ins>e</ins>etcode's first character. The sentence is circular.
42+
43+
**Example 3:**
44+
45+
**Input:** sentence = "Leetcode is cool"
46+
47+
**Output:** false
48+
49+
**Explanation:** The words in sentence are["Leetcode", "is", "cool"]. - Leetcod<ins>e</ins>'s last character is**not** equal to <ins>i</ins>s's first character. The sentence is**not** circular.
50+
51+
**Constraints:**
52+
53+
*`1 <= sentence.length <= 500`
54+
*`sentence` consist of only lowercase and uppercase English letters and spaces.
55+
* The words in`sentence` are separated by a single space.
56+
* There are no leading or trailing spaces.
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2401_2500.s2491_divide_players_into_teams_of_equal_skill;
2+
3+
// #Medium #Array #Hash_Table #Sorting #Two_Pointers
4+
// #2023_01_27_Time_21_ms_(70.31%)_Space_73.6_MB_(27.92%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publiclongdividePlayers(int[]skill) {
10+
inti =0;
11+
intj =skill.length -1;
12+
Arrays.sort(skill);
13+
intsum =skill[i] +skill[j];
14+
longp =0;
15+
while (i <j) {
16+
if (skill[i] +skill[j] !=sum) {
17+
return -1;
18+
}
19+
p += ((long)skill[i] *skill[j]);
20+
i++;
21+
j--;
22+
}
23+
returnp;
24+
}
25+
}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
2491\. Divide Players Into Teams of Equal Skill
2+
3+
Medium
4+
5+
You are given a positive integer array`skill` of**even** length`n` where`skill[i]` denotes the skill of the <code>i<sup>th</sup></code> player. Divide the players into`n / 2` teams of size`2` such that the total skill of each team is**equal**.
6+
7+
The**chemistry** of a team is equal to the**product** of the skills of the players on that team.
8+
9+
Return_the sum of the**chemistry** of all the teams, or return_`-1`_if there is no way to divide the players into teams such that the total skill of each team is equal._
10+
11+
**Example 1:**
12+
13+
**Input:** skill =[3,2,5,1,3,4]
14+
15+
**Output:** 22
16+
17+
**Explanation:** Divide the players into the following teams: (1, 5), (2, 4), (3, 3), where each team has a total skill of 6. The sum of the chemistry of all the teams is: 1\* 5 + 2\* 4 + 3\* 3 = 5 + 8 + 9 = 22.
18+
19+
**Example 2:**
20+
21+
**Input:** skill =[3,4]
22+
23+
**Output:** 12
24+
25+
**Explanation:** The two players form a team with a total skill of 7. The chemistry of the team is 3\* 4 = 12.
26+
27+
**Example 3:**
28+
29+
**Input:** skill =[1,1,2,3]
30+
31+
**Output:** -1
32+
33+
**Explanation:** There is no way to divide the players into teams such that the total skill of each team is equal.
34+
35+
**Constraints:**
36+
37+
* <code>2 <= skill.length <= 10<sup>5</sup></code>
38+
*`skill.length` is even.
39+
*`1 <= skill[i] <= 1000`
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
packageg2401_2500.s2492_minimum_score_of_a_path_between_two_cities;
2+
3+
// #Medium #Graph #Union_Find #Depth_First_Search #Breadth_First_Search
4+
// #2023_01_27_Time_13_ms_(92.82%)_Space_101.5_MB_(78.71%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
privateint[]dsu;
10+
11+
publicintminScore(intn,int[][]roads) {
12+
dsu =newint[n +1];
13+
int[]ans =newint[n +1];
14+
for (inti =0;i <=n;i++) {
15+
dsu[i] =i;
16+
}
17+
Arrays.fill(ans,Integer.MAX_VALUE);
18+
for (int[]r :roads) {
19+
inta =find(r[0]);
20+
intb =find(r[1]);
21+
dsu[a] =dsu[b];
22+
ans[a] =ans[b] =Math.min(r[2],Math.min(ans[a],ans[b]));
23+
}
24+
returnans[find(1)];
25+
}
26+
27+
privateintfind(inti) {
28+
returndsu[i] ==i ?i :find(dsu[i]);
29+
}
30+
}
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
2492\. Minimum Score of a Path Between Two Cities
2+
3+
Medium
4+
5+
You are given a positive integer`n` representing`n` cities numbered from`1` to`n`. You are also given a**2D** array`roads` where <code>roads[i] =[a<sub>i</sub>, b<sub>i</sub>, distance<sub>i</sub>]</code> indicates that there is a**bidirectional** road between cities <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> with a distance equal to <code>distance<sub>i</sub></code>. The cities graph is not necessarily connected.
6+
7+
The**score** of a path between two cities is defined as the**minimum** distance of a road in this path.
8+
9+
Return_the**minimum** possible score of a path between cities_`1`_and_`n`.
10+
11+
**Note**:
12+
13+
* A path is a sequence of roads between two cities.
14+
* It is allowed for a path to contain the same road**multiple** times, and you can visit cities`1` and`n` multiple times along the path.
15+
* The test cases are generated such that there is**at least** one path between`1` and`n`.
16+
17+
**Example 1:**
18+
19+
![](https://assets.leetcode.com/uploads/2022/10/12/graph11.png)
20+
21+
**Input:** n = 4, roads =[[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
22+
23+
**Output:** 5
24+
25+
**Explanation:** The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 4. The score of this path is min(9,5) = 5. It can be shown that no other path has less score.
26+
27+
**Example 2:**
28+
29+
![](https://assets.leetcode.com/uploads/2022/10/12/graph22.png)
30+
31+
**Input:** n = 4, roads =[[1,2,2],[1,3,4],[3,4,7]]
32+
33+
**Output:** 2
34+
35+
**Explanation:** The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 1 -> 3 -> 4. The score of this path is min(2,2,4,7) = 2.
36+
37+
**Constraints:**
38+
39+
* <code>2 <= n <= 10<sup>5</sup></code>
40+
* <code>1 <= roads.length <= 10<sup>5</sup></code>
41+
*`roads[i].length == 3`
42+
* <code>1 <= a<sub>i</sub>, b<sub>i</sub> <= n</code>
43+
* <code>a<sub>i</sub> != b<sub>i</sub></code>
44+
* <code>1 <= distance<sub>i</sub> <= 10<sup>4</sup></code>
45+
* There are no repeated edges.
46+
* There is at least one path between`1` and`n`.
Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
packageg2401_2500.s2493_divide_nodes_into_the_maximum_number_of_groups;
2+
3+
// #Hard #Graph #Union_Find #Breadth_First_Search
4+
// #2023_01_27_Time_443_ms_(77.02%)_Space_47.8_MB_(77.54%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
importjava.util.LinkedList;
9+
importjava.util.List;
10+
importjava.util.Queue;
11+
12+
publicclassSolution {
13+
publicintmagnificentSets(intn,int[][]edges) {
14+
List<List<Integer>>adj =newArrayList<>();
15+
int[]visited =newint[n +1];
16+
Arrays.fill(visited, -1);
17+
for (inti =0;i <=n;i++) {
18+
adj.add(newArrayList<>());
19+
}
20+
for (int[]edge :edges) {
21+
adj.get(edge[0]).add(edge[1]);
22+
adj.get(edge[1]).add(edge[0]);
23+
}
24+
int[]comp =newint[n +1];
25+
intcount = -1;
26+
intans =0;
27+
for (inti =1;i <=n;i++) {
28+
if (visited[i] == -1) {
29+
count++;
30+
comp[count] =bfs(i,adj,visited,count,n);
31+
if (comp[count] == -1) {
32+
return -1;
33+
}
34+
}else {
35+
comp[visited[i]] =Math.max(comp[visited[i]],bfs(i,adj,visited,visited[i],n));
36+
}
37+
}
38+
for (intgroup :comp) {
39+
ans +=group;
40+
}
41+
returnans;
42+
}
43+
44+
privateintbfs(intstart,List<List<Integer>>adj,int[]visited,intcount,intn) {
45+
Queue<Integer>q =newLinkedList<>();
46+
visited[start] =count;
47+
intans =1;
48+
int[]group =newint[n +1];
49+
q.add(start);
50+
group[start] =1;
51+
while (!q.isEmpty()) {
52+
intnode =q.remove();
53+
for (intadjN :adj.get(node)) {
54+
if (group[adjN] ==0) {
55+
visited[adjN] =count;
56+
group[adjN] =group[node] +1;
57+
q.add(adjN);
58+
ans =Math.max(ans,group[adjN]);
59+
}elseif (Math.abs(group[adjN] -group[node]) !=1) {
60+
return -1;
61+
}
62+
}
63+
}
64+
returnans;
65+
}
66+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
2493\. Divide Nodes Into the Maximum Number of Groups
2+
3+
Hard
4+
5+
You are given a positive integer`n` representing the number of nodes in an**undirected** graph. The nodes are labeled from`1` to`n`.
6+
7+
You are also given a 2D integer array`edges`, where <code>edges[i] =[a<sub>i,</sub> b<sub>i</sub>]</code> indicates that there is a**bidirectional** edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code>.**Notice** that the given graph may be disconnected.
8+
9+
Divide the nodes of the graph into`m` groups (**1-indexed**) such that:
10+
11+
* Each node in the graph belongs to exactly one group.
12+
* For every pair of nodes in the graph that are connected by an edge <code>[a<sub>i,</sub> b<sub>i</sub>]</code>, if <code>a<sub>i</sub></code> belongs to the group with index`x`, and <code>b<sub>i</sub></code> belongs to the group with index`y`, then`|y - x| = 1`.
13+
14+
Return_the maximum number of groups (i.e., maximum_`m`_) into which you can divide the nodes_. Return`-1`_if it is impossible to group the nodes with the given conditions_.
15+
16+
**Example 1:**
17+
18+
![](https://assets.leetcode.com/uploads/2022/10/13/example1.png)
19+
20+
**Input:** n = 6, edges =[[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]
21+
22+
**Output:** 4
23+
24+
**Explanation:** As shown in the image we:
25+
- Add node 5 to the first group.
26+
- Add node 1 to the second group.
27+
- Add nodes 2 and 4 to the third group.
28+
- Add nodes 3 and 6 to the fourth group.
29+
30+
We can see that every edge is satisfied. It can be shown that that if we create a fifth group and move any node from the third or fourth group to it, at least on of the edges will not be satisfied.
31+
32+
**Example 2:**
33+
34+
**Input:** n = 3, edges =[[1,2],[2,3],[3,1]]
35+
36+
**Output:** -1
37+
38+
**Explanation:** If we add node 1 to the first group, node 2 to the second group, and node 3 to the third group to satisfy the first two edges, we can see that the third edge will not be satisfied. It can be shown that no grouping is possible.
39+
40+
**Constraints:**
41+
42+
*`1 <= n <= 500`
43+
* <code>1 <= edges.length <= 10<sup>4</sup></code>
44+
*`edges[i].length == 2`
45+
* <code>1 <= a<sub>i</sub>, b<sub>i</sub> <= n</code>
46+
* <code>a<sub>i</sub> != b<sub>i</sub></code>
47+
* There is at most one edge between any pair of vertices.
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2401_2500.s2496_maximum_value_of_a_string_in_an_array;
2+
3+
// #Easy #Array #String #2023_01_27_Time_1_ms_(92.00%)_Space_41.7_MB_(54.56%)
4+
5+
publicclassSolution {
6+
publicintmaximumValue(String[]strs) {
7+
intmaxVal =0;
8+
for (Strings :strs) {
9+
maxVal =Math.max(maxVal,value(s));
10+
}
11+
returnmaxVal;
12+
}
13+
14+
privateintvalue(Strings) {
15+
inttotal =0;
16+
for (charch :s.toCharArray()) {
17+
if (ch >='0' &&ch <='9') {
18+
total =total *10 + (ch -'0');
19+
}else {
20+
returns.length();
21+
}
22+
}
23+
returntotal;
24+
}
25+
}

0 commit comments

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