Leetcode 2211. Count Collisions on a Road

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1，从左向右依次遍历，记录车辆左边可能发生碰撞的车辆状态及数量，当发生碰撞时，累加碰撞数量，并更新左边车辆状态。只有左边车辆状态为R时，才有可能出现多个连续R车辆与当前车辆发生碰撞，因此通过count来统计多个连续R车辆的数量，并在发生碰撞时重新计数。

• Version 1

class Solution:
    def countCollisions(self, directions: str) -> int:
        collisions = 0
        left = ''
        count = 0
        for ch in directions:
            if left == '':
                left = ch
                if ch == 'R':
                    count += 1
            else:
                if ch == 'L':
                    if left == 'R':
                        collisions = collisions + count + 1
                        left = 'S'
                        count = 0
                    elif left == 'S':
                        left = 'S'
                        collisions += 1
                elif ch == 'R':
                    left = 'R'
                    count += 1
                else:
                    if left == 'R':
                        collisions = collisions + count
                        count = 0
                    left = 'S'

        return collisions

• Version 2

解析：Version 2，只有最左边的连续L和最右边的连续R才不会发生碰撞，其它情况下L和R都会发生碰撞，找到碰撞的起点和终点，统计发生碰撞的数量即可。

class Solution:
    def countCollisions(self, directions: str) -> int:
        collisions = 0
        left = 0
        right = len(directions) - 1
        while left < len(directions) and directions[left] == 'L':
            left += 1
        while right >= 0 and directions[right] == 'R':
            right -= 1

        for i in range(left, right+1):
            if directions[i] != 'S':
                collisions += 1

        return collisions

Reference

1. https://leetcode.com/problems/count-collisions-on-a-road/description/