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

题目

给你一个二进制字符串 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 几天下来 都忘了

原文地址:https://blog.csdn.net/u013270444/article/details/131418421

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

上一篇 2023年06月28日 06:15
下一篇 2023年06月28日 06:16