2022/01/10 - 306. 累加数
306. 累加数 - Medium
Description¶
306. 累加数
累加数 是一个字符串,组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。
给你一个只包含数字 '0'-'9'
的字符串,编写一个算法来判断给定输入是否是 累加数 。如果是,返回 true
;否则,返回 false
。
说明:累加序列里的数 不会 以 0
开头,所以不会出现 1, 2, 03
或者 1, 02, 3
的情况。
提示:
1 <= num.length <= 35
- num 仅由数字(
0
-9
)组成
因为题目限制了num
的长度最长为35,所以做加法的时候很可能会出现溢出,所以我们需要引入高精度计算来计算。
引自 OI-WIKI 中对高精度计算的解释:
高精度计算
在平常的实现中,高精度数字利用字符串表示,每一个字符表示数字的一个十进制位。因此可以说,高精度数值计算实际上是一种特别的字符串处理。
读入字符串时,数字最高位在字符串首(下标小的位置)。但是习惯上,下标最小的位置存放的是数字的 最低位,即存储反转的字符串。这么做的原因在于,数字的长度可能发生变化,但我们希望同样权值位始终保持对齐(例如,希望所有的个位都在下标 [0]
,所有的十位都在下标 [1]
……);同时,加、减、乘的运算一般都从个位开始进行(回想小学的竖式运算~),这都给了「反转存储」以充分的理由。
Wikipedia: https://zh.wikipedia.org/wiki/高精度计算
Solution¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
|