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

Commit768bbac

Browse files
authored
Added tasks 3556-3663
1 parentf414bf5 commit768bbac

File tree

24 files changed

+1093
-0
lines changed

24 files changed

+1093
-0
lines changed
Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
packageg3501_3600.s3556_sum_of_largest_prime_substrings;
2+
3+
// #Medium #String #Hash_Table #Math #Sorting #Number_Theory
4+
// #2025_05_27_Time_7_ms_(99.93%)_Space_42.77_MB_(98.34%)
5+
6+
importjava.util.HashSet;
7+
importjava.util.Set;
8+
9+
publicclassSolution {
10+
publiclongsumOfLargestPrimes(Strings) {
11+
Set<Long>set =newHashSet<>();
12+
intn =s.length();
13+
longfirst = -1;
14+
longsecond = -1;
15+
longthird = -1;
16+
for (inti =0;i <n;i++) {
17+
longnum =0;
18+
for (intj =i;j <n;j++) {
19+
num =num *10 + (s.charAt(j) -'0');
20+
if (i !=j &&s.charAt(i) =='0') {
21+
break;
22+
}
23+
if (isPrime(num) && !set.contains(num)) {
24+
set.add(num);
25+
if (num >first) {
26+
third =second;
27+
second =first;
28+
first =num;
29+
}elseif (num >second) {
30+
third =second;
31+
second =num;
32+
}elseif (num >third) {
33+
third =num;
34+
}
35+
}
36+
}
37+
}
38+
longsum =0;
39+
if (first != -1) {
40+
sum +=first;
41+
}
42+
if (second != -1) {
43+
sum +=second;
44+
}
45+
if (third != -1) {
46+
sum +=third;
47+
}
48+
returnsum;
49+
}
50+
51+
publicbooleanisPrime(longnum) {
52+
if (num <=1) {
53+
returnfalse;
54+
}
55+
if (num ==2 ||num ==3) {
56+
returntrue;
57+
}
58+
if (num %2 ==0 ||num %3 ==0) {
59+
returnfalse;
60+
}
61+
for (longi =5;i *i <=num;i +=6) {
62+
if (num %i ==0 ||num % (i +2) ==0) {
63+
returnfalse;
64+
}
65+
}
66+
returntrue;
67+
}
68+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
3556\. Sum of Largest Prime Substrings
2+
3+
Medium
4+
5+
Given a string`s`, find the sum of the**3 largest unique prime numbers** that can be formed using any of its****substring****.
6+
7+
Return the**sum** of the three largest unique prime numbers that can be formed. If fewer than three exist, return the sum of**all** available primes. If no prime numbers can be formed, return 0.
8+
9+
**Note:** Each prime number should be counted only**once**, even if it appears in**multiple** substrings. Additionally, when converting a substring to an integer, any leading zeros are ignored.
10+
11+
**Example 1:**
12+
13+
**Input:** s = "12234"
14+
15+
**Output:** 1469
16+
17+
**Explanation:**
18+
19+
* The unique prime numbers formed from the substrings of`"12234"` are 2, 3, 23, 223, and 1223.
20+
* The 3 largest primes are 1223, 223, and 23. Their sum is 1469.
21+
22+
**Example 2:**
23+
24+
**Input:** s = "111"
25+
26+
**Output:** 11
27+
28+
**Explanation:**
29+
30+
* The unique prime number formed from the substrings of`"111"` is 11.
31+
* Since there is only one prime number, the sum is 11.
32+
33+
**Constraints:**
34+
35+
*`1 <= s.length <= 10`
36+
*`s` consists of only digits.
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
packageg3501_3600.s3557_find_maximum_number_of_non_intersecting_substrings;
2+
3+
// #Medium #String #Hash_Table #Dynamic_Programming #Greedy
4+
// #2025_05_27_Time_15_ms_(84.54%)_Space_45.82_MB_(91.39%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publicintmaxSubstrings(Strings) {
10+
int[]prev =newint[26];
11+
intr =0;
12+
Arrays.fill(prev, -1);
13+
for (inti =0;i <s.length(); ++i) {
14+
intj =s.charAt(i) -'a';
15+
if (prev[j] != -1 &&i -prev[j] +1 >=4) {
16+
++r;
17+
Arrays.fill(prev, -1);
18+
}elseif (prev[j] == -1) {
19+
prev[j] =i;
20+
}
21+
}
22+
returnr;
23+
}
24+
}
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
3557\. Find Maximum Number of Non Intersecting Substrings
2+
3+
Medium
4+
5+
You are given a string`word`.
6+
7+
Return the**maximum** number of non-intersecting****substring**** of word that are at**least** four characters long and start and end with the same letter.
8+
9+
**Example 1:**
10+
11+
**Input:** word = "abcdeafdef"
12+
13+
**Output:** 2
14+
15+
**Explanation:**
16+
17+
The two substrings are`"abcdea"` and`"fdef"`.
18+
19+
**Example 2:**
20+
21+
**Input:** word = "bcdaaaab"
22+
23+
**Output:** 1
24+
25+
**Explanation:**
26+
27+
The only substring is`"aaaa"`. Note that we cannot**also** choose`"bcdaaaab"` since it intersects with the other substring.
28+
29+
**Constraints:**
30+
31+
* <code>1 <= word.length <= 2 * 10<sup>5</sup></code>
32+
*`word` consists only of lowercase English letters.
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
packageg3501_3600.s3558_number_of_ways_to_assign_edge_weights_i;
2+
3+
// #Medium #Math #Tree #Depth_First_Search #2025_05_27_Time_12_ms_(100.00%)_Space_106.62_MB_(76.01%)
4+
5+
publicclassSolution {
6+
privatestaticintmod = (int)1e9 +7;
7+
privatelong[]pow2 =newlong[100001];
8+
9+
publicintassignEdgeWeights(int[][]edges) {
10+
if (pow2[0] ==0) {
11+
pow2[0] =1;
12+
for (inti =1;i <pow2.length;i++) {
13+
pow2[i] = (pow2[i -1] <<1) %mod;
14+
}
15+
}
16+
intn =edges.length +1;
17+
int[]adj =newint[n +1];
18+
int[]degrees =newint[n +1];
19+
for (int[]edge :edges) {
20+
intu =edge[0];
21+
intv =edge[1];
22+
adj[u] +=v;
23+
adj[v] +=u;
24+
degrees[u]++;
25+
degrees[v]++;
26+
}
27+
int[]que =newint[n];
28+
intwrite =0;
29+
intread =0;
30+
for (inti =2;i <=n; ++i) {
31+
if (degrees[i] ==1) {
32+
que[write++] =i;
33+
}
34+
}
35+
intdistance =0;
36+
while (read <write) {
37+
distance++;
38+
intsize =write -read;
39+
while (size-- >0) {
40+
intv =que[read++];
41+
intu =adj[v];
42+
adj[u] -=v;
43+
if (--degrees[u] ==1 &&u !=1) {
44+
que[write++] =u;
45+
}
46+
}
47+
}
48+
return (int)pow2[distance -1];
49+
}
50+
}
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
3558\. Number of Ways to Assign Edge Weights I
2+
3+
Medium
4+
5+
There is an undirected tree with`n` nodes labeled from 1 to`n`, rooted at node 1. The tree is represented by a 2D integer array`edges` of length`n - 1`, where <code>edges[i] =[u<sub>i</sub>, v<sub>i</sub>]</code> indicates that there is an edge between nodes <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code>.
6+
7+
Initially, all edges have a weight of 0. You must assign each edge a weight of either**1** or**2**.
8+
9+
The**cost** of a path between any two nodes`u` and`v` is the total weight of all edges in the path connecting them.
10+
11+
Select any one node`x` at the**maximum** depth. Return the number of ways to assign edge weights in the path from node 1 to`x` such that its total cost is**odd**.
12+
13+
Since the answer may be large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
14+
15+
**Note:** Ignore all edges**not** in the path from node 1 to`x`.
16+
17+
**Example 1:**
18+
19+
![](https://assets.leetcode.com/uploads/2025/03/23/screenshot-2025-03-24-at-060006.png)
20+
21+
**Input:** edges =[[1,2]]
22+
23+
**Output:** 1
24+
25+
**Explanation:**
26+
27+
* The path from Node 1 to Node 2 consists of one edge (`1 → 2`).
28+
* Assigning weight 1 makes the cost odd, while 2 makes it even. Thus, the number of valid assignments is 1.
29+
30+
**Example 2:**
31+
32+
![](https://assets.leetcode.com/uploads/2025/03/23/screenshot-2025-03-24-at-055820.png)
33+
34+
**Input:** edges =[[1,2],[1,3],[3,4],[3,5]]
35+
36+
**Output:** 2
37+
38+
**Explanation:**
39+
40+
* The maximum depth is 2, with nodes 4 and 5 at the same depth. Either node can be selected for processing.
41+
* For example, the path from Node 1 to Node 4 consists of two edges (`1 → 3` and`3 → 4`).
42+
* Assigning weights (1,2) or (2,1) results in an odd cost. Thus, the number of valid assignments is 2.
43+
44+
**Constraints:**
45+
46+
* <code>2 <= n <= 10<sup>5</sup></code>
47+
*`edges.length == n - 1`
48+
* <code>edges[i] ==[u<sub>i</sub>, v<sub>i</sub>]</code>
49+
* <code>1 <= u<sub>i</sub>, v<sub>i</sub> <= n</code>
50+
*`edges` represents a valid tree.
Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
packageg3501_3600.s3559_number_of_ways_to_assign_edge_weights_ii;
2+
3+
// #Hard #Array #Dynamic_Programming #Math #Tree #Depth_First_Search
4+
// #2025_05_27_Time_138_ms_(64.66%)_Space_133.20_MB_(11.56%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
privatestaticfinalintMOD =1000000007;
11+
privateList<List<Integer>>adj;
12+
privateint[]level;
13+
privateint[][]jumps;
14+
15+
privatevoidmark(intnode,intpar) {
16+
for (intneigh :adj.get(node)) {
17+
if (neigh ==par) {
18+
continue;
19+
}
20+
level[neigh] =level[node] +1;
21+
jumps[neigh][0] =node;
22+
mark(neigh,node);
23+
}
24+
}
25+
26+
publicintlift(intu,intdiff) {
27+
while (diff >0) {
28+
intrightmost =diff ^ (diff & (diff -1));
29+
intjump = (int) (Math.log(rightmost) /Math.log(2));
30+
u =jumps[u][jump];
31+
diff -=rightmost;
32+
}
33+
returnu;
34+
}
35+
36+
privateintfindLca(intu,intv) {
37+
if (level[u] >level[v]) {
38+
inttemp =u;
39+
u =v;
40+
v =temp;
41+
}
42+
v =lift(v,level[v] -level[u]);
43+
if (u ==v) {
44+
returnu;
45+
}
46+
for (inti =jumps[0].length -1;i >=0;i--) {
47+
if (jumps[u][i] !=jumps[v][i]) {
48+
u =jumps[u][i];
49+
v =jumps[v][i];
50+
}
51+
}
52+
returnjumps[u][0];
53+
}
54+
55+
privateintfindDist(inta,intb) {
56+
57+
returnlevel[a] +level[b] -2 *level[findLca(a,b)];
58+
}
59+
60+
publicint[]assignEdgeWeights(int[][]edges,int[][]queries) {
61+
intn =edges.length +1;
62+
adj =newArrayList<>();
63+
level =newint[n];
64+
for (inti =0;i <n;i++) {
65+
adj.add(newArrayList<>());
66+
}
67+
for (int[]i :edges) {
68+
adj.get(i[0] -1).add(i[1] -1);
69+
adj.get(i[1] -1).add(i[0] -1);
70+
}
71+
intm = (int) (Math.ceil(Math.log(n -1.0) /Math.log(2))) +1;
72+
jumps =newint[n][m];
73+
mark(0, -1);
74+
for (intj =1;j <m;j++) {
75+
for (inti =0;i <n;i++) {
76+
intp =jumps[i][j -1];
77+
jumps[i][j] =jumps[p][j -1];
78+
}
79+
}
80+
int[]pow =newint[n +1];
81+
pow[0] =1;
82+
for (inti =1;i <=n;i++) {
83+
pow[i] = (pow[i -1] *2) %MOD;
84+
}
85+
intq =queries.length;
86+
int[]ans =newint[q];
87+
for (inti =0;i <q;i++) {
88+
intd =findDist(queries[i][0] -1,queries[i][1] -1);
89+
ans[i] =d >0 ?pow[d -1] :0;
90+
}
91+
returnans;
92+
}
93+
}

0 commit comments

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