[Swift]LeetCode926. 将字符串翻转到单调递增 | Flip String to Monotone Increasing

概述A string of ‘0‘s and ‘1‘s is monotone increasing if it consists of some number of ‘0‘s (possibly 0), followed by some number of ‘1‘s (also possibly 0.) We are given a string S of ‘0‘s and ‘1‘s, and we

A string of ‘0‘s and ‘1‘s is monotone increasing if it consists of some number of ‘0‘s (possibly 0),followed by some number of ‘1‘s (also possibly 0.)

We are given a string S of ‘0‘s and ‘1‘s,and we may flip any ‘0‘ to a ‘1‘ or a ‘1‘ to a ‘0‘.

Return the minimum number of flips to make S monotone increasing.

 Example 1:

input: "00110"Output: 1 Explanation: We flip the last digit to get 00111. 

Example 2:

input: "010110"Output: 2 Explanation: We flip to get 011111,or alternatively 000111. 

Example 3:

input: "00011000"Output: 2 Explanation: We flip to get 00000000. 

 Note:

1 <= S.length <= 20000 S only consists of ‘0‘ and ‘1‘ characters.

如果一个由 ‘0‘ 和 ‘1‘ 组成的字符串，是以一些 ‘0‘（可能没有 ‘0‘）后面跟着一些 ‘1‘（也可能没有 ‘1‘）的形式组成的，那么该字符串是单调递增的。

我们给出一个由字符 ‘0‘ 和 ‘1‘ 组成的字符串 S，我们可以将任何 ‘0‘ 翻转为 ‘1‘ 或者将 ‘1‘ 翻转为 ‘0‘。

返回使 S 单调递增的最小翻转次数。

 示例 1：

输入："00110"输出：1解释：我们翻转最后一位得到 00111.

示例 2：

输入："010110"输出：2解释：我们翻转得到 011111，或者是 000111。

示例 3：

输入："00011000"输出：2解释：我们翻转得到 00000000。

 提示：

1 <= S.length <= 20000 S 中只包含字符 ‘0‘ 和 ‘1‘

 116ms

 1 class Solution { 2     func minFlipsMonoIncr(_ S: String) -> Int { 3         var arr:[Character] = [Character]() 4         for char in S.characters 5         { 6             arr.append(char) 7         }        8         let len = S.count 9         //声明数组10         var ct:[Int] = [Int](repeating: 0,count: len + 1)11         var x:Int = 012         for i in 0...len13         {14             ct[i] += x15             if i < len && arr[i] == "1"16             {17                 x += 118             }19         }20         x = 021         for i in (0...len).reversed()22         {23            ct[i] += x24             if i > 0 && arr[i - 1] == "0"25             {26                 x += 127             }            28         }29         var res = 99999999930         for i in 0...len31         {32             res = min(res,ct[i])33         }34         return res       35     }36 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode926. 将字符串翻转到单调递增 | Flip String to Monotone Increasing全部内容，希望文章能够帮你解决[Swift]LeetCode926. 将字符串翻转到单调递增 | Flip String to Monotone Increasing所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。