算法筆試模拟題精解之“神秘消失”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第41題：神秘消失 的題目解析，具體如下：

題目描述

題目等級：簡單

知識點：字元串

檢視題目：神秘消失

在書架上擺着一些書，這些書隻有兩種顔色，要麼是黃色，要麼是藍色，突然某一天這些書被施了魔法，如果一本黃色和一本藍色的書挨着，這兩本書就會消失不見，然後右邊的書會往左邊移動，直到和左邊的書挨着，如果這兩本顔色不同，這兩本書又會神秘消失。

現在給你一個隻包含A和B的字元串s(1<=|s|<=100000)，其中A表示黃色的書，B表示藍色的書，問這n本書中最多會消失多少本書?

輸入一個字元串s，s中A表示黃色的書，B表示藍色的書；

輸出最多會消失多少本書。

示例1

輸入：

"AABB"

輸出：

4

解題方法

本題可以通過觀察規律得出解題思路，根據題意，兩種顔色的書相鄰擺放，就都會消失。可以得知隻要兩種顔色的書同時存在，就會處于不穩定的狀态，總會有書消失，是以到最後的時候必然隻能剩下一種顔色的書。

分析到這裡，答案呼之欲出了。兩種書中，數量較少的書最終會全部消失，消失的時候又會帶走一本不同顔色的書。是以消失的書的數量為：數量較少的書的數量*2。

隻要把字元串轉成字元數組，然後分别統計字元A和字元B的數量即可。

時間複雜度：O(n)

空間複雜度：O(1)

看完之後是不是有了想法了呢，快來練練手吧>>