[Swift]LeetCode995.K连续位的最小翻转次数|MinimumNumberofKConsecutiveBitFlips ...

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

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

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

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

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

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

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

Example 1:

Input: A = 1
Output: 2
Explanation: Flip A[0], then flip A[2].

Example 2:

Input: A = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].

Example 3:

Input: A = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

Note:

1 <= A.length <= 30000
1 <= K <= A.length

在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。

返回所需的 K 位翻转的次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。

示例 1：

输入：A = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

示例 2：

输入：A = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

示例 3：

输入：A = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

提示：

1 <= A.length <= 30000
1 <= K <= A.length

Runtime: 632 ms

Memory Usage: 19 MB

 1 class Solution {
 2     func minKBitFlips(_ A: [Int], _ K: Int) -> Int {
 3         var ans:Int = 0
 4         var n:Int = A.count
 5         var f:[Bool] = [Bool](repeating:false,count:n + 1)
 6         var sum:Bool = false
 7         for i in 0..<n
 8         {
 9             //异或
10             sum = (sum == f[i]) ? false : true
11             if sum == (A[i] == 1)
12             {
13                 if i + K > n {return -1}
14                 f[i + K] = !f[i + K]
15                 sum = !sum
16                 ans += 1
17             }
18         }
19         return ans        
20     }
21 }

744ms

 1 class Solution {
 2     func minKBitFlips(_ A: [Int], _ K: Int) -> Int {
 3         var left = 0
 4         var flips = 0
 5         var totalFlips = 0
 6         var a = A
 7         
 8         while left < a.count {
 9             totalFlips = left < K ? totalFlips : totalFlips - a[left - K ]
10         
11             if totalFlips % 2 == 0 && a[left] == 0 {
12                 if left > a.count - K {
13                     return -1
14                 }
15                 flips += 1
16                 totalFlips += 1
17                 a[left] = 1
18             } else if totalFlips % 2 == 1 && a[left] == 1 {
19                 if left > a.count - K {
20                     return -1
21                 }
22                 
23                 flips += 1
24                 totalFlips += 1
25                 a[left] = 1
26             } else {
27                 a[left] = 0
28             }
29             
30             left += 1
31         }
32         
33         return flips
34     }
35 }

748ms

 1 class Solution {
 2     func minKBitFlips(_ A: [Int], _ K: Int) -> Int {
 3         var A = A
 4         var count = 0
 5         var i = 0
 6         var flipHint = A.map { _ in false }
 7         var flipped = false
 8         while i < A.count {
 9             if flipHint[i] == true {
10                 flipped.toggle()
11             }
12 
13             if A[i] == (flipped ? 1 : 0) {
14                 flipped.toggle()
15                 if i + K < A.count {
16                     flipHint[i+K] = true
17                 } else if i + K > A.count {
18                     return -1
19                 }
20                 count += 1
21             }
22             i += 1
23         }
24         return count
25     }
26 }

900ms

 1 class Solution {
 2     func minKBitFlips(_ A: [Int], _ K: Int) -> Int {
 3         var count = 0, firstIndex = 0, A = A
 4         var lastFlip: [Int] = []
 5 
 6         while firstIndex < A.count {
 7             defer { firstIndex += 1 }
 8 
 9             if let first = lastFlip.first,
10                 firstIndex >= first {
11                 lastFlip.removeFirst()
12             }
13 
14             guard (A[firstIndex] + lastFlip.count) % 2 == 0 else {
15                 continue
16             }
17             if firstIndex + K > A.endIndex {
18                 return -1
19             } else {
20                 lastFlip.append(firstIndex + K)
21                 count += 1
22             }
23         }
24 
25         return count
26     }
27 }