力扣每日一题（难的我也不会）2038. 如果相邻两个颜色均相同则删除当前颜色（2022.3.22）

2038. 如果相邻两个颜色均相同则删除当前颜色

难度中等62收藏分享切换为英文接收动态反馈

总共有 n 个颜色片段排成一列，每个颜色片段要么是 'A' 要么是 'B' 。给你一个长度为 n 的字符串 colors ，其中 colors[i] 表示第 i 个颜色片段的颜色。

Alice 和 Bob 在玩一个游戏，他们 轮流 从这个字符串中删除颜色。Alice 先手 。

• 如果一个颜色片段为 'A' 且 相邻两个颜色 都是颜色 'A' ，那么 Alice 可以删除该颜色片段。Alice 不可以 删除任何颜色 'B' 片段。
• 如果一个颜色片段为 'B' 且 相邻两个颜色 都是颜色 'B' ，那么 Bob 可以删除该颜色片段。Bob 不可以 删除任何颜色 'A' 片段。
• Alice 和 Bob 不能 从字符串两端删除颜色片段。
• 如果其中一人无法继续操作，则该玩家 输 掉游戏且另一玩家 获胜 。

假设 Alice 和 Bob 都采用最优策略，如果 Alice 获胜，请返回 true，否则 Bob 获胜，返回 false。

首先想到的就是模拟，然后直接超时...，贴上代码

class Solution {
    public boolean winnerOfGame(String colors) {
        int n=colors.length();
        if(n<3) return false;
        boolean isAlice=true;
        ArrayList<Character> list=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(colors.charAt(i));
        }
        boolean A=false;
        boolean B=false;
        while (true){
            n=list.size();
            if(n<3) return !isAlice;
            for (int i = 1; i < n-1; i++) {
                if(isAlice){
                    if(list.get(i)=='A'&&list.get(i-1)=='A'&&list.get(i+1)=='A'){
                        list.remove(i);
                        A=true;
                        B=false;
                        break;
                    }
                }else {
                    if(list.get(i)=='B'&&list.get(i-1)=='B'&&list.get(i+1)=='B'){
                        list.remove(i);
                        B=true;
                        A=false;
                        break;
                    }
                }
            }
            if(isAlice&&!A) return false;
            if(!isAlice&&!B) return true;
            isAlice=!isAlice;
        }
    }
}

 然后发现这个题可以采用贪心，将所有可以删除的A加起来，在将所有可以删除的B加起来，比较哪个大，贴上代码

class Solution {
    public boolean winnerOfGame(String colors) {
        int n=colors.length();
        if(n<3) return false;
        int a=0;
        int b=0;
        for (int i = 0; i < n-2; i++) {
            String s=colors.substring(i,i+3);
            if("AAA".equals(s)) a++;
            if("BBB".equals(s)) b++;
        }
        return a>b;
    }
}

然后这个其实可以优化，里面调用了太多的substring

优化版，采用滑动窗口

class Solution {
    public boolean winnerOfGame(String colors) {
        int n=colors.length();
        if(n<3) return false;
        int a=0;
        int b=0;
        for (int i = 1; i < n-1; i++) {
            if('A'==colors.charAt(i-1)&&'A'==colors.charAt(i)&&'A'==colors.charAt(i+1)) a++;
            if('B'==colors.charAt(i-1)&&'B'==colors.charAt(i)&&'B'==colors.charAt(i+1)) b++;
        }
        return a>b;
    }
}

结束！！！