Additive Number (M)
題目
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
Constraints:
numconsists only of digits'0'-'9'.1 <= num.length <= 35
Follow up:
How would you handle overflow for very large input integers?
題意
給定一個字串，判斷能否將該字串切割成若干個數字，且每個數字都是前兩個數字之和，
思路
先確定好最開始的兩個數，再遞回判斷整個字串，
代碼實作
Java
class Solution {
public boolean isAdditiveNumber(String num) {
for (int i = 1; i <= num.length() / 2; i++) {
if (i > 1 && num.charAt(0) == '0') break;
for (int j = 1; j <= num.length() / 2 && i + j < num.length(); j++) {
if (j > 1 && num.charAt(i) == '0') break;
String num1 = num.substring(0, i), num2 = num.substring(i, i + j);
if (dfs(num.substring(i + j), add(num1, num2), num2)) {
return true;
}
}
}
return false;
}
private boolean dfs(String s, String target, String pre) {
if (s.isEmpty()) {
return true;
}
if (!s.startsWith(target)) {
return false;
}
return dfs(s.substring(target.length()), add(target, pre), target);
}
private String add(String s, String t) {
String sum = "";
int i = 1;
int carry = 0;
while (i <= s.length() || i <= t.length()) {
int num1 = 0, num2 = 0;
if (i <= s.length()) {
num1 = s.charAt(s.length() - i) - '0';
}
if (i <= t.length()) {
num2 = t.charAt(t.length() - i) - '0';
}
int tmp = num1 + num2 + carry;
carry = tmp / 10;
sum = tmp % 10 + sum;
i++;
}
if (carry != 0) {
sum = carry + sum;
}
return sum;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24740.html
標籤：其他
上一篇：復原IP地址