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

Commite82f6ea

Browse files
authored
Added tasks 3582-3585
1 parent975b81e commite82f6ea

File tree

12 files changed

+574
-0
lines changed

12 files changed

+574
-0
lines changed
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
packageg3501_3600.s3582_generate_tag_for_video_caption;
2+
3+
// #Easy #String #Simulation #2025_06_17_Time_2_ms_(99.93%)_Space_43.54_MB_(89.89%)
4+
5+
publicclassSolution {
6+
publicStringgenerateTag(Stringcaption) {
7+
StringBuildersb =newStringBuilder();
8+
sb.append('#');
9+
booleanspace =false;
10+
caption =caption.trim();
11+
for (inti =0;i <caption.length();i++) {
12+
charc =caption.charAt(i);
13+
if (c ==' ') {
14+
space =true;
15+
}
16+
if (c >='A' &&c <='Z') {
17+
if (space) {
18+
space = !space;
19+
sb.append(c);
20+
}else {
21+
sb.append(Character.toLowerCase(c));
22+
}
23+
}
24+
if (c >='a' &&c <='z') {
25+
if (space) {
26+
space = !space;
27+
sb.append(Character.toUpperCase(c));
28+
}else {
29+
sb.append(c);
30+
}
31+
}
32+
}
33+
if (sb.length() >100) {
34+
returnsb.substring(0,100);
35+
}
36+
returnsb.toString();
37+
}
38+
}
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
3582\. Generate Tag for Video Caption
2+
3+
Easy
4+
5+
You are given a string`caption` representing the caption for a video.
6+
7+
The following actions must be performed**in order** to generate a**valid tag** for the video:
8+
9+
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.
10+
11+
2.**Remove** all characters that are not an English letter,**except** the first`'#'`.
12+
13+
3.**Truncate** the result to a maximum of 100 characters.
14+
15+
16+
Return the**tag** after performing the actions on`caption`.
17+
18+
**Example 1:**
19+
20+
**Input:** caption = "Leetcode daily streak achieved"
21+
22+
**Output:** "#leetcodeDailyStreakAchieved"
23+
24+
**Explanation:**
25+
26+
The first letter for all words except`"leetcode"` should be capitalized.
27+
28+
**Example 2:**
29+
30+
**Input:** caption = "can I Go There"
31+
32+
**Output:** "#canIGoThere"
33+
34+
**Explanation:**
35+
36+
The first letter for all words except`"can"` should be capitalized.
37+
38+
**Example 3:**
39+
40+
**Input:** caption = "hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh"
41+
42+
**Output:** "#hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh"
43+
44+
**Explanation:**
45+
46+
Since the first word has length 101, we need to truncate the last two letters from the word.
47+
48+
**Constraints:**
49+
50+
*`1 <= caption.length <= 150`
51+
*`caption` consists only of English letters and`' '`.
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg3501_3600.s3583_count_special_triplets;
2+
3+
// #Medium #Array #Hash_Table #Counting #2025_06_17_Time_30_ms_(99.81%)_Space_60.90_MB_(89.67%)
4+
5+
publicclassSolution {
6+
publicintspecialTriplets(int[]nums) {
7+
longans =0;
8+
int[]sum =newint[200002];
9+
int[]left =newint[nums.length];
10+
for (inti =0;i <nums.length;i++) {
11+
intcurr =nums[i];
12+
sum[curr]++;
13+
left[i] =sum[curr *2];
14+
}
15+
for (inti =0;i <nums.length;i++) {
16+
intcurr =nums[i];
17+
longleftCount =curr ==0 ?left[i] -1 :left[i];
18+
longrightCount =sum[curr *2] - (long)left[i];
19+
if (leftCount !=0 &&rightCount !=0) {
20+
ans +=leftCount *rightCount;
21+
}
22+
}
23+
return (int) (ans %1000000007);
24+
}
25+
}
Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
3583\. Count Special Triplets
2+
3+
Medium
4+
5+
You are given an integer array`nums`.
6+
7+
A**special triplet** is defined as a triplet of indices`(i, j, k)` such that:
8+
9+
*`0 <= i < j < k < n`, where`n = nums.length`
10+
*`nums[i] == nums[j] * 2`
11+
*`nums[k] == nums[j] * 2`
12+
13+
Return the total number of**special triplets** in the array.
14+
15+
Since the answer may be large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
16+
17+
**Example 1:**
18+
19+
**Input:** nums =[6,3,6]
20+
21+
**Output:** 1
22+
23+
**Explanation:**
24+
25+
The only special triplet is`(i, j, k) = (0, 1, 2)`, where:
26+
27+
*`nums[0] = 6`,`nums[1] = 3`,`nums[2] = 6`
28+
*`nums[0] = nums[1] * 2 = 3 * 2 = 6`
29+
*`nums[2] = nums[1] * 2 = 3 * 2 = 6`
30+
31+
**Example 2:**
32+
33+
**Input:** nums =[0,1,0,0]
34+
35+
**Output:** 1
36+
37+
**Explanation:**
38+
39+
The only special triplet is`(i, j, k) = (0, 2, 3)`, where:
40+
41+
*`nums[0] = 0`,`nums[2] = 0`,`nums[3] = 0`
42+
*`nums[0] = nums[2] * 2 = 0 * 2 = 0`
43+
*`nums[3] = nums[2] * 2 = 0 * 2 = 0`
44+
45+
**Example 3:**
46+
47+
**Input:** nums =[8,4,2,8,4]
48+
49+
**Output:** 2
50+
51+
**Explanation:**
52+
53+
There are exactly two special triplets:
54+
55+
*`(i, j, k) = (0, 1, 3)`
56+
*`nums[0] = 8`,`nums[1] = 4`,`nums[3] = 8`
57+
*`nums[0] = nums[1] * 2 = 4 * 2 = 8`
58+
*`nums[3] = nums[1] * 2 = 4 * 2 = 8`
59+
*`(i, j, k) = (1, 2, 4)`
60+
*`nums[1] = 4`,`nums[2] = 2`,`nums[4] = 4`
61+
*`nums[1] = nums[2] * 2 = 2 * 2 = 4`
62+
*`nums[4] = nums[2] * 2 = 2 * 2 = 4`
63+
64+
**Constraints:**
65+
66+
* <code>3 <= n == nums.length <= 10<sup>5</sup></code>
67+
* <code>0 <= nums[i] <= 10<sup>5</sup></code>
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
packageg3501_3600.s3584_maximum_product_of_first_and_last_elements_of_a_subsequence;
2+
3+
// #Medium #Array #Two_Pointers #2025_06_17_Time_4_ms_(86.42%)_Space_60.92_MB_(51.72%)
4+
5+
publicclassSolution {
6+
publiclongmaximumProduct(int[]nums,intm) {
7+
longma =nums[0];
8+
longmi =nums[0];
9+
longres = (long)nums[0] *nums[m -1];
10+
for (inti =m -1;i <nums.length; ++i) {
11+
ma =Math.max(ma,nums[i -m +1]);
12+
mi =Math.min(mi,nums[i -m +1]);
13+
res =Math.max(res,Math.max(mi *nums[i],ma *nums[i]));
14+
}
15+
returnres;
16+
}
17+
}
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
3584\. Maximum Product of First and Last Elements of a Subsequence
2+
3+
Medium
4+
5+
You are given an integer array`nums` and an integer`m`.
6+
7+
Return the**maximum** product of the first and last elements of any****subsequences**** of`nums` of size`m`.
8+
9+
**Example 1:**
10+
11+
**Input:** nums =[-1,-9,2,3,-2,-3,1], m = 1
12+
13+
**Output:** 81
14+
15+
**Explanation:**
16+
17+
The subsequence`[-9]` has the largest product of the first and last elements:`-9 * -9 = 81`. Therefore, the answer is 81.
18+
19+
**Example 2:**
20+
21+
**Input:** nums =[1,3,-5,5,6,-4], m = 3
22+
23+
**Output:** 20
24+
25+
**Explanation:**
26+
27+
The subsequence`[-5, 6, -4]` has the largest product of the first and last elements.
28+
29+
**Example 3:**
30+
31+
**Input:** nums =[2,-1,2,-6,5,2,-5,7], m = 2
32+
33+
**Output:** 35
34+
35+
**Explanation:**
36+
37+
The subsequence`[5, 7]` has the largest product of the first and last elements.
38+
39+
**Constraints:**
40+
41+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
42+
* <code>-10<sup>5</sup> <= nums[i] <= 10<sup>5</sup></code>
43+
*`1 <= m <= nums.length`
Lines changed: 142 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,142 @@
1+
packageg3501_3600.s3585_find_weighted_median_node_in_tree;
2+
3+
// #Hard #Array #Dynamic_Programming #Tree #Binary_Search #Depth_First_Search
4+
// #2025_06_17_Time_66_ms_(94.96%)_Space_142.62_MB_(49.64%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
importjava.util.List;
9+
10+
@SuppressWarnings("java:S2234")
11+
publicclassSolution {
12+
privateList<List<int[]>>adj;
13+
privateint[]depth;
14+
privatelong[]dist;
15+
privateint[][]parent;
16+
privateintlongMax;
17+
privateintnodes;
18+
19+
publicint[]findMedian(intn,int[][]edges,int[][]queries) {
20+
nodes =n;
21+
if (n >1) {
22+
longMax = (int)Math.ceil(Math.log(n) /Math.log(2));
23+
}else {
24+
longMax =1;
25+
}
26+
adj =newArrayList<>();
27+
for (inti =0;i <n;i++) {
28+
adj.add(newArrayList<>());
29+
}
30+
for (int[]edge :edges) {
31+
intu =edge[0];
32+
intv =edge[1];
33+
intw =edge[2];
34+
adj.get(u).add(newint[] {v,w});
35+
adj.get(v).add(newint[] {u,w});
36+
}
37+
depth =newint[n];
38+
dist =newlong[n];
39+
parent =newint[longMax][n];
40+
for (inti =0;i <longMax;i++) {
41+
Arrays.fill(parent[i], -1);
42+
}
43+
dfs(0, -1,0,0L);
44+
buildLcaTable();
45+
int[]ans =newint[queries.length];
46+
int[]sabrelonta;
47+
for (intqIdx =0;qIdx <queries.length;qIdx++) {
48+
sabrelonta =queries[qIdx];
49+
intu =sabrelonta[0];
50+
intv =sabrelonta[1];
51+
ans[qIdx] =findMedianNode(u,v);
52+
}
53+
54+
returnans;
55+
}
56+
57+
privatevoiddfs(intu,intp,intd,longcurrentDist) {
58+
depth[u] =d;
59+
parent[0][u] =p;
60+
dist[u] =currentDist;
61+
for (int[]edge :adj.get(u)) {
62+
intv =edge[0];
63+
intw =edge[1];
64+
if (v ==p) {
65+
continue;
66+
}
67+
dfs(v,u,d +1,currentDist +w);
68+
}
69+
}
70+
71+
privatevoidbuildLcaTable() {
72+
for (intk =1;k <longMax;k++) {
73+
for (intnode =0;node <nodes;node++) {
74+
if (parent[k -1][node] != -1) {
75+
parent[k][node] =parent[k -1][parent[k -1][node]];
76+
}
77+
}
78+
}
79+
}
80+
81+
privateintgetKthAncestor(intu,intk) {
82+
for (intp =longMax -1;p >=0;p--) {
83+
if (u == -1) {
84+
break;
85+
}
86+
if (((k >>p) &1) ==1) {
87+
u =parent[p][u];
88+
}
89+
}
90+
returnu;
91+
}
92+
93+
privateintgetLCA(intu,intv) {
94+
if (depth[u] <depth[v]) {
95+
inttemp =u;
96+
u =v;
97+
v =temp;
98+
}
99+
u =getKthAncestor(u,depth[u] -depth[v]);
100+
if (u ==v) {
101+
returnu;
102+
}
103+
for (intp =longMax -1;p >=0;p--) {
104+
if (parent[p][u] != -1 &&parent[p][u] !=parent[p][v]) {
105+
u =parent[p][u];
106+
v =parent[p][v];
107+
}
108+
}
109+
returnparent[0][u];
110+
}
111+
112+
privateintfindMedianNode(intu,intv) {
113+
if (u ==v) {
114+
returnu;
115+
}
116+
intlca =getLCA(u,v);
117+
longtotalPathWeight =dist[u] +dist[v] -2 *dist[lca];
118+
longhalfWeight = (totalPathWeight +1) /2L;
119+
if (dist[u] -dist[lca] >=halfWeight) {
120+
intcurr =u;
121+
for (intp =longMax -1;p >=0;p--) {
122+
intnextNode =parent[p][curr];
123+
if (nextNode != -1 && (dist[u] -dist[nextNode] <halfWeight)) {
124+
curr =nextNode;
125+
}
126+
}
127+
returnparent[0][curr];
128+
}else {
129+
longremainingWeightFromLCA =halfWeight - (dist[u] -dist[lca]);
130+
intcurr =v;
131+
for (intp =longMax -1;p >=0;p--) {
132+
intnextNode =parent[p][curr];
133+
if (nextNode != -1
134+
&&depth[nextNode] >=depth[lca]
135+
&& (dist[nextNode] -dist[lca]) >=remainingWeightFromLCA) {
136+
curr =nextNode;
137+
}
138+
}
139+
returncurr;
140+
}
141+
}
142+
}

0 commit comments

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