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

[Swift]LeetCode1013.将数组分成和相等的三个部分|PartitionArrayIntoThreePartsWithE ...

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

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

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

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

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

Given an array A of integers, return true if and only if we can partition the array into three non-emptyparts with equal sums.

Formally, we can partition the array if we can find indexes i+1 < j with (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])

Example 1:

Input: [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Example 2:

Input: [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false

Example 3:

Input: [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

Note:

  1. 3 <= A.length <= 50000
  2. -10000 <= A[i] <= 10000

给定一个整数数组 A,只有我们可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false

形式上,如果我们可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。

示例 1:

输出:[0,2,1,-6,6,-7,9,1,2,0,1]
输出:true
解释:0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

示例 2:

输入:[0,2,1,-6,6,7,9,-1,2,0,1]
输出:false

示例 3:

输入:[3,3,6,5,-2,2,5,1,-9,4]
输出:true
解释:3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

提示:

  1. 3 <= A.length <= 50000
  2. -10000 <= A[i] <= 10000

Runtime: 364 ms
Memory Usage: 19.5 MB
 1 class Solution {
 2     func canThreePartsEqualSum(_ A: [Int]) -> Bool {
 3         var sum:Int = 0
 4         var n:Int = A.count
 5         for i in 0..<n {sum += A[i]}
 6         if sum % 3 != 0 {return false}
 7         sum /= 3
 8         var cnt:Int = 0
 9         var ok:Int = 0
10         for i in 0..<n
11         {
12             cnt += A[i]
13             if sum == cnt && ok != 2
14             {
15                 cnt = 0
16                 ok += 1
17             }
18         }
19         return ok == 2 && sum == cnt        
20     }
21 }

364ms
 1 class Solution {
 2     func canThreePartsEqualSum(_ A: [Int]) -> Bool {
 3         var total = 0
 4         for i in 0..<A.count {
 5             total = total + A[i]
 6         }
 7         
 8         let target = total / 3
 9         if total % 3 != 0 {
10             return false
11         }
12         
13         var sum = 0
14         var count = 0
15         for i in 0..<A.count {
16             sum = sum + A[i]
17             if sum == target {
18                 count = count + 1
19                 sum = 0
20                 continue
21             }
22         }
23 
24         if count == 3 && sum == 0 {
25             return true
26         }
27         
28         return false
29     }
30 }

372ms

 1 class Solution {
 2     func canThreePartsEqualSum(_ A: [Int]) -> Bool {
 3         let count = A.count
 4         var sum = 0
 5         for item in A {
 6             sum = sum + item
 7         }
 8         guard sum % 3 == 0 else { return false }
 9         let part = Int(sum / 3)
10         print(part)
11         var i = -1
12         var j = count
13         var part1 = 0
14         var part2 = 0
15         while i+1<j {
16             i = i + 1
17             j = j - 1
18             var checkPart1 = true
19             if checkPart1 {
20                 checkPart1 = false
21                 while part1 != part && i < j+1 {
22                     part1 = part1 + A[i]
23                     i = i + 1
24                 }
25                 i = i - 1
26                 if i+1 > j {
27                     return false
28                 }
29             }
30             
31             var checkPart2 = true
32             if checkPart2 {
33                 checkPart2 = false
34                 while part2 != part && i < j+1 {
35                     part2 = part2 + A[j]
36                     j = j - 1
37                 }
38                 j = j + 1
39                 if i+1 > j {
40                     return false
41                 }
42             }
43 
44             if part1 == part2, part1 == part, i < j {
45                 return true
46             }
47         }
48         return false
49     }
50 }

376ms

 1 class Solution {
 2     func canThreePartsEqualSum(_ A: [Int]) -> Bool {
 3         let aSum = A.reduce(0, +)
 4         if aSum % 3 != 0 {
 5             return false
 6         }
 7         let expectedSectionSum = aSum / 3
 8         var expectedSectionSumSeenCount = 0
 9         var currentSectionSum = 0
10         for i in 0..<A.count {
11             let value = A[i]
12             if value == 0 {
13                 continue
14             }
15             currentSectionSum += value
16             if currentSectionSum == expectedSectionSum {
17                 expectedSectionSumSeenCount += 1
18                 currentSectionSum = 0
19             }
20         }
21         return expectedSectionSumSeenCount == 3
22     }
23 }

380ms

 1 class Solution {
 2     func canThreePartsEqualSum(_ A: [Int]) -> Bool {
 3         let sum = A.reduce(0, +)
 4         guard sum % 3 == 0 else { return false }
 5         let target = sum / 3
 6         var split = [Int](), currSum = 0
 7         for i in 0..<A.count {
 8             currSum += A[i]
 9             if currSum == target {
10                 split.append(i)
11                 currSum = 0
12             }
13         }
14         return split.count >= 2 && 0 <= split[0] && split[0] < split[1] && split[1] < A.count
15     }
16 }

400ms

 1 class Solution {
 2     func canThreePartsEqualSum(_ A: [Int]) -> Bool {
 3         guard A.count >= 3 else {
 4             return false
 5         }
 6         
 7         let sum = A.reduce(0) { $0 + $1 }
 8         guard sum % 3 == 0 else {
 9             return false
10         }
11         let partition = sum / 3
12         var count = 0 
13         var current = 0
14         for a in A {
15             current += a
16             if current == partition {
17                 count += 1
18                 current = 0
19             }
20         }
21         return count != 0 && count % 3 == 0
22     }
23 }

408ms

 1 class Solution {  
 2   func canThreePartsEqualSum(_ A: [Int]) -> Bool {
 3     var firstSum = 0
 4     let total = A.reduce(0, +)
 5     for (index, element) in A.enumerated() {
 6       firstSum += element
 7       let twoSums = total - firstSum
 8       if twoSums % 2 == 0 {
 9         if twoSums / 2 == firstSum && A.count - index > 2 {
10           let subarray: [Int] = Array(A[index..<A.count])
11           return validateSecondPart(subarray, withSum: firstSum)
12         }
13       }
14     }
15     return false
16   }
17   
18   func validateSecondPart(_ a: [Int], withSum sum: Int) -> Bool {
19     var leftover = a.reduce(0, +)
20     for (index, element) in a.enumerated() {
21       leftover -= element
22       if leftover == sum && a.count - index > 1 {
23         return true
24       }
25     }
26     return false
27   }
28 }

420ms

 1 class Solution {
 2     func canThreePartsEqualSum(_ A: [Int]) -> Bool {
 3         guard A.count >= 3 else { return false }
 4 
 5         var prefixSums = Array(repeating: 0, count: A.count + 1)
 6 
 7         for (i, num) in A.enumerated() {
 8             prefixSums[i + 1] = prefixSums[i] + num
 9         }
10 
11         let sum = prefixSums.last!
12 
13         guard sum % 3 == 0 else { return false }
14 
15         let partitionSum = sum / 3
16 
17         var a: Int?
18         var b: Int?
19 
20         for (i, num) in prefixSums.enumerated() {
21             if num == partitionSum && a == nil {
22                 a = i
23             } else if num == (partitionSum * 2) && b == nil && a != nil {
24                 b = i
25                 return true
26             }
27         }
28 
29         return false
30     }
31 }

440ms

 1 class Solution {
 2     func canThreePartsEqualSum(_ A: [Int]) -> Bool {
 3         if A.count < 3 {
 4             return false
 5         }
 6         if A.count == 3 {
 7             return (A[0] == A[1]) && (A[0] == A[2]) && (A[1] == A[2])
 8         }
 9         // start for the match.
10         var first = false
11         var second = false
12         var third = false
13         var firstSum = 0
14         var secondSum = 0
15         var thirdSum = 0
16         let totalSum = A.reduce(0,+)
17         if (totalSum % 3) != 0 {
18             return false
19         }
20         for number in A {
21             firstSum += number
22             if !first && (firstSum == (totalSum / 3)) {
23                 print("First met")
24                 first = true
25                 continue
26             }
27             if first && !second{
28                     secondSum += number
29                     if secondSum == (totalSum / 3) {
30                         print("Second met")
31                         second = true
32                         continue
33                     }
34             }
35             if second {
36                 thirdSum += number
37                     if thirdSum == (totalSum / 3) {
38                         print("Third met")
39                     }
40             }
41         }
42         if thirdSum == (totalSum / 3) {
43             return true
44         }
45         return false
46     }
47 }

452ms

 1 class Solution {
 2     func canThreePartsEqualSum(_ A: [Int]) -> Bool {
 3         var prefix: [Int] = [0]
 4         prefix.reserveCapacity(A.count + 1)
 5         for a in A {
 6             prefix.append(prefix.last! + a)
 7         }
 8         
 9         var first: Int?
10         var second: Int?
11         
12         guard prefix.last! % 3 == 0 else {
13             return false
14         }
15         
16         let oneThird = prefix.last! / 3
17         for (i, p) in prefix.enumerated() {
18             if p == oneThird {
19                 first = i
20                 break
21             }
22         }
23         
24         let twoThird = oneThird * 2
25         for (i, p) in prefix.enumerated().reversed() {
26              if p == twoThird {
27                 second = i
28                 break
29             }
30         }
31         
32         if let first = first,
33             let second = second {
34                 return first < second
35         }
36         
37         return false
38     }
39 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
苹果开源了Swift版Netty:SwiftNIO发布时间:2022-07-13
下一篇:
Swift 必备开发库 (高级篇)发布时间: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