题目分析

题目意思是说,给定一个字符串s, 求解里面是否含有递增的数字序列(斐波那契数列), 该数字序列至少包含3个数字,而且不能出现以0开头的多位数

思路分析

这道题的突破口在于要找到前两个数字,使这两个数字的和等于剩余字符串的开头数字。 首先对于第一个数字,它肯定是从位置0开始,最长长度为(num.length() - 1) / 2。 举个例子,比如一个字符串的长度为10,那么第一个数字的长度就不能超过4, 对于一个字符串长度为11的例子,第一个数字的长度就不能超过5。

对于第二个数字,设第一个数字的结束位置为i(不包含i),那么第二个数字的开始位置为i, 设第二个数字的结束位置为j(不包含j),那么对于第三个数字,它的开始位置就为j, 第二个数字的长度是j-i,第三个数字的长度是num.length()-j,由于数字是递增的关系, 因此第三个数字的长度必须要大于等于第一个和第二个数字的长度, 因此存在循环的约束条件:num.length()-j >= j-i && num.length() - j >= i

当把第一个,第二个,第三个数字都确定时候,如果存在第一个数字加上第二个数字等于第三个数字, 那么将剩余的子序列进行递归判断,递归判断的结束条件为剩余的字符串为空,或者第一个数字加上第二个数字不等于第三个数字

注:使用int会过不了一个例子,”121474836472147483648 ”,在这里可以分开1+2147483647=2147483648,但是2147483648对于int来说已经溢出,因此需要使用unsigned int

java

public class Solution {
    public boolean isAdditiveNumber(String num) {
        for(int i=1; i<=num.length()/2; ++i){
            if (num.charAt(0)=='0' && i>1) continue;
            for (int j = i+1; j<num.length(); ++j) {
                if (num.charAt(i)=='0' && j-i>1) continue;
                //针对各种情况都要进行判断,只要有对的就会返回true结束搜索了,只需要一个对的解
                if(dfs(num,0,i,j)) return true;
            }
        }
        // 所有的尝试都结束之后,便没有了可行解。
        return false;
    }

    private static boolean dfs(String num, int i, int j, int k) {
        long num1 = Long.parseLong(num.substring(i, j));
        long num2 = Long.parseLong(num.substring(j, k));

        final String addition = String.valueOf(num1+num2);
        if (!num.substring(k).startsWith(addition)) return false;
        if (k+addition.length()== num.length()) return true;
        return dfs(num, j, k, k+addition.length());
    }

}

python

  class Solution(object):
      def isAdditiveNumber(self, num):
          """
          :type num: str
          :rtype: bool
          """
          for i in range(1, len(num)/2+1):
              if num[0]=='0' and i>1: continue
              for j in range(i+1, len(num)):
                  if num[i]=='0' and j-i > 1: continue
                  if self.dfs(num, 0, i, j): return True
          return False

      def dfs(self, num, i, j, k):
          print i, j , k
          num1 = int(num[i:j])
          num2 = int(num[j:k])

          addition = str(num1+num2)

          if num[k:k+len(addition)] != addition:
              return False
          if k+len(addition) == len(num):
              return True
          return self.dfs(num, j, k, k+len(addition))