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

Commitf69942d

Browse files
authored
Added tasks 3295-3298
1 parentd9c7bc4 commitf69942d

File tree

12 files changed

+411
-0
lines changed

12 files changed

+411
-0
lines changed
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
packageg3201_3300.s3295_report_spam_message;
2+
3+
// #Medium #Array #String #Hash_Table #2024_09_24_Time_39_ms_(98.87%)_Space_85.4_MB_(9.13%)
4+
5+
importjava.util.Arrays;
6+
importjava.util.HashSet;
7+
importjava.util.Set;
8+
9+
publicclassSolution {
10+
publicbooleanreportSpam(String[]message,String[]bannedWords) {
11+
Set<String>bannedUnique =newHashSet<>(Arrays.asList(bannedWords));
12+
intbannedCount =0;
13+
for (Stringmsg :message) {
14+
if (bannedUnique.contains(msg)) {
15+
bannedCount++;
16+
}
17+
if (bannedCount ==2) {
18+
returntrue;
19+
}
20+
}
21+
returnfalse;
22+
}
23+
}
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
3295\. Report Spam Message
2+
3+
Medium
4+
5+
You are given an array of strings`message` and an array of strings`bannedWords`.
6+
7+
An array of words is considered**spam** if there are**at least** two words in it that**exactly** match any word in`bannedWords`.
8+
9+
Return`true` if the array`message` is spam, and`false` otherwise.
10+
11+
**Example 1:**
12+
13+
**Input:** message =["hello","world","leetcode"], bannedWords =["world","hello"]
14+
15+
**Output:** true
16+
17+
**Explanation:**
18+
19+
The words`"hello"` and`"world"` from the`message` array both appear in the`bannedWords` array.
20+
21+
**Example 2:**
22+
23+
**Input:** message =["hello","programming","fun"], bannedWords =["world","programming","leetcode"]
24+
25+
**Output:** false
26+
27+
**Explanation:**
28+
29+
Only one word from the`message` array (`"programming"`) appears in the`bannedWords` array.
30+
31+
**Constraints:**
32+
33+
* <code>1 <= message.length, bannedWords.length <= 10<sup>5</sup></code>
34+
*`1 <= message[i].length, bannedWords[i].length <= 15`
35+
*`message[i]` and`bannedWords[i]` consist only of lowercase English letters.
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
packageg3201_3300.s3296_minimum_number_of_seconds_to_make_mountain_height_zero;
2+
3+
// #Medium #Array #Math #Binary_Search #2024_09_24_Time_6_ms_(100.00%)_Space_45.2_MB_(90.23%)
4+
5+
publicclassSolution {
6+
publiclongminNumberOfSeconds(intmountainHeight,int[]workerTimes) {
7+
longleft =0;
8+
longright = (long)mountainHeight * (mountainHeight +1) /2 *workerTimes[0];
9+
while (left <right) {
10+
longmid =left + (right -left) /2;
11+
if (canReduceMountain(workerTimes,mountainHeight,mid)) {
12+
right =mid;
13+
}else {
14+
left =mid +1;
15+
}
16+
}
17+
returnleft;
18+
}
19+
20+
privatebooleancanReduceMountain(int[]workerTimes,intmountainHeight,longtimeLimit) {
21+
longtotalHeightReduced =0;
22+
for (intworkerTime :workerTimes) {
23+
longmaxHeightThisWorker =
24+
(long) (Math.sqrt(2.0 *timeLimit /workerTime +0.25) -0.5);
25+
totalHeightReduced +=maxHeightThisWorker;
26+
if (totalHeightReduced >=mountainHeight) {
27+
returntrue;
28+
}
29+
}
30+
returntotalHeightReduced >=mountainHeight;
31+
}
32+
}
Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
3296\. Minimum Number of Seconds to Make Mountain Height Zero
2+
3+
Medium
4+
5+
You are given an integer`mountainHeight` denoting the height of a mountain.
6+
7+
You are also given an integer array`workerTimes` representing the work time of workers in**seconds**.
8+
9+
The workers work**simultaneously** to**reduce** the height of the mountain. For worker`i`:
10+
11+
* To decrease the mountain's height by`x`, it takes`workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x` seconds. For example:
12+
* To reduce the height of the mountain by 1, it takes`workerTimes[i]` seconds.
13+
* To reduce the height of the mountain by 2, it takes`workerTimes[i] + workerTimes[i] * 2` seconds, and so on.
14+
15+
Return an integer representing the**minimum** number of seconds required for the workers to make the height of the mountain 0.
16+
17+
**Example 1:**
18+
19+
**Input:** mountainHeight = 4, workerTimes =[2,1,1]
20+
21+
**Output:** 3
22+
23+
**Explanation:**
24+
25+
One way the height of the mountain can be reduced to 0 is:
26+
27+
* Worker 0 reduces the height by 1, taking`workerTimes[0] = 2` seconds.
28+
* Worker 1 reduces the height by 2, taking`workerTimes[1] + workerTimes[1] * 2 = 3` seconds.
29+
* Worker 2 reduces the height by 1, taking`workerTimes[2] = 1` second.
30+
31+
Since they work simultaneously, the minimum time needed is`max(2, 3, 1) = 3` seconds.
32+
33+
**Example 2:**
34+
35+
**Input:** mountainHeight = 10, workerTimes =[3,2,2,4]
36+
37+
**Output:** 12
38+
39+
**Explanation:**
40+
41+
* Worker 0 reduces the height by 2, taking`workerTimes[0] + workerTimes[0] * 2 = 9` seconds.
42+
* Worker 1 reduces the height by 3, taking`workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12` seconds.
43+
* Worker 2 reduces the height by 3, taking`workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12` seconds.
44+
* Worker 3 reduces the height by 2, taking`workerTimes[3] + workerTimes[3] * 2 = 12` seconds.
45+
46+
The number of seconds needed is`max(9, 12, 12, 12) = 12` seconds.
47+
48+
**Example 3:**
49+
50+
**Input:** mountainHeight = 5, workerTimes =[1]
51+
52+
**Output:** 15
53+
54+
**Explanation:**
55+
56+
There is only one worker in this example, so the answer is`workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15`.
57+
58+
**Constraints:**
59+
60+
* <code>1 <= mountainHeight <= 10<sup>5</sup></code>
61+
* <code>1 <= workerTimes.length <= 10<sup>4</sup></code>
62+
* <code>1 <= workerTimes[i] <= 10<sup>6</sup></code>
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
packageg3201_3300.s3297_count_substrings_that_can_be_rearranged_to_contain_a_string_i;
2+
3+
// #Medium #String #Hash_Table #Sliding_Window #2024_09_24_Time_5_ms_(99.40%)_Space_44.9_MB_(51.04%)
4+
5+
publicclassSolution {
6+
publiclongvalidSubstringCount(Stringword1,Stringword2) {
7+
longres =0;
8+
intkeys =0;
9+
intlen =word1.length();
10+
int[]count =newint[26];
11+
boolean[]letters =newboolean[26];
12+
for (charletter :word2.toCharArray()) {
13+
intindex =letter -'a';
14+
if (count[index]++ ==0) {
15+
letters[index] =true;
16+
keys++;
17+
}
18+
}
19+
intstart =0;
20+
intend =0;
21+
while (end <len) {
22+
intindex =word1.charAt(end) -'a';
23+
if (!letters[index]) {
24+
end++;
25+
continue;
26+
}
27+
if (--count[index] ==0) {
28+
--keys;
29+
}
30+
while (keys ==0) {
31+
res +=len -end;
32+
intbeginIndex =word1.charAt(start++) -'a';
33+
if (!letters[beginIndex]) {
34+
continue;
35+
}
36+
if (count[beginIndex]++ ==0) {
37+
keys++;
38+
}
39+
}
40+
end++;
41+
}
42+
returnres;
43+
}
44+
}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
3297\. Count Substrings That Can Be Rearranged to Contain a String I
2+
3+
Medium
4+
5+
You are given two strings`word1` and`word2`.
6+
7+
A string`x` is called**valid** if`x` can be rearranged to have`word2` as a prefix.
8+
9+
Return the total number of**valid** substrings of`word1`.
10+
11+
**Example 1:**
12+
13+
**Input:** word1 = "bcca", word2 = "abc"
14+
15+
**Output:** 1
16+
17+
**Explanation:**
18+
19+
The only valid substring is`"bcca"` which can be rearranged to`"abcc"` having`"abc"` as a prefix.
20+
21+
**Example 2:**
22+
23+
**Input:** word1 = "abcabc", word2 = "abc"
24+
25+
**Output:** 10
26+
27+
**Explanation:**
28+
29+
All the substrings except substrings of size 1 and size 2 are valid.
30+
31+
**Example 3:**
32+
33+
**Input:** word1 = "abcabc", word2 = "aaabc"
34+
35+
**Output:** 0
36+
37+
**Constraints:**
38+
39+
* <code>1 <= word1.length <= 10<sup>5</sup></code>
40+
* <code>1 <= word2.length <= 10<sup>4</sup></code>
41+
*`word1` and`word2` consist only of lowercase English letters.
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
packageg3201_3300.s3298_count_substrings_that_can_be_rearranged_to_contain_a_string_ii;
2+
3+
// #Hard #String #Hash_Table #Sliding_Window #2024_09_24_Time_31_ms_(100.00%)_Space_56.1_MB_(68.76%)
4+
5+
publicclassSolution {
6+
publiclongvalidSubstringCount(Stringword1,Stringword2) {
7+
char[]ar =word1.toCharArray();
8+
intn =ar.length;
9+
char[]temp =word2.toCharArray();
10+
int[]f =newint[26];
11+
for (chari :temp) {
12+
f[i -97]++;
13+
}
14+
longans =0;
15+
intneeded =temp.length;
16+
intbeg =0;
17+
intend =0;
18+
while (end <n) {
19+
if (f[ar[end] -97]-- >0) {
20+
needed--;
21+
}
22+
while (needed ==0) {
23+
// All substrings from [beg, i], where end <= i < n are valid
24+
ans +=n -end;
25+
// Shrink
26+
if (f[ar[beg++] -97]++ ==0) {
27+
needed++;
28+
}
29+
}
30+
end++;
31+
}
32+
returnans;
33+
}
34+
}
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
3298\. Count Substrings That Can Be Rearranged to Contain a String II
2+
3+
Hard
4+
5+
You are given two strings`word1` and`word2`.
6+
7+
A string`x` is called**valid** if`x` can be rearranged to have`word2` as a prefix.
8+
9+
Return the total number of**valid** substrings of`word1`.
10+
11+
**Note** that the memory limits in this problem are**smaller** than usual, so you**must** implement a solution with a_linear_ runtime complexity.
12+
13+
**Example 1:**
14+
15+
**Input:** word1 = "bcca", word2 = "abc"
16+
17+
**Output:** 1
18+
19+
**Explanation:**
20+
21+
The only valid substring is`"bcca"` which can be rearranged to`"abcc"` having`"abc"` as a prefix.
22+
23+
**Example 2:**
24+
25+
**Input:** word1 = "abcabc", word2 = "abc"
26+
27+
**Output:** 10
28+
29+
**Explanation:**
30+
31+
All the substrings except substrings of size 1 and size 2 are valid.
32+
33+
**Example 3:**
34+
35+
**Input:** word1 = "abcabc", word2 = "aaabc"
36+
37+
**Output:** 0
38+
39+
**Constraints:**
40+
41+
* <code>1 <= word1.length <= 10<sup>6</sup></code>
42+
* <code>1 <= word2.length <= 10<sup>4</sup></code>
43+
*`word1` and`word2` consist only of lowercase English letters.
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
packageg3201_3300.s3295_report_spam_message;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidreportSpam() {
11+
assertThat(
12+
newSolution()
13+
.reportSpam(
14+
newString[] {"hello","world","leetcode"},
15+
newString[] {"world","hello"}),
16+
equalTo(true));
17+
}
18+
19+
@Test
20+
voidreportSpam2() {
21+
assertThat(
22+
newSolution()
23+
.reportSpam(
24+
newString[] {"hello","programming","fun"},
25+
newString[] {"world","programming","leetcode"}),
26+
equalTo(false));
27+
}
28+
}
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
packageg3201_3300.s3296_minimum_number_of_seconds_to_make_mountain_height_zero;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidminNumberOfSeconds() {
11+
assertThat(newSolution().minNumberOfSeconds(4,newint[] {2,1,1}),equalTo(3L));
12+
}
13+
14+
@Test
15+
voidminNumberOfSeconds2() {
16+
assertThat(newSolution().minNumberOfSeconds(10,newint[] {3,2,2,4}),equalTo(12L));
17+
}
18+
19+
@Test
20+
voidminNumberOfSeconds3() {
21+
assertThat(newSolution().minNumberOfSeconds(5,newint[] {1}),equalTo(15L));
22+
}
23+
}

0 commit comments

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