Leetcode.2038 如果相邻两个颜色均相同则删除当前颜色
题目链接
Leetcode.2038 如果相邻两个颜色均相同则删除当前颜色 Rating : 1468
题目描述
总共有 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 < = c o l o r s . l e n g t h < = 1 0 5 1 <= colors.length <= 10^5 1<=colors.length<=105
colors
只包含字母'A'
和'B'
解法:计数
根据题意,Alice 只能删除 A AAAAAA A
,Bob 只能删除 B BBBBBBBB B
各自中间的部分。
实际上 Alice 删除一个 A
之后是不会影响 Bob的操作的;反之,Bob也一样。
所以我们只需要统计 Alice 能操作的次数 是否大于 Bob 能操作的次数。
时间复杂度: O ( n ) O(n) O(n)
C++代码:
class Solution {
public:
int get(char ch,string &s){
int n = s.size();
int ans = 0;
for(int i = 0;i < n;i++){
if(s[i] == ch){
int j = i + 1;
while(j < n && s[j] == ch) j++;
ans += max(0,j - i - 2);
i = j - 1;
}
}
return ans;
}
bool winnerOfGame(string colors) {
return get('A',colors) > get('B',colors);
}
};
相关文章
- Java实现 LeetCode 712 两个字符串的最小ASCII删除和(最长公共子串&&ASCII值最小)...
- Java实现 LeetCode 583 两个字符串的删除操作(求最长公共子序列问题)
- 数据结构之各种数据结构插入、删除、查找的时间复杂度
- LeetCode(82):删除排序链表中的重复元素 II
- 算法练习之合并两个有序链表, 删除排序数组中的重复项,移除元素,实现strStr(),搜索插入位置,无重复字符的最长子串
- 创建和删除文件
- linux shell 字符串操作详解 (长度,读取,替换,截取,连接,对比,删除,位置 )
- 2038. 如果相邻两个颜色均相同则删除当前颜色(贪心)
- CM: 关于删除attachment时是否需要commit work的问题
- QT安装、添加或删除、更新组件
- Node.js 博客实例(五)编辑与删除功能
- 删除docker网络docker0
- appdata文件太大了可以删除吗?
- e831. 从JTabbedPane中删除一个卡片
- 下列哪一个接口定义了用于查找、创建和删除EJB实例
- Mysql 索引增加与删除