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

Commit54b28d4

Browse files
authored
Added tasks 3280-3283
1 parent479e220 commit54b28d4

File tree

12 files changed

+406
-0
lines changed

12 files changed

+406
-0
lines changed
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
packageg3201_3300.s3280_convert_date_to_binary;
2+
3+
// #Easy #String #Math #2024_09_09_Time_3_ms_(100.00%)_Space_42.4_MB_(50.00%)
4+
5+
publicclassSolution {
6+
privateStringhelper(Stringstr) {
7+
returnInteger.toBinaryString(Integer.parseInt(str));
8+
}
9+
10+
publicStringconvertDateToBinary(Stringdate) {
11+
StringBuildersb =newStringBuilder();
12+
for (Stringstr :date.split("-")) {
13+
sb.append(helper(str));
14+
sb.append("-");
15+
}
16+
sb.deleteCharAt(sb.length() -1);
17+
returnsb.toString();
18+
}
19+
}
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
3280\. Convert Date to Binary
2+
3+
Easy
4+
5+
You are given a string`date` representing a Gregorian calendar date in the`yyyy-mm-dd` format.
6+
7+
`date` can be written in its binary representation obtained by converting year, month, and day to their binary representations without any leading zeroes and writing them down in`year-month-day` format.
8+
9+
Return the**binary** representation of`date`.
10+
11+
**Example 1:**
12+
13+
**Input:** date = "2080-02-29"
14+
15+
**Output:** "100000100000-10-11101"
16+
17+
**Explanation:**
18+
19+
100000100000, 10, and 11101 are the binary representations of 2080, 02, and 29 respectively.
20+
21+
**Example 2:**
22+
23+
**Input:** date = "1900-01-01"
24+
25+
**Output:** "11101101100-1-1"
26+
27+
**Explanation:**
28+
29+
11101101100, 1, and 1 are the binary representations of 1900, 1, and 1 respectively.
30+
31+
**Constraints:**
32+
33+
*`date.length == 10`
34+
*`date[4] == date[7] == '-'`, and all other`date[i]`'s are digits.
35+
* The input is generated such that`date` represents a valid Gregorian calendar date between Jan 1<sup>st</sup>, 1900 and Dec 31<sup>st</sup>, 2100 (both inclusive).
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
packageg3201_3300.s3281_maximize_score_of_numbers_in_ranges;
2+
3+
// #Medium #Array #Sorting #Greedy #Binary_Search
4+
// #2024_09_09_Time_47_ms_(100.00%)_Space_58.3_MB_(100.00%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
publicintmaxPossibleScore(int[]start,intd) {
10+
Arrays.sort(start);
11+
intn =start.length;
12+
intl =0;
13+
intr =start[n -1] -start[0] +d +1;
14+
while (l <r) {
15+
intm =l + (r -l) /2;
16+
if (isPossible(start,d,m)) {
17+
l =m +1;
18+
}else {
19+
r =m;
20+
}
21+
}
22+
returnl -1;
23+
}
24+
25+
privatebooleanisPossible(int[]start,intd,intscore) {
26+
intpre =start[0];
27+
for (inti =1;i <start.length;i++) {
28+
if (start[i] +d -pre <score) {
29+
returnfalse;
30+
}
31+
pre =Math.max(start[i],pre +score);
32+
}
33+
returntrue;
34+
}
35+
}
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
3281\. Maximize Score of Numbers in Ranges
2+
3+
Medium
4+
5+
You are given an array of integers`start` and an integer`d`, representing`n` intervals`[start[i], start[i] + d]`.
6+
7+
You are asked to choose`n` integers where the <code>i<sup>th</sup></code> integer must belong to the <code>i<sup>th</sup></code> interval. The**score** of the chosen integers is defined as the**minimum** absolute difference between any two integers that have been chosen.
8+
9+
Return the**maximum**_possible score_ of the chosen integers.
10+
11+
**Example 1:**
12+
13+
**Input:** start =[6,0,3], d = 2
14+
15+
**Output:** 4
16+
17+
**Explanation:**
18+
19+
The maximum possible score can be obtained by choosing integers: 8, 0, and 4. The score of these chosen integers is`min(|8 - 0|, |8 - 4|, |0 - 4|)` which equals 4.
20+
21+
**Example 2:**
22+
23+
**Input:** start =[2,6,13,13], d = 5
24+
25+
**Output:** 5
26+
27+
**Explanation:**
28+
29+
The maximum possible score can be obtained by choosing integers: 2, 7, 13, and 18. The score of these chosen integers is`min(|2 - 7|, |2 - 13|, |2 - 18|, |7 - 13|, |7 - 18|, |13 - 18|)` which equals 5.
30+
31+
**Constraints:**
32+
33+
* <code>2 <= start.length <= 10<sup>5</sup></code>
34+
* <code>0 <= start[i] <= 10<sup>9</sup></code>
35+
* <code>0 <= d <= 10<sup>9</sup></code>
Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
packageg3201_3300.s3282_reach_end_of_array_with_max_score;
2+
3+
// #Medium #Array #Greedy #2024_09_09_Time_9_ms_(100.00%)_Space_63.2_MB_(100.00%)
4+
5+
importjava.util.List;
6+
7+
publicclassSolution {
8+
publiclongfindMaximumScore(List<Integer>nums) {
9+
longres =0;
10+
longma =0;
11+
for (intnum :nums) {
12+
res +=ma;
13+
ma =Math.max(ma,num);
14+
}
15+
returnres;
16+
}
17+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
3282\. Reach End of Array With Max Score
2+
3+
Medium
4+
5+
You are given an integer array`nums` of length`n`.
6+
7+
Your goal is to start at index`0` and reach index`n - 1`. You can only jump to indices**greater** than your current index.
8+
9+
The score for a jump from index`i` to index`j` is calculated as`(j - i) * nums[i]`.
10+
11+
Return the**maximum** possible**total score** by the time you reach the last index.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[1,3,1,5]
16+
17+
**Output:** 7
18+
19+
**Explanation:**
20+
21+
First, jump to index 1 and then jump to the last index. The final score is`1 * 1 + 2 * 3 = 7`.
22+
23+
**Example 2:**
24+
25+
**Input:** nums =[4,3,1,3,2]
26+
27+
**Output:** 16
28+
29+
**Explanation:**
30+
31+
Jump directly to the last index. The final score is`4 * 4 = 16`.
32+
33+
**Constraints:**
34+
35+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
36+
* <code>1 <= nums[i] <= 10<sup>5</sup></code>
Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
packageg3201_3300.s3283_maximum_number_of_moves_to_kill_all_pawns;
2+
3+
// #Hard #Array #Math #Breadth_First_Search #Bit_Manipulation #Bitmask #Game_Theory
4+
// #2024_09_09_Time_250_ms_(98.43%)_Space_50.1_MB_(66.27%)
5+
6+
importjava.util.LinkedList;
7+
importjava.util.Queue;
8+
9+
publicclassSolution {
10+
privatestaticfinalint[][]KNIGHT_MOVES = {
11+
{-2, -1}, {-2,1}, {-1, -2}, {-1,2},
12+
{1, -2}, {1,2}, {2, -1}, {2,1}
13+
};
14+
privateint[][]distances;
15+
privateInteger[][]memo;
16+
17+
publicintmaxMoves(intkx,intky,int[][]positions) {
18+
intn =positions.length;
19+
distances =newint[n +1][n +1];
20+
memo =newInteger[n +1][1 <<n];
21+
// Calculate distances between all pairs of positions (including knight's initial position)
22+
for (inti =0;i <n;i++) {
23+
distances[n][i] =calculateMoves(kx,ky,positions[i][0],positions[i][1]);
24+
for (intj =i +1;j <n;j++) {
25+
intdist =
26+
calculateMoves(
27+
positions[i][0],positions[i][1],positions[j][0],positions[j][1]);
28+
distances[i][j] =distances[j][i] =dist;
29+
}
30+
}
31+
returnminimax(n, (1 <<n) -1,true);
32+
}
33+
34+
privateintminimax(intlastPos,intremainingPawns,booleanisAlice) {
35+
if (remainingPawns ==0) {
36+
return0;
37+
}
38+
if (memo[lastPos][remainingPawns] !=null) {
39+
returnmemo[lastPos][remainingPawns];
40+
}
41+
intresult =isAlice ?0 :Integer.MAX_VALUE;
42+
for (inti =0;i <distances.length -1;i++) {
43+
if ((remainingPawns & (1 <<i)) !=0) {
44+
intnewRemainingPawns =remainingPawns & ~(1 <<i);
45+
intmoveValue =distances[lastPos][i] +minimax(i,newRemainingPawns, !isAlice);
46+
47+
if (isAlice) {
48+
result =Math.max(result,moveValue);
49+
}else {
50+
result =Math.min(result,moveValue);
51+
}
52+
}
53+
}
54+
memo[lastPos][remainingPawns] =result;
55+
returnresult;
56+
}
57+
58+
privateintcalculateMoves(intx1,inty1,intx2,inty2) {
59+
if (x1 ==x2 &&y1 ==y2) {
60+
return0;
61+
}
62+
boolean[][]visited =newboolean[50][50];
63+
Queue<int[]>queue =newLinkedList<>();
64+
queue.offer(newint[] {x1,y1,0});
65+
visited[x1][y1] =true;
66+
while (!queue.isEmpty()) {
67+
int[]current =queue.poll();
68+
intx =current[0];
69+
inty =current[1];
70+
intmoves =current[2];
71+
for (int[]move :KNIGHT_MOVES) {
72+
intnx =x +move[0];
73+
intny =y +move[1];
74+
if (nx ==x2 &&ny ==y2) {
75+
returnmoves +1;
76+
}
77+
if (nx >=0 &&nx <50 &&ny >=0 &&ny <50 && !visited[nx][ny]) {
78+
queue.offer(newint[] {nx,ny,moves +1});
79+
visited[nx][ny] =true;
80+
}
81+
}
82+
}
83+
// Should never reach here if input is valid
84+
return -1;
85+
}
86+
}
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
3283\. Maximum Number of Moves to Kill All Pawns
2+
3+
Hard
4+
5+
There is a`50 x 50` chessboard with**one** knight and some pawns on it. You are given two integers`kx` and`ky` where`(kx, ky)` denotes the position of the knight, and a 2D array`positions` where <code>positions[i] =[x<sub>i</sub>, y<sub>i</sub>]</code> denotes the position of the pawns on the chessboard.
6+
7+
Alice and Bob play a_turn-based_ game, where Alice goes first. In each player's turn:
8+
9+
* The player_selects_ a pawn that still exists on the board and captures it with the knight in the**fewest** possible**moves**.**Note** that the player can select**any** pawn, it**might not** be one that can be captured in the**least** number of moves.
10+
* In the process of capturing the_selected_ pawn, the knight**may** pass other pawns**without** capturing them.**Only** the_selected_ pawn can be captured in_this_ turn.
11+
12+
Alice is trying to**maximize** the**sum** of the number of moves made by_both_ players until there are no more pawns on the board, whereas Bob tries to**minimize** them.
13+
14+
Return the**maximum**_total_ number of moves made during the game that Alice can achieve, assuming both players play**optimally**.
15+
16+
Note that in one**move,** a chess knight has eight possible positions it can move to, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.
17+
18+
![](https://assets.leetcode.com/uploads/2024/08/01/chess_knight.jpg)
19+
20+
**Example 1:**
21+
22+
**Input:** kx = 1, ky = 1, positions =[[0,0]]
23+
24+
**Output:** 4
25+
26+
**Explanation:**
27+
28+
![](https://assets.leetcode.com/uploads/2024/08/16/gif3.gif)
29+
30+
The knight takes 4 moves to reach the pawn at`(0, 0)`.
31+
32+
**Example 2:**
33+
34+
**Input:** kx = 0, ky = 2, positions =[[1,1],[2,2],[3,3]]
35+
36+
**Output:** 8
37+
38+
**Explanation:**
39+
40+
**![](https://assets.leetcode.com/uploads/2024/08/16/gif4.gif)**
41+
42+
* Alice picks the pawn at`(2, 2)` and captures it in two moves:`(0, 2) -> (1, 4) -> (2, 2)`.
43+
* Bob picks the pawn at`(3, 3)` and captures it in two moves:`(2, 2) -> (4, 1) -> (3, 3)`.
44+
* Alice picks the pawn at`(1, 1)` and captures it in four moves:`(3, 3) -> (4, 1) -> (2, 2) -> (0, 3) -> (1, 1)`.
45+
46+
**Example 3:**
47+
48+
**Input:** kx = 0, ky = 0, positions =[[1,2],[2,4]]
49+
50+
**Output:** 3
51+
52+
**Explanation:**
53+
54+
* Alice picks the pawn at`(2, 4)` and captures it in two moves:`(0, 0) -> (1, 2) -> (2, 4)`. Note that the pawn at`(1, 2)` is not captured.
55+
* Bob picks the pawn at`(1, 2)` and captures it in one move:`(2, 4) -> (1, 2)`.
56+
57+
**Constraints:**
58+
59+
*`0 <= kx, ky <= 49`
60+
*`1 <= positions.length <= 15`
61+
*`positions[i].length == 2`
62+
*`0 <= positions[i][0], positions[i][1] <= 49`
63+
* All`positions[i]` are unique.
64+
* The input is generated such that`positions[i] != [kx, ky]` for all`0 <= i < positions.length`.
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
packageg3201_3300.s3280_convert_date_to_binary;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidconvertDateToBinary() {
11+
assertThat(
12+
newSolution().convertDateToBinary("2080-02-29"),equalTo("100000100000-10-11101"));
13+
}
14+
15+
@Test
16+
voidconvertDateToBinary2() {
17+
assertThat(newSolution().convertDateToBinary("1900-01-01"),equalTo("11101101100-1-1"));
18+
}
19+
}
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg3201_3300.s3281_maximize_score_of_numbers_in_ranges;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classSolutionTest {
9+
@Test
10+
voidmaxPossibleScore() {
11+
assertThat(newSolution().maxPossibleScore(newint[] {6,0,3},2),equalTo(4));
12+
}
13+
14+
@Test
15+
voidmaxPossibleScore2() {
16+
assertThat(newSolution().maxPossibleScore(newint[] {2,6,13,13},5),equalTo(5));
17+
}
18+
}
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
packageg3201_3300.s3282_reach_end_of_array_with_max_score;
2+
3+
importstaticorg.hamcrest.CoreMatchers.equalTo;
4+
importstaticorg.hamcrest.MatcherAssert.assertThat;
5+
6+
importjava.util.List;
7+
importorg.junit.jupiter.api.Test;
8+
9+
classSolutionTest {
10+
@Test
11+
voidfindMaximumScore() {
12+
assertThat(newSolution().findMaximumScore(List.of(1,3,1,5)),equalTo(7L));
13+
}
14+
15+
@Test
16+
voidfindMaximumScore2() {
17+
assertThat(newSolution().findMaximumScore(List.of(4,3,1,3,2)),equalTo(16L));
18+
}
19+
}

0 commit comments

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