41.神秘消失 - 图1

题目概述

题目详情(点我)

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

输入:
输入一个字符串s，s中A表示黄色的书，B表示蓝色的书

输出:
输出最多会消失多少本书

题解

解题方法

  • 数组的运用

算法知识

  • 数学计算

    • 时间复杂度: n
    • 空间复杂度: 1

解题思路

审题

  • String str : 字符串, 只包含两种字母, 代表不同的书
  • 不同的书碰到会消失, 并且剩下的书会相互靠拢

题目要求

  • 最多消失多少本书

思路

  • 统计出每个种类的书有多少本, 然后返回书最少的种类的本数*2
  • 因为无论这两种书如何排列, 只要两种书的总类不同, 必定会接触到, 只要接触到,就直接消失了。
    如: AAAABBBBB消失的本数为8本

步骤

  1. 定义变量

    • int a,b : 分别为a, b出现的次数, 初始化为0

  2. 遍历数组字符串str, 统计每中书有多少本

  3. 判断那种书比较少, 返回书少的种类的本书 * 2