同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
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:
i
and j
, pair (i,j)
and pair (j,i)
are considered the same pair.
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 * 109
0 <= d <= 109
nums.length == s.length
s
consists of 'L' and 'R' onlynums[i]
will be unique.After two robots collide, they will immediately change direction, which is equivalent to the two robots continuing to move in their original direction. Therefore, we traverse the array $nums$, and according to the instructions in the string $s$, we add or subtract $d$ from the position of each robot, and then sort the array $nums$.
Next, we enumerate the position of each robot from small to large, and calculate the sum of the distances between the current robot and all robots in front, which is the answer.
The time complexity is $O(n \times \log n)$ and the space complexity is $O(n)$, where $n$ is the number of robots.
class Solution:
def sumDistance(self, nums: List[int], s: str, d: int) -> int:
mod = 10**9 + 7
for i, c in enumerate(s):
nums[i] += d if c == "R" else -d
nums.sort()
ans = s = 0
for i, x in enumerate(nums):
ans += i * x - s
s += x
return ans % mod
class Solution {
public int sumDistance(int[] nums, String s, int d) {
int n = nums.length;
long[] arr = new long[n];
for (int i = 0; i < n; ++i) {
arr[i] = (long) nums[i] + (s.charAt(i) == 'L' ? -d : d);
}
Arrays.sort(arr);
long ans = 0, sum = 0;
final int mod = (int) 1e9 + 7;
for (int i = 0; i < n; ++i) {
ans = (ans + i * arr[i] - sum) % mod;
sum += arr[i];
}
return (int) ans;
}
}
class Solution {
public:
int sumDistance(vector<int>& nums, string s, int d) {
int n = nums.size();
vector<long long> arr(n);
for (int i = 0; i < n; ++i) {
arr[i] = 1LL * nums[i] + (s[i] == 'L' ? -d : d);
}
sort(arr.begin(), arr.end());
long long ans = 0;
long long sum = 0;
const int mod = 1e9 + 7;
for (int i = 0; i < n; ++i) {
ans = (ans + i * arr[i] - sum) % mod;
sum += arr[i];
}
return ans;
}
};
func sumDistance(nums []int, s string, d int) (ans int) {
for i, c := range s {
if c == 'R' {
nums[i] += d
} else {
nums[i] -= d
}
}
sort.Ints(nums)
sum := 0
const mod int = 1e9 + 7
for i, x := range nums {
ans = (ans + i*x - sum) % mod
sum += x
}
return
}
function sumDistance(nums: number[], s: string, d: number): number {
const n = nums.length;
for (let i = 0; i < n; ++i) {
nums[i] += s[i] === 'L' ? -d : d;
}
nums.sort((a, b) => a - b);
let ans = 0;
let sum = 0;
const mod = 1e9 + 7;
for (let i = 0; i < n; ++i) {
ans = (ans + i * nums[i] - sum) % mod;
sum += nums[i];
}
return ans;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。