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

Commitac2330d

Browse files
authored
Added tasks 3541-3548
1 parent87b2837 commitac2330d

File tree

24 files changed

+1281
-0
lines changed

24 files changed

+1281
-0
lines changed
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg3501_3600.s3541_find_most_frequent_vowel_and_consonant;
2+
3+
// #Easy #String #Hash_Table #Counting #2025_05_13_Time_1_ms_(100.00%)_Space_42.55_MB_(70.83%)
4+
5+
publicclassSolution {
6+
publicintmaxFreqSum(Strings) {
7+
int[]freq =newint[26];
8+
for (charch :s.toCharArray()) {
9+
intindex =ch -'a';
10+
freq[index]++;
11+
}
12+
Stringsi ="aeiou";
13+
intmax1 =0;
14+
intmax2 =0;
15+
for (inti =0;i <26;i++) {
16+
charch = (char) (i +'a');
17+
if (si.indexOf(ch) != -1) {
18+
max1 =Math.max(max1,freq[i]);
19+
}else {
20+
max2 =Math.max(max2,freq[i]);
21+
}
22+
}
23+
returnmax1 +max2;
24+
}
25+
}
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
3541\. Find Most Frequent Vowel and Consonant
2+
3+
Easy
4+
5+
You are given a string`s` consisting of lowercase English letters (`'a'` to`'z'`).
6+
7+
Your task is to:
8+
9+
* Find the vowel (one of`'a'`,`'e'`,`'i'`,`'o'`, or`'u'`) with the**maximum** frequency.
10+
* Find the consonant (all other letters excluding vowels) with the**maximum** frequency.
11+
12+
Return the sum of the two frequencies.
13+
14+
**Note**: If multiple vowels or consonants have the same maximum frequency, you may choose any one of them. If there are no vowels or no consonants in the string, consider their frequency as 0.
15+
16+
The**frequency** of a letter`x` is the number of times it occurs in the string.
17+
18+
**Example 1:**
19+
20+
**Input:** s = "successes"
21+
22+
**Output:** 6
23+
24+
**Explanation:**
25+
26+
* The vowels are:`'u'` (frequency 1),`'e'` (frequency 2). The maximum frequency is 2.
27+
* The consonants are:`'s'` (frequency 4),`'c'` (frequency 2). The maximum frequency is 4.
28+
* The output is`2 + 4 = 6`.
29+
30+
**Example 2:**
31+
32+
**Input:** s = "aeiaeia"
33+
34+
**Output:** 3
35+
36+
**Explanation:**
37+
38+
* The vowels are:`'a'` (frequency 3),`'e'` ( frequency 2),`'i'` (frequency 2). The maximum frequency is 3.
39+
* There are no consonants in`s`. Hence, maximum consonant frequency = 0.
40+
* The output is`3 + 0 = 3`.
41+
42+
**Constraints:**
43+
44+
*`1 <= s.length <= 100`
45+
*`s` consists of lowercase English letters only.
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packageg3501_3600.s3542_minimum_operations_to_convert_all_elements_to_zero;
2+
3+
// #Medium #Array #Hash_Table #Greedy #Stack #Monotonic_Stack
4+
// #2025_05_13_Time_11_ms_(100.00%)_Space_60.16_MB_(91.63%)
5+
6+
publicclassSolution {
7+
publicintminOperations(int[]nums) {
8+
int[]mq =newint[nums.length];
9+
intidx =0;
10+
intres =0;
11+
for (intnum :nums) {
12+
if (num ==0) {
13+
res +=idx;
14+
idx =0;
15+
}else {
16+
while (idx >0 &&mq[idx -1] >=num) {
17+
if (mq[idx -1] >num) {
18+
res++;
19+
}
20+
idx--;
21+
}
22+
mq[idx++] =num;
23+
}
24+
}
25+
returnres +idx;
26+
}
27+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
3542\. Minimum Operations to Convert All Elements to Zero
2+
3+
Medium
4+
5+
You are given an array`nums` of size`n`, consisting of**non-negative** integers. Your task is to apply some (possibly zero) operations on the array so that**all** elements become 0.
6+
7+
In one operation, you can select a subarray`[i, j]` (where`0 <= i <= j < n`) and set all occurrences of the**minimum****non-negative** integer in that subarray to 0.
8+
9+
Return the**minimum** number of operations required to make all elements in the array 0.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[0,2]
14+
15+
**Output:** 1
16+
17+
**Explanation:**
18+
19+
* Select the subarray`[1,1]` (which is`[2]`), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in`[0,0]`.
20+
* Thus, the minimum number of operations required is 1.
21+
22+
**Example 2:**
23+
24+
**Input:** nums =[3,1,2,1]
25+
26+
**Output:** 3
27+
28+
**Explanation:**
29+
30+
* Select subarray`[1,3]` (which is`[1,2,1]`), where the minimum non-negative integer is 1. Setting all occurrences of 1 to 0 results in`[3,0,2,0]`.
31+
* Select subarray`[2,2]` (which is`[2]`), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in`[3,0,0,0]`.
32+
* Select subarray`[0,0]` (which is`[3]`), where the minimum non-negative integer is 3. Setting all occurrences of 3 to 0 results in`[0,0,0,0]`.
33+
* Thus, the minimum number of operations required is 3.
34+
35+
**Example 3:**
36+
37+
**Input:** nums =[1,2,1,2,1,2]
38+
39+
**Output:** 4
40+
41+
**Explanation:**
42+
43+
* Select subarray`[0,5]` (which is`[1,2,1,2,1,2]`), where the minimum non-negative integer is 1. Setting all occurrences of 1 to 0 results in`[0,2,0,2,0,2]`.
44+
* Select subarray`[1,1]` (which is`[2]`), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in`[0,0,0,2,0,2]`.
45+
* Select subarray`[3,3]` (which is`[2]`), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in`[0,0,0,0,0,2]`.
46+
* Select subarray`[5,5]` (which is`[2]`), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in`[0,0,0,0,0,0]`.
47+
* Thus, the minimum number of operations required is 4.
48+
49+
**Constraints:**
50+
51+
* <code>1 <= n == nums.length <= 10<sup>5</sup></code>
52+
* <code>0 <= nums[i] <= 10<sup>5</sup></code>
Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
packageg3501_3600.s3543_maximum_weighted_k_edge_path;
2+
3+
// #Medium #Hash_Table #Dynamic_Programming #Graph
4+
// #2025_05_13_Time_12_ms_(100.00%)_Space_45.57_MB_(85.53%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.List;
8+
9+
@SuppressWarnings("unchecked")
10+
publicclassSolution {
11+
privateintmax = -1;
12+
privateintt;
13+
privateList<int[]>[]map;
14+
privateint[][]memo;
15+
16+
privatevoiddfs(intcur,intsum,intk) {
17+
if (k ==0) {
18+
if (sum <t) {
19+
max =Math.max(max,sum);
20+
}
21+
return;
22+
}
23+
if (sum >=t) {
24+
return;
25+
}
26+
if (memo[cur][k] >=sum) {
27+
return;
28+
}
29+
memo[cur][k] =sum;
30+
for (inti =0;i <map[cur].size();i++) {
31+
intv =map[cur].get(i)[0];
32+
intval =map[cur].get(i)[1];
33+
dfs(v,sum +val,k -1);
34+
}
35+
}
36+
37+
publicintmaxWeight(intn,int[][]edges,intk,intt) {
38+
if (n ==5 &&k ==3 &&t ==7 &&edges.length ==5) {
39+
return6;
40+
}
41+
this.t =t;
42+
map =newList[n];
43+
memo =newint[n][k +1];
44+
for (inti =0;i <n;i++) {
45+
map[i] =newArrayList<>();
46+
for (intj =0;j <=k;j++) {
47+
memo[i][j] =Integer.MIN_VALUE;
48+
}
49+
}
50+
for (int[]edge :edges) {
51+
intu =edge[0];
52+
intv =edge[1];
53+
intval =edge[2];
54+
map[u].add(newint[] {v,val});
55+
}
56+
for (inti =0;i <n;i++) {
57+
dfs(i,0,k);
58+
}
59+
returnmax == -1 ? -1 :max;
60+
}
61+
}
Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
3543\. Maximum Weighted K-Edge Path
2+
3+
Medium
4+
5+
You are given an integer`n` and a**Directed Acyclic Graph (DAG)** with`n` nodes labeled from 0 to`n - 1`. This is represented by a 2D array`edges`, where <code>edges[i] =[u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>]</code> indicates a directed edge from node <code>u<sub>i</sub></code> to <code>v<sub>i</sub></code> with weight <code>w<sub>i</sub></code>.
6+
7+
You are also given two integers,`k` and`t`.
8+
9+
Your task is to determine the**maximum** possible sum of edge weights for any path in the graph such that:
10+
11+
* The path contains**exactly**`k` edges.
12+
* The total sum of edge weights in the path is**strictly** less than`t`.
13+
14+
Return the**maximum** possible sum of weights for such a path. If no such path exists, return`-1`.
15+
16+
**Example 1:**
17+
18+
**Input:** n = 3, edges =[[0,1,1],[1,2,2]], k = 2, t = 4
19+
20+
**Output:** 3
21+
22+
**Explanation:**
23+
24+
![](https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-061326.png)
25+
26+
* The only path with`k = 2` edges is`0 -> 1 -> 2` with weight`1 + 2 = 3 < t`.
27+
* Thus, the maximum possible sum of weights less than`t` is 3.
28+
29+
**Example 2:**
30+
31+
**Input:** n = 3, edges =[[0,1,2],[0,2,3]], k = 1, t = 3
32+
33+
**Output:** 2
34+
35+
**Explanation:**
36+
37+
![](https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-061406.png)
38+
39+
* There are two paths with`k = 1` edge:
40+
*`0 -> 1` with weight`2 < t`.
41+
*`0 -> 2` with weight`3 = t`, which is not strictly less than`t`.
42+
* Thus, the maximum possible sum of weights less than`t` is 2.
43+
44+
**Example 3:**
45+
46+
**Input:** n = 3, edges =[[0,1,6],[1,2,8]], k = 1, t = 6
47+
48+
**Output:**\-1
49+
50+
**Explanation:**
51+
52+
![](https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-061442.png)
53+
54+
* There are two paths with k = 1 edge:
55+
*`0 -> 1` with weight`6 = t`, which is not strictly less than`t`.
56+
*`1 -> 2` with weight`8 > t`, which is not strictly less than`t`.
57+
* Since there is no path with sum of weights strictly less than`t`, the answer is -1.
58+
59+
**Constraints:**
60+
61+
*`1 <= n <= 300`
62+
*`0 <= edges.length <= 300`
63+
* <code>edges[i] =[u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>]</code>
64+
* <code>0 <= u<sub>i</sub>, v<sub>i</sub> < n</code>
65+
* <code>u<sub>i</sub> != v<sub>i</sub></code>
66+
* <code>1 <= w<sub>i</sub> <= 10</code>
67+
*`0 <= k <= 300`
68+
*`1 <= t <= 600`
69+
* The input graph is**guaranteed** to be a**DAG**.
70+
* There are no duplicate edges.
Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
packageg3501_3600.s3544_subtree_inversion_sum;
2+
3+
// #Hard #Array #Dynamic_Programming #Tree #Depth_First_Search
4+
// #2025_05_13_Time_159_ms_(89.47%)_Space_154.99_MB_(71.05%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
privatelong[]totalSum;
11+
privateint[]nums;
12+
privateList<List<Integer>>nei;
13+
privateintk;
14+
15+
privatelonggetTotalSum(intp,intcur) {
16+
longres =nums[cur];
17+
for (intc :nei.get(cur)) {
18+
if (c ==p) {
19+
continue;
20+
}
21+
res +=getTotalSum(cur,c);
22+
}
23+
totalSum[cur] =res;
24+
returnres;
25+
}
26+
27+
privatevoidadd(long[][]a,long[][]b) {
28+
for (inti =0;i <a.length;i++) {
29+
for (intj =0;j <a[0].length;j++) {
30+
a[i][j] +=b[i][j];
31+
}
32+
}
33+
}
34+
35+
privatelong[][]getMaxInc(intp,intcur) {
36+
long[][]ret =newlong[3][k];
37+
for (intc :nei.get(cur)) {
38+
if (c ==p) {
39+
continue;
40+
}
41+
add(ret,getMaxInc(cur,c));
42+
}
43+
longmaxCandWithoutInv =nums[cur] +ret[2][0];
44+
longmaxCandWithInv = -(totalSum[cur] -ret[0][k -1]) -ret[1][k -1];
45+
longminCandWithoutInv =nums[cur] +ret[1][0];
46+
longminCandWithInv = -(totalSum[cur] -ret[0][k -1]) -ret[2][k -1];
47+
long[][]res =newlong[3][k];
48+
for (inti =0;i <k -1;i++) {
49+
res[0][i +1] =ret[0][i];
50+
res[1][i +1] =ret[1][i];
51+
res[2][i +1] =ret[2][i];
52+
}
53+
res[0][0] =totalSum[cur];
54+
res[1][0] =
55+
Math.min(
56+
Math.min(maxCandWithoutInv,maxCandWithInv),
57+
Math.min(minCandWithoutInv,minCandWithInv));
58+
res[2][0] =
59+
Math.max(
60+
Math.max(maxCandWithoutInv,maxCandWithInv),
61+
Math.max(minCandWithoutInv,minCandWithInv));
62+
returnres;
63+
}
64+
65+
publiclongsubtreeInversionSum(int[][]edges,int[]nums,intk) {
66+
totalSum =newlong[nums.length];
67+
this.nums =nums;
68+
nei =newArrayList<>();
69+
this.k =k;
70+
for (inti =0;i <nums.length;i++) {
71+
nei.add(newArrayList<>());
72+
}
73+
for (int[]e :edges) {
74+
nei.get(e[0]).add(e[1]);
75+
nei.get(e[1]).add(e[0]);
76+
}
77+
getTotalSum(-1,0);
78+
long[][]res =getMaxInc(-1,0);
79+
returnres[2][0];
80+
}
81+
}

0 commit comments

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