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

[Swift]LeetCode525.连续数组|ContiguousArray

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

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

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

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

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

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1. 

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1. 

Note: The length of the given binary array will not exceed 50,000.


给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组(的长度)。 

示例 1:

输入: [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。

示例 2:

输入: [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。 

注意: 给定的二进制数组的长度不会超过50000。


760ms

 1 class Solution {
 2     func findMaxLength(_ nums: [Int]) -> Int {
 3         var map = [Int: Int]()
 4         map[0] = -1
 5         
 6         var maxLength = 0
 7         var count = 0
 8         for i in 0..<nums.count {
 9             count += nums[i] == 1 ? 1 : -1
10             if let v = map[count] {
11                 maxLength = max(maxLength, i - v)
12             } else {
13                 map[count] = i
14             }
15         }
16         
17         return maxLength
18     }
19 }

804ms

 1 class Solution {
 2     func findMaxLength(_ nums: [Int]) -> Int {
 3         let nums = nums.map { (n: Int) -> Int in
 4             if n == 0 { 
 5                 return -1 
 6             } else { 
 7                 return 1 
 8             }
 9         }
10         var preSum: [Int: Int] = [:] // sum - index
11         preSum[0] = -1
12         var sum = 0
13         var res = 0
14         for i in 0 ..< nums.count {
15             sum += nums[i]
16             if preSum[sum] != nil {
17                 res = max(res, i - preSum[sum]!)  
18             } else {
19                 preSum[sum] = i
20             }
21         }
22         return res
23     }
24 }

Runtime: 812 ms
Memory Usage: 19.7 MB
 1 class Solution {
 2     func findMaxLength(_ nums: [Int]) -> Int {
 3         var res:Int = 0
 4         var n:Int = nums.count
 5         var sum:Int = 0
 6         var m:[Int:Int] = [0:-1]
 7         for i in 0..<n
 8         {
 9             let num:Int = (nums[i] << 1) - 1
10             sum += num
11             if m[sum] != nil
12             {
13                 res = max(res, i - m[sum]!)
14             }
15             else
16             {
17                 m[sum] = i
18             }
19         }
20         return res
21     }
22 }

904ms

 1 class Solution {
 2     func findMaxLength(_ nums: [Int]) -> Int {
 3         if nums.isEmpty { return 0 }
 4         
 5         var sums = [Int: (Int?, Int?)]()
 6         sums[0] = (-1, nil)
 7 
 8         var sum = 0
 9         for i in 0..<nums.count {
10             sum += (nums[i] == 1) ? 1 : -1
11             if sums[sum] == nil {
12                 sums[sum] = (i, nil)
13             } else {
14                 sums[sum]!.1 = i
15             }
16         }
17         
18         var ret = 0
19         for (sum, pair) in sums {
20             if pair.1 != nil {
21                 ret = max(ret, pair.1! - pair.0!)
22             }
23         }
24         return ret
25     }
26 }

976ms

 1 class Solution {
 2     func findMaxLength(_ nums: [Int]) -> Int {
 3         let n = nums.count
 4         if n == 0 { return 0 }
 5         var max = [Int](repeating: 0, count: n)
 6         var count_ones = [Int](repeating: 0, count: n)
 7         for i in 0..<n {
 8             if i == 0 { count_ones[i] = nums[0] }
 9             else { count_ones[i] = count_ones[i-1] + nums[i] }
10         }
11         
12         max[n-1] = 0
13         var i = n-2
14         var res = 0
15         while i >= 0 {
16             var diff = (nums[i] == 1 ? 1 : -1)
17             var j = i
18             while diff != 0 && j < n {
19                 let next_j = j + abs(diff)
20                 if next_j >= n { break }
21                 let ones = (count_ones[next_j] - count_ones[j])
22                 let zeros = (next_j - j) - ones
23                 diff = diff + ones - zeros
24                 j = next_j
25             }
26             
27             if diff == 0 {
28                 max[i] = (j-i+1) + (j < n-1 ? max[j+1] : 0)
29             }
30             
31             if res < max[i] { res = max[i] }
32             
33             i -= 1
34         }
35         
36         return res
37     }
38 }

1160ms

 1 class Solution {
 2     func findMaxLength(_ nums: [Int]) -> Int {
 3         var map: [Int: [Int]] = [:]
 4         var curr = 0
 5         map[0] = [0]
 6         
 7         for i in 0..<nums.count {
 8             var bin = nums[i]
 9             
10             if (bin == 1) {
11                 curr += 1
12             }
13             else {
14                 curr -= 1
15             }
16                 
17             if let _ = map[curr] {
18                 map[curr]!.append(i+1)
19             }
20             else {
21                 map[curr] = [i+1]
22             }
23         }
24         
25         return getMaxLengthFromMap(map)
26     }
27     
28     func getMaxLengthFromMap(_ map: [Int: [Int]]) -> Int {
29         var maxL = 0
30         
31         for key in map.keys {
32             let indexes = map[key]!
33             if indexes.count > 1 {
34                 var tempMax = indexes[indexes.count-1] - indexes[0]
35                 
36                 maxL = max(maxL, tempMax)
37             }
38         }
39         
40         return maxL
41     }
42 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
iOS代码规范-swift发布时间:2022-07-13
下一篇:
[Swift]LeetCode657.机器人能否返回原点|RobotReturntoOrigin发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

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

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

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