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

Commit76f8c93

Browse files
authored
Added tasks 3330-3337
1 parent30be440 commit76f8c93

File tree

24 files changed

+1003
-0
lines changed

24 files changed

+1003
-0
lines changed
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
packageg3301_3400.s3330_find_the_original_typed_string_i;
2+
3+
// #Easy #String #2024_10_29_Time_1_ms_(96.13%)_Space_42_MB_(72.46%)
4+
5+
publicclassSolution {
6+
publicintpossibleStringCount(Stringword) {
7+
intn =word.length();
8+
intcount =1;
9+
charpre =word.charAt(0);
10+
inttemp =0;
11+
for (inti =1;i <n;i++) {
12+
charch =word.charAt(i);
13+
if (ch ==pre) {
14+
temp++;
15+
}else {
16+
if (temp >=1) {
17+
count +=temp;
18+
}
19+
temp =0;
20+
pre =ch;
21+
}
22+
}
23+
if (temp >=1) {
24+
count +=temp;
25+
}
26+
returncount;
27+
}
28+
}
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
3330\. Find the Original Typed String I
2+
3+
Easy
4+
5+
Alice is attempting to type a specific string on her computer. However, she tends to be clumsy and**may** press a key for too long, resulting in a character being typed**multiple** times.
6+
7+
Although Alice tried to focus on her typing, she is aware that she may still have done this**at most**_once_.
8+
9+
You are given a string`word`, which represents the**final** output displayed on Alice's screen.
10+
11+
Return the total number of_possible_ original strings that Alice_might_ have intended to type.
12+
13+
**Example 1:**
14+
15+
**Input:** word = "abbcccc"
16+
17+
**Output:** 5
18+
19+
**Explanation:**
20+
21+
The possible strings are:`"abbcccc"`,`"abbccc"`,`"abbcc"`,`"abbc"`, and`"abcccc"`.
22+
23+
**Example 2:**
24+
25+
**Input:** word = "abcd"
26+
27+
**Output:** 1
28+
29+
**Explanation:**
30+
31+
The only possible string is`"abcd"`.
32+
33+
**Example 3:**
34+
35+
**Input:** word = "aaaa"
36+
37+
**Output:** 4
38+
39+
**Constraints:**
40+
41+
*`1 <= word.length <= 100`
42+
*`word` consists only of lowercase English letters.
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
packageg3301_3400.s3331_find_subtree_sizes_after_changes;
2+
3+
// #Medium #Array #String #Hash_Table #Tree #Depth_First_Search
4+
// #2024_10_29_Time_166_ms_(52.73%)_Space_86.3_MB_(8.86%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.HashMap;
8+
9+
publicclassSolution {
10+
privateint[]finalAns;
11+
12+
publicint[]findSubtreeSizes(int[]parent,Strings) {
13+
intn =parent.length;
14+
char[]arr =s.toCharArray();
15+
int[]newParent =newint[n];
16+
finalAns =newint[n];
17+
HashMap<Integer,ArrayList<Integer>>tree =newHashMap<>();
18+
19+
for (inti =1;i <n;i++) {
20+
intparentNode =parent[i];
21+
newParent[i] =parentNode;
22+
while (parentNode != -1) {
23+
if (arr[parentNode] ==arr[i]) {
24+
newParent[i] =parentNode;
25+
break;
26+
}
27+
parentNode =parent[parentNode];
28+
}
29+
}
30+
31+
for (inti =1;i <n;i++) {
32+
if (!tree.containsKey(newParent[i])) {
33+
tree.put(newParent[i],newArrayList<>());
34+
}
35+
36+
tree.get(newParent[i]).add(i);
37+
}
38+
39+
findNodes(0,tree);
40+
returnfinalAns;
41+
}
42+
43+
privateintfindNodes(intparent,HashMap<Integer,ArrayList<Integer>>tree) {
44+
intcount =1;
45+
if (tree.containsKey(parent)) {
46+
for (inti :tree.get(parent)) {
47+
count +=findNodes(i,tree);
48+
}
49+
}
50+
finalAns[parent] =count;
51+
returncount;
52+
}
53+
}
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
3331\. Find Subtree Sizes After Changes
2+
3+
Medium
4+
5+
You are given a tree rooted at node 0 that consists of`n` nodes numbered from`0` to`n - 1`. The tree is represented by an array`parent` of size`n`, where`parent[i]` is the parent of node`i`. Since node 0 is the root,`parent[0] == -1`.
6+
7+
You are also given a string`s` of length`n`, where`s[i]` is the character assigned to node`i`.
8+
9+
We make the following changes on the tree**one** time**simultaneously** for all nodes`x` from`1` to`n - 1`:
10+
11+
* Find the**closest** node`y` to node`x` such that`y` is an ancestor of`x`, and`s[x] == s[y]`.
12+
* If node`y` does not exist, do nothing.
13+
* Otherwise,**remove** the edge between`x` and its current parent and make node`y` the new parent of`x` by adding an edge between them.
14+
15+
Return an array`answer` of size`n` where`answer[i]` is the**size** of the subtree rooted at node`i` in the**final** tree.
16+
17+
A**subtree** of`treeName` is a tree consisting of a node in`treeName` and all of its descendants.
18+
19+
**Example 1:**
20+
21+
**Input:** parent =[-1,0,0,1,1,1], s = "abaabc"
22+
23+
**Output:**[6,3,1,1,1,1]
24+
25+
**Explanation:**
26+
27+
![](https://assets.leetcode.com/uploads/2024/08/15/graphex1drawio.png)
28+
29+
The parent of node 3 will change from node 1 to node 0.
30+
31+
**Example 2:**
32+
33+
**Input:** parent =[-1,0,4,0,1], s = "abbba"
34+
35+
**Output:**[5,2,1,1,1]
36+
37+
**Explanation:**
38+
39+
![](https://assets.leetcode.com/uploads/2024/08/20/exgraph2drawio.png)
40+
41+
The following changes will happen at the same time:
42+
43+
* The parent of node 4 will change from node 1 to node 0.
44+
* The parent of node 2 will change from node 4 to node 1.
45+
46+
**Constraints:**
47+
48+
*`n == parent.length == s.length`
49+
* <code>1 <= n <= 10<sup>5</sup></code>
50+
*`0 <= parent[i] <= n - 1` for all`i >= 1`.
51+
*`parent[0] == -1`
52+
*`parent` represents a valid tree.
53+
*`s` consists only of lowercase English letters.
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
packageg3301_3400.s3332_maximum_points_tourist_can_earn;
2+
3+
// #Medium #Array #Dynamic_Programming #Matrix #2024_10_29_Time_53_ms_(100.00%)_Space_55_MB_(78.55%)
4+
5+
publicclassSolution {
6+
publicintmaxScore(intn,intk,int[][]stayScores,int[][]travelScores) {
7+
// dp[day][city]
8+
int[][]dp =newint[k +1][n];
9+
intresult =0;
10+
for (intday =k -1;day >=0;day--) {
11+
for (intcity =0;city <n;city++) {
12+
intstayScore =stayScores[day][city] +dp[day +1][city];
13+
inttravelScore =0;
14+
for (intnextCity =0;nextCity <n;nextCity++) {
15+
intnextScore =travelScores[city][nextCity] +dp[day +1][nextCity];
16+
travelScore =Math.max(nextScore,travelScore);
17+
}
18+
dp[day][city] =Math.max(stayScore,travelScore);
19+
result =Math.max(dp[day][city],result);
20+
}
21+
}
22+
returnresult;
23+
}
24+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
3332\. Maximum Points Tourist Can Earn
2+
3+
Medium
4+
5+
You are given two integers,`n` and`k`, along with two 2D integer arrays,`stayScore` and`travelScore`.
6+
7+
A tourist is visiting a country with`n` cities, where each city is**directly** connected to every other city. The tourist's journey consists of**exactly**`k`**0-indexed** days, and they can choose**any** city as their starting point.
8+
9+
Each day, the tourist has two choices:
10+
11+
***Stay in the current city**: If the tourist stays in their current city`curr` during day`i`, they will earn`stayScore[i][curr]` points.
12+
***Move to another city**: If the tourist moves from their current city`curr` to city`dest`, they will earn`travelScore[curr][dest]` points.
13+
14+
Return the**maximum** possible points the tourist can earn.
15+
16+
**Example 1:**
17+
18+
**Input:** n = 2, k = 1, stayScore =[[2,3]], travelScore =[[0,2],[1,0]]
19+
20+
**Output:** 3
21+
22+
**Explanation:**
23+
24+
The tourist earns the maximum number of points by starting in city 1 and staying in that city.
25+
26+
**Example 2:**
27+
28+
**Input:** n = 3, k = 2, stayScore =[[3,4,2],[2,1,2]], travelScore =[[0,2,1],[2,0,4],[3,2,0]]
29+
30+
**Output:** 8
31+
32+
**Explanation:**
33+
34+
The tourist earns the maximum number of points by starting in city 1, staying in that city on day 0, and traveling to city 2 on day 1.
35+
36+
**Constraints:**
37+
38+
*`1 <= n <= 200`
39+
*`1 <= k <= 200`
40+
*`n == travelScore.length == travelScore[i].length == stayScore[i].length`
41+
*`k == stayScore.length`
42+
*`1 <= stayScore[i][j] <= 100`
43+
*`0 <= travelScore[i][j] <= 100`
44+
*`travelScore[i][i] == 0`
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
packageg3301_3400.s3333_find_the_original_typed_string_ii;
2+
3+
// #Hard #String #Dynamic_Programming #Prefix_Sum
4+
// #2024_10_29_Time_89_ms_(90.20%)_Space_55.6_MB_(40.38%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
privatestaticfinallongMOD = (long)1e9 +7;
11+
12+
publicintpossibleStringCount(Stringword,intk) {
13+
List<Integer>list =newArrayList<>();
14+
intn =word.length();
15+
inti =0;
16+
while (i <n) {
17+
intj =i +1;
18+
while (j <n &&word.charAt(j) ==word.charAt(j -1)) {
19+
j++;
20+
}
21+
list.add(j -i);
22+
i =j;
23+
}
24+
intm =list.size();
25+
long[]power =newlong[m];
26+
power[m -1] =list.get(m -1);
27+
for (i =m -2;i >=0;i--) {
28+
power[i] = (power[i +1] *list.get(i)) %MOD;
29+
}
30+
if (m >=k) {
31+
return (int)power[0];
32+
}
33+
long[][]dp =newlong[m][k -m +1];
34+
for (i =0;i <k -m +1;i++) {
35+
if (list.get(m -1) +i +m >k) {
36+
dp[m -1][i] =list.get(m -1) - (long) (k -m -i);
37+
}
38+
}
39+
for (i =m -2;i >=0;i--) {
40+
longsum = (dp[i +1][k -m] *list.get(i)) %MOD;
41+
for (intj =k -m;j >=0;j--) {
42+
sum +=dp[i +1][j];
43+
if (j +list.get(i) >k -m) {
44+
sum = (sum -dp[i +1][k -m] +MOD) %MOD;
45+
}else {
46+
sum = (sum -dp[i +1][j +list.get(i)] +MOD) %MOD;
47+
}
48+
dp[i][j] =sum;
49+
}
50+
}
51+
return (int)dp[0][0];
52+
}
53+
}
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
3333\. Find the Original Typed String II
2+
3+
Hard
4+
5+
Alice is attempting to type a specific string on her computer. However, she tends to be clumsy and**may** press a key for too long, resulting in a character being typed**multiple** times.
6+
7+
You are given a string`word`, which represents the**final** output displayed on Alice's screen. You are also given a**positive** integer`k`.
8+
9+
Return the total number of_possible_ original strings that Alice_might_ have intended to type, if she was trying to type a string of size**at least**`k`.
10+
11+
Since the answer may be very large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
12+
13+
**Example 1:**
14+
15+
**Input:** word = "aabbccdd", k = 7
16+
17+
**Output:** 5
18+
19+
**Explanation:**
20+
21+
The possible strings are:`"aabbccdd"`,`"aabbccd"`,`"aabbcdd"`,`"aabccdd"`, and`"abbccdd"`.
22+
23+
**Example 2:**
24+
25+
**Input:** word = "aabbccdd", k = 8
26+
27+
**Output:** 1
28+
29+
**Explanation:**
30+
31+
The only possible string is`"aabbccdd"`.
32+
33+
**Example 3:**
34+
35+
**Input:** word = "aaabbb", k = 3
36+
37+
**Output:** 8
38+
39+
**Constraints:**
40+
41+
* <code>1 <= word.length <= 5 * 10<sup>5</sup></code>
42+
*`word` consists only of lowercase English letters.
43+
*`1 <= k <= 2000`

0 commit comments

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