專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近一網友發文稱：帶團隊太崩潰了，下屬躺平心態，怎么讓他們上進？啥叫躺平心態，活干完不就行了，只要工作能完成，想咋躺咋躺。

下屬躺平有多方面原因，有可能是目標缺少，不清晰，或者是缺乏成就感。但我覺得最重要的是缺少激勵，要想讓他們上進也不難辦，可以建立獎勵機制，不能光提供口頭表揚，最重要的是提供物質獎勵。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1529題：最少的后綴翻轉次數。難度是中等。

給你一個長度為 n 、下標從 0 開始的二進制字符串 target 。你自己有另一個長度為 n 的二進制字符串 s ，最初每一位上都是 0 。你想要讓 s 和 target 相等。

在一步操作，你可以選擇下標 i（0 <= i < n）并翻轉在閉區間 [i, n - 1] 內的所有位。翻轉意味著 '0' 變為 '1' ，而 '1' 變為 '0' 。返回使 s 與 target 相等需要的最少翻轉次數。

示例1：

輸入：target = "10111" 輸出：3 解釋：最初，s = "00000" 。 選擇下標 i = 2: "00000" -> "00111" 選擇下標 i = 0: "00111" -> "11000" 選擇下標 i = 1: "11000" -> "10111" 要達成目標，需要至少 3 次翻轉。

示例2：

輸入：target = "101" 輸出：3 解釋：最初，s = "000" 。 選擇下標 i = 0: "000" -> "111" 選擇下標 i = 1: "111" -> "100" 選擇下標 i = 2: "100" -> "101" 要達成目標，需要至少 3 次翻轉。

• n == target.length

• 1 <= n <= 10^5

• target[i] 為 '0' 或 '1'

問題分析

這題說的是把字符串"0000……"轉換成目標字符串target，所需要轉換的次數，target字符串只包含 0 和 1 。如果從第 i 個字符串開始轉換，則它后面所有的字符都要轉。

這里我們直接模擬，遇到連續相同的字符，只需要轉換一次，比如示例一中，把字符串 "00000" 全部反轉得到 "11111" ，然后再從第 2 個開始全部反轉，得到 "10000"，接著再從第 3 個開始全部反轉，得到 "10111" 。

所以這題實際上是計算 1 ，0 交替的次數，如果連續的 0 或連續的 1 ，則表示沒有交替，不需要計算。

我們可以使用一個變量preChar來記錄前一個字符，因為初始字符串都是 0 ，所以preChar的初始值也是字符 '0' ，代碼如下所示。

JAVA：

public int minFlips(String target) {     char[] chars = target.toCharArray();     int ans = 0;     char preChar = '0';// 上一個字符     for (char ch : chars) {         if (ch != preChar) {             ans++;             preChar = ch;         }     }     return ans; }

C++：

public:     int minFlips(string target) {         int ans = 0;         char preChar = '0';// 上一個字符         for (const char &ch: target) {             if (ch != preChar) {                 ans++;                 preChar = ch;             }         }         return ans;     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。