统计道路上的碰撞次数
难度:
标签:
题目描述
代码结果
运行时间: 35 ms, 内存: 16.5 MB
/*
* 思路:
* 使用Java Stream API实现。
* 1. 将字符串转换为字符流。
* 2. 使用两个IntStream来模拟右移和左移的车的索引。
* 3. 使用一个BooleanSupplier来跟踪车辆是否移动。
* 4. 根据车辆的方向和静止状态来计算碰撞次数。
*/
import java.util.stream.IntStream;
import java.util.function.BooleanSupplier;
public class CarCollisionsStream {
public int countCollisions(String directions) {
int[] collisions = {0};
char[] cars = directions.toCharArray();
int n = cars.length;
IntStream.range(0, n).forEach(i -> {
if (cars[i] == 'R') {
IntStream.range(i + 1, n).forEach(j -> {
if (cars[j] == 'L') {
collisions[0] += 2;
cars[i] = cars[j] = 'S';
} else if (cars[j] == 'S') {
collisions[0] += 1;
cars[i] = 'S';
}
});
} else if (cars[i] == 'S') {
IntStream.range(i + 1, n).forEach(j -> {
if (cars[j] == 'L') {
collisions[0] += 1;
cars[j] = 'S';
}
});
}
});
return collisions[0];
}
}
解释
方法:
这个题解的核心思路是通过预处理字符串来简化碰撞计算的过程。首先,从字符串的左端开始,跳过所有向左移动的车辆('L'),因为它们不会与任何车辆发生碰撞。接着,从字符串的右端开始,跳过所有向右移动的车辆('R'),因为它们也不会与任何车辆发生碰撞。经过这样的处理后,剩余的中间部分包含了所有可能的碰撞。在这个子字符串中,只有向左移动的车辆('L')和静止的车辆('S')会保持原位,而向右移动的车辆('R')会与它们发生碰撞。然后,对于这个处理后的子字符串,碰撞次数等于子字符串的长度减去其中'S'的数量。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在原题解中,跳过所有向左移动的车辆和向右移动的车辆是否可能导致错过某些碰撞情况?例如,如果一个向左移动的车辆在中间位置,会不会与后面的停车或向右移动的车辆发生碰撞?
▷🦆
题解中提到的子字符串处理方法是否考虑了车辆的初始位置?即,两辆车虽然在处理后的子字符串中相邻,但在实际情况下可能因为位置较远而不会碰撞。
▷🦆
题解中计算碰撞次数时只是简单地用子字符串的长度减去'S'的数量,这种方法是否能准确反映所有类型的碰撞,特别是两辆相反方向移动的车辆相遇时应该加2次碰撞?
▷