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

Commit0bbf322

Browse files
authored
Added tasks 2849-2856
1 parent0d81bd2 commit0bbf322

File tree

15 files changed

+567
-0
lines changed

15 files changed

+567
-0
lines changed
Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
packageg2801_2900.s2849_determine_if_a_cell_is_reachable_at_a_given_time;
2+
3+
// #Medium #Math #2023_12_15_Time_1_ms_(91.15%)_Space_39.3_MB_(87.43%)
4+
5+
publicclassSolution {
6+
publicbooleanisReachableAtTime(intsx,intsy,intfx,intfy,intt) {
7+
if (sx ==fx &&sy ==fy) {
8+
returnt !=1;
9+
}
10+
intwidth =Math.abs(sx -fx) +1;
11+
intheight =Math.abs(sy -fy) +1;
12+
returnMath.max(width,height) -1 <=t;
13+
}
14+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2849\. Determine if a Cell Is Reachable at a Given Time
2+
3+
Medium
4+
5+
You are given four integers`sx`,`sy`,`fx`,`fy`, and a**non-negative** integer`t`.
6+
7+
In an infinite 2D grid, you start at the cell`(sx, sy)`. Each second, you**must** move to any of its adjacent cells.
8+
9+
Return`true`_if you can reach cell_`(fx, fy)`_after**exactly**_`t`**_seconds_**,_or_`false`_otherwise_.
10+
11+
A cell's**adjacent cells** are the 8 cells around it that share at least one corner with it. You can visit the same cell several times.
12+
13+
**Example 1:**
14+
15+
![](https://assets.leetcode.com/uploads/2023/08/05/example2.svg)
16+
17+
**Input:** sx = 2, sy = 4, fx = 7, fy = 7, t = 6
18+
19+
**Output:** true
20+
21+
**Explanation:** Starting at cell (2, 4), we can reach cell (7, 7) in exactly 6 seconds by going through the cells depicted in the picture above.
22+
23+
**Example 2:**
24+
25+
![](https://assets.leetcode.com/uploads/2023/08/05/example1.svg)
26+
27+
**Input:** sx = 3, sy = 1, fx = 7, fy = 3, t = 3
28+
29+
**Output:** false
30+
31+
**Explanation:** Starting at cell (3, 1), it takes at least 4 seconds to reach cell (7, 3) by going through the cells depicted in the picture above. Hence, we cannot reach cell (7, 3) at the third second.
32+
33+
**Constraints:**
34+
35+
* <code>1 <= sx, sy, fx, fy <= 10<sup>9</sup></code>
36+
* <code>0 <= t <= 10<sup>9</sup></code>
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
packageg2801_2900.s2850_minimum_moves_to_spread_stones_over_grid;
2+
3+
// #Medium #Array #Dynamic_Programming #Matrix #Breadth_First_Search
4+
// #2023_12_15_Time_1_ms_(100.00%)_Space_40.5_MB_(89.16%)
5+
6+
publicclassSolution {
7+
publicintminimumMoves(int[][]grid) {
8+
inta =grid[0][0] -1;
9+
intb =grid[0][1] -1;
10+
intc =grid[0][2] -1;
11+
intd =grid[1][0] -1;
12+
intf =grid[1][2] -1;
13+
intg =grid[2][0] -1;
14+
inth =grid[2][1] -1;
15+
inti =grid[2][2] -1;
16+
intminCost =Integer.MAX_VALUE;
17+
for (intx =Math.min(a,0);x <=Math.max(a,0);x++) {
18+
for (inty =Math.min(c,0);y <=Math.max(c,0);y++) {
19+
for (intz =Math.min(i,0);z <=Math.max(i,0);z++) {
20+
for (intt =Math.min(g,0);t <=Math.max(g,0);t++) {
21+
intcost =
22+
Math.abs(x)
23+
+Math.abs(y)
24+
+Math.abs(z)
25+
+Math.abs(t)
26+
+Math.abs(x -a)
27+
+Math.abs(y -c)
28+
+Math.abs(z -i)
29+
+Math.abs(t -g)
30+
+Math.abs(x -y +b +c)
31+
+Math.abs(y -z +i +f)
32+
+Math.abs(z -t +g +h)
33+
+Math.abs(t -x +a +d);
34+
if (cost <minCost) {
35+
minCost =cost;
36+
}
37+
}
38+
}
39+
}
40+
}
41+
returnminCost;
42+
}
43+
}
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
2850\. Minimum Moves to Spread Stones Over Grid
2+
3+
Medium
4+
5+
You are given a**0-indexed** 2D integer matrix`grid` of size`3 * 3`, representing the number of stones in each cell. The grid contains exactly`9` stones, and there can be**multiple** stones in a single cell.
6+
7+
In one move, you can move a single stone from its current cell to any other cell if the two cells share a side.
8+
9+
Return_the**minimum number of moves** required to place one stone in each cell_.
10+
11+
**Example 1:**
12+
13+
![](https://assets.leetcode.com/uploads/2023/08/23/example1-3.svg)
14+
15+
**Input:** grid =[[1,1,0],[1,1,1],[1,2,1]]
16+
17+
**Output:** 3
18+
19+
**Explanation:** One possible sequence of moves to place one stone in each cell is:
20+
21+
1- Move one stone from cell (2,1) to cell (2,2).
22+
23+
2- Move one stone from cell (2,2) to cell (1,2).
24+
25+
3- Move one stone from cell (1,2) to cell (0,2).
26+
27+
In total, it takes 3 moves to place one stone in each cell of the grid.
28+
29+
It can be shown that 3 is the minimum number of moves required to place one stone in each cell.
30+
31+
**Example 2:**
32+
33+
![](https://assets.leetcode.com/uploads/2023/08/23/example2-2.svg)
34+
35+
**Input:** grid =[[1,3,0],[1,0,0],[1,0,3]]
36+
37+
**Output:** 4
38+
39+
**Explanation:** One possible sequence of moves to place one stone in each cell is:
40+
41+
1- Move one stone from cell (0,1) to cell (0,2).
42+
43+
2- Move one stone from cell (0,1) to cell (1,1).
44+
45+
3- Move one stone from cell (2,2) to cell (1,2).
46+
47+
4- Move one stone from cell (2,2) to cell (2,1).
48+
49+
In total, it takes 4 moves to place one stone in each cell of the grid.
50+
51+
It can be shown that 4 is the minimum number of moves required to place one stone in each cell.
52+
53+
**Constraints:**
54+
55+
*`grid.length == grid[i].length == 3`
56+
*`0 <= grid[i][j] <= 9`
57+
* Sum of`grid` is equal to`9`.
Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
packageg2801_2900.s2851_string_transformation;
2+
3+
// #Hard #String #Dynamic_Programming #Math #String_Matching
4+
// #2023_12_15_Time_54_ms_(78.45%)_Space_54.3_MB_(93.97%)
5+
6+
publicclassSolution {
7+
privatelong[][]g;
8+
9+
publicintnumberOfWays(Strings,Stringt,longk) {
10+
intn =s.length();
11+
intv =kmp(s +s,t);
12+
g =newlong[][] {{v -1,v}, {n -v,n -1 -v}};
13+
long[][]f =qmi(k);
14+
returns.equals(t) ? (int)f[0][0] : (int)f[0][1];
15+
}
16+
17+
privateintkmp(Strings,Stringp) {
18+
intn =p.length();
19+
intm =s.length();
20+
s ="#" +s;
21+
p ="#" +p;
22+
int[]ne =newint[n +1];
23+
intj =0;
24+
for (inti =2;i <=n;i++) {
25+
while (j >0 &&p.charAt(i) !=p.charAt(j +1)) {
26+
j =ne[j];
27+
}
28+
if (p.charAt(i) ==p.charAt(j +1)) {
29+
j++;
30+
}
31+
ne[i] =j;
32+
}
33+
34+
intcnt =0;
35+
j =0;
36+
for (inti =1;i <=m;i++) {
37+
while (j >0 &&s.charAt(i) !=p.charAt(j +1)) {
38+
j =ne[j];
39+
}
40+
if (s.charAt(i) ==p.charAt(j +1)) {
41+
j++;
42+
}
43+
if (j ==n) {
44+
if (i -n +1 <=n) {
45+
cnt++;
46+
}
47+
j =ne[j];
48+
}
49+
}
50+
returncnt;
51+
}
52+
53+
privatevoidmul(long[][]c,long[][]a,long[][]b) {
54+
long[][]t =newlong[2][2];
55+
for (inti =0;i <2;i++) {
56+
for (intj =0;j <2;j++) {
57+
for (intk =0;k <2;k++) {
58+
intmod = (int)1e9 +7;
59+
t[i][j] = (t[i][j] +a[i][k] *b[k][j]) %mod;
60+
}
61+
}
62+
}
63+
for (inti =0;i <2;i++) {
64+
System.arraycopy(t[i],0,c[i],0,2);
65+
}
66+
}
67+
68+
privatelong[][]qmi(longk) {
69+
long[][]f =newlong[2][2];
70+
f[0][0] =1;
71+
while (k >0) {
72+
if ((k &1) ==1) {
73+
mul(f,f,g);
74+
}
75+
mul(g,g,g);
76+
k >>=1;
77+
}
78+
returnf;
79+
}
80+
}
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
2851\. String Transformation
2+
3+
Hard
4+
5+
You are given two strings`s` and`t` of equal length`n`. You can perform the following operation on the string`s`:
6+
7+
* Remove a**suffix** of`s` of length`l` where`0 < l < n` and append it at the start of`s`.
8+
For example, let`s = 'abcd'` then in one operation you can remove the suffix`'cd'` and append it in front of`s` making`s = 'cdab'`.
9+
10+
You are also given an integer`k`. Return_the number of ways in which_`s`_can be transformed into_`t`_in**exactly**_`k`_operations._
11+
12+
Since the answer can be large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
13+
14+
**Example 1:**
15+
16+
**Input:** s = "abcd", t = "cdab", k = 2
17+
18+
**Output:** 2
19+
20+
**Explanation:**
21+
22+
First way:
23+
24+
In first operation, choose suffix from index = 3, so resulting s = "dabc".
25+
26+
In second operation, choose suffix from index = 3, so resulting s = "cdab".
27+
28+
Second way:
29+
30+
In first operation, choose suffix from index = 1, so resulting s = "bcda".
31+
32+
In second operation, choose suffix from index = 1, so resulting s = "cdab".
33+
34+
**Example 2:**
35+
36+
**Input:** s = "ababab", t = "ababab", k = 1
37+
38+
**Output:** 2
39+
40+
**Explanation:**
41+
42+
First way:
43+
44+
Choose suffix from index = 2, so resulting s = "ababab".
45+
46+
Second way:
47+
48+
Choose suffix from index = 4, so resulting s = "ababab".
49+
50+
**Constraints:**
51+
52+
* <code>2 <= s.length <= 5 * 10<sup>5</sup></code>
53+
* <code>1 <= k <= 10<sup>15</sup></code>
54+
*`s.length == t.length`
55+
*`s` and`t` consist of only lowercase English alphabets.
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
packageg2801_2900.s2855_minimum_right_shifts_to_sort_the_array;
2+
3+
// #Easy #Array #2023_12_15_Time_1_ms_(100.00%)_Space_42.6_MB_(5.66%)
4+
5+
importjava.util.List;
6+
7+
publicclassSolution {
8+
publicintminimumRightShifts(List<Integer>nums) {
9+
inti;
10+
for (i =1;i <nums.size();i++) {
11+
if (nums.get(i) <nums.get(i -1)) {
12+
break;
13+
}
14+
}
15+
if (nums.size() ==i) {
16+
return0;
17+
}else {
18+
intk;
19+
for (k =i +1;k <nums.size();k++) {
20+
if (nums.get(k) <=nums.get(k -1)) {
21+
break;
22+
}
23+
}
24+
if (k ==nums.size() &&nums.get(k -1) <nums.get(0)) {
25+
returnnums.size() -i;
26+
}
27+
return -1;
28+
}
29+
}
30+
}
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
2855\. Minimum Right Shifts to Sort the Array
2+
3+
Easy
4+
5+
You are given a**0-indexed** array`nums` of length`n` containing**distinct** positive integers. Return_the**minimum** number of**right shifts** required to sort_`nums`_and_`-1`_if this is not possible._
6+
7+
A**right shift** is defined as shifting the element at index`i` to index`(i + 1) % n`, for all indices.
8+
9+
**Example 1:**
10+
11+
**Input:** nums =[3,4,5,1,2]
12+
13+
**Output:** 2
14+
15+
**Explanation:**
16+
17+
After the first right shift, nums =[2,3,4,5,1].
18+
19+
After the second right shift, nums =[1,2,3,4,5].
20+
21+
Now nums is sorted; therefore the answer is 2.
22+
23+
**Example 2:**
24+
25+
**Input:** nums =[1,3,5]
26+
27+
**Output:** 0
28+
29+
**Explanation:** nums is already sorted therefore, the answer is 0.
30+
31+
**Example 3:**
32+
33+
**Input:** nums =[2,1,4]
34+
35+
**Output:** -1
36+
37+
**Explanation:** It's impossible to sort the array using right shifts.
38+
39+
**Constraints:**
40+
41+
*`1 <= nums.length <= 100`
42+
*`1 <= nums[i] <= 100`
43+
*`nums` contains distinct integers.
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
packageg2801_2900.s2856_minimum_array_length_after_pair_removals;
2+
3+
// #Medium #Array #Hash_Table #Greedy #Binary_Search #Two_Pointers #Counting
4+
// #2023_12_15_Time_5_ms_(97.63%)_Space_59.1_MB_(36.50%)
5+
6+
importjava.util.List;
7+
8+
publicclassSolution {
9+
publicintminLengthAfterRemovals(List<Integer>nums) {
10+
intn =nums.size();
11+
inti =0;
12+
intj;
13+
if (n %2 ==0) {
14+
j =n /2;
15+
}else {
16+
j =n /2 +1;
17+
}
18+
intcount =0;
19+
while (i <n /2 &&j <n) {
20+
if (nums.get(i) <nums.get(j)) {
21+
count +=2;
22+
}
23+
i++;
24+
j++;
25+
}
26+
returnn -count;
27+
}
28+
}

0 commit comments

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