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

Commit39c8184

Browse files
authored
Added tasks 2596-2601
1 parent1adfea4 commit39c8184

File tree

15 files changed

+522
-0
lines changed

15 files changed

+522
-0
lines changed
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
packageg2501_2600.s2596_check_knight_tour_configuration;
2+
3+
// #Medium #Array #Depth_First_Search #Breadth_First_Search #Matrix #Simulation
4+
// #2023_08_29_Time_1_ms_(100.00%)_Space_43.4_MB_(42.62%)
5+
6+
publicclassSolution {
7+
publicbooleancheckValidGrid(int[][]grid) {
8+
if (grid[0][0] !=0) {
9+
returnfalse;
10+
}
11+
intn =grid.length;
12+
intm =grid[0].length;
13+
int[]rmove = {2,2, -2, -2,1,1, -1, -1};
14+
int[]cmove = {1, -1,1, -1,2, -2,2, -2};
15+
intcnt =0;
16+
for (inti =0;i <n;i++) {
17+
for (intj =0;j <m;j++) {
18+
intval =grid[i][j];
19+
booleanisPoss =false;
20+
for (intd =0;d <8;d++) {
21+
intr =i +rmove[d];
22+
intc =j +cmove[d];
23+
if (r >=0 &&c >=0 &&r <n &&c <m &&grid[r][c] ==val +1) {
24+
isPoss =true;
25+
}
26+
}
27+
if (!isPoss) {
28+
cnt++;
29+
}
30+
if (cnt >1) {
31+
returnfalse;
32+
}
33+
}
34+
}
35+
returntrue;
36+
}
37+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2596\. Check Knight Tour Configuration
2+
3+
Medium
4+
5+
There is a knight on an`n x n` chessboard. In a valid configuration, the knight starts**at the top-left cell** of the board and visits every cell on the board**exactly once**.
6+
7+
You are given an`n x n` integer matrix`grid` consisting of distinct integers from the range`[0, n * n - 1]` where`grid[row][col]` indicates that the cell`(row, col)` is the <code>grid[row][col]<sup>th</sup></code> cell that the knight visited. The moves are**0-indexed**.
8+
9+
Return`true`_if_`grid`_represents a valid configuration of the knight's movements or_`false`_otherwise_.
10+
11+
**Note** that a valid knight move consists of moving two squares vertically and one square horizontally, or two squares horizontally and one square vertically. The figure below illustrates all the possible eight moves of a knight from some cell.
12+
13+
![](https://assets.leetcode.com/uploads/2018/10/12/knight.png)
14+
15+
**Example 1:**
16+
17+
![](https://assets.leetcode.com/uploads/2022/12/28/yetgriddrawio-5.png)
18+
19+
**Input:** grid =[[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
20+
21+
**Output:** true
22+
23+
**Explanation:** The above diagram represents the grid. It can be shown that it is a valid configuration.
24+
25+
**Example 2:**
26+
27+
![](https://assets.leetcode.com/uploads/2022/12/28/yetgriddrawio-6.png)
28+
29+
**Input:** grid =[[0,3,6],[5,8,1],[2,7,4]]
30+
31+
**Output:** false
32+
33+
**Explanation:** The above diagram represents the grid. The 8<sup>th</sup> move of the knight is not valid considering its position after the 7<sup>th</sup> move.
34+
35+
**Constraints:**
36+
37+
*`n == grid.length == grid[i].length`
38+
*`3 <= n <= 7`
39+
*`0 <= grid[row][col] < n * n`
40+
* All integers in`grid` are**unique**.
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
packageg2501_2600.s2597_the_number_of_beautiful_subsets;
2+
3+
// #Medium #Array #Dynamic_Programming #Backtracking
4+
// #2023_08_29_Time_4_ms_(100.00%)_Space_43.8_MB_(67.74%)
5+
6+
importjava.util.ArrayList;
7+
importjava.util.HashMap;
8+
importjava.util.List;
9+
importjava.util.Map;
10+
11+
publicclassSolution {
12+
publicintbeautifulSubsets(int[]nums,intk) {
13+
Map<Integer,Integer>map =newHashMap<>();
14+
for (intn :nums) {
15+
map.put(n,map.getOrDefault(n,0) +1);
16+
}
17+
intres =1;
18+
for (intkey :map.keySet()) {
19+
if (!map.containsKey(key -k)) {
20+
if (!map.containsKey(key +k)) {
21+
res *=1 <<map.get(key);
22+
}else {
23+
List<Integer>freq =newArrayList<>();
24+
intlocalKey =key;
25+
while (map.containsKey(localKey)) {
26+
freq.add(map.get(localKey));
27+
localKey +=k;
28+
}
29+
res *=helper(freq);
30+
}
31+
}
32+
}
33+
returnres -1;
34+
}
35+
36+
privateinthelper(List<Integer>freq) {
37+
intn =freq.size();
38+
if (n ==1) {
39+
return1 <<freq.get(0);
40+
}
41+
int[]dp =newint[n];
42+
dp[0] = (1 <<freq.get(0)) -1;
43+
dp[1] = (1 <<freq.get(1)) -1;
44+
if (n ==2) {
45+
returndp[0] +dp[1] +1;
46+
}
47+
for (inti =2;i <n;i++) {
48+
if (i >2) {
49+
dp[i -2] +=dp[i -3];
50+
}
51+
52+
dp[i] = (dp[i -2] +1) * ((1 <<freq.get(i)) -1);
53+
}
54+
returndp[n -1] +dp[n -2] +dp[n -3] +1;
55+
}
56+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2597\. The Number of Beautiful Subsets
2+
3+
Medium
4+
5+
You are given an array`nums` of positive integers and a**positive** integer`k`.
6+
7+
A subset of`nums` is**beautiful** if it does not contain two integers with an absolute difference equal to`k`.
8+
9+
Return_the number of**non-empty beautiful** subsets of the array_`nums`.
10+
11+
A**subset** of`nums` is an array that can be obtained by deleting some (possibly none) elements from`nums`. Two subsets are different if and only if the chosen indices to delete are different.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[2,4,6], k = 2
16+
17+
**Output:** 4
18+
19+
**Explanation:**
20+
21+
The beautiful subsets of the array nums are:[2],[4],[6],[2, 6].
22+
23+
It can be proved that there are only 4 beautiful subsets in the array[2,4,6].
24+
25+
**Example 2:**
26+
27+
**Input:** nums =[1], k = 1
28+
29+
**Output:** 1
30+
31+
**Explanation:**
32+
33+
The beautiful subset of the array nums is[1].
34+
35+
It can be proved that there is only 1 beautiful subset in the array[1].
36+
37+
**Constraints:**
38+
39+
*`1 <= nums.length <= 20`
40+
*`1 <= nums[i], k <= 1000`
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
packageg2501_2600.s2598_smallest_missing_non_negative_integer_after_operations;
2+
3+
// #Medium #Array #Hash_Table #Math #Greedy #2023_08_29_Time_4_ms_(99.19%)_Space_58.2_MB_(83.87%)
4+
5+
publicclassSolution {
6+
publicintfindSmallestInteger(int[]nums,intvalue) {
7+
intn =nums.length;
8+
if (value ==1) {
9+
returnn;
10+
}
11+
int[]a =newint[value];
12+
for (inti =0;i <n;i++) {
13+
intk =nums[i] %value;
14+
if (k <0) {
15+
k = (value +k) %value;
16+
}
17+
a[k]++;
18+
}
19+
int[]minsResult =mins(a);
20+
intmin =minsResult[0];
21+
intminIndex =minsResult[1];
22+
returnmin *value +minIndex;
23+
}
24+
25+
privateint[]mins(int[]a) {
26+
intn =a.length;
27+
intmin =100001;
28+
intminIndex = -1;
29+
for (inti =0;i <n;i++) {
30+
if (a[i] <min) {
31+
min =a[i];
32+
minIndex =i;
33+
}
34+
}
35+
returnnewint[] {min,minIndex};
36+
}
37+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
2598\. Smallest Missing Non-negative Integer After Operations
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums` and an integer`value`.
6+
7+
In one operation, you can add or subtract`value` from any element of`nums`.
8+
9+
* For example, if`nums = [1,2,3]` and`value = 2`, you can choose to subtract`value` from`nums[0]` to make`nums = [-1,2,3]`.
10+
11+
The MEX (minimum excluded) of an array is the smallest missing**non-negative** integer in it.
12+
13+
* For example, the MEX of`[-1,2,3]` is`0` while the MEX of`[1,0,3]` is`2`.
14+
15+
Return_the maximum MEX of_`nums`_after applying the mentioned operation**any number of times**_.
16+
17+
**Example 1:**
18+
19+
**Input:** nums =[1,-10,7,13,6,8], value = 5
20+
21+
**Output:** 4
22+
23+
**Explanation:**
24+
25+
One can achieve this result by applying the following operations:
26+
27+
- Add value to nums[1] twice to make nums =[1,**<ins>0</ins>**,7,13,6,8]
28+
29+
- Subtract value from nums[2] once to make nums =[1,0,**<ins>2</ins>**,13,6,8]
30+
31+
- Subtract value from nums[3] twice to make nums =[1,0,2,**<ins>3</ins>**,6,8]
32+
33+
The MEX of nums is 4. It can be shown that 4 is the maximum MEX we can achieve.
34+
35+
**Example 2:**
36+
37+
**Input:** nums =[1,-10,7,13,6,8], value = 7
38+
39+
**Output:** 2
40+
41+
**Explanation:**
42+
43+
One can achieve this result by applying the following operation:
44+
45+
- subtract value from nums[2] once to make nums =[1,-10,<ins>**0**</ins>,13,6,8]
46+
47+
The MEX of nums is 2. It can be shown that 2 is the maximum MEX we can achieve.
48+
49+
**Constraints:**
50+
51+
* <code>1 <= nums.length, value <= 10<sup>5</sup></code>
52+
* <code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
packageg2501_2600.s2600_k_items_with_the_maximum_sum;
2+
3+
// #Easy #Math #Greedy #2023_08_29_Time_1_ms_(100.00%)_Space_40.3_MB_(19.10%)
4+
5+
publicclassSolution {
6+
publicintkItemsWithMaximumSum(intnumOnes,intnumZeros,intnumNegOnes,intk) {
7+
if (k <=numOnes) {
8+
returnk;
9+
}
10+
if (k <=numOnes +numZeros) {
11+
returnnumOnes;
12+
}
13+
intremainingSum =k - (numOnes +numZeros);
14+
returnnumOnes -remainingSum;
15+
}
16+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2600\. K Items With the Maximum Sum
2+
3+
Easy
4+
5+
There is a bag that consists of items, each item has a number`1`,`0`, or`-1` written on it.
6+
7+
You are given four**non-negative** integers`numOnes`,`numZeros`,`numNegOnes`, and`k`.
8+
9+
The bag initially contains:
10+
11+
*`numOnes` items with`1`s written on them.
12+
*`numZeroes` items with`0`s written on them.
13+
*`numNegOnes` items with`-1`s written on them.
14+
15+
We want to pick exactly`k` items among the available items. Return_the**maximum** possible sum of numbers written on the items_.
16+
17+
**Example 1:**
18+
19+
**Input:** numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
20+
21+
**Output:** 2
22+
23+
**Explanation:** We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 2 items with 1 written on them and get a sum in a total of 2. It can be proven that 2 is the maximum possible sum.
24+
25+
**Example 2:**
26+
27+
**Input:** numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
28+
29+
**Output:** 3
30+
31+
**Explanation:** We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 3 items with 1 written on them, and 1 item with 0 written on it, and get a sum in a total of 3. It can be proven that 3 is the maximum possible sum.
32+
33+
**Constraints:**
34+
35+
*`0 <= numOnes, numZeros, numNegOnes <= 50`
36+
*`0 <= k <= numOnes + numZeros + numNegOnes`
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
packageg2601_2700.s2601_prime_subtraction_operation;
2+
3+
// #Medium #Array #Math #Greedy #Binary_Search #Number_Theory
4+
// #2023_08_29_Time_2_ms_(100.00%)_Space_43.9_MB_(39.47%)
5+
6+
importjava.util.Arrays;
7+
8+
publicclassSolution {
9+
privateint[]primesUntil(intn) {
10+
if (n <2) {
11+
returnnewint[0];
12+
}
13+
int[]primes =newint[200];
14+
boolean[]composite =newboolean[n +1];
15+
primes[0] =2;
16+
intadded =1;
17+
inti =3;
18+
while (i <=n) {
19+
if (composite[i]) {
20+
i +=2;
21+
continue;
22+
}
23+
primes[added++] =i;
24+
intj =i *i;
25+
while (j <=n) {
26+
composite[j] =true;
27+
j +=i;
28+
}
29+
i +=2;
30+
}
31+
returnArrays.copyOf(primes,added);
32+
}
33+
34+
publicbooleanprimeSubOperation(int[]nums) {
35+
intmax =0;
36+
for (intn :nums) {
37+
max =Math.max(max,n);
38+
}
39+
int[]primes =primesUntil(max);
40+
intprev =0;
41+
for (intn :nums) {
42+
intpos =Arrays.binarySearch(primes,n -prev -1);
43+
if (pos == -1 &&n <=prev) {
44+
returnfalse;
45+
}
46+
prev =n - (pos == -1 ?0 : (pos <0 ?primes[-pos -2] :primes[pos]));
47+
}
48+
returntrue;
49+
}
50+
}

0 commit comments

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