C#版 - Leetcode 306. 累加数 - 题解
C#版 - Leetcode 306. 累加数 - 题解
C#版 - Leetcode 306. 累加数 - 题解
306.Additive Number
在线提交: https://leetcode-cn.com/problems/additive-number/
累加数是一个字符串，组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含 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进阶: 你如何处理一个溢出的过大的整数输入?
- 题目难度：
Medium - 通过次数：68
- 提交次数：296
- 相关话题 回溯算法 相似题目 将数组拆分成斐波那契序列
思路: Additive Number(累计数)的定义类似于Fibonacci数列，先将其划分为字串，用数学公式可将其满足的关系表示为: substrn=substrn−2substrn=substrn−2substr_{n} = substr_{n-2} +(concat) substrn−1substrn−1substr_{n-1}. 可用暴力搜索(Brute Force search)的方法来求解，让第一个数字先从第1位开始，第2个数字从第1位，第2位，往高位开始搜索，前两个数字确定了，相加得到第3位数字，3个数拼接起来形成一个字符串，和原字符串长度相比，如果小于原长度，则取出上一次计算的第2个和第3个数当做新一次计算的前两个数做同样的操作得到新字符串，再和原字符串长度相比…依此类推，直到当前字符串长度不小于原字符串长度，比较两者是否相同，相同返回true，不同则继续循环。如果遍历完了还是没有返回true，则返回false。
已AC代码(使用迭代，这里而不是递归):
public class Solution
{
public bool IsAdditiveNumber(string num)
{
if (String.IsNullOrEmpty(num))
return false;
int len = num.Length;
for (int i = 1; i < len; i++) // 使用两个游标i, j分别作为substr{n-2}和substr{n-1}的开始位置
{
for (int j = i + 1; j < len; j++)
{
string s1 = num.Substring(0, i); // Substring(startIndex, length)
string s2 = num.Substring(i, j - i);
var d1 = long.Parse(s1);
var d2 = long.Parse(s2);
var next = d1 + d2;
if ((s1.Length > 1 && s1[0] == '0') || (s2.Length > 1 && s2[0] == '0'))
continue;
var now = s1 + s2 + next.ToString();
//if (num.IndexOf(now) >= 0)
//{
while (now.Length < num.Length) // Move forward
{
d1 = d2;
d2 = next;
next = d1 + d2;
now += next.ToString();
}
//}
if (now == num)
return true;
}
}
return false;
}
}Rank:
You are here! Your runtime beats 77.78% of csharp submissions.
有点疑惑的是为何加不加原字符串含是否有新串的判断，对结果没影响呢？欢迎留言交流~