2020-04-11 14:00:00 左右刷到的第一题
https://leetcode.com/problems/additive-number/
题干
给一个数字字符串，分割成若干个小数字，这些小数字前后有序组成一个斐波那契数列
解答过程：
看到这题有点懵，闻到了回溯的味道，感觉又是一个难题啊，
画了画，突然发现一个问题，斐波那契数列 看起来是一个数列，其实只有两个变量，
前两个数决定了数列后面的值，那我只要循环取前两项 然后做判断不就好啦？ 取前两个数相当于在一列数之间找到两个分界点，复杂度是 n 个里面选两个，n^2 ，遍历剩下的字符串能不能和前两个组成斐波那契数列，那就遍历做判断就好了，O(n),总的复杂度是 n^3。
虽然挺简单的，但是边界条件也挺不好处理的，也要适当剪枝，设前两个数的长度是 n1,n2，入参字符串长度是n,那剩下的字符串长度一定和n1,n2组成 ： （n-n1-n2）>=n1,(n-n1-n2)>=n2 。
错误提交了两次，第三次终于 Accept 了 ！
代码
class Solution {
public static boolean isAdditiveNumber(String num) {
int n = num.length();
if (n < 3) {
return false;
}
int min1 = (n - 1) / 2;
int min2 = 2 * n / 3;
for (int n1 = 1; n1 <= min1 && n1 <= min2; n1++) {
String s1 = num.substring(0, n1);
for (int n2 = 1; n2 <= min1 && n2 <= min2; n2++) {
String s2 = num.substring(n1, n1 + n2);
//数字不能以0开头，除了0自己
if (s2.startsWith("0") && s2.length() > 1) {
break;
}
String left = num.substring(n1 + n2);
//数字不能以0开头，除了0自己
if (left.startsWith("0") && left.length() > 1) {
continue;
}
//有一次成功就成功了，不然就试试其他的
if (isOk(s1, s2, left)) {
return true;
}
}
if (s1.startsWith("0")) {
break;
}
}
return false;
}
public static boolean isOk(String n1, String n2, String left) {
String s = String.valueOf(Long.valueOf(n1).longValue() + Long.valueOf(n2).longValue());
if (left.indexOf(s) != 0) {
return false;
}
if (left.length() == s.length()) {
return true;
}
String next = left.substring(s.length());
return isOk(n2, s, next);
}
}
启发
难题都是不断简化成简单的问题的，多想想哪些是变量，复杂度往往由变量决定，边界条件的处理 最好还是不要放在循环里，显得很优雅，怎么让边界条件处理得更优雅，更好看，还是有点模糊，还需要不断地练习。
