[Swift]LeetCode696.计数二进制子串|CountBinarySubstrings

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Note:

s.length will be between 1 and 50,000.
s will only consist of "0" or "1" characters.

给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

示例 1 :

输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。

另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

示例 2 :

输入: "10101"
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。

注意：

s.length 在1到50,000之间。
s 只包含“0”或“1”字符。

80ms

 1 class Solution {
 2     func countBinarySubstrings(_ s: String) -> Int {
 3         var chars = Array(s)
 4         var prev = 0, cur = 1
 5         var result = 0
 6         for i in 1..<chars.count {
 7             if chars[i-1] != chars[i] {
 8                 result += min(prev, cur)
 9                 prev = cur
10                 cur = 1
11                 
12             } else{
13                 cur += 1
14             }
15         }
16         result += min(prev, cur)
17         return result
18     }
19 }

Runtime: 92 ms

Memory Usage: 19.4 MB

 1 class Solution {
 2     func countBinarySubstrings(_ s: String) -> Int {
 3         var arr:[Character] = Array(s)
 4         var res:Int = 0
 5         var pre:Int = 0
 6         var cur:Int = 1
 7         var n:Int = s.count
 8         for i in 1..<n
 9         {
10             if arr[i] == arr[i - 1]
11             {
12                 cur += 1              
13             }
14             else
15             {
16                 pre = cur
17                 cur = 1
18             }
19             if pre >= cur
20             {
21                 res += 1
22             }
23         }
24         return res
25     }
26 }

112ms

 1 class Solution {
 2   func countBinarySubstrings(_ s: String) -> Int {
 3     var zero = 0
 4     var one = 0
 5     
 6     var substrCount = 0
 7     
 8     let s = Array(s)
 9     
10     var i = 0
11     while i < s.count {
12       while i < s.count && s[i] == "0" {
13         zero += 1
14         if one > 0 {
15           substrCount += 1
16           one -= 1
17         }
18         i += 1
19       }
20       
21       one = 0
22       
23       while i < s.count && s[i] == "1" {
24         one += 1
25         if zero > 0 {
26           substrCount += 1
27           zero -= 1
28         }
29         i += 1
30       }
31       
32       zero = 0
33     }
34     
35     return substrCount
36   }
37 }

136ms

 1 class Solution {
 2     func countBinarySubstrings(_ s: String) -> Int {
 3         var chs = Array(s)
 4         
 5         var groups:[Int] = [Int]()
 6         
 7         groups.append(1)
 8         
 9         for i in 1..<chs.count {
10             if chs[i] == chs[i - 1] {
11                 groups[groups.count - 1] += 1
12             } else {
13                 groups.append(1)
14             }
15         }
16         
17         var res = 0
18         for i in 1..<groups.count {
19             res += min(groups[i], groups[i - 1])
20         }
21         
22         return res
23     }
24 }

148ms

 1 class Solution {
 2     func countBinarySubstrings(_ s: String) -> Int {
 3         var zeros = 0
 4         var ones = 0
 5         var res = 0
 6         var isOne = s.first! == "1"
 7         for char in s {
 8             if char == "1" {
 9                 if !isOne { ones = 0 }
10                 isOne = true
11                 ones += 1
12                 if zeros > 0 {
13                     res += 1
14                     zeros -= 1
15                 }
16             } else {
17                 if isOne { zeros = 0 }
18                 isOne = false
19                 
20                 zeros += 1
21                 if ones > 0 {
22                     res += 1
23                     ones -= 1
24                 }
25             }
26         }
27         return res
28     }
29 }

188ms

 1 class Solution {
 2     func countBinarySubstrings(_ s: String) -> Int {
 3         guard s.count > 1 else { return 0 }        
 4         var sArray = s.map{ String($0) }        
 5         var count = 0
 6         for i in 0..<sArray.count-1 {            
 7             if sArray[i] != sArray[i+1] {
 8                 count += findPalindrom(at: i, in: sArray)
 9             }            
10         }        
11         return count        
12     }
13     
14     
15     func findPalindrom(at index: Int, in array: [String])->Int {        
16         guard index < array.count-1 else { return 0 }        
17         var count = 1        
18         var left = index-1
19         var right = index+2        
20         while left >= 0 && right < array.count {
21             if array[left] == array[left+1] && array[right] == array[right-1] { count += 1 }
22             else { break }            
23             left -= 1
24             right += 1
25         }        
26         return count
27     }        
28 }
29