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

Commit395b7d5

Browse files
authored
Added tasks 2748-2760
1 parenta827c81 commit395b7d5

File tree

15 files changed

+512
-0
lines changed

15 files changed

+512
-0
lines changed
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
packageg2701_2800.s2748_number_of_beautiful_pairs;
2+
3+
// #Easy #Array #Math #Number_Theory #2023_09_24_Time_11_ms_(91.00%)_Space_43.3_MB_(63.82%)
4+
5+
publicclassSolution {
6+
publicintcountBeautifulPairs(int[]nums) {
7+
intbeautifulPairs =0;
8+
inti =0;
9+
intj =1;
10+
while (i <nums.length -1) {
11+
intfirstDigit =getFirstDigit(nums[i]);
12+
while (j <nums.length) {
13+
intlastDigit =nums[j] %10;
14+
booleanbotDigitsAreEqualAndNot1 =firstDigit ==lastDigit &&firstDigit >1;
15+
booleanbotDigitsAreDivisibleBy2 =firstDigit %2 ==0 &&lastDigit %2 ==0;
16+
booleanbotDigitsAreDivisibleBy3 =firstDigit %3 ==0 &&lastDigit %3 ==0;
17+
18+
if (!botDigitsAreEqualAndNot1
19+
&& !botDigitsAreDivisibleBy2
20+
&& !botDigitsAreDivisibleBy3) {
21+
beautifulPairs++;
22+
}
23+
j++;
24+
}
25+
i++;
26+
j =i +1;
27+
}
28+
returnbeautifulPairs;
29+
}
30+
31+
privateintgetFirstDigit(intnum) {
32+
intn =num;
33+
intdigit =0;
34+
while (n >0) {
35+
digit =n %10;
36+
n /=10;
37+
}
38+
returndigit;
39+
}
40+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
2748\. Number of Beautiful Pairs
2+
3+
Easy
4+
5+
You are given a**0-indexed** integer array`nums`. A pair of indices`i`,`j` where`0 <= i < j < nums.length` is called beautiful if the**first digit** of`nums[i]` and the**last digit** of`nums[j]` are**coprime**.
6+
7+
Return_the total number of beautiful pairs in_`nums`.
8+
9+
Two integers`x` and`y` are**coprime** if there is no integer greater than 1 that divides both of them. In other words,`x` and`y` are coprime if`gcd(x, y) == 1`, where`gcd(x, y)` is the**greatest common divisor** of`x` and`y`.
10+
11+
**Example 1:**
12+
13+
**Input:** nums =[2,5,1,4]
14+
15+
**Output:** 5
16+
17+
**Explanation:** There are 5 beautiful pairs in nums:
18+
19+
When i = 0 and j = 1: the first digit of nums[0] is 2, and the last digit of nums[1] is 5. We can confirm that 2 and 5 are coprime, since gcd(2,5) == 1.
20+
21+
When i = 0 and j = 2: the first digit of nums[0] is 2, and the last digit of nums[2] is 1. Indeed, gcd(2,1) == 1.
22+
23+
When i = 1 and j = 2: the first digit of nums[1] is 5, and the last digit of nums[2] is 1. Indeed, gcd(5,1) == 1.
24+
25+
When i = 1 and j = 3: the first digit of nums[1] is 5, and the last digit of nums[3] is 4. Indeed, gcd(5,4) == 1.
26+
27+
When i = 2 and j = 3: the first digit of nums[2] is 1, and the last digit of nums[3] is 4. Indeed, gcd(1,4) == 1.
28+
29+
Thus, we return 5.
30+
31+
**Example 2:**
32+
33+
**Input:** nums =[11,21,12]
34+
35+
**Output:** 2
36+
37+
**Explanation:** There are 2 beautiful pairs:
38+
39+
When i = 0 and j = 1: the first digit of nums[0] is 1, and the last digit of nums[1] is 1. Indeed, gcd(1,1) == 1.
40+
41+
When i = 0 and j = 2: the first digit of nums[0] is 1, and the last digit of nums[2] is 2. Indeed, gcd(1,2) == 1.
42+
43+
Thus, we return 2.
44+
45+
**Constraints:**
46+
47+
*`2 <= nums.length <= 100`
48+
*`1 <= nums[i] <= 9999`
49+
*`nums[i] % 10 != 0`
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
packageg2701_2800.s2749_minimum_operations_to_make_the_integer_zero;
2+
3+
// #Medium #Bit_Manipulation #Brainteaser #2023_09_24_Time_1_ms_(91.11%)_Space_40.2_MB_(9.63%)
4+
5+
publicclassSolution {
6+
publicintmakeTheIntegerZero(intnum1,intnum2) {
7+
for (inti =0;i <=60;i++) {
8+
longtarget =num1 - (long)num2 *i;
9+
longnoOfBits =Long.bitCount(target);
10+
if (i >=noOfBits &&i <=target) {
11+
returni;
12+
}
13+
}
14+
return -1;
15+
}
16+
}
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
2749\. Minimum Operations to Make the Integer Zero
2+
3+
Medium
4+
5+
You are given two integers`num1` and`num2`.
6+
7+
In one operation, you can choose integer`i` in the range`[0, 60]` and subtract <code>2<sup>i</sup> + num2</code> from`num1`.
8+
9+
Return_the integer denoting the**minimum** number of operations needed to make_`num1`_equal to_`0`.
10+
11+
If it is impossible to make`num1` equal to`0`, return`-1`.
12+
13+
**Example 1:**
14+
15+
**Input:** num1 = 3, num2 = -2
16+
17+
**Output:** 3
18+
19+
**Explanation:** We can make 3 equal to 0 with the following operations:
20+
- We choose i = 2 and substract 2<sup>2</sup> + (-2) from 3, 3 - (4 + (-2)) = 1.
21+
- We choose i = 2 and substract 2<sup>2</sup> + (-2) from 1, 1 - (4 + (-2)) = -1.
22+
- We choose i = 0 and substract 2<sup>0</sup> + (-2) from -1, (-1) - (1 + (-2)) = 0.
23+
24+
It can be proven, that 3 is the minimum number of operations that we need to perform.
25+
26+
**Example 2:**
27+
28+
**Input:** num1 = 5, num2 = 7
29+
30+
**Output:** -1
31+
32+
**Explanation:** It can be proven, that it is impossible to make 5 equal to 0 with the given operation.
33+
34+
**Constraints:**
35+
36+
* <code>1 <= num1 <= 10<sup>9</sup></code>
37+
* <code>-10<sup>9</sup> <= num2 <= 10<sup>9</sup></code>
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
packageg2701_2800.s2750_ways_to_split_array_into_good_subarrays;
2+
3+
// #Medium #Array #Dynamic_Programming #Math #2023_09_24_Time_7_ms_(96.36%)_Space_59.3_MB_(75.71%)
4+
5+
publicclassSolution {
6+
publicintnumberOfGoodSubarraySplits(int[]nums) {
7+
intlastOne = -1;
8+
intn =nums.length;
9+
longans =1;
10+
longmod = (long)1e9 +7;
11+
for (inti =0;i <n;i++) {
12+
if (nums[i] ==1) {
13+
if (lastOne != -1) {
14+
ans =ans * (i -lastOne) %mod;
15+
}
16+
lastOne =i;
17+
}
18+
}
19+
if (lastOne == -1) {
20+
return0;
21+
}
22+
return (int)ans;
23+
}
24+
}
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
2750\. Ways to Split Array Into Good Subarrays
2+
3+
Medium
4+
5+
You are given a binary array`nums`.
6+
7+
A subarray of an array is**good** if it contains**exactly****one** element with the value`1`.
8+
9+
Return_an integer denoting the number of ways to split the array_`nums`_into**good** subarrays_. As the number may be too large, return it**modulo** <code>10<sup>9</sup> + 7</code>.
10+
11+
A subarray is a contiguous**non-empty** sequence of elements within an array.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[0,1,0,0,1]
16+
17+
**Output:** 3
18+
19+
**Explanation:** There are 3 ways to split nums into good subarrays:
20+
-[0,1][0,0,1]
21+
-[0,1,0][0,1]
22+
-[0,1,0,0][1]
23+
24+
**Example 2:**
25+
26+
**Input:** nums =[0,1,0]
27+
28+
**Output:** 1
29+
30+
**Explanation:** There is 1 way to split nums into good subarrays: -[0,1,0]
31+
32+
**Constraints:**
33+
34+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
35+
*`0 <= nums[i] <= 1`
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
packageg2701_2800.s2751_robot_collisions;
2+
3+
// #Hard #Array #Sorting #Stack #Simulation #2023_09_24_Time_29_ms_(98.29%)_Space_59.5_MB_(66.29%)
4+
5+
importjava.util.ArrayDeque;
6+
importjava.util.ArrayList;
7+
importjava.util.Comparator;
8+
importjava.util.Deque;
9+
importjava.util.List;
10+
11+
publicclassSolution {
12+
publicList<Integer>survivedRobotsHealths(int[]positions,int[]healths,Stringdirections) {
13+
intn =positions.length;
14+
List<Integer>rindex =newArrayList<>();
15+
for (inti =0;i <n;i++) {
16+
rindex.add(i);
17+
}
18+
rindex.sort(Comparator.comparingInt(a ->positions[a]));
19+
Deque<Integer>stack =newArrayDeque<>();
20+
for (inti :rindex) {
21+
if (directions.charAt(i) =='R') {
22+
stack.push(i);
23+
continue;
24+
}
25+
while (!stack.isEmpty() &&healths[i] >0) {
26+
if (healths[stack.peek()] <healths[i]) {
27+
healths[stack.pop()] =0;
28+
healths[i] -=1;
29+
}elseif (healths[stack.peek()] >healths[i]) {
30+
healths[stack.peek()] -=1;
31+
healths[i] =0;
32+
}else {
33+
healths[stack.pop()] =0;
34+
healths[i] =0;
35+
}
36+
}
37+
}
38+
39+
List<Integer>ans =newArrayList<>();
40+
for (inth :healths) {
41+
if (h >0) {
42+
ans.add(h);
43+
}
44+
}
45+
returnans;
46+
}
47+
}
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
2751\. Robot Collisions
2+
3+
Hard
4+
5+
There are`n`**1-indexed** robots, each having a position on a line, health, and movement direction.
6+
7+
You are given**0-indexed** integer arrays`positions`,`healths`, and a string`directions` (`directions[i]` is either**'L'** for**left** or**'R'** for**right**). All integers in`positions` are**unique**.
8+
9+
All robots start moving on the line**simultaneously** at the**same speed** in their given directions. If two robots ever share the same position while moving, they will**collide**.
10+
11+
If two robots collide, the robot with**lower health** is**removed** from the line, and the health of the other robot**decreases****by one**. The surviving robot continues in the**same** direction it was going. If both robots have the**same** health, they are both removed from the line.
12+
13+
Your task is to determine the**health** of the robots that survive the collisions, in the same**order** that the robots were given, i.e. final heath of robot 1 (if survived), final health of robot 2 (if survived), and so on. If there are no survivors, return an empty array.
14+
15+
Return_an array containing the health of the remaining robots (in the order they were given in the input), after no further collisions can occur._
16+
17+
**Note:** The positions may be unsorted.
18+
19+
**Example 1:**
20+
21+
![](https://assets.leetcode.com/uploads/2023/05/15/image-20230516011718-12.png)
22+
23+
**Input:** positions =[5,4,3,2,1], healths =[2,17,9,15,10], directions = "RRRRR"
24+
25+
**Output:**[2,17,9,15,10]
26+
27+
**Explanation:** No collision occurs in this example, since all robots are moving in the same direction. So, the health of the robots in order from the first robot is returned,[2, 17, 9, 15, 10].
28+
29+
**Example 2:**
30+
31+
![](https://assets.leetcode.com/uploads/2023/05/15/image-20230516004433-7.png)
32+
33+
**Input:** positions =[3,5,2,6], healths =[10,10,15,12], directions = "RLRL"
34+
35+
**Output:**[14]
36+
37+
**Explanation:** There are 2 collisions in this example. Firstly, robot 1 and robot 2 will collide, and since both have the same health, they will be removed from the line. Next, robot 3 and robot 4 will collide and since robot 4's health is smaller, it gets removed, and robot 3's health becomes 15 - 1 = 14. Only robot 3 remains, so we return[14].
38+
39+
**Example 3:**
40+
41+
![](https://assets.leetcode.com/uploads/2023/05/15/image-20230516005114-9.png)
42+
43+
**Input:** positions =[1,2,5,6], healths =[10,10,11,11], directions = "RLRL"
44+
45+
**Output:**[]
46+
47+
**Explanation:** Robot 1 and robot 2 will collide and since both have the same health, they are both removed. Robot 3 and 4 will collide and since both have the same health, they are both removed. So, we return an empty array,[].
48+
49+
**Constraints:**
50+
51+
* <code>1 <= positions.length == healths.length == directions.length == n <= 10<sup>5</sup></code>
52+
* <code>1 <= positions[i], healths[i] <= 10<sup>9</sup></code>
53+
*`directions[i] == 'L'` or`directions[i] == 'R'`
54+
* All values in`positions` are distinct
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
packageg2701_2800.s2760_longest_even_odd_subarray_with_threshold;
2+
3+
// #Easy #Array #Sliding_Window #2023_09_25_Time_4_ms_(96.92%)_Space_43.8_MB_(40.90%)
4+
5+
publicclassSolution {
6+
publicintlongestAlternatingSubarray(int[]nums,intthreshold) {
7+
intmaxLength =0;
8+
inti =0;
9+
while (i <nums.length) {
10+
if (nums[i] %2 ==0 &&nums[i] <=threshold) {
11+
intlength =1;
12+
intj =i +1;
13+
while (j <nums.length &&nums[j] <=threshold &&nums[j] %2 !=nums[j -1] %2) {
14+
length++;
15+
j++;
16+
}
17+
maxLength =Math.max(maxLength,length);
18+
i =j -1;
19+
}
20+
i++;
21+
}
22+
returnmaxLength;
23+
}
24+
}
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
2760\. Longest Even Odd Subarray With Threshold
2+
3+
Easy
4+
5+
You are given a**0-indexed** integer array`nums` and an integer`threshold`.
6+
7+
Find the length of the**longest subarray** of`nums` starting at index`l` and ending at index`r``(0 <= l <= r < nums.length)` that satisfies the following conditions:
8+
9+
*`nums[l] % 2 == 0`
10+
* For all indices`i` in the range`[l, r - 1]`,`nums[i] % 2 != nums[i + 1] % 2`
11+
* For all indices`i` in the range`[l, r]`,`nums[i] <= threshold`
12+
13+
Return_an integer denoting the length of the longest such subarray._
14+
15+
**Note:** A**subarray** is a contiguous non-empty sequence of elements within an array.
16+
17+
**Example 1:**
18+
19+
**Input:** nums =[3,2,5,4], threshold = 5
20+
21+
**Output:** 3
22+
23+
**Explanation:**
24+
25+
In this example, we can select the subarray that starts at l = 1 and ends at r = 3 =>[2,5,4]. This subarray satisfies the conditions.
26+
27+
Hence, the answer is the length of the subarray, 3. We can show that 3 is the maximum possible achievable length.
28+
29+
**Example 2:**
30+
31+
**Input:** nums =[1,2], threshold = 2
32+
33+
**Output:** 1
34+
35+
**Explanation:**
36+
37+
In this example, we can select the subarray that starts at l = 1 and ends at r = 1 =>[2].
38+
39+
It satisfies all the conditions and we can show that 1 is the maximum possible achievable length.
40+
41+
**Example 3:**
42+
43+
**Input:** nums =[2,3,4,5], threshold = 4
44+
45+
**Output:** 3
46+
47+
**Explanation:**
48+
49+
In this example, we can select the subarray that starts at l = 0 and ends at r = 2 =>[2,3,4].
50+
51+
It satisfies all the conditions. Hence, the answer is the length of the subarray, 3. We can show that 3 is the maximum possible achievable length.
52+
53+
**Constraints:**
54+
55+
*`1 <= nums.length <= 100`
56+
*`1 <= nums[i] <= 100`
57+
*`1 <= threshold <= 100`

0 commit comments

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