leetcode
leetcode 1901 ~ 1950
统计道路上的碰撞次数

统计道路上的碰撞次数

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
在原题解中,跳过所有向左移动的车辆和向右移动的车辆是否可能导致错过某些碰撞情况?例如,如果一个向左移动的车辆在中间位置,会不会与后面的停车或向右移动的车辆发生碰撞?
在原题解中,跳过所有初始位置在字符串左端的向左移动的车辆('L')和初始位置在字符串右端的向右移动的车辆('R')是合理的,因为这些车辆不会与其他车辆发生碰撞。对于在字符串中间的向左移动的车辆('L'),如果它们位于处理后的子字符串中,它们仍然会被计算在内,因此不会错过与后面的停车('S')或向右移动的车辆('R')的碰撞。因此,题解的方法不会漏掉这类碰撞情况。
🦆
题解中提到的子字符串处理方法是否考虑了车辆的初始位置?即,两辆车虽然在处理后的子字符串中相邻,但在实际情况下可能因为位置较远而不会碰撞。
题解中的方法确实考虑了车辆的初始位置。通过跳过所有不会导致碰撞的车辆,处理后的子字符串包含了所有可能发生碰撞的车辆,这些车辆在原始字符串中是相邻的。因此,若两辆车在处理后的子字符串中相邻,则它们在原始字符串中也是紧密相邻的,能够发生碰撞。这表示题解逻辑确实反映了车辆的实际相对位置和碰撞的可能性。
🦆
题解中计算碰撞次数时只是简单地用子字符串的长度减去'S'的数量,这种方法是否能准确反映所有类型的碰撞,特别是两辆相反方向移动的车辆相遇时应该加2次碰撞?
题解中的碰撞计算方法可能会低估实际的碰撞次数。确实,当两辆相反方向移动的车辆('R'和'L')相遇时,每辆车都会因碰撞而改变方向,这可以被视为两次碰撞。然而,题解中的方法仅统计这种情况为一次碰撞。因此,这种计算方法虽然简洁,但不完全准确地反映了所有类型的碰撞,尤其是在处理相反方向移动的车辆相遇的情况时。

相关问题