[Swift Weekly Contest 126]LeetCode1004. 最大连续1的个数 III

发布时间：2020-12-14 05:03:23 所属栏目：百科来源：网络整理

导读：Given an array? A ?of 0s and 1s,we may change up to? K ?values from 0 to 1. Return the length of the longest (contiguous) subarray that contains only 1s.?? Example 1: Input: A = [1,1,0],K = 2 Output: 6 Explanation: [1, 1,1 ] Bolded numbers

Given an array?A?of 0s and 1s,we may change up to?K?values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.??

Example 1:

Input: A = [1,1,0],K = 2 Output: 6 Explanation: [1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: A = [0,1],K = 3 Output: 10 Explanation: [0,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.?

Note:

1 <= A.length <= 20000
0 <= K <= A.length
A[i]?is?0?or?1?

给定一个由若干?0?和?1?组成的数组?A，我们最多可以将?K?个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。?

示例 1：

输入：A = [1,K = 2
输出：6
解释： 
[1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：A = [0,K = 3
输出：10
解释：
[0,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。?

提示：

1 <= A.length <= 20000
0 <= K <= A.length
A[i]?为?0?或?1?

Runtime:?476 ms

Memory Usage:?18.9 MB

 1 class Solution {
 2     func longestOnes(_ A: [Int],_ K: Int) -> Int {
 3         var res:Int = 0
 4         var zero:Int = 0
 5         var left:Int = 0
 6         for right in 0..<A.count
 7         {
 8             if A[right] == 0
 9             {
10                 zero += 1
11             }
12             while (zero > K)
13             {
14                 if A[left] == 0
15                 {
16                     zero -= 1
17                 }
18                 left += 1
19             }
20             res = max(res,right - left + 1)
21         }
22         return res        
23     }
24 }

Runtime:?576 ms

Memory Usage:?18.9 MB

 1 class Solution {
 2     func longestOnes(_ A: [Int],_ K: Int) -> Int {
 3         var n:Int = A.count
 4         var pre:[Int] = [Int](repeating:0,count:n)
 5         for i in 0..<n
 6         {
 7             if A[i] == 0
 8             {
 9                 pre[i] = 1
10             }
11         }
12         for i in 1..<n
13         {
14             pre[i] = pre[i - 1] + pre[i]
15         }
16         var fans:Int = 0
17         for i in -1..<(n - 1)
18         {
19             var lo:Int = i + 1
20             var hi:Int = n - 1
21             var ans:Int = i
22             while(lo <= hi)
23             {
24                 var mid:Int = (lo + hi) / 2
25                 var val:Int = pre[mid]
26                 if i >= 0
27                 {
28                     val -= pre[i]
29                 }
30                 if val <= K
31                 {
32                     ans = mid
33                     lo = mid + 1
34                 }
35                 else
36                 {
37                     hi = mid - 1
38                 }                
39             }
40             fans = max(fans,ans - i)
41         }
42         return fans    
43     }
44 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!