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 3582-3585#1996

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 4 commits intojavadev:mainfromjscrdev:tasks-3582-3585
Jun 17, 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,38 @@
package g3501_3600.s3582_generate_tag_for_video_caption;

// #Easy #String #Simulation #2025_06_17_Time_2_ms_(99.93%)_Space_43.54_MB_(89.89%)

public class Solution {
public String generateTag(String caption) {
StringBuilder sb = new StringBuilder();
sb.append('#');
boolean space = false;
caption = caption.trim();
for (int i = 0; i < caption.length(); i++) {
char c = caption.charAt(i);
if (c == ' ') {
space = true;
}
if (c >= 'A' && c <= 'Z') {
if (space) {
space = !space;
sb.append(c);
} else {
sb.append(Character.toLowerCase(c));
}
}
if (c >= 'a' && c <= 'z') {
if (space) {
space = !space;
sb.append(Character.toUpperCase(c));
} else {
sb.append(c);
}
}
}
if (sb.length() > 100) {
return sb.substring(0, 100);
}
return sb.toString();
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
3582\. Generate Tag for Video Caption

Easy

You are given a string `caption` representing the caption for a video.

The following actions must be performed **in order** to generate a **valid tag** for the video:

1. **Combine all words** in the string into a single _camelCase string_ prefixed with `'#'`. A _camelCase string_ is one where the first letter of all words _except_ the first one is capitalized. All characters after the first character in **each** word must be lowercase.

2. **Remove** all characters that are not an English letter, **except** the first `'#'`.

3. **Truncate** the result to a maximum of 100 characters.


Return the **tag** after performing the actions on `caption`.

**Example 1:**

**Input:** caption = "Leetcode daily streak achieved"

**Output:** "#leetcodeDailyStreakAchieved"

**Explanation:**

The first letter for all words except `"leetcode"` should be capitalized.

**Example 2:**

**Input:** caption = "can I Go There"

**Output:** "#canIGoThere"

**Explanation:**

The first letter for all words except `"can"` should be capitalized.

**Example 3:**

**Input:** caption = "hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh"

**Output:** "#hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh"

**Explanation:**

Since the first word has length 101, we need to truncate the last two letters from the word.

**Constraints:**

* `1 <= caption.length <= 150`
* `caption` consists only of English letters and `' '`.
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
package g3501_3600.s3583_count_special_triplets;

// #Medium #Array #Hash_Table #Counting #2025_06_17_Time_30_ms_(99.81%)_Space_60.90_MB_(89.67%)

public class Solution {
public int specialTriplets(int[] nums) {
long ans = 0;
int[] sum = new int[200002];
int[] left = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
int curr = nums[i];
sum[curr]++;
left[i] = sum[curr * 2];
}
for (int i = 0; i < nums.length; i++) {
int curr = nums[i];
long leftCount = curr == 0 ? left[i] - 1 : left[i];
long rightCount = sum[curr * 2] - (long) left[i];
if (leftCount != 0 && rightCount != 0) {
ans += leftCount * rightCount;
}
}
return (int) (ans % 1000000007);
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
3583\. Count Special Triplets

Medium

You are given an integer array `nums`.

A **special triplet** is defined as a triplet of indices `(i, j, k)` such that:

* `0 <= i < j < k < n`, where `n = nums.length`
* `nums[i] == nums[j] * 2`
* `nums[k] == nums[j] * 2`

Return the total number of **special triplets** in the array.

Since the answer may be large, return it **modulo** <code>10<sup>9</sup> + 7</code>.

**Example 1:**

**Input:** nums = [6,3,6]

**Output:** 1

**Explanation:**

The only special triplet is `(i, j, k) = (0, 1, 2)`, where:

* `nums[0] = 6`, `nums[1] = 3`, `nums[2] = 6`
* `nums[0] = nums[1] * 2 = 3 * 2 = 6`
* `nums[2] = nums[1] * 2 = 3 * 2 = 6`

**Example 2:**

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

**Output:** 1

**Explanation:**

The only special triplet is `(i, j, k) = (0, 2, 3)`, where:

* `nums[0] = 0`, `nums[2] = 0`, `nums[3] = 0`
* `nums[0] = nums[2] * 2 = 0 * 2 = 0`
* `nums[3] = nums[2] * 2 = 0 * 2 = 0`

**Example 3:**

**Input:** nums = [8,4,2,8,4]

**Output:** 2

**Explanation:**

There are exactly two special triplets:

* `(i, j, k) = (0, 1, 3)`
* `nums[0] = 8`, `nums[1] = 4`, `nums[3] = 8`
* `nums[0] = nums[1] * 2 = 4 * 2 = 8`
* `nums[3] = nums[1] * 2 = 4 * 2 = 8`
* `(i, j, k) = (1, 2, 4)`
* `nums[1] = 4`, `nums[2] = 2`, `nums[4] = 4`
* `nums[1] = nums[2] * 2 = 2 * 2 = 4`
* `nums[4] = nums[2] * 2 = 2 * 2 = 4`

**Constraints:**

* <code>3 <= n == nums.length <= 10<sup>5</sup></code>
* <code>0 <= nums[i] <= 10<sup>5</sup></code>
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
package g3501_3600.s3584_maximum_product_of_first_and_last_elements_of_a_subsequence;

// #Medium #Array #Two_Pointers #2025_06_17_Time_4_ms_(86.42%)_Space_60.92_MB_(51.72%)

public class Solution {
public long maximumProduct(int[] nums, int m) {
long ma = nums[0];
long mi = nums[0];
long res = (long) nums[0] * nums[m - 1];
for (int i = m - 1; i < nums.length; ++i) {
ma = Math.max(ma, nums[i - m + 1]);
mi = Math.min(mi, nums[i - m + 1]);
res = Math.max(res, Math.max(mi * nums[i], ma * nums[i]));
}
return res;
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
3584\. Maximum Product of First and Last Elements of a Subsequence

Medium

You are given an integer array `nums` and an integer `m`.

Return the **maximum** product of the first and last elements of any ****subsequences**** of `nums` of size `m`.

**Example 1:**

**Input:** nums = [-1,-9,2,3,-2,-3,1], m = 1

**Output:** 81

**Explanation:**

The subsequence `[-9]` has the largest product of the first and last elements: `-9 * -9 = 81`. Therefore, the answer is 81.

**Example 2:**

**Input:** nums = [1,3,-5,5,6,-4], m = 3

**Output:** 20

**Explanation:**

The subsequence `[-5, 6, -4]` has the largest product of the first and last elements.

**Example 3:**

**Input:** nums = [2,-1,2,-6,5,2,-5,7], m = 2

**Output:** 35

**Explanation:**

The subsequence `[5, 7]` has the largest product of the first and last elements.

**Constraints:**

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

// #Hard #Array #Dynamic_Programming #Tree #Binary_Search #Depth_First_Search
// #2025_06_17_Time_66_ms_(94.96%)_Space_142.62_MB_(49.64%)

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

@SuppressWarnings("java:S2234")
public class Solution {
private List<List<int[]>> adj;
private int[] depth;
private long[] dist;
private int[][] parent;
private int longMax;
private int nodes;

public int[] findMedian(int n, int[][] edges, int[][] queries) {
nodes = n;
if (n > 1) {
longMax = (int) Math.ceil(Math.log(n) / Math.log(2));
} else {
longMax = 1;
}
adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int w = edge[2];
adj.get(u).add(new int[] {v, w});
adj.get(v).add(new int[] {u, w});
}
depth = new int[n];
dist = new long[n];
parent = new int[longMax][n];
for (int i = 0; i < longMax; i++) {
Arrays.fill(parent[i], -1);
}
dfs(0, -1, 0, 0L);
buildLcaTable();
int[] ans = new int[queries.length];
int[] sabrelonta;
for (int qIdx = 0; qIdx < queries.length; qIdx++) {
sabrelonta = queries[qIdx];
int u = sabrelonta[0];
int v = sabrelonta[1];
ans[qIdx] = findMedianNode(u, v);
}

return ans;
}

private void dfs(int u, int p, int d, long currentDist) {
depth[u] = d;
parent[0][u] = p;
dist[u] = currentDist;
for (int[] edge : adj.get(u)) {
int v = edge[0];
int w = edge[1];
if (v == p) {
continue;
}
dfs(v, u, d + 1, currentDist + w);
}
}

private void buildLcaTable() {
for (int k = 1; k < longMax; k++) {
for (int node = 0; node < nodes; node++) {
if (parent[k - 1][node] != -1) {
parent[k][node] = parent[k - 1][parent[k - 1][node]];
}
}
}
}

private int getKthAncestor(int u, int k) {
for (int p = longMax - 1; p >= 0; p--) {
if (u == -1) {
break;
}
if (((k >> p) & 1) == 1) {
u = parent[p][u];
}
}
return u;
}

private int getLCA(int u, int v) {
if (depth[u] < depth[v]) {
int temp = u;
u = v;
v = temp;
}
u = getKthAncestor(u, depth[u] - depth[v]);
if (u == v) {
return u;
}
for (int p = longMax - 1; p >= 0; p--) {
if (parent[p][u] != -1 && parent[p][u] != parent[p][v]) {
u = parent[p][u];
v = parent[p][v];
}
}
return parent[0][u];
}

private int findMedianNode(int u, int v) {
if (u == v) {
return u;
}
int lca = getLCA(u, v);
long totalPathWeight = dist[u] + dist[v] - 2 * dist[lca];
long halfWeight = (totalPathWeight + 1) / 2L;
if (dist[u] - dist[lca] >= halfWeight) {
int curr = u;
for (int p = longMax - 1; p >= 0; p--) {
int nextNode = parent[p][curr];
if (nextNode != -1 && (dist[u] - dist[nextNode] < halfWeight)) {
curr = nextNode;
}
}
return parent[0][curr];
} else {
long remainingWeightFromLCA = halfWeight - (dist[u] - dist[lca]);
int curr = v;
for (int p = longMax - 1; p >= 0; p--) {
int nextNode = parent[p][curr];
if (nextNode != -1
&& depth[nextNode] >= depth[lca]
&& (dist[nextNode] - dist[lca]) >= remainingWeightFromLCA) {
curr = nextNode;
}
}
return curr;
}
}
}
Loading
[8]ページ先頭
©2009-2025 Movatter.jp