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

Commitc31be13

Browse files
authored
Added tasks 2768-2772
1 parent5498a9e commitc31be13

File tree

15 files changed

+492
-0
lines changed

15 files changed

+492
-0
lines changed
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
packageg2701_2800.s2768_number_of_black_blocks;
2+
3+
// #Medium #Array #Hash_Table #Enumeration #2023_09_21_Time_94_ms_(98.91%)_Space_55.3_MB_(48.37%)
4+
5+
importjava.util.Arrays;
6+
importjava.util.HashMap;
7+
importjava.util.Map;
8+
9+
publicclassSolution {
10+
publiclong[]countBlackBlocks(intm,intn,int[][]coordinates) {
11+
long[]ans =newlong[5];
12+
Map<Integer,Integer>count =newHashMap<>();
13+
for (int[]coordinate :coordinates) {
14+
intx =coordinate[0];
15+
inty =coordinate[1];
16+
for (inti =x;i <x +2;i++) {
17+
for (intj =y;j <y +2;j++) {
18+
if (i -1 >=0 &&i <m &&j -1 >=0 &&j <n) {
19+
count.merge(i *n +j,1, (a,b) ->a +b);
20+
}
21+
}
22+
}
23+
}
24+
for (intfreq :count.values()) {
25+
ans[freq]++;
26+
}
27+
ans[0] = (m -1L) * (n -1) -Arrays.stream(ans).sum();
28+
returnans;
29+
}
30+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
2768\. Number of Black Blocks
2+
3+
Medium
4+
5+
You are given two integers`m` and`n` representing the dimensions of a**0-indexed**`m x n` grid.
6+
7+
You are also given a**0-indexed** 2D integer matrix`coordinates`, where`coordinates[i] = [x, y]` indicates that the cell with coordinates`[x, y]` is colored**black**. All cells in the grid that do not appear in`coordinates` are**white**.
8+
9+
A block is defined as a`2 x 2` submatrix of the grid. More formally, a block with cell`[x, y]` as its top-left corner where`0 <= x < m - 1` and`0 <= y < n - 1` contains the coordinates`[x, y]`,`[x + 1, y]`,`[x, y + 1]`, and`[x + 1, y + 1]`.
10+
11+
Return_a**0-indexed** integer array_`arr`_of size_`5`_such that_`arr[i]`_is the number of blocks that contains exactly_`i`_**black** cells_.
12+
13+
**Example 1:**
14+
15+
**Input:** m = 3, n = 3, coordinates =[[0,0]]
16+
17+
**Output:**[3,1,0,0,0]
18+
19+
**Explanation:** The grid looks like this:![](https://assets.leetcode.com/uploads/2023/06/18/screen-shot-2023-06-18-at-44656-am.png)
20+
21+
There is only 1 block with one black cell, and it is the block starting with cell[0,0].
22+
23+
The other 3 blocks start with cells[0,1],[1,0] and[1,1]. They all have zero black cells.
24+
25+
Thus, we return[3,1,0,0,0].
26+
27+
**Example 2:**
28+
29+
**Input:** m = 3, n = 3, coordinates =[[0,0],[1,1],[0,2]]
30+
31+
**Output:**[0,2,2,0,0]
32+
33+
**Explanation:** The grid looks like this:![](https://assets.leetcode.com/uploads/2023/06/18/screen-shot-2023-06-18-at-45018-am.png)
34+
35+
There are 2 blocks with two black cells (the ones starting with cell coordinates[0,0] and[0,1]).
36+
37+
The other 2 blocks have starting cell coordinates of[1,0] and[1,1]. They both have 1 black cell.
38+
39+
Therefore, we return[0,2,2,0,0].
40+
41+
**Constraints:**
42+
43+
* <code>2 <= m <= 10<sup>5</sup></code>
44+
* <code>2 <= n <= 10<sup>5</sup></code>
45+
* <code>0 <= coordinates.length <= 10<sup>4</sup></code>
46+
*`coordinates[i].length == 2`
47+
*`0 <= coordinates[i][0] < m`
48+
*`0 <= coordinates[i][1] < n`
49+
* It is guaranteed that`coordinates` contains pairwise distinct coordinates.
Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
packageg2701_2800.s2769_find_the_maximum_achievable_number;
2+
3+
// #Easy #Math #2023_09_21_Time_1_ms_(100.00%)_Space_40.4_MB_(26.03%)
4+
5+
publicclassSolution {
6+
publicinttheMaximumAchievableX(intnum,intt) {
7+
returnnum +t *2;
8+
}
9+
}
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
2769\. Find the Maximum Achievable Number
2+
3+
Easy
4+
5+
You are given two integers,`num` and`t`.
6+
7+
An integer`x` is called**achievable** if it can become equal to`num` after applying the following operation no more than`t` times:
8+
9+
* Increase or decrease`x` by`1`, and simultaneously increase or decrease`num` by`1`.
10+
11+
Return_the maximum possible achievable number_. It can be proven that there exists at least one achievable number.
12+
13+
**Example 1:**
14+
15+
**Input:** num = 4, t = 1
16+
17+
**Output:** 6
18+
19+
**Explanation:**
20+
21+
The maximum achievable number is x = 6; it can become equal to num after performing this operation:
22+
23+
1- Decrease x by 1, and increase num by 1. Now, x = 5 and num = 5.
24+
25+
It can be proven that there is no achievable number larger than 6.
26+
27+
**Example 2:**
28+
29+
**Input:** num = 3, t = 2
30+
31+
**Output:** 7
32+
33+
**Explanation:**
34+
35+
The maximum achievable number is x = 7; after performing these operations, x will equal num:
36+
37+
1- Decrease x by 1, and increase num by 1. Now, x = 6 and num = 4.
38+
39+
2- Decrease x by 1, and increase num by 1. Now, x = 5 and num = 5.
40+
41+
It can be proven that there is no achievable number larger than 7.
42+
43+
**Constraints:**
44+
45+
*`1 <= num, t <= 50`
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
packageg2701_2800.s2770_maximum_number_of_jumps_to_reach_the_last_index;
2+
3+
// #Medium #Array #Dynamic_Programming #2023_09_21_Time_17_ms_(60.93%)_Space_44_MB_(28.52%)
4+
5+
publicclassSolution {
6+
privatestaticclassPair {
7+
intprev;
8+
intlen;
9+
10+
Pair(intprev,intlen) {
11+
this.prev =prev;
12+
this.len =len;
13+
}
14+
}
15+
16+
publicintmaximumJumps(int[]nums,inttarget) {
17+
Pair[]arr =newPair[nums.length];
18+
arr[0] =newPair(0,0);
19+
for (inti =1;i <nums.length;i++) {
20+
arr[i] =newPair(-1,0);
21+
for (intj =i -1;j >=0;j--) {
22+
if (Math.abs(nums[i] -nums[j]) <=target
23+
&&arr[j].prev != -1
24+
&&arr[j].len +1 >arr[i].len) {
25+
arr[i].prev =j;
26+
arr[i].len =arr[j].len +1;
27+
}
28+
}
29+
}
30+
returnarr[nums.length -1].len >0 ?arr[nums.length -1].len : -1;
31+
}
32+
}
Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
2770\. Maximum Number of Jumps to Reach the Last Index
2+
3+
Medium
4+
5+
You are given a**0-indexed** array`nums` of`n` integers and an integer`target`.
6+
7+
You are initially positioned at index`0`. In one step, you can jump from index`i` to any index`j` such that:
8+
9+
*`0 <= i < j < n`
10+
*`-target <= nums[j] - nums[i] <= target`
11+
12+
Return_the**maximum number of jumps** you can make to reach index_`n - 1`.
13+
14+
If there is no way to reach index`n - 1`, return`-1`.
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[1,3,6,4,1,2], target = 2
19+
20+
**Output:** 3
21+
22+
**Explanation:**
23+
24+
To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
25+
26+
- Jump from index 0 to index 1.
27+
28+
- Jump from index 1 to index 3.
29+
30+
- Jump from index 3 to index 5.
31+
32+
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps.
33+
34+
Hence, the answer is 3.
35+
36+
**Example 2:**
37+
38+
**Input:** nums =[1,3,6,4,1,2], target = 3
39+
40+
**Output:** 5
41+
42+
**Explanation:**
43+
44+
To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
45+
46+
- Jump from index 0 to index 1.
47+
48+
- Jump from index 1 to index 2.
49+
50+
- Jump from index 2 to index 3.
51+
52+
- Jump from index 3 to index 4.
53+
54+
- Jump from index 4 to index 5.
55+
56+
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps.
57+
58+
Hence, the answer is 5.
59+
60+
**Example 3:**
61+
62+
**Input:** nums =[1,3,6,4,1,2], target = 0
63+
64+
**Output:** -1
65+
66+
**Explanation:** It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1.
67+
68+
**Constraints:**
69+
70+
*`2 <= nums.length == n <= 1000`
71+
* <code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code>
72+
* <code>0 <= target <= 2 * 10<sup>9</sup></code>
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
packageg2701_2800.s2771_longest_non_decreasing_subarray_from_two_arrays;
2+
3+
// #Medium #Array #Dynamic_Programming #2023_09_21_Time_4_ms_(97.62%)_Space_56.9_MB_(78.75%)
4+
5+
publicclassSolution {
6+
publicintmaxNonDecreasingLength(int[]nums1,int[]nums2) {
7+
intres =1;
8+
intdp1 =1;
9+
intdp2 =1;
10+
intn =nums1.length;
11+
intt11;
12+
intt12;
13+
intt21;
14+
intt22;
15+
for (inti =1;i <n;i++) {
16+
t11 = (nums1[i -1] <=nums1[i]) ?dp1 +1 :1;
17+
t12 = (nums1[i -1] <=nums2[i]) ?dp1 +1 :1;
18+
t21 = (nums2[i -1] <=nums1[i]) ?dp2 +1 :1;
19+
t22 = (nums2[i -1] <=nums2[i]) ?dp2 +1 :1;
20+
dp1 =Math.max(t11,t21);
21+
dp2 =Math.max(t12,t22);
22+
res =Math.max(res,Math.max(dp1,dp2));
23+
}
24+
returnres;
25+
}
26+
}
Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
2771\. Longest Non-decreasing Subarray From Two Arrays
2+
3+
Medium
4+
5+
You are given two**0-indexed** integer arrays`nums1` and`nums2` of length`n`.
6+
7+
Let's define another**0-indexed** integer array,`nums3`, of length`n`. For each index`i` in the range`[0, n - 1]`, you can assign either`nums1[i]` or`nums2[i]` to`nums3[i]`.
8+
9+
Your task is to maximize the length of the**longest non-decreasing subarray** in`nums3` by choosing its values optimally.
10+
11+
Return_an integer representing the length of the**longest non-decreasing** subarray in_`nums3`.
12+
13+
**Note:** A**subarray** is a contiguous**non-empty** sequence of elements within an array.
14+
15+
**Example 1:**
16+
17+
**Input:** nums1 =[2,3,1], nums2 =[1,2,1]
18+
19+
**Output:** 2
20+
21+
**Explanation:**
22+
23+
One way to construct nums3 is:
24+
25+
nums3 =[nums1[0], nums2[1], nums2[2]] =>[2,2,1].
26+
27+
The subarray starting from index 0 and ending at index 1,[2,2], forms a non-decreasing subarray of length 2.
28+
29+
We can show that 2 is the maximum achievable length.
30+
31+
**Example 2:**
32+
33+
**Input:** nums1 =[1,3,2,1], nums2 =[2,2,3,4]
34+
35+
**Output:** 4
36+
37+
**Explanation:**
38+
39+
One way to construct nums3 is:
40+
41+
nums3 =[nums1[0], nums2[1], nums2[2], nums2[3]] =>[1,2,3,4].
42+
43+
The entire array forms a non-decreasing subarray of length 4, making it the maximum achievable length.
44+
45+
**Example 3:**
46+
47+
**Input:** nums1 =[1,1], nums2 =[2,2]
48+
49+
**Output:** 2
50+
51+
**Explanation:**
52+
53+
One way to construct nums3 is:
54+
55+
nums3 =[nums1[0], nums1[1]] =>[1,1].
56+
57+
The entire array forms a non-decreasing subarray of length 2, making it the maximum achievable length.
58+
59+
**Constraints:**
60+
61+
* <code>1 <= nums1.length == nums2.length == n <= 10<sup>5</sup></code>
62+
* <code>1 <= nums1[i], nums2[i] <= 10<sup>9</sup></code>
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
packageg2701_2800.s2772_apply_operations_to_make_all_array_elements_equal_to_zero;
2+
3+
// #Medium #Array #Prefix_Sum #2023_09_21_Time_1_ms_(100.00%)_Space_58.1_MB_(54.11%)
4+
5+
publicclassSolution {
6+
publicbooleancheckArray(int[]nums,intk) {
7+
intcur =0;
8+
intn =nums.length;
9+
for (inti =0;i <n;i++) {
10+
if (cur >nums[i]) {
11+
returnfalse;
12+
}
13+
nums[i] -=cur;
14+
cur +=nums[i];
15+
if (i >=k -1) {
16+
cur -=nums[i -k +1];
17+
}
18+
}
19+
returncur ==0;
20+
}
21+
}

0 commit comments

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