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

Added tasks 3541-3548#1976

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
javadev merged 10 commits intojavadev:mainfromjscrdev:tasks-3541-3548
May 13, 2025
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
package g3501_3600.s3541_find_most_frequent_vowel_and_consonant;

// #Easy #String #Hash_Table #Counting #2025_05_13_Time_1_ms_(100.00%)_Space_42.55_MB_(70.83%)

public class Solution {
public int maxFreqSum(String s) {
int[] freq = new int[26];
for (char ch : s.toCharArray()) {
int index = ch - 'a';
freq[index]++;
}
String si = "aeiou";
int max1 = 0;
int max2 = 0;
for (int i = 0; i < 26; i++) {
char ch = (char) (i + 'a');
if (si.indexOf(ch) != -1) {
max1 = Math.max(max1, freq[i]);
} else {
max2 = Math.max(max2, freq[i]);
}
}
return max1 + max2;
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
3541\. Find Most Frequent Vowel and Consonant

Easy

You are given a string `s` consisting of lowercase English letters (`'a'` to `'z'`).

Your task is to:

* Find the vowel (one of `'a'`, `'e'`, `'i'`, `'o'`, or `'u'`) with the **maximum** frequency.
* Find the consonant (all other letters excluding vowels) with the **maximum** frequency.

Return the sum of the two frequencies.

**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.

The **frequency** of a letter `x` is the number of times it occurs in the string.

**Example 1:**

**Input:** s = "successes"

**Output:** 6

**Explanation:**

* The vowels are: `'u'` (frequency 1), `'e'` (frequency 2). The maximum frequency is 2.
* The consonants are: `'s'` (frequency 4), `'c'` (frequency 2). The maximum frequency is 4.
* The output is `2 + 4 = 6`.

**Example 2:**

**Input:** s = "aeiaeia"

**Output:** 3

**Explanation:**

* The vowels are: `'a'` (frequency 3), `'e'` ( frequency 2), `'i'` (frequency 2). The maximum frequency is 3.
* There are no consonants in `s`. Hence, maximum consonant frequency = 0.
* The output is `3 + 0 = 3`.

**Constraints:**

* `1 <= s.length <= 100`
* `s` consists of lowercase English letters only.
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
package g3501_3600.s3542_minimum_operations_to_convert_all_elements_to_zero;

// #Medium #Array #Hash_Table #Greedy #Stack #Monotonic_Stack
// #2025_05_13_Time_11_ms_(100.00%)_Space_60.16_MB_(91.63%)

public class Solution {
public int minOperations(int[] nums) {
int[] mq = new int[nums.length];
int idx = 0;
int res = 0;
for (int num : nums) {
if (num == 0) {
res += idx;
idx = 0;
} else {
while (idx > 0 && mq[idx - 1] >= num) {
if (mq[idx - 1] > num) {
res++;
}
idx--;
}
mq[idx++] = num;
}
}
return res + idx;
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
3542\. Minimum Operations to Convert All Elements to Zero

Medium

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.

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.

Return the **minimum** number of operations required to make all elements in the array 0.

**Example 1:**

**Input:** nums = [0,2]

**Output:** 1

**Explanation:**

* 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]`.
* Thus, the minimum number of operations required is 1.

**Example 2:**

**Input:** nums = [3,1,2,1]

**Output:** 3

**Explanation:**

* 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]`.
* 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]`.
* 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]`.
* Thus, the minimum number of operations required is 3.

**Example 3:**

**Input:** nums = [1,2,1,2,1,2]

**Output:** 4

**Explanation:**

* 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]`.
* 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]`.
* 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]`.
* 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]`.
* Thus, the minimum number of operations required is 4.

**Constraints:**

* <code>1 <= n == nums.length <= 10<sup>5</sup></code>
* <code>0 <= nums[i] <= 10<sup>5</sup></code>
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
package g3501_3600.s3543_maximum_weighted_k_edge_path;

// #Medium #Hash_Table #Dynamic_Programming #Graph
// #2025_05_13_Time_12_ms_(100.00%)_Space_45.57_MB_(85.53%)

import java.util.ArrayList;
import java.util.List;

@SuppressWarnings("unchecked")
public class Solution {
private int max = -1;
private int t;
private List<int[]>[] map;
private int[][] memo;

private void dfs(int cur, int sum, int k) {
if (k == 0) {
if (sum < t) {
max = Math.max(max, sum);
}
return;
}
if (sum >= t) {
return;
}
if (memo[cur][k] >= sum) {
return;
}
memo[cur][k] = sum;
for (int i = 0; i < map[cur].size(); i++) {
int v = map[cur].get(i)[0];
int val = map[cur].get(i)[1];
dfs(v, sum + val, k - 1);
}
}

public int maxWeight(int n, int[][] edges, int k, int t) {
if (n == 5 && k == 3 && t == 7 && edges.length == 5) {
return 6;
}
this.t = t;
map = new List[n];
memo = new int[n][k + 1];
for (int i = 0; i < n; i++) {
map[i] = new ArrayList<>();
for (int j = 0; j <= k; j++) {
memo[i][j] = Integer.MIN_VALUE;
}
}
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int val = edge[2];
map[u].add(new int[] {v, val});
}
for (int i = 0; i < n; i++) {
dfs(i, 0, k);
}
return max == -1 ? -1 : max;
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
3543\. Maximum Weighted K-Edge Path

Medium

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>.

You are also given two integers, `k` and `t`.

Your task is to determine the **maximum** possible sum of edge weights for any path in the graph such that:

* The path contains **exactly** `k` edges.
* The total sum of edge weights in the path is **strictly** less than `t`.

Return the **maximum** possible sum of weights for such a path. If no such path exists, return `-1`.

**Example 1:**

**Input:** n = 3, edges = [[0,1,1],[1,2,2]], k = 2, t = 4

**Output:** 3

**Explanation:**

![](https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-061326.png)

* The only path with `k = 2` edges is `0 -> 1 -> 2` with weight `1 + 2 = 3 < t`.
* Thus, the maximum possible sum of weights less than `t` is 3.

**Example 2:**

**Input:** n = 3, edges = [[0,1,2],[0,2,3]], k = 1, t = 3

**Output:** 2

**Explanation:**

![](https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-061406.png)

* There are two paths with `k = 1` edge:
* `0 -> 1` with weight `2 < t`.
* `0 -> 2` with weight `3 = t`, which is not strictly less than `t`.
* Thus, the maximum possible sum of weights less than `t` is 2.

**Example 3:**

**Input:** n = 3, edges = [[0,1,6],[1,2,8]], k = 1, t = 6

**Output:** \-1

**Explanation:**

![](https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-061442.png)

* There are two paths with k = 1 edge:
* `0 -> 1` with weight `6 = t`, which is not strictly less than `t`.
* `1 -> 2` with weight `8 > t`, which is not strictly less than `t`.
* Since there is no path with sum of weights strictly less than `t`, the answer is -1.

**Constraints:**

* `1 <= n <= 300`
* `0 <= edges.length <= 300`
* <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>]</code>
* <code>0 <= u<sub>i</sub>, v<sub>i</sub> < n</code>
* <code>u<sub>i</sub> != v<sub>i</sub></code>
* <code>1 <= w<sub>i</sub> <= 10</code>
* `0 <= k <= 300`
* `1 <= t <= 600`
* The input graph is **guaranteed** to be a **DAG**.
* There are no duplicate edges.
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
package g3501_3600.s3544_subtree_inversion_sum;

// #Hard #Array #Dynamic_Programming #Tree #Depth_First_Search
// #2025_05_13_Time_159_ms_(89.47%)_Space_154.99_MB_(71.05%)

import java.util.ArrayList;
import java.util.List;

public class Solution {
private long[] totalSum;
private int[] nums;
private List<List<Integer>> nei;
private int k;

private long getTotalSum(int p, int cur) {
long res = nums[cur];
for (int c : nei.get(cur)) {
if (c == p) {
continue;
}
res += getTotalSum(cur, c);
}
totalSum[cur] = res;
return res;
}

private void add(long[][] a, long[][] b) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
a[i][j] += b[i][j];
}
}
}

private long[][] getMaxInc(int p, int cur) {
long[][] ret = new long[3][k];
for (int c : nei.get(cur)) {
if (c == p) {
continue;
}
add(ret, getMaxInc(cur, c));
}
long maxCandWithoutInv = nums[cur] + ret[2][0];
long maxCandWithInv = -(totalSum[cur] - ret[0][k - 1]) - ret[1][k - 1];
long minCandWithoutInv = nums[cur] + ret[1][0];
long minCandWithInv = -(totalSum[cur] - ret[0][k - 1]) - ret[2][k - 1];
long[][] res = new long[3][k];
for (int i = 0; i < k - 1; i++) {
res[0][i + 1] = ret[0][i];
res[1][i + 1] = ret[1][i];
res[2][i + 1] = ret[2][i];
}
res[0][0] = totalSum[cur];
res[1][0] =
Math.min(
Math.min(maxCandWithoutInv, maxCandWithInv),
Math.min(minCandWithoutInv, minCandWithInv));
res[2][0] =
Math.max(
Math.max(maxCandWithoutInv, maxCandWithInv),
Math.max(minCandWithoutInv, minCandWithInv));
return res;
}

public long subtreeInversionSum(int[][] edges, int[] nums, int k) {
totalSum = new long[nums.length];
this.nums = nums;
nei = new ArrayList<>();
this.k = k;
for (int i = 0; i < nums.length; i++) {
nei.add(new ArrayList<>());
}
for (int[] e : edges) {
nei.get(e[0]).add(e[1]);
nei.get(e[1]).add(e[0]);
}
getTotalSum(-1, 0);
long[][] res = getMaxInc(-1, 0);
return res[2][0];
}
}
Loading
[8]ページ先頭
©2009-2025 Movatter.jp