Skip to content

Commit 273a5f9

Browse files
authored
Added tasks 1775, 1776, 1779, 1780, 1782.
1 parent d380f3b commit 273a5f9

File tree

15 files changed

+557
-0
lines changed

15 files changed

+557
-0
lines changed
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package g1701_1800.s1775_equal_sum_arrays_with_minimum_number_of_operations;
2+
3+
// #Medium #Array #Hash_Table #Greedy #Counting
4+
// #2022_04_30_Time_16_ms_(70.88%)_Space_106.1_MB_(19.23%)
5+
6+
import java.util.Arrays;
7+
8+
public class Solution {
9+
public int minOperations(int[] nums1, int[] nums2) {
10+
int[] longer = nums1.length > nums2.length ? nums1 : nums2;
11+
int[] shorter = nums1.length > nums2.length ? nums2 : nums1;
12+
if (longer.length > shorter.length * 6) {
13+
return -1;
14+
}
15+
Arrays.sort(longer);
16+
Arrays.sort(shorter);
17+
int i = 0;
18+
int j = 0;
19+
int diff = 0;
20+
while (i < longer.length || j < shorter.length) {
21+
if (i < longer.length) {
22+
diff += longer[i++];
23+
}
24+
if (j < shorter.length) {
25+
diff -= shorter[j++];
26+
}
27+
}
28+
int minOps = 0;
29+
i = 0;
30+
j = shorter.length - 1;
31+
if (diff < 0) {
32+
while (diff < 0) {
33+
if (i < longer.length && j >= 0) {
34+
if (6 - longer[i] < shorter[j] - 1) {
35+
diff += shorter[j--] - 1;
36+
} else {
37+
diff += 6 - longer[i++];
38+
}
39+
} else if (i < longer.length) {
40+
diff += 6 - longer[i++];
41+
} else {
42+
diff += shorter[j--] - 1;
43+
}
44+
minOps++;
45+
}
46+
return minOps;
47+
} else if (diff > 0) {
48+
i = longer.length - 1;
49+
j = 0;
50+
while (diff > 0) {
51+
if (i >= 0 && j < shorter.length) {
52+
if (longer[i] - 1 > 6 - shorter[j]) {
53+
diff -= longer[i--] - 1;
54+
} else {
55+
diff -= 6 - shorter[j++];
56+
}
57+
} else if (i >= 0) {
58+
diff -= longer[i--] - 1;
59+
} else {
60+
diff -= 6 - shorter[j++];
61+
}
62+
minOps++;
63+
}
64+
return minOps;
65+
} else {
66+
return minOps;
67+
}
68+
}
69+
}
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
1775\. Equal Sum Arrays With Minimum Number of Operations
2+
3+
Medium
4+
5+
You are given two arrays of integers `nums1` and `nums2`, possibly of different lengths. The values in the arrays are between `1` and `6`, inclusive.
6+
7+
In one operation, you can change any integer's value in **any** of the arrays to **any** value between `1` and `6`, inclusive.
8+
9+
Return _the minimum number of operations required to make the sum of values in_ `nums1` _equal to the sum of values in_ `nums2`_._ Return `-1` if it is not possible to make the sum of the two arrays equal.
10+
11+
**Example 1:**
12+
13+
**Input:** nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
14+
15+
**Output:** 3
16+
17+
**Explanation:** You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed.
18+
19+
- Change nums2[0] to 6. nums1 = [1,2,3,4,5,6], nums2 = [**6**,1,2,2,2,2].
20+
21+
- Change nums1[5] to 1. nums1 = [1,2,3,4,5,**1**], nums2 = [6,1,2,2,2,2].
22+
23+
- Change nums1[2] to 2. nums1 = [1,2,**2**,4,5,1], nums2 = [6,1,2,2,2,2].
24+
25+
**Example 2:**
26+
27+
**Input:** nums1 = [1,1,1,1,1,1,1], nums2 = [6]
28+
29+
**Output:** -1
30+
31+
**Explanation:** There is no way to decrease the sum of nums1 or to increase the sum of nums2 to make them equal.
32+
33+
**Example 3:**
34+
35+
**Input:** nums1 = [6,6], nums2 = [1]
36+
37+
**Output:** 3
38+
39+
**Explanation:** You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed.
40+
41+
- Change nums1[0] to 2. nums1 = [**2**,6], nums2 = [1].
42+
43+
- Change nums1[1] to 2. nums1 = [2,**2**], nums2 = [1].
44+
45+
- Change nums2[0] to 4. nums1 = [2,2], nums2 = [**4**].
46+
47+
**Constraints:**
48+
49+
* <code>1 <= nums1.length, nums2.length <= 10<sup>5</sup></code>
50+
* `1 <= nums1[i], nums2[i] <= 6`
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package g1701_1800.s1776_car_fleet_ii;
2+
3+
// #Hard #Array #Math #Stack #Heap_Priority_Queue #Monotonic_Stack
4+
// #2022_04_30_Time_19_ms_(93.81%)_Space_100.6_MB_(87.17%)
5+
6+
import java.util.Deque;
7+
import java.util.LinkedList;
8+
9+
public class Solution {
10+
public double[] getCollisionTimes(int[][] cars) {
11+
Deque<Integer> stack = new LinkedList<>();
12+
13+
int n = cars.length;
14+
double[] ans = new double[n];
15+
16+
for (int i = n - 1; i >= 0; i--) {
17+
ans[i] = -1.0;
18+
int[] presentCar = cars[i];
19+
int presentCarSpeed = presentCar[1];
20+
21+
while (!stack.isEmpty()) {
22+
int previousCar = stack.peekLast();
23+
int previousCarSpeed = cars[previousCar][1];
24+
if (presentCarSpeed > previousCarSpeed
25+
&& (ans[previousCar] == -1.0
26+
|| catchTime(cars, i, previousCar) <= ans[previousCar])) {
27+
ans[i] = catchTime(cars, i, previousCar);
28+
break;
29+
}
30+
stack.pollLast();
31+
}
32+
33+
stack.offerLast(i);
34+
}
35+
36+
return ans;
37+
}
38+
39+
private double catchTime(int[][] cars, int presentCar, int previousCar) {
40+
int dist = cars[previousCar][0] - cars[presentCar][0];
41+
int speed = cars[presentCar][1] - cars[previousCar][1];
42+
return 1.0 * dist / speed;
43+
}
44+
}
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
1776\. Car Fleet II
2+
3+
Hard
4+
5+
There are `n` cars traveling at different speeds in the same direction along a one-lane road. You are given an array `cars` of length `n`, where <code>cars[i] = [position<sub>i</sub>, speed<sub>i</sub>]</code> represents:
6+
7+
* <code>position<sub>i</sub></code> is the distance between the <code>i<sup>th</sup></code> car and the beginning of the road in meters. It is guaranteed that <code>position<sub>i</sub> < position<sub>i+1</sub></code>.
8+
* <code>speed<sub>i</sub></code> is the initial speed of the <code>i<sup>th</sup></code> car in meters per second.
9+
10+
For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the **slowest** car in the fleet.
11+
12+
Return an array `answer`, where `answer[i]` is the time, in seconds, at which the <code>i<sup>th</sup></code> car collides with the next car, or `-1` if the car does not collide with the next car. Answers within <code>10<sup>-5</sup></code> of the actual answers are accepted.
13+
14+
**Example 1:**
15+
16+
**Input:** cars = [[1,2],[2,1],[4,3],[7,2]]
17+
18+
**Output:** [1.00000,-1.00000,3.00000,-1.00000]
19+
20+
**Explanation:** After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s.
21+
22+
**Example 2:**
23+
24+
**Input:** cars = [[3,4],[5,4],[6,3],[9,1]]
25+
26+
**Output:** [2.00000,1.00000,1.50000,-1.00000]
27+
28+
**Constraints:**
29+
30+
* <code>1 <= cars.length <= 10<sup>5</sup></code>
31+
* <code>1 <= position<sub>i</sub>, speed<sub>i</sub> <= 10<sup>6</sup></code>
32+
* <code>position<sub>i</sub> < position<sub>i+1</sub></code>
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package g1701_1800.s1779_find_nearest_point_that_has_the_same_x_or_y_coordinate;
2+
3+
// #Easy #Array #Programming_Skills_I_Day_3_Conditional_Statements
4+
// #2022_04_30_Time_1_ms_(100.00%)_Space_50.1_MB_(80.01%)
5+
6+
public class Solution {
7+
public int nearestValidPoint(int x, int y, int[][] points) {
8+
int nearestManDistance = Integer.MAX_VALUE;
9+
int result = -1;
10+
for (int i = 0; i < points.length; i++) {
11+
int[] point = points[i];
12+
if (point[0] == x || point[1] == y) {
13+
int distance = Math.abs(point[0] - x) + Math.abs(point[1] - y);
14+
if (distance < nearestManDistance) {
15+
result = i;
16+
nearestManDistance = distance;
17+
}
18+
}
19+
}
20+
return result;
21+
}
22+
}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
1779\. Find Nearest Point That Has the Same X or Y Coordinate
2+
3+
Easy
4+
5+
You are given two integers, `x` and `y`, which represent your current location on a Cartesian grid: `(x, y)`. You are also given an array `points` where each <code>points[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> represents that a point exists at <code>(a<sub>i</sub>, b<sub>i</sub>)</code>. A point is **valid** if it shares the same x-coordinate or the same y-coordinate as your location.
6+
7+
Return _the index **(0-indexed)** of the **valid** point with the smallest **Manhattan distance** from your current location_. If there are multiple, return _the valid point with the **smallest** index_. If there are no valid points, return `-1`.
8+
9+
The **Manhattan distance** between two points <code>(x<sub>1</sub>, y<sub>1</sub>)</code> and <code>(x<sub>2</sub>, y<sub>2</sub>)</code> is <code>abs(x<sub>1</sub> - x<sub>2</sub>) + abs(y<sub>1</sub> - y<sub>2</sub>)</code>.
10+
11+
**Example 1:**
12+
13+
**Input:** x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
14+
15+
**Output:** 2
16+
17+
**Explanation:** Of all the points, only [3,1], [2,4] and [4,4] are valid. Of the valid points, [2,4] and [4,4] have the smallest Manhattan distance from your current location, with a distance of 1. [2,4] has the smallest index, so return 2.
18+
19+
**Example 2:**
20+
21+
**Input:** x = 3, y = 4, points = [[3,4]]
22+
23+
**Output:** 0
24+
25+
**Explanation:** The answer is allowed to be on the same location as your current location.
26+
27+
**Example 3:**
28+
29+
**Input:** x = 3, y = 4, points = [[2,3]]
30+
31+
**Output:** -1
32+
33+
**Explanation:** There are no valid points.
34+
35+
**Constraints:**
36+
37+
* <code>1 <= points.length <= 10<sup>4</sup></code>
38+
* `points[i].length == 2`
39+
* <code>1 <= x, y, a<sub>i</sub>, b<sub>i</sub> <= 10<sup>4</sup></code>
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package g1701_1800.s1780_check_if_number_is_a_sum_of_powers_of_three;
2+
3+
// #Medium #Math #2022_04_30_Time_2_ms_(19.71%)_Space_41.1_MB_(41.61%)
4+
5+
import java.util.ArrayList;
6+
import java.util.List;
7+
8+
public class Solution {
9+
public boolean checkPowersOfThree(int n) {
10+
List<Integer> powers = new ArrayList<>();
11+
int power = 1;
12+
for (int i = 1; power <= n; i++) {
13+
powers.add(power);
14+
power = (int) Math.pow(3, i);
15+
}
16+
int i = powers.size() - 1;
17+
while (n > 0 && i >= 0) {
18+
if (n - powers.get(i) > 0) {
19+
n -= powers.get(i--);
20+
} else if (n - powers.get(i) == 0) {
21+
return true;
22+
} else {
23+
i--;
24+
}
25+
}
26+
return n == 0;
27+
}
28+
}
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
1780\. Check if Number is a Sum of Powers of Three
2+
3+
Medium
4+
5+
Given an integer `n`, return `true` _if it is possible to represent_ `n` _as the sum of distinct powers of three._ Otherwise, return `false`.
6+
7+
An integer `y` is a power of three if there exists an integer `x` such that <code>y == 3<sup>x</sup></code>.
8+
9+
**Example 1:**
10+
11+
**Input:** n = 12
12+
13+
**Output:** true
14+
15+
**Explanation:** 12 = 3<sup>1</sup> + 3<sup>2</sup>
16+
17+
**Example 2:**
18+
19+
**Input:** n = 91
20+
21+
**Output:** true
22+
23+
**Explanation:** 91 = 3<sup>0</sup> + 3<sup>2</sup> + 3<sup>4</sup>
24+
25+
**Example 3:**
26+
27+
**Input:** n = 21
28+
29+
**Output:** false
30+
31+
**Constraints:**
32+
33+
* <code>1 <= n <= 10<sup>7</sup></code>
Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package g1701_1800.s1782_count_pairs_of_nodes;
2+
3+
// #Hard #Binary_Search #Two_Pointers #Graph
4+
// #2022_04_30_Time_128_ms_(86.96%)_Space_175.4_MB_(39.13%)
5+
6+
import java.util.HashMap;
7+
import java.util.Map;
8+
9+
public class Solution {
10+
public int[] countPairs(int n, int[][] edges, int[] queries) {
11+
Map<Integer, Integer> edgeCount = new HashMap<>();
12+
int[] degree = new int[n];
13+
14+
for (int[] e : edges) {
15+
int u = e[0] - 1;
16+
int v = e[1] - 1;
17+
degree[u]++;
18+
degree[v]++;
19+
20+
int eId = Math.min(u, v) * n + Math.max(u, v);
21+
edgeCount.put(eId, edgeCount.getOrDefault(eId, 0) + 1);
22+
}
23+
24+
Map<Integer, Integer> degreeCount = new HashMap<>();
25+
int maxDegree = 0;
26+
for (int d : degree) {
27+
degreeCount.put(d, degreeCount.getOrDefault(d, 0) + 1);
28+
maxDegree = Math.max(maxDegree, d);
29+
}
30+
31+
int[] count = new int[2 * maxDegree + 1];
32+
33+
for (Map.Entry<Integer, Integer> d1 : degreeCount.entrySet()) {
34+
for (Map.Entry<Integer, Integer> d2 : degreeCount.entrySet()) {
35+
count[d1.getKey() + d2.getKey()] +=
36+
(d1 == d2)
37+
? d1.getValue() * (d1.getValue() - 1)
38+
: d1.getValue() * d2.getValue();
39+
}
40+
}
41+
for (int i = 0; i < count.length; i++) {
42+
count[i] /= 2;
43+
}
44+
45+
for (Map.Entry<Integer, Integer> e : edgeCount.entrySet()) {
46+
int u = e.getKey() / n;
47+
int v = e.getKey() % n;
48+
49+
count[degree[u] + degree[v]]--;
50+
count[degree[u] + degree[v] - e.getValue()]++;
51+
}
52+
53+
for (int i = count.length - 2; i >= 0; i--) {
54+
count[i] += count[i + 1];
55+
}
56+
57+
int[] res = new int[queries.length];
58+
for (int q = 0; q < queries.length; q++) {
59+
res[q] = ((queries[q] + 1) >= count.length) ? 0 : count[queries[q] + 1];
60+
}
61+
return res;
62+
}
63+
}

0 commit comments

Comments
 (0)