争吵问题.md

1. 题目描述

有一个队列，每个人要么朝左边（L表示）,要么朝右边(R表示)，因为每个人都讨厌其他任何人，只要两人面对面就会发生争吵。争吵结果是胜者留在队列中，败的人移除队中。如果序列中有多对争吵，可以任选一对，胜者留在队中，败者出局，求最后队列最少人数是多少。

例子：

LRRLRL

输出：2

Hint

一种可能的变化情况是：LRRLRL -> LRLRL -> LRRL -> LRL -> LR

2.解题思路

由题意可知，如果真的吵架就只有RL（两人面对面）情况，像LL,RR,LR就不会争吵。

• 如果吵架前面是R，则吵架结果应该是L胜利.

• 如果吵架前面是L，则吵架结果为R胜利

3.代码

import java.util.ArrayList;
import java.util.List;
public class test {
    public static void main(String[] args) {
        String arr ="LRRLRL";
        String res = solut(arr);
        System.out.println(res.length());
        System.out.println(res);
    }
    public static  String  solut(String arr)
    {
        //获取第一次争吵得到的结果
       String str = solution(arr);
       //如果还存在第二次争吵，则继续，否则得到结果
        while (str.contains("RL")){
            str = solution(str);
        }
        return str;
    }
    public static String solution(String arr){
        List<Character> list = new ArrayList<>();
        for(int i = 0;i<arr.length()-1;i++){
            //争吵
            if(arr.charAt(i)=='R'&&arr.charAt(i+1)=='L'){
                if(i==0) {
                    list.add('R');
                    i++;
                }
                else{
                if(list.get(list.size()-1)=='L') {
                    {
                        list.add('R');
                        i++;
                    }
                }else{
                    {
                        list.add('L');
                        i++;
                    }
                }
                }
            }else {
                //没有争吵，下一次争吵中还有该人
                list.add(arr.charAt(i));
            }
        }
        //将list转换成String
        String str = "";
        for(int i = 0;i<list.size();i++){
            str = str+list.get(i);
        }
        return str;
    }
}