在线编程解题之神秘消失

简介: 概述:在书架上摆着一些书,这些书只有两种颜色,要么是黄色,要么是蓝色,突然某一天这些书被施了魔法,如果一本黄色和一本蓝色的书挨着,这两本书就会消失不见,然后右边的书会往左边移动,直到和左边的书挨着,如果这两本颜色不同,这两本书又会神秘消失。现在给你一个只包含A和B的字符串s(1<=|s|<=100000),其中A表示黄色的书,B表示蓝色的书,问这n本书中最多会消失多少本书。输入一个字符串s,s中A表示黄色的书,B表示蓝色的书输出最多会消失多少本书

一、题目详情

在书架上摆着一些书,这些书只有两种颜色,要么是黄色,要么是蓝色,突然某一天这些书被施了魔法,如果一本黄色和一本蓝色的书挨着,这两本书就会消失不见,然后右边的书会往左边移动,直到和左边的书挨着,如果这两本颜色不同,这两本书又会神秘消失。现在给你一个只包含A和B的字符串s(1<=|s|<=100000),其中A表示黄色的书,B表示蓝色的书,问这n本书中最多会消失多少本书。
输入一个字符串s,s中A表示黄色的书,B表示蓝色的书
输出最多会消失多少本书

示例1

输入:
"AABB"
输出:
4

二、解题思路

解题主要找的是问题的关键点和对问题的理解程度,这道题的关键点有两个:

关键点一:消失。

如果一本黄色和一本蓝色的书挨着,这两本书就会消失不见。解读一下就是A与B挨着就会同时消失。再理解一下就是,消失的书本数量是2的倍数。

关键点二:挨着。

不管有多少本书,也不管怎么放,必定会有一本黄色和一本蓝色的书挨着。比如一种极端的情况就是示例中展示的:“AABB”。而AB挨着的结果就是AB同时消失。再换一个思路,如果AB不想不会同时消失,唯一的可能性就是你只有A或者只有B。

根据题目,结合关键点,可以得出以下结论:

  1. N本书摆在书架上,最后只会剩下A或者B(依据关键点二)
  2. 消失书本的数量是A或者B数量的两倍(依据关键点一)

时间复杂度:O(1)

空间复杂度:O(1)

相关文章
|
7天前
|
算法
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
11 3
|
1月前
|
存储 索引
【冲击蓝桥篇】动态规划(下):你还在怕动态规划!?进来!答题模板+思路解析+真题实战
【冲击蓝桥篇】动态规划(下):你还在怕动态规划!?进来!答题模板+思路解析+真题实战
|
5月前
|
算法 测试技术 容器
代码随想录算法训练营第四十二天 | LeetCode 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零
代码随想录算法训练营第四十二天 | LeetCode 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零
28 1
|
5月前
|
算法
代码随想录算法训练营第三十一天 | LeetCode 455. 分发饼干、376. 摆动序列、53. 最大子数组和
代码随想录算法训练营第三十一天 | LeetCode 455. 分发饼干、376. 摆动序列、53. 最大子数组和
37 0
|
8月前
|
算法 Android开发 Kotlin
LeetCode 周赛上分之旅 #42 当 LeetCode 考树上倍增,出题的趋势在变化吗
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
92 0
LeetCode 周赛上分之旅 #42 当 LeetCode 考树上倍增,出题的趋势在变化吗
|
8月前
|
存储 算法 C语言
深度理解递归,手撕经典递归问题(汉诺塔,青蛙跳台阶),保姆级教学。
深度理解递归,手撕经典递归问题(汉诺塔,青蛙跳台阶),保姆级教学。
|
8月前
|
算法
[算法刷题题解笔记] 洛谷 P1008 [NOIP1998 普及组] 三连击 [枚举|模拟]
[算法刷题题解笔记] 洛谷 P1008 [NOIP1998 普及组] 三连击 [枚举|模拟]
|
10月前
|
机器学习/深度学习 算法 Java
代码随想录训练营day43| 1049. 最后一块石头的重量 II 494. 目标和 474.一和零...
代码随想录训练营day43| 1049. 最后一块石头的重量 II 494. 目标和 474.一和零...
|
12月前
|
算法 C++
【快乐手撕LeetCode题解系列】——消失的数字
哈喽各位友友们😊,我今天又学到了很多有趣的知识,现在迫不及待的想和大家分享一下!😘我仅已此文,和大家分享【快乐手撕LeetCode题解系列】——消失的数字~ 都是精华内容,可不要错过哟!!!😍😍😍
65 0
(思维)(必要做题步骤)(皮卡丘与 Codeforces )D - 先来签个到
(思维)(必要做题步骤)(皮卡丘与 Codeforces )D - 先来签个到
75 0