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

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

文章目录

1. 题目

2. 解题

1. 题目

总共有 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。

示例 1:
输入:colors = "AAABABB"
输出:true
解释:
AAABABB -> AABABB
Alice 先操作。
她删除从左数第二个 'A' ,这也是唯一一个相邻颜色片段都是 'A' 的 'A' 。
现在轮到 Bob 操作。
Bob 无法执行任何操作,因为没有相邻位置都是 'B' 的颜色片段 'B' 。
因此,Alice 获胜,返回 true 。
示例 2:
输入:colors = "AA"
输出:false
解释:
Alice 先操作。
只有 2 个 'A' 且它们都在字符串的两端,所以她无法执行任何操作。
因此,Bob 获胜,返回 false 。
示例 3:
输入:colors = "ABBBBBBBAAA"
输出:false
解释:
ABBBBBBBAAA -> ABBBBBBBAA
Alice 先操作。
她唯一的选择是删除从右数起第二个 'A' 。
ABBBBBBBAA -> ABBBBBBAA
接下来轮到 Bob 操作。
他有许多选择,他可以选择任何一个 'B' 删除。
然后轮到 Alice 操作,她无法删除任何片段。
所以 Bob 获胜,返回 false 。
提示:
1 <= colors.length <= 10^5
colors 只包含字母 'A' 和 'B'


2. 解题


  • 记录连续的 A 或者 B 的个数,然后可以操作的次数为 其数量 - 2,记录总的操作次数,Alice的操作次数必须大于 Bob
class Solution {
public:
    bool winnerOfGame(string colors) {
        int a = 0, b = 0, ct = 1;
        colors += "*";
        char prev = colors[0];
        for(int i = 1; i < colors.size(); ++i)
        {
            if(prev != colors[i])
            {
                if(prev == 'A')
                    a += max(0, ct-2);
                else
                    b += max(0, ct-2);
                ct = 1;
            }
            else
                ct++;
            prev = colors[i];
        }
        return a>b;
    }
};

28 ms 14.8 MB C++

相关文章
|
7月前
|
算法
每日一题:LeetCode-75. 颜色分类
每日一题:LeetCode-75. 颜色分类
|
7月前
|
存储 算法
LeetCode刷题---75. 颜色分类(双指针,循环不变量)
LeetCode刷题---75. 颜色分类(双指针,循环不变量)
|
4月前
|
算法 搜索推荐
LeetCode第75题颜色分类
文章介绍了LeetCode第75题"颜色分类"的解法,通过双指针技术对数组中的0、1和2进行排序,避免了传统的排序算法,提供了一种时间复杂度为O(n)的高效解决方案。
LeetCode第75题颜色分类
|
4月前
|
算法 Python
【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
本文介绍了LeetCode 2038题的解法,题目要求在一个由'A'和'B'组成的字符串中,按照特定规则轮流删除颜色片段,判断Alice是否能够获胜,并提供了Python的实现代码。
55 3
|
4月前
|
Python
【Leetcode刷题Python】75. 颜色分类
在不使用sort函数的情况下对包含红色、白色和蓝色元素的数组进行排序的方法:插入排序法和单指针交换法,并提供了相应的Python实现代码。
17 0
|
6月前
|
数据采集 SQL 算法
LeetCode题目75:颜色分类【python】
LeetCode题目75:颜色分类【python】
|
7月前
|
算法
【力扣】75.颜色分类
【力扣】75.颜色分类
|
7月前
leetcode代码记录(删除字符串中的所有相邻重复项
leetcode代码记录(删除字符串中的所有相邻重复项
39 0
|
7月前
|
Java
|
7月前
leetcode-777:在LR字符串中交换相邻字符
leetcode-777:在LR字符串中交换相邻字符
53 0