★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公眾號：山青詠芝（shanqingyongzhi）
?博客園地址：山青詠芝（https://www.cnblogs.com/strengthen/）
?GitHub地址：https://github.com/strengthen/LeetCode
?原文地址：https://www.cnblogs.com/strengthen/p/9826329.html?
?如果鏈接不是山青詠芝的博客園地址，則可能是爬取作者的文章。
?原文已修改更新！強烈建議點擊原文地址閱讀！支持作者！支持原創！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Given an array?A?of?0s and?1s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.

If it is possible, return?any?[i, j]?with?i+1 < j, such that:

• A[0], A[1], ..., A[i]?is the first part;
• A[i+1], A[i+2], ..., A[j-1]?is the second part, and
• A[j], A[j+1], ..., A[A.length - 1]?is the third part.
• All three parts have equal binary value.

If it is not possible, return?[-1, -1].

Note that the entire part is used when considering what binary value it represents.? For example,?[1,1,0]?represents?6?in decimal,?not?3.? Also, leading zeros are allowed, so?[0,1,1]?and?[1,1]?represent the same value.

?Example 1:

Input: [1,0,1,0,1] Output: [0,3]

Example 2:

Input: [1,1,0,1,1] Output: [-1,-1]

Note:

3 <= A.length <= 30000

A[i] == 0?or?A[i] == 1

---

?給定一個由?0?和?1?組成的數組?A，將數組分成 3?個非空的部分，使得所有這些部分表示相同的二進制值。

如果可以做到，請返回任何?[i, j]，其中?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, -1]。

注意，在考慮每個部分所表示的二進制時，應當將其看作一個整體。例如，[1,1,0]?表示十進制中的?6，而不會是?3。此外，前導零也是被允許的，所以?[0,1,1]?和?[1,1]?表示相同的值。

?示例 1：

輸入：[1,0,1,0,1] 輸出：[0,3]

示例 2：

輸出：[1,1,0,1,1] 輸出：[-1,-1]

?提示：

3 <= A.length <= 30000

A[i] == 0?或?A[i] == 1

---

388ms

1 class Solution { 2 func threeEqualParts(_ A: [Int]) -> [Int] { 3 var ones = [Int]() 4 for var i in 0..<A.count { 5 if A[i] == 1 { 6 ones.append(i) 7 } 8 } 9 if ones.count%3 != 0 { 10 return [-1, -1] 11 } 12 13 if ones.count == 0 { 14 return [0, A.count-1] 15 } 16 17 let part = ones.count/3 18 19 let trZero = A.count - ones.last! - 1 20 let i = ones[part-1] + trZero 21 let j = ones[part*2-1] + trZero 22 23 if i >= ones[part] { 24 return [-1, -1] 25 } 26 if j >= ones[part*2] { 27 return [-1, -1] 28 } 29 30 for var k in 0..<part { 31 let a = i - ones[k] 32 let b = j - ones[k+part] 33 let c = A.count - ones[k+part*2]-1 34 if a != b { 35 return [-1, -1] 36 } 37 if b != c { 38 return [-1, -1] 39 } 40 } 41 42 return [i, j+1] 43 } 44 }

---

424ms

1 class Solution { 2 func threeEqualParts(_ A: [Int]) -> [Int] { 3 let countA:Int = A.count 4 var one:Int = 0 5 for x in A {one += x} 6 if one % 3 != 0 {return [-1,-1]} 7 if one == 0 {return [0,countA - 1]} 8 one /= 3 9 var cc:Int = 0 10 var pos:[Int] = [Int](repeating: -2,count: 3) 11 var idx:Int = 0 12 for i in 0..<countA 13 { 14 if A[i] == 1 && cc % one == 0 15 { 16 pos[idx] = i 17 idx += 1 18 } 19 cc += A[i] 20 } 21 var len:Int = countA - pos[2] 22 if pos[1] < (pos[0] + len) || pos[2] < (pos[1] + len) {return [-1,-1]} 23 var i:Int = pos[0], j:Int = pos[1], k:Int = pos[2] 24 repeat 25 { 26 if (A[i] != A[j] || A[i] != A[k]) {return [-1,-1]}; 27 i += 1 28 j += 1 29 k += 1 30 }while(k < countA) 31 return [pos[0] + len - 1, pos[1] + len] 32 } 33 }

---

428ms

1 class Solution { 2 func threeEqualParts(_ A: [Int]) -> [Int] { 3 let countA:Int = A.count 4 var one:Int = 0 5 for x in A {one += x} 6 if one % 3 != 0 {return [-1,-1]} 7 if one == 0 {return [0,countA - 1]} 8 one /= 3 9 var cc:Int = 0 10 var pos:[Int] = [Int](repeating: -2,count: 3) 11 var idx:Int = 0 12 for i in 0..<countA 13 { 14 if A[i] == 1 && cc % one == 0 15 { 16 pos[idx] = i 17 idx += 1 18 } 19 cc += A[i] 20 } 21 var len:Int = countA - pos[2] 22 if pos[1] < (pos[0] + len) || pos[2] < (pos[1] + len) {return [-1,-1]} 23 var i:Int = pos[0], j:Int = pos[1], k:Int = pos[2] 24 repeat 25 { 26 if (A[i] != A[j] || A[i] != A[k]) {return [-1,-1]}; 27 i += 1 28 j += 1 29 k += 1 30 }while(k < countA) 31 return [pos[0] + len - 1, pos[1] + len] 32 } 33 }

?

轉載于:https://www.cnblogs.com/strengthen/p/9826329.html

總結

以上是生活随笔為你收集整理的[Swift]LeetCode927. 三等分 | Three Equal Parts的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。