306. 累加数

题目

image-20240911220437947

解法

这道题目其实不难，纯粹的步骤多点，一开始自己写的时候没有好好审题，做了一些无用功从而导致解题的精力被浪费掉一部分。

解题的关键就在1 和 2 的数据上，穷尽前两个的排序才能继续进行下去

都是常用的代码，字符串模拟运算，斐波那契数列的检验

提醒一下，不要被 回溯 给干扰自己对穷举的判断

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
bool StringTopic::isAdditiveNumber(string num)
{ 
	//穷举1和2 位置上的所有组合
 
	int n = num.length();
 
    //穷举second的所有可能性
	for (int secondStart = 1; secondStart < n-1; ++secondStart)
	{
		if (num[0] == '0' && secondStart != 1)
		{
			break;
		}
 
		for (int secondEnd = secondStart; secondEnd < n - 1; ++secondEnd) 
		{
			if (num[secondStart] == '0' && secondStart != secondEnd) break;
 
			if (Valid(secondStart, secondEnd, num)) return true;
		}
	}
 
	return true;
 
}
 
/// <summary>
/// 斐波那契数列检验
/// </summary>
/// <param name="secondStart"></param>
/// <param name="secondEnd"></param>
/// <param name="num"></param>
/// <returns></returns>
bool Valid(int secondStart, int secondEnd, string num) {
	int n = num.size();
	int firstStart = 0, firstEnd = secondStart - 1;
	while (secondEnd <= n - 1) {
		string third = StringAdd(num, firstStart, firstEnd, secondStart, secondEnd);
		int thirdStart = secondEnd + 1;
		int thirdEnd = secondEnd + third.size();
		if (thirdEnd >= n || !(num.substr(thirdStart, thirdEnd - thirdStart + 1) == third)) {
			break;
		}
		if (thirdEnd == n - 1) {
			return true;
		}
		firstStart = secondStart;
		firstEnd = secondEnd;
		secondStart = thirdStart;
		secondEnd = thirdEnd;
	}
	return false;
 
}
 
/// <summary>
/// 字符窜模拟运算
/// </summary>
/// <param name="s"></param>
/// <param name="firstStart"></param>
/// <param name="firstEnd"></param>
/// <param name="secondStart"></param>
/// <param name="secondEnd"></param>
/// <returns></returns>
string StringAdd(string s, int firstStart, int firstEnd, int secondStart, int secondEnd) {
	string third;
	int carry = 0, cur = 0;
	while (firstEnd >= firstStart || secondEnd >= secondStart || carry != 0)
	{
		cur = carry;
		if (firstEnd >= firstStart)
		{
			cur += s[firstEnd] - '0';
			--firstEnd;
		}
 
		if (secondEnd >= secondStart)
		{
			cur += s[secondEnd] - '0';
			--secondEnd;
		}
 
		carry = cur / 10;
		cur %= 10;
		third.push_back(cur + '0'); //一个int类型和char相加，结果是对应的 ASCII编码，这里是还原为对应的char
	}
 
	ranges::reverse(third);
	return third;
}