解题思路

这是一个队列模拟问题。关键点如下：

  1. 表示面向左的人， 表示面向右的人
  2. 当两个人面对面时会发生争吵，其中一个人会被踢出队列
  3. 需要找出经过一系列争吵后，队列最少会剩下多少人

解题思路：

  1. 找到最左边的 和最右边的 的位置
  2. 如果不存在 或 ，或者最右边的 在最左边的 的左边，则不会发生争吵，返回原长度
  3. 否则，最终剩余人数 = 总人数 - (最右 位置 - 最左 位置)

代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str;
    while (cin >> str) {
        int n = str.size();
        int leftmostR = -1, rightmostL = -1;
        
        // 找最左边的R
        for (int i = 0; i < n; i++) {
            if (str[i] == 'R') {
                leftmostR = i;
                break;
            }
        }
        
        // 找最右边的L
        for (int i = n - 1; i >= 0; i--) {
            if (str[i] == 'L') {
                rightmostL = i;
                break;
            }
        }
        
        // 计算结果
        if (leftmostR == -1 || rightmostL == -1 || rightmostL < leftmostR)
            cout << n << endl;
        else
            cout << n - (rightmostL - leftmostR) << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.next();
            int n = str.length();
            int leftmostR = -1, rightmostL = -1;
            
            // 找最左边的R
            for (int i = 0; i < n; i++) {
                if (str.charAt(i) == 'R') {
                    leftmostR = i;
                    break;
                }
            }
            
            // 找最右边的L
            for (int i = n - 1; i >= 0; i--) {
                if (str.charAt(i) == 'L') {
                    rightmostL = i;
                    break;
                }
            }
            
            // 计算结果
            if (leftmostR == -1 || rightmostL == -1 || rightmostL < leftmostR)
                System.out.println(n);
            else
                System.out.println(n - (rightmostL - leftmostR));
        }
    }
}

while True:
    try:
        s = input()
        n = len(s)
        leftmost_r = -1
        rightmost_l = -1
        
        # 找最左边的R
        for i in range(n):
            if s[i] == 'R':
                leftmost_r = i
                break
        
        # 找最右边的L
        for i in range(n-1, -1, -1):
            if s[i] == 'L':
                rightmost_l = i
                break
        
        # 计算结果
        if leftmost_r == -1 or rightmost_l == -1 or rightmost_l < leftmost_r:
            print(n)
        else:
            print(n - (rightmost_l - leftmost_r))
            
    except EOFError:
        break

算法及复杂度

  • 算法：贪心
  • 时间复杂度： - 需要遍历一遍字符串找到最左 和最右
  • 空间复杂度： - 只使用常数额外空间