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

Commitfba23f5

Browse files
authored
Added tasks 2614-2618
1 parentbfdce7b commitfba23f5

File tree

15 files changed

+520
-0
lines changed

15 files changed

+520
-0
lines changed
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
packageg2601_2700.s2614_prime_in_diagonal;
2+
3+
// #Easy #Array #Math #Matrix #Number_Theory #2023_08_30_Time_0_ms_(100.00%)_Space_56.5_MB_(21.81%)
4+
5+
publicclassSolution {
6+
publicintdiagonalPrime(int[][]nums) {
7+
inti =0;
8+
intj =nums[0].length -1;
9+
intlp =0;
10+
while (i <nums.length) {
11+
intn1 =nums[i][i];
12+
if (n1 >lp &&isPrime(n1)) {
13+
lp =n1;
14+
}
15+
intn2 =nums[i][j];
16+
if (n2 >lp &&isPrime(n2)) {
17+
lp =n2;
18+
}
19+
i++;
20+
j--;
21+
}
22+
returnlp;
23+
}
24+
25+
privatebooleanisPrime(intn) {
26+
if (n ==1) {
27+
returnfalse;
28+
}
29+
if (n ==2 ||n ==3) {
30+
returntrue;
31+
}
32+
inti =2;
33+
while (i <=Math.sqrt(n)) {
34+
if (n %i ==0) {
35+
returnfalse;
36+
}
37+
i++;
38+
}
39+
returntrue;
40+
}
41+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
2614\. Prime In Diagonal
2+
3+
Easy
4+
5+
You are given a 0-indexed two-dimensional integer array`nums`.
6+
7+
Return_the largest**prime** number that lies on at least one of the**diagonals** of_`nums`. In case, no prime is present on any of the diagonals, return_0._
8+
9+
Note that:
10+
11+
* An integer is**prime** if it is greater than`1` and has no positive integer divisors other than`1` and itself.
12+
* An integer`val` is on one of the**diagonals** of`nums` if there exists an integer`i` for which`nums[i][i] = val` or an`i` for which`nums[i][nums.length - i - 1] = val`.
13+
14+
![](https://assets.leetcode.com/uploads/2023/03/06/screenshot-2023-03-06-at-45648-pm.png)
15+
16+
In the above diagram, one diagonal is**[1,5,9]** and another diagonal is**[3,5,7]**.
17+
18+
**Example 1:**
19+
20+
**Input:** nums =[[1,2,3],[5,6,7],[9,10,11]]
21+
22+
**Output:** 11
23+
24+
**Explanation:** The numbers 1, 3, 6, 9, and 11 are the only numbers present on at least one of the diagonals. Since 11 is the largest prime, we return 11.
25+
26+
**Example 2:**
27+
28+
**Input:** nums =[[1,2,3],[5,17,7],[9,11,10]]
29+
30+
**Output:** 17
31+
32+
**Explanation:** The numbers 1, 3, 9, 10, and 17 are all present on at least one of the diagonals. 17 is the largest prime, so we return 17.
33+
34+
**Constraints:**
35+
36+
*`1 <= nums.length <= 300`
37+
* <code>nums.length == nums<sub>i</sub>.length</code>
38+
* <code>1 <= nums[i][j] <= 4*10<sup>6</sup></code>
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg2601_2700.s2615_sum_of_distances;
2+
3+
// #Medium #Array #Hash_Table #Prefix_Sum #2023_08_30_Time_13_ms_(100.00%)_Space_70.4_MB_(43.45%)
4+
5+
importjava.util.HashMap;
6+
7+
publicclassSolution {
8+
publiclong[]distance(int[]nums) {
9+
HashMap<Integer,long[]>map =newHashMap<>();
10+
for (inti =0;i <nums.length;i++) {
11+
long[]temp =map.computeIfAbsent(nums[i],k ->newlong[4]);
12+
temp[0] +=i;
13+
temp[2]++;
14+
}
15+
long[]ans =newlong[nums.length];
16+
for (inti =0;i <nums.length;i++) {
17+
long[]temp =map.get(nums[i]);
18+
ans[i] +=i *temp[3] -temp[1];
19+
temp[1] +=i;
20+
temp[3]++;
21+
ans[i] +=temp[0] -temp[1] -i * (temp[2] -temp[3]);
22+
}
23+
returnans;
24+
}
25+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
2615\. Sum of Distances
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums`. There exists an array`arr` of length`nums.length`, where`arr[i]` is the sum of`|i - j|` over all`j` such that`nums[j] == nums[i]` and`j != i`. If there is no such`j`, set`arr[i]` to be`0`.
6+
7+
Return_the array_`arr`_._
8+
9+
**Example 1:**
10+
11+
**Input:** nums =[1,3,1,1,2]
12+
13+
**Output:**[5,0,3,4,0]
14+
15+
**Explanation:**
16+
17+
When i = 0, nums[0] == nums[2] and nums[0] == nums[3]. Therefore, arr[0] = |0 - 2| + |0 - 3| = 5.
18+
19+
When i = 1, arr[1] = 0 because there is no other index with value 3.
20+
21+
When i = 2, nums[2] == nums[0] and nums[2] == nums[3]. Therefore, arr[2] = |2 - 0| + |2 - 3| = 3.
22+
23+
When i = 3, nums[3] == nums[0] and nums[3] == nums[2]. Therefore, arr[3] = |3 - 0| + |3 - 2| = 4.
24+
25+
When i = 4, arr[4] = 0 because there is no other index with value 2.
26+
27+
**Example 2:**
28+
29+
**Input:** nums =[0,5,3]
30+
31+
**Output:**[0,0,0]
32+
33+
**Explanation:** Since each element in nums is distinct, arr[i] = 0 for all i.
34+
35+
**Constraints:**
36+
37+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
38+
* <code>0 <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
packageg2601_2700.s2616_minimize_the_maximum_difference_of_pairs;
2+
3+
// #Medium #Array #Greedy #Binary_Search #2023_08_30_Time_16_ms_(91.77%)_Space_58.7_MB_(90.15%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
privatebooleanisPossible(int[]nums,intp,intdiff) {
9+
intn =nums.length;
10+
inti =1;
11+
while (i <n) {
12+
if (nums[i] -nums[i -1] <=diff) {
13+
p--;
14+
i++;
15+
}
16+
i++;
17+
}
18+
returnp <=0;
19+
}
20+
21+
publicintminimizeMax(int[]nums,intp) {
22+
intn =nums.length;
23+
Arrays.sort(nums);
24+
intleft =0;
25+
intright =nums[n -1] -nums[0];
26+
intans =right;
27+
while (left <=right) {
28+
intmid =left + (right -left) /2;
29+
if (isPossible(nums,p,mid)) {
30+
ans =mid;
31+
right =mid -1;
32+
}else {
33+
left =mid +1;
34+
}
35+
}
36+
returnans;
37+
}
38+
}
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
2616\. Minimize the Maximum Difference of Pairs
2+
3+
Medium
4+
5+
You are given a**0-indexed** integer array`nums` and an integer`p`. Find`p` pairs of indices of`nums` such that the**maximum** difference amongst all the pairs is**minimized**. Also, ensure no index appears more than once amongst the`p` pairs.
6+
7+
Note that for a pair of elements at the index`i` and`j`, the difference of this pair is`|nums[i] - nums[j]|`, where`|x|` represents the**absolute****value** of`x`.
8+
9+
Return_the**minimum****maximum** difference among all_`p`_pairs._ We define the maximum of an empty set to be zero.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[10,1,2,7,1,3], p = 2
14+
15+
**Output:** 1
16+
17+
**Explanation:**
18+
19+
The first pair is formed from the indices 1 and 4, and the second pair is formed from the indices 2 and 5.
20+
21+
The maximum difference is max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1. Therefore, we return 1.
22+
23+
**Example 2:**
24+
25+
**Input:** nums =[4,2,1,2], p = 1
26+
27+
**Output:** 0
28+
29+
**Explanation:**
30+
31+
Let the indices 1 and 3 form a pair. The difference of that pair is |2 - 2| = 0, which is the minimum we can attain.
32+
33+
**Constraints:**
34+
35+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
36+
* <code>0 <= nums[i] <= 10<sup>9</sup></code>
37+
*`0 <= p <= (nums.length)/2`
Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
packageg2601_2700.s2617_minimum_number_of_visited_cells_in_a_grid;
2+
3+
// #Hard #Array #Dynamic_Programming #Binary_Search #Stack #Union_Find #Segment_Tree
4+
// #Binary_Indexed_Tree #2023_08_30_Time_34_ms_(100.00%)_Space_76_MB_(65.00%)
5+
6+
importjava.util.ArrayDeque;
7+
importjava.util.Arrays;
8+
importjava.util.Queue;
9+
10+
publicclassSolution {
11+
privatestaticfinalintLIMIT =2;
12+
13+
publicintminimumVisitedCells(int[][]grid) {
14+
int[][]len =newint[grid.length][grid[0].length];
15+
for (int[]ints :len) {
16+
Arrays.fill(ints, -1);
17+
}
18+
Queue<int[]>q =newArrayDeque<>();
19+
q.add(newint[] {0,0});
20+
len[0][0] =1;
21+
while (!q.isEmpty()) {
22+
int[]tmp =q.poll();
23+
inti =tmp[0];
24+
intj =tmp[1];
25+
intc =0;
26+
for (intk =Math.min(grid[0].length -1,grid[i][j] +j);k >j;k--) {
27+
if (len[i][k] != -1) {
28+
c++;
29+
if (c >LIMIT) {
30+
break;
31+
}
32+
}else {
33+
len[i][k] =len[i][j] +1;
34+
q.add(newint[] {i,k});
35+
}
36+
}
37+
if (len[grid.length -1][grid[0].length -1] != -1) {
38+
returnlen[grid.length -1][grid[0].length -1];
39+
}
40+
c =0;
41+
for (intk =Math.min(grid.length -1,grid[i][j] +i);k >i;k--) {
42+
if (len[k][j] != -1) {
43+
c++;
44+
if (c >LIMIT) {
45+
break;
46+
}
47+
}else {
48+
len[k][j] =len[i][j] +1;
49+
q.add(newint[] {k,j});
50+
}
51+
}
52+
if (len[grid.length -1][grid[0].length -1] != -1) {
53+
returnlen[grid.length -1][grid[0].length -1];
54+
}
55+
}
56+
return -1;
57+
}
58+
}
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
2617\. Minimum Number of Visited Cells in a Grid
2+
3+
Hard
4+
5+
You are given a**0-indexed**`m x n` integer matrix`grid`. Your initial position is at the**top-left** cell`(0, 0)`.
6+
7+
Starting from the cell`(i, j)`, you can move to one of the following cells:
8+
9+
* Cells`(i, k)` with`j < k <= grid[i][j] + j` (rightward movement), or
10+
* Cells`(k, j)` with`i < k <= grid[i][j] + i` (downward movement).
11+
12+
Return_the minimum number of cells you need to visit to reach the**bottom-right** cell_`(m - 1, n - 1)`. If there is no valid path, return`-1`.
13+
14+
**Example 1:**
15+
16+
![](https://assets.leetcode.com/uploads/2023/01/25/ex1.png)
17+
18+
**Input:** grid =[[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
19+
20+
**Output:** 4
21+
22+
**Explanation:** The image above shows one of the paths that visits exactly 4 cells.
23+
24+
**Example 2:**
25+
26+
![](https://assets.leetcode.com/uploads/2023/01/25/ex2.png)
27+
28+
**Input:** grid =[[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
29+
30+
**Output:** 3
31+
32+
**Explanation:** The image above shows one of the paths that visits exactly 3 cells.
33+
34+
**Example 3:**
35+
36+
![](https://assets.leetcode.com/uploads/2023/01/26/ex3.png)
37+
38+
**Input:** grid =[[2,1,0],[1,0,0]]
39+
40+
**Output:** -1
41+
42+
**Explanation:** It can be proven that no path exists.
43+
44+
**Constraints:**
45+
46+
*`m == grid.length`
47+
*`n == grid[i].length`
48+
* <code>1 <= m, n <= 10<sup>5</sup></code>
49+
* <code>1 <= m * n <= 10<sup>5</sup></code>
50+
*`0 <= grid[i][j] < m * n`
51+
*`grid[m - 1][n - 1] == 0`
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
2618\. Check if Object Instance of Class
2+
3+
Medium
4+
5+
Write a function that checks if a given value is an instance of a given class or superclass. For this problem, an object is considered an instance of a given class if that object has access to that class's methods.
6+
7+
There are no constraints on the data types that can be passed to the function. For example, the value or the class could be`undefined`.
8+
9+
**Example 1:**
10+
11+
**Input:** func = () => checkIfInstanceOf(new Date(), Date)
12+
13+
**Output:** true
14+
15+
**Explanation:** The object returned by the Date constructor is, by definition, an instance of Date.
16+
17+
**Example 2:**
18+
19+
**Input:** func = () => { class Animal {}; class Dog extends Animal {}; return checkIfInstanceOf(new Dog(), Animal); }
20+
21+
**Output:** true
22+
23+
**Explanation:**
24+
25+
class Animal {};
26+
27+
class Dog extends Animal {};
28+
29+
checkIfInstanceOf(new Dog(), Animal); // true
30+
31+
Dog is a subclass of Animal. Therefore, a Dog object is an instance of both Dog and Animal.
32+
33+
**Example 3:**
34+
35+
**Input:** func = () => checkIfInstanceOf(Date, Date)
36+
37+
**Output:** false
38+
39+
**Explanation:** A date constructor cannot logically be an instance of itself.
40+
41+
**Example 4:**
42+
43+
**Input:** func = () => checkIfInstanceOf(5, Number)
44+
45+
**Output:** true
46+
47+
**Explanation:** 5 is a Number. Note that the "instanceof" keyword would return false. However, it is still considered an instance of Number because it accesses the Number methods. For example "toFixed()".

0 commit comments

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