• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode926.将字符串翻转到单调递增|FlipStringtoMonotoneIncreasing ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/9824906.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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: 1
Explanation: We flip the last digit to get 00111.

Example 2:

Input: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: 2
Explanation: We flip to get 00000000.

 Note:

  1. 1 <= S.length <= 20000
  2. 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. 1 <= S.length <= 20000
  2. S 中只包含字符 '0' 和 '1'

 36ms

 1 class Solution {
 2     func minFlipsMonoIncr(_ S: String) -> Int {
 3         var zeros = 0;
 4         var ones = 0;
 5         var res = 0;
 6         var S = Array(S)
 7         for i in S {
 8             if i == "0" {
 9                 zeros+=1
10             } else {
11                 ones+=1
12             }
13         }
14         
15         var start = 0;
16         var end = S.count - 1;
17         while end > start {
18             if ones >= zeros {
19                 if(S[end] == "1") {
20                     ones-=1
21                 }
22                 if S[end] == "0" {
23                     zeros-=1
24                     res+=1
25                 }
26                 end-=1
27             }
28             else{
29                 if(S[start] == "0") {
30                     zeros-=1
31                 }
32                 if(S[start] == "1"){
33                     ones-=1;
34                     res+=1;
35                 }
36                 start+=1;
37             }
38         }
39         return res;    
40     }
41 }

56ms

 1 class Solution {
 2     func minFlipsMonoIncr(_ S: String) -> Int {
 3         
 4         var chars = Array(S)
 5         let totalItems = chars.count
 6         var prefixSums = [Int](repeating: 0, count: totalItems + 1)
 7         for i in 0..<chars.count {
 8             prefixSums[i + 1] = prefixSums[i] + (chars[i] == "1" ? 1 : 0)
 9         }
10         var result = Int.max
11         for i in 0..<prefixSums.count {
12             
13             let flipCounter = prefixSums[i] + (totalItems - i) - (prefixSums.last! - prefixSums[i])
14             result = min(result, flipCounter)
15         }
16         return result
17     }
18 }

60ms

 1 class Solution {
 2     func minFlipsMonoIncr(_ S: String) -> Int {
 3         var s: [Int] = S.map { $0 == "0" ? 0 : 1}
 4         var onlyOnes: [Int] = Array(repeating: 0, count: s.count)
 5         var onlyZeros: [Int] = Array(repeating: 0, count: s.count)
 6         
 7         for i in (0..<s.count).reversed() {            
 8             let prev = (i < (s.count - 1)) ? onlyOnes[i+1] : 0
 9             onlyOnes[i] = (s[i] == 0 ? 1 : 0) + prev
10         }
11         
12         for i in 0..<s.count {
13             let prev = (i > 0) ? onlyZeros[i-1] : 0
14             onlyZeros[i] = (s[i] == 1 ? 1 : 0) + prev
15         }
16         
17         var minFlips = min(onlyZeros.last!, onlyOnes.first!)
18         for i in 0..<(onlyOnes.count - 1) {
19             minFlips = min(minFlips, onlyZeros[i] + onlyOnes[i+1])
20         }
21         return minFlips
22     }    
23 }

108ms

 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 = 0
12         for i in 0...len
13         {
14             ct[i] += x
15             if i < len && arr[i] == "1"
16             {
17                 x += 1
18             }
19         }
20         x = 0
21         for i in (0...len).reversed()
22         {
23            ct[i] += x
24             if i > 0 && arr[i - 1] == "0"
25             {
26                 x += 1
27             }            
28         }
29         var res = 999999999
30         for i in 0...len
31         {
32             res = min(res,ct[i])
33         }
34         return res       
35     }
36 }

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 = 0
12         for i in 0...len
13         {
14             ct[i] += x
15             if i < len && arr[i] == "1"
16             {
17                 x += 1
18             }
19         }
20         x = 0
21         for i in (0...len).reversed()
22         {
23            ct[i] += x
24             if i > 0 && arr[i - 1] == "0"
25             {
26                 x += 1
27             }            
28         }
29         var res = 999999999
30         for i in 0...len
31         {
32             res = min(res,ct[i])
33         }
34         return res       
35     }
36 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap