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

[Swift]LeetCode306.累加数|AdditiveNumber

原作者: [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 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
iOS8开发~Swift(二)Playground发布时间:2022-07-13
下一篇:
5.5 类的引用(reference)特征 [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