算法----使二进制字符串字符交替的最少反转次数

题目

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

类型 1 ：删除字符串 s 的第一个字符并将它添加到字符串结尾。
类型 2 ：选择字符串 s 中任意一个字符并将该字符反转，也就是如果值为 ‘0’ ，则反转得到 ‘1’ ，反之亦然。
请你返回使 s 变成交替字符串的前提下，类型 2 的最少操作次数。

我们称一个字符串是交替的，需要满足任意相邻字符都不同。

比方说，字符串 “010” 和 “1010” 都是交替的，但是字符串 “0100” 不是。

示例 1：

输入：s = “111000”
输出：2
解释：执行第一种操作两次，得到 s = “100011” 。
然后对第三个和第六个字符执行第二种操作，得到 s = “101010” 。
示例 2：

输入：s = “010”
输出：0
解释：字符串已经是交替的。
示例 3：

输入：s = “1110”
输出：1
解释：对第二个字符执行第二种操作，得到 s = “1010” 。

提示：

1 <= s.length <= 105
s[i] 要么是 ‘0’ ，要么是 ‘1’ 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-number-of-flips-to-make-the-binary-string-alternating
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决思路

    fun minFlips(s: String): Int {
        //按照101010
        var count = 0
        for (i in s.toCharArray().indices){
            var char = getChar(i)
            if (s[i] != (char)){
                count++
            }
        }
        var result = count.coerceAtMost(s.length - count)


        val s2 = s + s
        for (i in s.indices){

            if (s2[i] != getChar(i)){
                count--
            }
            if (s2[i + s.length] != getChar(i + s.length)){
                count++
            }

            result = result.coerceAtMost(count.coerceAtMost(s.length - count))
        }
        return result
    }

    private fun getChar(i: Int) = if (i % 2 == 1) '0' else '1'

解决方法

1.按照 01 检测时需要修改的次数，用 len 减去就是按照 10 检测时修改的次数
2.类型 1 的操作，其实是头尾相接，但是先删除再添加操作开销太大，并且操作很麻烦
将字符串复制一份接在后面，即可使用滑动窗口丝滑拼接
3.滑窗时减去离开的格子，加上进来的格子，即可避免大量重复计算
答案就是滑窗过程中出现的最小修改次数

在这里插入图片描述
参考：https://leetcode.cn/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/solution/minimum-number-of-flips-by-ikaruga-lu32/

总结

1.好多天没有做了真的太懒了
2.程序员做一天是一天在这里插入图片描述
3.真是：聪明人有聪明人的活法不聪明的难道就不能活了吗？
一天可以做10道题也可以10天做一道题
龟兔赛跑看似是小孩子的故事，却蕴含着大道理啊
多少成年人能懂啊家人们文章来源地址https://uudwc.com/A/wJgXO

杂记

    //这题有点难啊 上来就没思路
    //我怎么知道要操作几次操作1 几次操作二最少呢？？？？
    //暴力破解的话 也不是不可以

    //就好像做了一道数学题
    //思路不清晰 不明确
    //看别人写的 真的是很清晰
    //我的思维能力 思考能力不行吗？？？？


    // 1.转换成0101 和 1010 需要的次数关系
    //小算法计算
    //woca 几天下来 都忘了