[Swift]LeetCode306.累加数|AdditiveNumber

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: "112358"
Output: true 
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

Input: "199100199"
Output: true 
Explanation: The additive sequence is: 1, 99, 100, 199. 
             1 + 99 = 100, 99 + 100 = 199

Follow up:
How would you handle overflow for very large input integers?

累加数是一个字符串，组成它的数字可以形成累加序列。

一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

给定一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。

说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

示例 1:

输入: "112358"
输出: true 
解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

示例 2:

输入: "199100199"
输出: true 
解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

进阶:
你如何处理一个溢出的过大的整数输入?

16ms

 1 class Solution {
 2     func isAdditiveNumber(_ num: String) -> Bool {
 3         let array = [Character](num)
 4         let n = array.count
 5         if n < 3 { return false }
 6         
 7         func helper(s1: String, s2: String, remain: String) -> Bool {
 8             let one = Int(s1)!
 9             let two = Int(s2)!
10             let next = "\(one + two)"
11             if next == remain { return true }
12             var newRemain = remain
13             if remain.hasPrefix(next) {
14                 let range = remain.range(of: next)!
15                 newRemain.replaceSubrange(range, with: "")
16                 return helper(s1: s2, s2: next, remain: newRemain)
17             } else {
18                 return false
19             }
20         }
21         
22         //设第一个数是以i结尾的，第二个数是以j结尾的
23         for i in 0 ... (n - 1)/2 - 1 { //i只能取到一半以下的值
24             let one = String(array[0...i])
25             if one != "0" && one.hasPrefix("0") { continue }
26             for j in i + 1 ... n - 2 - i { //j至少取一位，且 n - j >= i
27                 let two = String(array[i+1 ... j])
28                 if two != "0" && two.hasPrefix("0") { continue }
29                 let remain = String(array[j+1 ... n-1])
30                 if remain != "0" && remain.hasPrefix("0") { continue }
31                 if helper(s1: one, s2: two, remain: remain) {
32                     return true
33                 }
34             }
35         }
36         return false
37     }
38 }

24ms

 1 class Solution {
 2     func isAdditiveNumber(_ num: String) -> Bool {
 3         
 4         if num.count < 3 {
 5             return false
 6         }
 7         
 8         let numArr = Array(num)
 9         
10         for i in 1..<numArr.count-1 {
11             for j in i+1..<numArr.count {
12                 let f = String(numArr[0..<i])
13                 let s = String(numArr[i..<j])
14                 var fn = Int(f)!
15                 var sn = Int(s)!
16                 var ln = fn + sn
17                 
18                 var l = "\(ln)"
19                 var total = f + s + l
20                 
21                 if (f.count > 1 && f.first == "0" )||(s.count > 1 && s.first == "0") {
22                     continue
23                 }
24                 while total.count < num.count {
25                     let totalArr = Array(total)
26                     if totalArr != Array(numArr[0..<totalArr.count]) {
27                         break
28                     }
29                     fn = sn
30                     sn = ln
31                     ln = fn + sn
32                     l = "\(ln)"
33                     total += l
34                 }
35                 if total == num {
36                     return true
37                 }
38             }
39         }
40         return false
41     }
42 }