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

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

原作者: [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. 1 <= A.length <= 30000
  2. 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. 1 <= A.length <= 30000
  2. 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 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

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

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

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

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

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