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

Commitf279792

Browse files
authored
Added tasks 2809-2824
1 parentccd5c9c commitf279792

File tree

30 files changed

+1215
-0
lines changed

30 files changed

+1215
-0
lines changed
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
packageg2801_2900.s2809_minimum_time_to_make_array_sum_at_most_x;
2+
3+
// #Hard #Array #Dynamic_Programming #Sorting #2023_11_20_Time_14_ms_(100.00%)_Space_44_MB_(47.62%)
4+
5+
importjava.util.Arrays;
6+
importjava.util.List;
7+
8+
publicclassSolution {
9+
publicintminimumTime(List<Integer>nums1,List<Integer>nums2,intx) {
10+
intn =nums1.size();
11+
int[][]nums =newint[n][2];
12+
for (inti =0;i <n;i++) {
13+
nums[i] =newint[] {nums1.get(i),nums2.get(i)};
14+
}
15+
Arrays.sort(nums, (a,b) ->a[1] -b[1]);
16+
int[]dp =newint[n +1];
17+
longsum1 =0;
18+
longsum2 =0;
19+
for (inti =0;i <n;i++) {
20+
sum1 +=nums[i][0];
21+
sum2 +=nums[i][1];
22+
}
23+
if (sum1 <=x) {
24+
return0;
25+
}
26+
for (intj =0;j <n;j++) {
27+
for (inti =j +1;i >0;i--) {
28+
dp[i] =Math.max(dp[i],nums[j][0] + (nums[j][1] *i) +dp[i -1]);
29+
}
30+
}
31+
for (inti =1;i <=n;i++) {
32+
if (sum1 +sum2 *i -dp[i] <=x) {
33+
returni;
34+
}
35+
}
36+
return -1;
37+
}
38+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2809\. Minimum Time to Make Array Sum At Most x
2+
3+
Hard
4+
5+
You are given two**0-indexed** integer arrays`nums1` and`nums2` of equal length. Every second, for all indices`0 <= i < nums1.length`, value of`nums1[i]` is incremented by`nums2[i]`.**After** this is done, you can do the following operation:
6+
7+
* Choose an index`0 <= i < nums1.length` and make`nums1[i] = 0`.
8+
9+
You are also given an integer`x`.
10+
11+
Return_the**minimum** time in which you can make the sum of all elements of_`nums1`_to be**less than or equal** to_`x`,_or_`-1`_if this is not possible._
12+
13+
**Example 1:**
14+
15+
**Input:** nums1 =[1,2,3], nums2 =[1,2,3], x = 4
16+
17+
**Output:** 3
18+
19+
**Explanation:**
20+
21+
For the 1st second, we apply the operation on i = 0. Therefore nums1 = [0,2+2,3+3] = [0,4,6].
22+
For the 2nd second, we apply the operation on i = 1. Therefore nums1 = [0+1,0,6+3] = [1,0,9].
23+
For the 3rd second, we apply the operation on i = 2. Therefore nums1 = [1+1,0+2,0] = [2,2,0].
24+
Now sum of nums1 = 4. It can be shown that these operations are optimal, so we return 3.
25+
26+
**Example 2:**
27+
28+
**Input:** nums1 =[1,2,3], nums2 =[3,3,3], x = 4
29+
30+
**Output:** -1
31+
32+
**Explanation:** It can be shown that the sum of nums1 will always be greater than x, no matter which operations are performed.
33+
34+
**Constraints:**
35+
36+
* <code>1 <= nums1.length <= 10<sup>3</sup></code>
37+
* <code>1 <= nums1[i] <= 10<sup>3</sup></code>
38+
* <code>0 <= nums2[i] <= 10<sup>3</sup></code>
39+
*`nums1.length == nums2.length`
40+
* <code>0 <= x <= 10<sup>6</sup></code>
Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
packageg2801_2900.s2810_faulty_keyboard;
2+
3+
// #Easy #String #Simulation #2023_11_20_Time_3_ms_(96.04%)_Space_44.2_MB_(14.74%)
4+
5+
publicclassSolution {
6+
publicStringfinalString(Strings) {
7+
StringBuilderstringBuilder =newStringBuilder();
8+
for (charch :s.toCharArray()) {
9+
if (ch =='i') {
10+
stringBuilder.reverse();
11+
continue;
12+
}
13+
stringBuilder.append(ch);
14+
}
15+
returnstringBuilder.toString();
16+
}
17+
}
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
2810\. Faulty Keyboard
2+
3+
Easy
4+
5+
Your laptop keyboard is faulty, and whenever you type a character`'i'` on it, it reverses the string that you have written. Typing other characters works as expected.
6+
7+
You are given a**0-indexed** string`s`, and you type each character of`s` using your faulty keyboard.
8+
9+
Return_the final string that will be present on your laptop screen._
10+
11+
**Example 1:**
12+
13+
**Input:** s = "string"
14+
15+
**Output:** "rtsng"
16+
17+
**Explanation:**
18+
19+
After typing first character, the text on the screen is "s".
20+
21+
After the second character, the text is "st".
22+
23+
After the third character, the text is "str".
24+
25+
Since the fourth character is an 'i', the text gets reversed and becomes "rts".
26+
27+
After the fifth character, the text is "rtsn".
28+
29+
After the sixth character, the text is "rtsng".
30+
31+
Therefore, we return "rtsng".
32+
33+
**Example 2:**
34+
35+
**Input:** s = "poiinter"
36+
37+
**Output:** "ponter"
38+
39+
**Explanation:**
40+
41+
After the first character, the text on the screen is "p".
42+
43+
After the second character, the text is "po".
44+
45+
Since the third character you type is an 'i', the text gets reversed and becomes "op".
46+
47+
Since the fourth character you type is an 'i', the text gets reversed and becomes "po".
48+
49+
After the fifth character, the text is "pon". After the sixth character, the text is "pont".
50+
51+
After the seventh character, the text is "ponte". After the eighth character, the text is "ponter".
52+
53+
Therefore, we return "ponter".
54+
55+
**Constraints:**
56+
57+
*`1 <= s.length <= 100`
58+
*`s` consists of lowercase English letters.
59+
*`s[0] != 'i'`
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg2801_2900.s2811_check_if_it_is_possible_to_split_array;
2+
3+
// #Medium #Array #Dynamic_Programming #Greedy #2023_11_20_Time_1_ms_(98.31%)_Space_43_MB_(50.00%)
4+
5+
importjava.util.List;
6+
7+
publicclassSolution {
8+
publicbooleancanSplitArray(List<Integer>nums,intm) {
9+
if (nums.size() <3 && !nums.isEmpty()) {
10+
returntrue;
11+
}
12+
booleanans =false;
13+
for (inti =0;i <nums.size() -1;i++) {
14+
if (nums.get(i) +nums.get(i +1) >=m) {
15+
ans =true;
16+
}
17+
}
18+
returnans;
19+
}
20+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
2811\. Check if it is Possible to Split Array
2+
3+
Medium
4+
5+
You are given an array`nums` of length`n` and an integer`m`. You need to determine if it is possible to split the array into`n`**non-empty** arrays by performing a series of steps.
6+
7+
In each step, you can select an existing array (which may be the result of previous steps) with a length of**at least two** and split it into**two** subarrays, if,**for each** resulting subarray,**at least** one of the following holds:
8+
9+
* The length of the subarray is one, or
10+
* The sum of elements of the subarray is**greater than or equal** to`m`.
11+
12+
Return`true`_if you can split the given array into_`n`_arrays, otherwise return_`false`.
13+
14+
**Note:** A subarray is_a contiguous non-empty sequence of elements within an array_.
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[2, 2, 1], m = 4
19+
20+
**Output:** true
21+
22+
**Explanation:** We can split the array into[2, 2] and[1] in the first step. Then, in the second step, we can split[2, 2] into[2] and[2]. As a result, the answer is true.
23+
24+
**Example 2:**
25+
26+
**Input:** nums =[2, 1, 3], m = 5
27+
28+
**Output:** false
29+
30+
**Explanation:** We can try splitting the array in two different ways: the first way is to have[2, 1] and[3], and the second way is to have[2] and[1, 3]. However, both of these ways are not valid. So, the answer is false.
31+
32+
**Example 3:**
33+
34+
**Input:** nums =[2, 3, 3, 2, 3], m = 6
35+
36+
**Output:** true
37+
38+
**Explanation:** We can split the array into[2, 3, 3, 2] and[3] in the first step. Then, in the second step, we can split[2, 3, 3, 2] into[2, 3, 3] and[2]. Then, in the third step, we can split[2, 3, 3] into[2] and[3, 3]. And in the last step we can split[3, 3] into[3] and[3]. As a result, the answer is true.
39+
40+
**Constraints:**
41+
42+
*`1 <= n == nums.length <= 100`
43+
*`1 <= nums[i] <= 100`
44+
*`1 <= m <= 200`
Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
packageg2801_2900.s2812_find_the_safest_path_in_a_grid;
2+
3+
// #Medium #Array #Binary_Search #Matrix #Union_Find #Breadth_First_Search
4+
// #2023_11_20_Time_57_ms_(100.00%)_Space_65.3_MB_(77.00%)
5+
6+
importjava.util.Arrays;
7+
importjava.util.List;
8+
9+
@SuppressWarnings("java:S6541")
10+
publicclassSolution {
11+
privatestaticfinalint[][]MOVES =newint[][] {{-1,0}, {1,0}, {0, -1}, {0,1}};
12+
13+
publicintmaximumSafenessFactor(List<List<Integer>>grid) {
14+
finalintyLen =grid.size();
15+
finalintxLen =grid.get(0).size();
16+
if (grid.get(0).get(0) ==1 ||grid.get(yLen -1).get(xLen -1) ==1) {
17+
return0;
18+
}
19+
int[][]secure =newint[yLen][xLen];
20+
int[]deque =newint[yLen *xLen];
21+
int[]nDeque =newint[yLen *xLen];
22+
int[]tmpDeque;
23+
int[]queue =newint[yLen *xLen];
24+
int[]root =newint[yLen *xLen];
25+
inthead = -1;
26+
inttail = -1;
27+
intqIdx = -1;
28+
intend =yLen *xLen -1;
29+
intcurY;
30+
intcurX;
31+
intnextY;
32+
intnextX;
33+
intcurID;
34+
intnextID;
35+
for (inty =0;y <yLen;y++) {
36+
Arrays.fill(secure[y], -1);
37+
for (intx =0;x <xLen;x++) {
38+
if (grid.get(y).get(x) ==1) {
39+
secure[y][x] =0;
40+
curID =y *xLen +x;
41+
root[curID] =queue[++qIdx] =nDeque[++tail] =curID;
42+
}
43+
}
44+
}
45+
intstart =0;
46+
intstop =qIdx;
47+
for (intt =1;tail > -1;t++) {
48+
tmpDeque =deque;
49+
deque =nDeque;
50+
nDeque =tmpDeque;
51+
head =tail;
52+
tail = -1;
53+
start =qIdx;
54+
for (;head >=0;head--) {
55+
curY =deque[head] /xLen;
56+
curX =deque[head] %xLen;
57+
for (int[]move :MOVES) {
58+
nextY =curY +move[0];
59+
nextX =curX +move[1];
60+
if (nextY >=0
61+
&&nextY <yLen
62+
&&nextX >=0
63+
&&nextX <xLen
64+
&&secure[nextY][nextX] <0) {
65+
secure[nextY][nextX] =t;
66+
nextID =nextY *xLen +nextX;
67+
root[nextID] =queue[++qIdx] =nDeque[++tail] =nextID;
68+
}
69+
}
70+
}
71+
}
72+
for (qIdx =start;qIdx >stop;qIdx--) {
73+
curY =queue[qIdx] /xLen;
74+
curX =queue[qIdx] %xLen;
75+
curID =curY *xLen +curX;
76+
for (int[]move :MOVES) {
77+
nextY =curY +move[0];
78+
nextX =curX +move[1];
79+
if (nextY >=0
80+
&&nextY <yLen
81+
&&nextX >=0
82+
&&nextX <xLen
83+
&&secure[nextY][nextX] >=secure[curY][curX]) {
84+
nextID =nextY *xLen +nextX;
85+
root[find(root,curID)] =find(root,nextID);
86+
}
87+
}
88+
if (find(root,0) ==find(root,end)) {
89+
returnsecure[curY][curX];
90+
}
91+
}
92+
return0;
93+
}
94+
95+
privateintfind(int[]root,intidx) {
96+
if (idx ==root[idx]) {
97+
returnidx;
98+
}
99+
root[idx] =find(root,root[idx]);
100+
returnroot[idx];
101+
}
102+
}

0 commit comments

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