移动机器人
难度:
标签:
题目描述
Some robots are standing on an infinite number line with their initial coordinates given by a 0-indexed integer array nums and will start moving once given the command to move. The robots will move a unit distance each second.
You are given a string s denoting the direction in which robots will move on command. 'L' means the robot will move towards the left side or negative side of the number line, whereas 'R' means the robot will move towards the right side or positive side of the number line.
If two robots collide, they will start moving in opposite directions.
Return the sum of distances between all the pairs of robots d seconds after the command. Since the sum can be very large, return it modulo 109 + 7.
Note:
- For two robots at the index
iandj, pair(i,j)and pair(j,i)are considered the same pair. - When robots collide, they instantly change their directions without wasting any time.
- Collision happens when two robots share the same place in a moment.
- For example, if a robot is positioned in 0 going to the right and another is positioned in 2 going to the left, the next second they'll be both in 1 and they will change direction and the next second the first one will be in 0, heading left, and another will be in 2, heading right.
- For example, if a robot is positioned in 0 going to the right and another is positioned in 1 going to the left, the next second the first one will be in 0, heading left, and another will be in 1, heading right.
Example 1:
Input: nums = [-2,0,2], s = "RLL", d = 3 Output: 8 Explanation: After 1 second, the positions are [-1,-1,1]. Now, the robot at index 0 will move left, and the robot at index 1 will move right. After 2 seconds, the positions are [-2,0,0]. Now, the robot at index 1 will move left, and the robot at index 2 will move right. After 3 seconds, the positions are [-3,-1,1]. The distance between the robot at index 0 and 1 is abs(-3 - (-1)) = 2. The distance between the robot at index 0 and 2 is abs(-3 - 1) = 4. The distance between the robot at index 1 and 2 is abs(-1 - 1) = 2. The sum of the pairs of all distances = 2 + 4 + 2 = 8.
Example 2:
Input: nums = [1,0], s = "RL", d = 2 Output: 5 Explanation: After 1 second, the positions are [2,-1]. After 2 seconds, the positions are [3,-2]. The distance between the two robots is abs(-2 - 3) = 5.
Constraints:
2 <= nums.length <= 105-2 * 109 <= nums[i] <= 2 * 1090 <= d <= 109nums.length == s.lengthsconsists of 'L' and 'R' onlynums[i]will be unique.
代码结果
运行时间: 96 ms, 内存: 27.8 MB
/*
* Solution explanation using Java Streams:
* 1. Initialize the positions of the robots based on the nums array.
* 2. Update the positions of the robots according to the directions given by the string s.
* 3. Calculate the new positions after d seconds using streams.
* 4. Calculate pairwise distances and sum them up.
* 5. Return the result modulo (10^9 + 7).
*/
import java.util.*;
import java.util.stream.*;
public class RobotDistanceStream {
public static int calculateTotalDistance(int[] nums, String s, int d) {
final int MOD = 1000000007;
int n = nums.length;
// Update positions after d seconds using streams
int[] positions = IntStream.range(0, n)
.map(i -> s.charAt(i) == 'L' ? nums[i] - d : nums[i] + d)
.sorted()
.toArray();
long totalDistance = IntStream.range(0, n)
.mapToLong(i -> IntStream.range(i + 1, n)
.mapToLong(j -> positions[j] - positions[i])
.sum())
.reduce(0L, (a, b) -> (a + b) % MOD);
return (int) totalDistance;
}
public static void main(String[] args) {
int[] nums = {-2, 0, 2};
String s = "RLL";
int d = 3;
System.out.println(calculateTotalDistance(nums, s, d)); // Output: 8
}
}
解释
方法:
此题解的思路是首先根据移动指令更新每个机器人在d秒后的位置。然后将更新后的位置排序，以便计算任意两个机器人之间的距离。最后，利用数学方法计算所有机器人对之间的距离之和。对于排序后的数组中的每个元素nums[i]，它与前面的i个元素的距离总和为(nums[i] - nums[i - 1]) * i，与后面的(n - i)个元素的距离总和相同。因此，对于每个i，距离之和为(nums[i] - nums[i - 1]) * i * (n - i)。将所有这些距离相加并取模得到最终结果。
时间复杂度:
O(nlogn)
空间复杂度:
O(1)
代码细节讲解
🦆
在代码中，当机器人相撞时，如何处理它们改变方向的逻辑？这似乎在题解中没有明确处理。
▷🦆
题解中提到了将机器人位置进行排序后计算距离，那么排序是否考虑了机器人在移动过程中可能发生的相遇和方向改变？
▷🦆
在计算距离之和的公式`(nums[i] - nums[i - 1]) * i * (n - i)`中，为什么乘以`i`和`(n - i)`能得到正确的两两距离之和？
▷