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

Commitaff631d

Browse files
authored
Added tasks 2575-2579
1 parent08e8cec commitaff631d

File tree

15 files changed

+455
-0
lines changed

15 files changed

+455
-0
lines changed
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
packageg2501_2600.s2575_find_the_divisibility_array_of_a_string;
2+
3+
// #Medium #Array #String #Math #2023_08_22_Time_6_ms_(100.00%)_Space_56.4_MB_(49.79%)
4+
5+
publicclassSolution {
6+
publicint[]divisibilityArray(Stringword,intm) {
7+
intn =word.length();
8+
longmodulo =0;
9+
int[]result =newint[n];
10+
for (inti =0;i <n;i++) {
11+
intnumericValue =word.charAt(i) -'0';
12+
modulo = (modulo *10 +numericValue) %m;
13+
if (modulo ==0) {
14+
result[i] =1;
15+
}
16+
}
17+
returnresult;
18+
}
19+
}
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
2575\. Find the Divisibility Array of a String
2+
3+
Medium
4+
5+
You are given a**0-indexed** string`word` of length`n` consisting of digits, and a positive integer`m`.
6+
7+
The**divisibility array**`div` of`word` is an integer array of length`n` such that:
8+
9+
*`div[i] = 1` if the**numeric value** of`word[0,...,i]` is divisible by`m`, or
10+
*`div[i] = 0` otherwise.
11+
12+
Return_the divisibility array of_`word`.
13+
14+
**Example 1:**
15+
16+
**Input:** word = "998244353", m = 3
17+
18+
**Output:**[1,1,0,0,0,1,1,0,0]
19+
20+
**Explanation:** There are only 4 prefixes that are divisible by 3: "9", "99", "998244", and "9982443".
21+
22+
**Example 2:**
23+
24+
**Input:** word = "1010", m = 10
25+
26+
**Output:**[0,1,0,1]
27+
28+
**Explanation:** There are only 2 prefixes that are divisible by 10: "10", and "1010".
29+
30+
**Constraints:**
31+
32+
* <code>1 <= n <= 10<sup>5</sup></code>
33+
*`word.length == n`
34+
*`word` consists of digits from`0` to`9`
35+
* <code>1 <= m <= 10<sup>9</sup></code>
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2501_2600.s2576_find_the_maximum_number_of_marked_indices;
2+
3+
// #Medium #Array #Sorting #Greedy #Binary_Search #Two_Pointers
4+
// #2023_08_22_Time_27_ms_(95.36%)_Space_54.9_MB_(88.74%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publicintmaxNumOfMarkedIndices(int[]nums) {
10+
Arrays.sort(nums);
11+
inti =0;
12+
intj =nums.length /2;
13+
longcount =0;
14+
while (i <nums.length /2 &&j <nums.length) {
15+
if (nums[i] *2 <=nums[j]) {
16+
i++;
17+
j++;
18+
count =count +2;
19+
}else {
20+
j++;
21+
}
22+
}
23+
return (int)count;
24+
}
25+
}
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
2576\. Find the Maximum Number of Marked Indices
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums`.
6+
7+
Initially, all of the indices are unmarked. You are allowed to make this operation any number of times:
8+
9+
* Pick two**different unmarked** indices`i` and`j` such that`2 * nums[i] <= nums[j]`, then mark`i` and`j`.
10+
11+
Return_the maximum possible number of marked indices in`nums` using the above operation any number of times_.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[3,5,2,4]
16+
17+
**Output:** 2
18+
19+
**Explanation:** In the first operation: pick i = 2 and j = 1, the operation is allowed because 2\* nums[2] <= nums[1]. Then mark index 2 and 1. It can be shown that there's no other valid operation so the answer is 2.
20+
21+
**Example 2:**
22+
23+
**Input:** nums =[9,2,5,4]
24+
25+
**Output:** 4
26+
27+
**Explanation:** In the first operation: pick i = 3 and j = 0, the operation is allowed because 2\* nums[3] <= nums[0].
28+
29+
Then mark index 3 and 0.
30+
31+
In the second operation: pick i = 1 and j = 2, the operation is allowed because 2\* nums[1] <= nums[2]. Then mark index 1 and 2.
32+
33+
Since there is no other operation, the answer is 4.
34+
35+
**Example 3:**
36+
37+
**Input:** nums =[7,6,8]
38+
39+
**Output:** 0
40+
41+
**Explanation:** There is no valid operation to do, so the answer is 0.
42+
43+
**Constraints:**
44+
45+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
46+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
packageg2501_2600.s2577_minimum_time_to_visit_a_cell_in_a_grid;
2+
3+
// #Hard #Array #Breadth_First_Search #Matrix #Heap_Priority_Queue #Graph #Shortest_Path
4+
// #2023_08_22_Time_132_ms_(85.82%)_Space_56_MB_(57.46%)
5+
6+
importjava.util.Arrays;
7+
importjava.util.Comparator;
8+
importjava.util.PriorityQueue;
9+
10+
publicclassSolution {
11+
publicintminimumTime(int[][]grid) {
12+
intm =grid.length;
13+
intn =grid[0].length;
14+
if (grid[0][1] >1 &&grid[1][0] >1) {
15+
return -1;
16+
}
17+
PriorityQueue<Node>pq =newPriorityQueue<>(Comparator.comparingInt(a ->a.time));
18+
pq.add(newNode(0,0,0));
19+
int[]xDir = {0,0,1, -1};
20+
int[]yDir = {1, -1,0,0};
21+
int[][]vis =newint[m][n];
22+
for (int[]temp :vis) {
23+
Arrays.fill(temp, -1);
24+
}
25+
while (!pq.isEmpty()) {
26+
Nodecurr =pq.remove();
27+
if (curr.x ==m -1 &&curr.y ==n -1) {
28+
returncurr.time;
29+
}
30+
vis[curr.x][curr.y] =1;
31+
intcurrTime =curr.time +1;
32+
for (inti =0;i <4;i++) {
33+
intnewX =curr.x +xDir[i];
34+
intnewY =curr.y +yDir[i];
35+
if (newX >=0 &&newY >=0 &&newX <m &&newY <n &&vis[newX][newY] == -1) {
36+
vis[newX][newY] =1;
37+
if (grid[newX][newY] <=currTime) {
38+
pq.add(newNode(newX,newY,currTime));
39+
}else {
40+
if ((grid[newX][newY] -curr.time) %2 ==0) {
41+
pq.add(newNode(newX,newY,grid[newX][newY] +1));
42+
}else {
43+
pq.add(newNode(newX,newY,grid[newX][newY]));
44+
}
45+
}
46+
}
47+
}
48+
}
49+
return -1;
50+
}
51+
52+
privatestaticclassNode {
53+
intx;
54+
inty;
55+
inttime;
56+
57+
Node(intxx,intyy,inttt) {
58+
x =xx;
59+
y =yy;
60+
time =tt;
61+
}
62+
}
63+
}
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
2577\. Minimum Time to Visit a Cell In a Grid
2+
3+
Hard
4+
5+
You are given a`m x n` matrix`grid` consisting of**non-negative** integers where`grid[row][col]` represents the**minimum** time required to be able to visit the cell`(row, col)`, which means you can visit the cell`(row, col)` only when the time you visit it is greater than or equal to`grid[row][col]`.
6+
7+
You are standing in the**top-left** cell of the matrix in the <code>0<sup>th</sup></code> second, and you must move to**any** adjacent cell in the four directions: up, down, left, and right. Each move you make takes 1 second.
8+
9+
Return_the**minimum** time required in which you can visit the bottom-right cell of the matrix_. If you cannot visit the bottom-right cell, then return`-1`.
10+
11+
**Example 1:**
12+
13+
![](https://assets.leetcode.com/uploads/2023/02/14/yetgriddrawio-8.png)
14+
15+
**Input:** grid =[[0,1,3,2],[5,1,2,5],[4,3,8,6]]
16+
17+
**Output:** 7
18+
19+
**Explanation:** One of the paths that we can take is the following:
20+
- at t = 0, we are on the cell (0,0).
21+
- at t = 1, we move to the cell (0,1). It is possible because grid[0][1] <= 1.
22+
- at t = 2, we move to the cell (1,1). It is possible because grid[1][1] <= 2.
23+
- at t = 3, we move to the cell (1,2). It is possible because grid[1][2] <= 3.
24+
- at t = 4, we move to the cell (1,1). It is possible because grid[1][1] <= 4.
25+
- at t = 5, we move to the cell (1,2). It is possible because grid[1][2] <= 5.
26+
- at t = 6, we move to the cell (1,3). It is possible because grid[1][3] <= 6.
27+
- at t = 7, we move to the cell (2,3). It is possible because grid[2][3] <= 7.
28+
29+
The final time is 7. It can be shown that it is the minimum time possible.
30+
31+
**Example 2:**
32+
33+
![](https://assets.leetcode.com/uploads/2023/02/14/yetgriddrawio-9.png)
34+
35+
**Input:** grid =[[0,2,4],[3,2,1],[1,0,4]]
36+
37+
**Output:** -1
38+
39+
**Explanation:** There is no path from the top left to the bottom-right cell.
40+
41+
**Constraints:**
42+
43+
*`m == grid.length`
44+
*`n == grid[i].length`
45+
*`2 <= m, n <= 1000`
46+
* <code>4 <= m * n <= 10<sup>5</sup></code>
47+
* <code>0 <= grid[i][j] <= 10<sup>5</sup></code>
48+
*`grid[0][0] == 0`
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
packageg2501_2600.s2578_split_with_minimum_sum;
2+
3+
// #Easy #Math #Sorting #Greedy #2023_08_22_Time_0_ms_(100.00%)_Space_39.3_MB_(76.63%)
4+
5+
publicclassSolution {
6+
publicintsplitNum(intnumber) {
7+
intnum1 =0;
8+
intnum2 =0;
9+
booleanaddToOne =true;
10+
for (inti =0;i <=9;i++) {
11+
inttmpNumber =number;
12+
while (tmpNumber >0) {
13+
intdigit =tmpNumber %10;
14+
if (digit ==i) {
15+
if (addToOne) {
16+
num1 *=10;
17+
num1 +=digit;
18+
addToOne =false;
19+
}else {
20+
num2 *=10;
21+
num2 +=digit;
22+
addToOne =true;
23+
}
24+
}
25+
tmpNumber /=10;
26+
}
27+
}
28+
returnnum1 +num2;
29+
}
30+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2578\. Split With Minimum Sum
2+
3+
Easy
4+
5+
Given a positive integer`num`, split it into two non-negative integers`num1` and`num2` such that:
6+
7+
* The concatenation of`num1` and`num2` is a permutation of`num`.
8+
* In other words, the sum of the number of occurrences of each digit in`num1` and`num2` is equal to the number of occurrences of that digit in`num`.
9+
*`num1` and`num2` can contain leading zeros.
10+
11+
Return_the**minimum** possible sum of_`num1`_and_`num2`.
12+
13+
**Notes:**
14+
15+
* It is guaranteed that`num` does not contain any leading zeros.
16+
* The order of occurrence of the digits in`num1` and`num2` may differ from the order of occurrence of`num`.
17+
18+
**Example 1:**
19+
20+
**Input:** num = 4325
21+
22+
**Output:** 59
23+
24+
**Explanation:** We can split 4325 so that`num1` is 24 and num2`is` 35, giving a sum of 59. We can prove that 59 is indeed the minimal possible sum.
25+
26+
**Example 2:**
27+
28+
**Input:** num = 687
29+
30+
**Output:** 75
31+
32+
**Explanation:** We can split 687 so that`num1` is 68 and`num2` is 7, which would give an optimal sum of 75.
33+
34+
**Constraints:**
35+
36+
* <code>10 <= num <= 10<sup>9</sup></code>
Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
packageg2501_2600.s2579_count_total_number_of_colored_cells;
2+
3+
// #Medium #Math #2023_08_22_Time_0_ms_(100.00%)_Space_39.2_MB_(60.33%)
4+
5+
publicclassSolution {
6+
publiclongcoloredCells(intn) {
7+
return (long)Math.pow(n,2) + (long)Math.pow(n - (double)1,2);
8+
}
9+
}
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
2579\. Count Total Number of Colored Cells
2+
3+
Medium
4+
5+
There exists an infinitely large two-dimensional grid of uncolored unit cells. You are given a positive integer`n`, indicating that you must do the following routine for`n` minutes:
6+
7+
* At the first minute, color**any** arbitrary unit cell blue.
8+
* Every minute thereafter, color blue**every** uncolored cell that touches a blue cell.
9+
10+
Below is a pictorial representation of the state of the grid after minutes 1, 2, and 3.
11+
12+
![](https://assets.leetcode.com/uploads/2023/01/10/example-copy-2.png)
13+
14+
Return_the number of**colored cells** at the end of_`n`_minutes_.
15+
16+
**Example 1:**
17+
18+
**Input:** n = 1
19+
20+
**Output:** 1
21+
22+
**Explanation:** After 1 minute, there is only 1 blue cell, so we return 1.
23+
24+
**Example 2:**
25+
26+
**Input:** n = 2
27+
28+
**Output:** 5
29+
30+
**Explanation:** After 2 minutes, there are 4 colored cells on the boundary and 1 in the center, so we return 5.
31+
32+
**Constraints:**
33+
34+
* <code>1 <= n <= 10<sup>5</sup></code>
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageg2501_2600.s2575_find_the_divisibility_array_of_a_string;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voiddivisibilityArray() {
11+
assertThat(
12+
newSolution().divisibilityArray("998244353",3),
13+
equalTo(newint[] {1,1,0,0,0,1,1,0,0}));
14+
}
15+
16+
@Test
17+
voiddivisibilityArray2() {
18+
assertThat(newSolution().divisibilityArray("1010",10),equalTo(newint[] {0,1,0,1}));
19+
}
20+
}

0 commit comments

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