专栏：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算法文档 。