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

Commitfe9e5c2

Browse files
authored
Added tasks 2742-2747
1 parentfaf7911 commitfe9e5c2

File tree

15 files changed

+515
-0
lines changed

15 files changed

+515
-0
lines changed
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
packageg2701_2800.s2742_painting_the_walls;
2+
3+
// #Hard #Array #Dynamic_Programming #2023_09_23_Time_8_ms_(98.78%)_Space_43_MB_(100.00%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publicintpaintWalls(int[]cost,int[]time) {
9+
intn =cost.length;
10+
int[]dp =newint[n +1];
11+
Arrays.fill(dp, (int)1e9);
12+
dp[0] =0;
13+
14+
for (inti =0;i <n; ++i) {
15+
for (intj =n;j >0; --j) {
16+
dp[j] =Math.min(dp[j],dp[Math.max(j -time[i] -1,0)] +cost[i]);
17+
}
18+
}
19+
20+
returndp[n];
21+
}
22+
}
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
2742\. Painting the Walls
2+
3+
Hard
4+
5+
You are given two**0-indexed** integer arrays,`cost` and`time`, of size`n` representing the costs and the time taken to paint`n` different walls respectively. There are two painters available:
6+
7+
* A** paid painter** that paints the <code>i<sup>th</sup></code> wall in`time[i]` units of time and takes`cost[i]` units of money.
8+
* A** free painter** that paints**any** wall in`1` unit of time at a cost of`0`. But the free painter can only be used if the paid painter is already**occupied**.
9+
10+
Return_the minimum amount of money required to paint the_`n`_walls._
11+
12+
**Example 1:**
13+
14+
**Input:** cost =[1,2,3,2], time =[1,2,3,2]
15+
16+
**Output:** 3
17+
18+
**Explanation:** The walls at index 0 and 1 will be painted by the paid painter, and it will take 3 units of time; meanwhile, the free painter will paint the walls at index 2 and 3, free of cost in 2 units of time. Thus, the total cost is 1 + 2 = 3.
19+
20+
**Example 2:**
21+
22+
**Input:** cost =[2,3,4,2], time =[1,1,1,1]
23+
24+
**Output:** 4
25+
26+
**Explanation:** The walls at index 0 and 3 will be painted by the paid painter, and it will take 2 units of time; meanwhile, the free painter will paint the walls at index 1 and 2, free of cost in 2 units of time. Thus, the total cost is 2 + 2 = 4.
27+
28+
**Constraints:**
29+
30+
*`1 <= cost.length <= 500`
31+
*`cost.length == time.length`
32+
* <code>1 <= cost[i] <= 10<sup>6</sup></code>
33+
*`1 <= time[i] <= 500`
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
packageg2701_2800.s2744_find_maximum_number_of_string_pairs;
2+
3+
// #Easy #Array #String #Hash_Table #Simulation
4+
// #2023_09_23_Time_1_ms_(100.00%)_Space_40.8_MB_(93.18%)
5+
6+
publicclassSolution {
7+
privatebooleanfunc(Stringa,Stringb) {
8+
intn =a.length();
9+
intm =b.length();
10+
if (n !=m) {
11+
returnfalse;
12+
}
13+
for (inti =0;i <n;i++) {
14+
if (a.charAt(i) !=b.charAt(n -1 -i)) {
15+
returnfalse;
16+
}
17+
}
18+
returntrue;
19+
}
20+
21+
publicintmaximumNumberOfStringPairs(String[]words) {
22+
intans =0;
23+
intn =words.length;
24+
for (inti =0;i <n -1;i++) {
25+
for (intj =i +1;j <n;j++) {
26+
if (func(words[i],words[j])) {
27+
ans++;
28+
}
29+
}
30+
}
31+
returnans;
32+
}
33+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
2744\. Find Maximum Number of String Pairs
2+
3+
Easy
4+
5+
You are given a**0-indexed** array`words` consisting of**distinct** strings.
6+
7+
The string`words[i]` can be paired with the string`words[j]` if:
8+
9+
* The string`words[i]` is equal to the reversed string of`words[j]`.
10+
*`0 <= i < j < words.length`.
11+
12+
Return_the**maximum** number of pairs that can be formed from the array_`words`_._
13+
14+
Note that each string can belong in**at most one** pair.
15+
16+
**Example 1:**
17+
18+
**Input:** words =["cd","ac","dc","ca","zz"]
19+
20+
**Output:** 2
21+
22+
**Explanation:** In this example, we can form 2 pair of strings in the following way:
23+
- We pair the 0<sup>th</sup> string with the 2<sup>nd</sup> string, as the reversed string of word[0] is "dc" and is equal to words[2].
24+
- We pair the 1<sup>st</sup> string with the 3<sup>rd</sup> string, as the reversed string of word[1] is "ca" and is equal to words[3].
25+
26+
It can be proven that 2 is the maximum number of pairs that can be formed.
27+
28+
**Example 2:**
29+
30+
**Input:** words =["ab","ba","cc"]
31+
32+
**Output:** 1
33+
34+
**Explanation:** In this example, we can form 1 pair of strings in the following way:
35+
- We pair the 0<sup>th</sup> string with the 1<sup>st</sup> string, as the reversed string of words[1] is "ab" and is equal to words[0].
36+
37+
It can be proven that 1 is the maximum number of pairs that can be formed.
38+
39+
**Example 3:**
40+
41+
**Input:** words =["aa","ab"]
42+
43+
**Output:** 0
44+
45+
**Explanation:** In this example, we are unable to form any pair of strings.
46+
47+
**Constraints:**
48+
49+
*`1 <= words.length <= 50`
50+
*`words[i].length == 2`
51+
*`words` consists of distinct strings.
52+
*`words[i]` contains only lowercase English letters.
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
packageg2701_2800.s2745_construct_the_longest_new_string;
2+
3+
// #Medium #Math #Greedy #Brainteaser #2023_09_23_Time_1_ms_(100.00%)_Space_40.1_MB_(66.80%)
4+
5+
publicclassSolution {
6+
publicintlongestString(intx,inty,intz) {
7+
intmin =Math.min(x,y);
8+
intres =0;
9+
if (x ==y) {
10+
res =2 *min +z;
11+
}else {
12+
res =2 *min +1 +z;
13+
}
14+
returnres *2;
15+
}
16+
}
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
2745\. Construct the Longest New String
2+
3+
Medium
4+
5+
You are given three integers`x`,`y`, and`z`.
6+
7+
You have`x` strings equal to`"AA"`,`y` strings equal to`"BB"`, and`z` strings equal to`"AB"`. You want to choose some (possibly all or none) of these strings and concactenate them in some order to form a new string. This new string must not contain`"AAA"` or`"BBB"` as a substring.
8+
9+
Return_the maximum possible length of the new string_.
10+
11+
A**substring** is a contiguous**non-empty** sequence of characters within a string.
12+
13+
**Example 1:**
14+
15+
**Input:** x = 2, y = 5, z = 1
16+
17+
**Output:** 12
18+
19+
**Explanation:** We can concactenate the strings "BB", "AA", "BB", "AA", "BB", and "AB" in that order. Then, our new string is "BBAABBAABBAB". That string has length 12, and we can show that it is impossible to construct a string of longer length.
20+
21+
**Example 2:**
22+
23+
**Input:** x = 3, y = 2, z = 2
24+
25+
**Output:** 14
26+
27+
**Explanation:** We can concactenate the strings "AB", "AB", "AA", "BB", "AA", "BB", and "AA" in that order. Then, our new string is "ABABAABBAABBAA". That string has length 14, and we can show that it is impossible to construct a string of longer length.
28+
29+
**Constraints:**
30+
31+
*`1 <= x, y, z <= 50`
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
packageg2701_2800.s2746_decremental_string_concatenation;
2+
3+
// #Medium #Array #String #Dynamic_Programming
4+
// #2023_09_24_Time_34_ms_(85.89%)_Space_50.1_MB_(44.78%)
5+
6+
publicclassSolution {
7+
privateInteger[][][]dp;
8+
9+
publicintminimizeConcatenatedLength(String[]words) {
10+
intn =words.length;
11+
dp =newInteger[n][26][26];
12+
StringcurWord =words[0];
13+
intcurLen =curWord.length();
14+
charcurFirst =curWord.charAt(0);
15+
charcurLast =curWord.charAt(curLen -1);
16+
returncurLen +solve(1,curFirst,curLast,n,words);
17+
}
18+
19+
privateintsolve(intidx,charprevFirst,charprevLast,intn,String[]words) {
20+
if (idx ==n) {
21+
return0;
22+
}
23+
if (dp[idx][prevFirst -'a'][prevLast -'a'] !=null) {
24+
returndp[idx][prevFirst -'a'][prevLast -'a'];
25+
}
26+
StringcurWord =words[idx];
27+
intcurLen =curWord.length();
28+
charcurFirst =curWord.charAt(0);
29+
charcurLast =curWord.charAt(curLen -1);
30+
intans = (int)1e9;
31+
if (prevFirst ==curLast) {
32+
ans =Math.min(ans,curLen -1 +solve(idx +1,curFirst,prevLast,n,words));
33+
}else {
34+
ans =Math.min(ans,curLen +solve(idx +1,curFirst,prevLast,n,words));
35+
}
36+
if (prevLast ==curFirst) {
37+
ans =Math.min(ans,curLen -1 +solve(idx +1,prevFirst,curLast,n,words));
38+
}else {
39+
ans =Math.min(ans,curLen +solve(idx +1,prevFirst,curLast,n,words));
40+
}
41+
dp[idx][prevFirst -'a'][prevLast -'a'] =ans;
42+
returnans;
43+
}
44+
}
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
2746\. Decremental String Concatenation
2+
3+
Medium
4+
5+
You are given a**0-indexed** array`words` containing`n` strings.
6+
7+
Let's define a**join** operation`join(x, y)` between two strings`x` and`y` as concatenating them into`xy`. However, if the last character of`x` is equal to the first character of`y`, one of them is**deleted**.
8+
9+
For example`join("ab", "ba") = "aba"` and`join("ab", "cde") = "abcde"`.
10+
11+
You are to perform`n - 1`**join** operations. Let <code>str<sub>0</sub> = words[0]</code>. Starting from`i = 1` up to`i = n - 1`, for the <code>i<sup>th</sup></code> operation, you can do one of the following:
12+
13+
* Make <code>str<sub>i</sub> = join(str<sub>i - 1</sub>, words[i])</code>
14+
* Make <code>str<sub>i</sub> = join(words[i], str<sub>i - 1</sub>)</code>
15+
16+
Your task is to**minimize** the length of <code>str<sub>n - 1</sub></code>.
17+
18+
Return_an integer denoting the minimum possible length of_ <code>str<sub>n - 1</sub></code>.
19+
20+
**Example 1:**
21+
22+
**Input:** words =["aa","ab","bc"]
23+
24+
**Output:** 4
25+
26+
**Explanation:** In this example, we can perform join operations in the following order to minimize the length of str<sub>2</sub>:
27+
28+
str<sub>0</sub> = "aa"
29+
30+
str<sub>1</sub> = join(str<sub>0</sub>, "ab") = "aab"
31+
32+
str<sub>2</sub> = join(str<sub>1</sub>, "bc") = "aabc"
33+
34+
It can be shown that the minimum possible length of str<sub>2</sub> is 4.
35+
36+
**Example 2:**
37+
38+
**Input:** words =["ab","b"]
39+
40+
**Output:** 2
41+
42+
**Explanation:** In this example, str<sub>0</sub> = "ab", there are two ways to get str<sub>1</sub>: join(str<sub>0</sub>, "b") = "ab" or join("b", str<sub>0</sub>) = "bab". The first string, "ab", has the minimum length. Hence, the answer is 2.
43+
44+
**Example 3:**
45+
46+
**Input:** words =["aaa","c","aba"]
47+
48+
**Output:** 6
49+
50+
**Explanation:** In this example, we can perform join operations in the following order to minimize the length of str<sub>2</sub>:
51+
52+
str<sub>0</sub> = "aaa"
53+
54+
str<sub>1</sub> = join(str<sub>0</sub>, "c") = "aaac"
55+
56+
str<sub>2</sub> = join("aba", str<sub>1</sub>) = "abaaac"
57+
58+
It can be shown that the minimum possible length of str<sub>2</sub> is 6.
59+
60+
**Constraints:**
61+
62+
*`1 <= words.length <= 1000`
63+
*`1 <= words[i].length <= 50`
64+
* Each character in`words[i]` is an English lowercase letter
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
packageg2701_2800.s2747_count_zero_request_servers;
2+
3+
// #Medium #Array #Hash_Table #Sorting #Sliding_Window
4+
// #2023_09_24_Time_43_ms_(76.92%)_Space_85.7_MB_(63.85%)
5+
6+
importjava.util.Arrays;
7+
importjava.util.Comparator;
8+
importjava.util.HashMap;
9+
10+
publicclassSolution {
11+
publicint[]countServers(intn,int[][]logs,intx,int[]qs) {
12+
intm =qs.length;
13+
varvalIdx =newint[m][2];
14+
for (inti =0;i <m;i++) {
15+
valIdx[i] =newint[] {qs[i],i};
16+
}
17+
Arrays.sort(valIdx,Comparator.comparingInt(a ->a[0]));
18+
Arrays.sort(logs,Comparator.comparingInt(a ->a[1]));
19+
intl =0;
20+
intr =0;
21+
varres =newint[m];
22+
varservCount =newHashMap<Integer,Integer>();
23+
for (varq :valIdx) {
24+
intrVal =q[0];
25+
intlVal =q[0] -x;
26+
inti =q[1];
27+
while (r <logs.length &&logs[r][1] <=rVal) {
28+
servCount.merge(logs[r++][0],1,Integer::sum);
29+
}
30+
while (l <r &&logs[l][1] <lVal) {
31+
servCount.compute(logs[l][0], (k,v) ->v -1);
32+
servCount.remove(logs[l][0],0);
33+
l++;
34+
}
35+
res[i] =n -servCount.size();
36+
}
37+
returnres;
38+
}
39+
}
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
2747\. Count Zero Request Servers
2+
3+
Medium
4+
5+
You are given an integer`n` denoting the total number of servers and a**2D****0-indexed** integer array`logs`, where`logs[i] = [server_id, time]` denotes that the server with id`server_id` received a request at time`time`.
6+
7+
You are also given an integer`x` and a**0-indexed** integer array`queries`.
8+
9+
Return_a**0-indexed** integer array_`arr`_of length_`queries.length`_where_`arr[i]`_represents the number of servers that**did not receive** any requests during the time interval_`[queries[i] - x, queries[i]]`.
10+
11+
Note that the time intervals are inclusive.
12+
13+
**Example 1:**
14+
15+
**Input:** n = 3, logs =[[1,3],[2,6],[1,5]], x = 5, queries =[10,11]
16+
17+
**Output:**[1,2]
18+
19+
**Explanation:**
20+
21+
For queries[0]: The servers with ids 1 and 2 get requests in the duration of[5, 10].
22+
23+
Hence, only server 3 gets zero requests.
24+
25+
For queries[1]: Only the server with id 2 gets a request in duration of[6,11]. Hence, the servers with ids 1 and 3 are the only servers that do not receive any requests during that time period.
26+
27+
**Example 2:**
28+
29+
**Input:** n = 3, logs =[[2,4],[2,1],[1,2],[3,1]], x = 2, queries =[3,4]
30+
31+
**Output:**[0,1]
32+
33+
**Explanation:**
34+
35+
For queries[0]: All servers get at least one request in the duration of[1, 3].
36+
37+
For queries[1]: Only server with id 3 gets no request in the duration[2,4].
38+
39+
**Constraints:**
40+
41+
* <code>1 <= n <= 10<sup>5</sup></code>
42+
* <code>1 <= logs.length <= 10<sup>5</sup></code>
43+
* <code>1 <= queries.length <= 10<sup>5</sup></code>
44+
*`logs[i].length == 2`
45+
*`1 <= logs[i][0] <= n`
46+
* <code>1 <= logs[i][1] <= 10<sup>6</sup></code>
47+
* <code>1 <= x <= 10<sup>5</sup></code>
48+
* <code>x < queries[i] <= 10<sup>6</sup></code>

0 commit comments

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