当前位置： 面试刷题>> 加法数 (经典算法题500道)
### 完整题目描述
**加法数（Additive Number）**
加法数是一个字符串，它的数字可以分成一些非空的连续子串，这些子串的数值从左到右依次增加，且相邻两个子串之间没有前导零（除了数字0本身）。给定一个只包含数字字符的字符串，判断它是否是一个加法数。
**示例 1**:
```
输入: "12345657"
输出: true
解释: 字符串可以拆分为子串 "12", "34", "565", "7"，它们的数值为 12, 34, 565, 7，且 12 < 34 < 565 < 7。
```
**示例 2**:
```
输入: "123456579"
输出: false
解释: 虽然我们可以拆分出 "12", "34", "565", "7", "9"，但 "565" 不是一个有效的拆分，因为它的数值大于 "7"。
```
**注意**:
- 字符串长度不会超过 100。
- 字符串中只包含数字字符 [0-9]。
### PHP 示例代码
```php
function isAdditiveNumber($num) {
$n = strlen($num);
for ($i = 1; $i <= $n / 2; $i++) {
$num1 = intval(substr($num, 0, $i));
if ($num1 == 0 && $i > 1) continue; // 排除前导零
$num2 = intval(substr($num, $i, $n - $i));
if ($num2 == 0 && $n - $i > 1) continue; // 排除第二个数前导零
if (isValid($num, $num1, $num2)) {
return true;
}
}
return false;
}
function isValid($num, $num1, $num2, &$index = 0) {
$n = strlen($num);
$len1 = strlen((string)$num1);
$len2 = strlen((string)$num2);
while ($index + $len1 <= $n) {
$nextNum = intval(substr($num, $index, $len1));
$index += $len1;
if ($index + $len2 > $n) {
return false; // 剩余字符串长度不足以构成下一个数
}
$nextNextNum = intval(substr($num, $index, $len2));
$index += $len2;
if ($num1 + $num2 != $nextNum) {
return false; // 当前和与下一个数不匹配
}
$num1 = $num2;
$num2 = $nextNextNum;
if ($index == $n) {
return true; // 字符串完全遍历完成
}
}
return false;
}
// 示例测试
echo isAdditiveNumber("12345657") ? "true" : "false"; // 输出 true
echo "\n";
echo isAdditiveNumber("123456579") ? "true" : "false"; // 输出 false
```
### Python 示例代码
```python
def isAdditiveNumber(num):
def is_valid(num, num1, num2, index=0):
len1, len2 = len(str(num1)), len(str(num2))
while index + len1 <= len(num):
next_num = int(num[index:index + len1])
index += len1
if index + len2 > len(num):
return False
next_next_num = int(num[index:index + len2])
index += len2
if num1 + num2 != next_num:
return False
num1, num2 = num2, next_next_num
if index == len(num):
return True
return False
n = len(num)
for i in range(1, n // 2 + 1):
num1 = int(num[:i])
if num1 == 0 and i > 1:
continue
num2 = int(num[i:])
if num2 == 0 and len(num[i:]) > 1:
continue
if is_valid(num, num1, num2):
return True
return False
# 示例测试
print(isAdditiveNumber("12345657")) # 输出 True
print(isAdditiveNumber("123456579")) # 输出 False
```
### JavaScript 示例代码
```javascript
function isAdditiveNumber(num) {
function isValid(num, num1, num2, index = 0) {
const len1 = num1.toString().length;
const len2 = num2.toString().length;
while (index + len1 <= num.length) {
const nextNum = parseInt(num.substring(index, index + len1));
index += len1;
if (index + len2 > num.length) {
return false;
}
const nextNextNum = parseInt(num.substring(index, index + len2));
index += len2;
if (num1 + num2 !== nextNum) {
return false;
}
[num1, num2] = [num2, nextNextNum];
if (index === num.length) {
return true;
}
}
return false;
}
const n = num.length;
for (let i = 1; i <= Math.floor(n / 2); i++) {
const num1 = parseInt(num.substring(0, i));
if (num1 === 0 && i > 1) continue;
const num2 = parseInt(num.substring(i));
if (num2 === 0 && num.length - i > 1) continue;
if (isValid(num, num1, num2)) {
return true;
}
}
return false;
}
// 示例测试
console.log(isAdditiveNumber("12345657")); // 输出 true
console.log(isAdditiveNumber("123456579")); // 输出 false
```
**码小课网站中有更多相关内容分享给大家学习**，希望这些示例代码和解释能帮助你理解并解答这个问题。