Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Problem description

There are n cars on an infinite stretch of highway. Cars are numbered from 0 to N-1 from left to right, each in a unique location.

You are given a string of n directions from 0. Directions [I] can be ‘L’, ‘R’, or ‘S’ to indicate that the ith car is going left, right, or staying in the current position, respectively. Each car moves at the same speed.

The number of collisions can be calculated as follows:

  • When the two cars move in the directionOn the contraryWhen a car collides, the number of collisions increases2 。
  • When a moving car collides with a stationary car, the number of collisions increases1 。

After a collision, the vehicle involved will no longer be able to move and remain in the collision position. In addition, cars cannot change their state or direction of movement.

Returns the total number of collisions that occurred on this road.

Statistics on the number of collisions on roads.

Two, the title requirements

The sample

Directions = "RLRSLL" Output: 5 Explanation: Lists the collisions that will occur on the road as follows: - Car 0 and car 1 will collide with each other. As they move in opposite directions, the number of collisions becomes 0 + 2 = 2. - Car 2 and car 3 are going to crash into each other. Since 3 is stationary, the number of collisions becomes 2 + 1 = 3. - Car 3 and car 4 are going to crash into each other. Since 3 is stationary, the number of collisions becomes 3 + 1 = 4. - Car 4 and car 5 will crash into each other. After car 4 collides with car 3, car 4 stays in the collision position, and then it collides with car 5. The number of collisions becomes 4 + 1 = 5. So the total number of collisions that will occur on the road is 5.Copy the code

inspection

1. Dual-pointer, analog 2. The recommended time is 20 to 35 minutesCopy the code

Third, problem analysis

At first, MY idea was to simulate the situation, but there were always a few examples that couldn’t get through.

Later saw the solution directly to the big guy kneel:

First of all if the first is L, the second is also L…… So all of these cars are going to go out of the left boundary.

Similarly, if the last one is R, the penultimate one is also R…… So all of these cars are going to go off the right boundary.

The number of collisions is calculated directly by the cars moving in the middle, such as the collision of two opposite cars, the number of +2.

If a moving car collides with a stationary car, the number of times plus 1, then the number of times is going to be the car moving in the middle of the left and right boundary.

Four, coding implementation

class Solution {
public:
    int countCollisions(string s) {
        int i,l,r,n=s.size(),ans=0;// Initialize the data
        l=0,r=n- 1;// The left and right boundaries are initialized
        while(l<n&&s[l]=='L')// Left margin judgment
            l++;
        while(r>=0&&s[r]=='R')// Right edge judgment
            r--;
        for(i=l; i<=r; i++)// Count moving cars
            if(s[i]! ='S')
                ans++;
        returnans; }};Copy the code

V. Test results