• 每日一题：LeetCode：306.累加数
  • 时间：2022-01-10
  • 力扣难度：Medium
  • 个人难度：Medium+
  • 数据结构：字符串、决策树
  • 算法：DFS、回溯、高精度加法

LeetCode每日一题.jpg

2022-01-10：LeetCode：306.累加数

1. 题目描述

• 题目：原题链接

  • 累加数是一个字符串，组成它的数字可以形成累加序列。
  • 一个有效的累加序列必须 至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
  • 给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。如果是，返回 true ；否则，返回 false 。
  • 说明：累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
  • 输入的数列的长度满足：1 <= num.length <= 35

• 输入输出规范

  • 输入：字符串
  • 输出：布尔值，表示该字符串是否是累加数

• 输入输出示例

  • 输入："199100199"
  • 输出：true

2. 方法一：递归：DFS & 字符串相加(高精度加法)

• 思路：递归 —— DFS深搜

  • 本题要求判断字符串表示的序列是否是累加数，判断条件是除了前两个数以外，其他的数都等于其前两个数的和，因此可以想到递归的思路
  • 因此，整体思路是根据递归的思想，每次根据前两个数确定第三个数的值，然后在序列上取出与第三个数相等长度的数字进行匹配
    • 匹配时，记录值对应的下标起始位置index，用于下次递归，继续向下一轮累加数判断
    • 不匹配时，直接返回false
  • 分析前两个数之和是否等于第三个数字时，注意这三个数字的位数是不确定的，可以是一位数、两位数等等
    • 所以外层需要两重循环对应前两个数，循环变量分别为前两个数字在累加数序列中的结尾下标
    • 而内层通过递归(DFS)搜索后面整个序列来依次匹配、查找第三个数
  • 注意
    • 本题说明了后面的累加数序列中不含前导0，但是并不意味着不存在数字0或以0结尾的数字
    • 如：00000、101、0121224、1002102104206等都是累加数
  • 因此，需要对字符串的前两位是否为0进行分类讨论
    • 情况一：前两个数都是0，如：00XXXX，此时只有整个序列全为0才是累加数
    • 情况二：只有第一个数是0，如：012345，此时相当于第一个数是确定的，外层循环只需要一重即可
    • 情况三：第一个数不是0，第二个数可0可不为0，如：101、1002102104206，此时外层循环需要两重循环，即前两个数字都是变化的
  • 其中，由于不断求和，可能会导致整数过大溢出，因此需要进行特殊处理，实现高精度加法
    • 方式一：通过字符串存储、模拟数字相加
    • 方式二：通过数组存储、模拟数字相加

• 题解：DFS + 字符串实现高精度加法

  // 方法一：DFS + 字符串实现高精度加法
  public boolean isAdditiveNumber(String num) {
      if (num == null || num.length() < 3) return false;
      String first = "", second = "", third = "";
      int n = num.length();
      boolean zeroFlag = false;
      // 情况一：开头是 00xxxx的情况
      if (num.charAt(0) == '0' && num.charAt(1) == '0') {
          zeroFlag = true;
          for (int i = 2; i < n; i++) {
              if (num.charAt(i) != '0') return false;
          }
          // 情况二：开头是 0xxxxx的情况
      } else if (num.charAt(0) == '0') {
          first = "0";
          for (int i = 2; i < n; i++) {
              second = num.substring(1, i);
              third = second;
              // System.out.println(third);
              if (dfs(second, third, num, i)) {
                  return true;
              }
          }
      } else {
          // 情况三：开头是 Nxxxxx的情况
          for (int i = 1; i <= n; i++) {
              for (int j = i + 1; j < n; j++) {
                  first = num.substring(0, i);
                  second = num.substring(i, j);
                  // 剪枝：如果Second的开头存在0，则不符合题意，直接跳出本次循环,进入外层循环，将该0作为first的一部分
                  if (second.length() > 1 && second.charAt(0) == '0') break;
                  //                    System.out.println(first + "  " + second);
                  third = getTarget(first, second);
                  if (dfs(second, third, num, j)) {
                      return true;
                  }
              }
          }
      }
      return zeroFlag;
  }
  
  private boolean dfs(String second, String third, String num, int index) {
      // DFS搜索到了字符串的结尾，自然结束，即是累加数 true
      if (index == num.length()) return true;
      int len = third.length();
      // 下一次搜索需要找到的数的长度超出字符串剩余的长度，一定搜索不到，false
      if (index + len > num.length()) return false;
      // 取出字符串中与要查找的third长度相等的数
      String subStr = num.substring(index, index + len);
      // 匹配就继续搜索下一轮，否则直接返回false
      if (third.equals(subStr)) {
          return dfs(third, getTarget(second, third), num, index + len);
      } else {
          return false;
      }
  }
  
  private String getTarget(String num1, String num2) {
      StringBuilder sb = new StringBuilder();
      int carry = 0, i = num1.length() - 1, j = num2.length() - 1;
      while (i >= 0 || j >= 0 || carry != 0) {
          if (i >= 0) carry += num1.charAt(i--) - '0';
          if (j >= 0) carry += num2.charAt(j--) - '0';
          sb.append(carry % 10);
          carry /= 10;
      }
      String res = sb.reverse().toString();
      // System.out.println(res);
      return res;
  }
  

• 思考一：此时的分类讨论部分非常冗长，是否可以简化

  • 原始版本中，关于前两个数字是否为0的分类讨论是直接在最外面通过if-else进行的，过于冗长，可以简化为在进行前两个数字的遍历过程中进行判断，完成分类讨论
  • 对于第一个数字first，在遍历时，可以判断此时该数字的位数，以及第一位是否为0(前导0)，如果是的话，直接返回false，因为此时只有序列为00000全0类型才是累加数，而既然已经进入了外层循环的第二轮，说明这种情况已经被排除了，该序列一定不是累加数
  • 对于第二个数字second，在遍历时，同样判断此时该数字的位数，以及第一位是否为0(前导0)，如果是的话，直接break跳出内层循环，将该前导0作为第一个数字的末尾继续进行遍历

• 思考二：DFS过程中的剪枝

  • 实际上，由于累加数序列的第三个数third是前两个数字的和，所以第三个数字的位数一定大于等于前两个数字中位数多的那个，即满足third.length() >= Math.max(first.length(), second.length())，该特性可以用于剪枝
  • 剪枝一：对于第一个数字的遍历，其位数应该小于等于整个累加数序列的一半，这样第三个数才可能存在，即外层循环的循环变量满足i <= n / 2
  • 剪枝二：对于第二个数字的遍历，其位数也有一定的要求，即整个累加数序列除去前两个数字后，剩余的位数需要大于等于前两个数字的最大位数
    • 即：n - j >= i、n - j >= j - i
    • 则有：j <= Math.min(n - i, n / 2 + i / 2) + 1

• 题解：简化+剪枝优化：字符串相加和DFS搜索的方法不变

  // 方法1: DFS+字符串相加实现高精度加法+剪枝优化、简化
  public boolean isAdditiveNumber(String num) {
      if (num == null || num.length() < 3) return false;
      String first = "", second = "", third = "";
      int n = num.length();
      // 简化分类讨论
      for (int i = 1; i <= n / 2; i++) {
          // 1. 对应0xxxx,且非0000情况
          if (first.length() > 1 && first.charAt(0) == '0') {
              return false;
          }
          for (int j = i + 1; j <= Math.min(n - i, n / 2 + i / 2) + 1; j++) {
              first = num.substring(0, i);
              second = num.substring(i, j);
              // 2. 对应N0xxxx
              if (second.length() > 1 && second.charAt(0) == '0') break;
  
              // 3. 其他情况，包括 0000 类型
              third = getTarget(first, second);
              if (dfs(second, third, num, j)) {
                  return true;
              }
          }
  
      }
      return false;
  }
  

• 思考三：DFS与回溯

  • 看到不少同学对本题属于DFS还是回溯很疑惑，这里分享一下自己的拙见
  • 首先，我认为DFS和回溯实际上都是递归思想的一种具体实现，并没有什么实质的不同，只是因为其思想理念有一些差异，所以适用于不同的题型、场景，具体而言
    • DFS是深度优先搜索，在二叉树、图等结构中经常使用，个人认为DFS就是将循环、遍历换成了递归的形式来写，即逐个分析可能的答案来寻找最终的结果，是暴力搜索
    • 回溯实际上也是暴力搜索，只是在应用场景上面多了一重回溯、试错的概念，即当一个答案不是我们所需要的答案时，进行Save&Load大法，拿到该答案的前一步答案，继续搜索后面的，比如求排列组合、子集、棋盘迷宫等问题
  • 对于本题而言，在判断序列是否存在第三个数匹配前两个数之和时，就是递归的进行搜索，属于DFS，同时，当遍历了每一个可能的第二个数后，该轮循环仍未找到结果，此时会移动第一个数字的结尾下标，相当于将本来放在第二个数的一部分给了第一个数，也算是类似回溯的概念

3. 方法二：非递归

• 本题除了使用DFS递归的进行搜索外，也可以直接通过循环、遍历来求解，即非递归形式

• 题解

  public boolean isAdditiveNumber(String num) {
      if (num == null || num.length() < 3) return false;
      String first = "", second = "", third = "";
      int n = num.length();
      // 简化分类讨论
      for (int i = 1; i <= n / 2; i++) {
          // 1. 对应0xxxx,且非0000情况
          if (first.length() > 1 && first.charAt(0) == '0') {
              return false;
          }
          for (int j = i + 1; j <= Math.min(n - i, n / 2 + i / 2) + 1; j++) {
              first = num.substring(0, i);
              second = num.substring(i, j);
              // 2. 对应N0xxxx
              if (second.length() > 1 && second.charAt(0) == '0') break;
              // 3. 其他情况，包括 0000 类型
              third = getTarget(first, second);
              // String rest = num.substring(j); // 剩下的序列
              StringBuilder rest = new StringBuilder(num.substring(j)); // 剩下的序列
              while (rest.indexOf(third) != -1) { // rest.startsWith(third)
                  first = second;
                  second = third;
                  third = getTarget(first, second);
                  // rest = rest.substring(second.length());
                  rest.delete(0, second.length());
                  if (rest.length() == 0) return true;
              }
          }
      }
      return false;
  }
  
  private String getTarget(String num1, String num2) {
      StringBuilder sb = new StringBuilder();
      int carry = 0, i = num1.length() - 1, j = num2.length() - 1;
      while (i >= 0 || j >= 0 || carry != 0) {
          if (i >= 0) carry += num1.charAt(i--) - '0';
          if (j >= 0) carry += num2.charAt(j--) - '0';
          sb.append(carry % 10);
          carry /= 10;
      }
      String res = sb.reverse().toString();
      // System.out.println(res);
      return res;
  }
  

最后

• 贴一个代码量很小的方法，来自社区：rainlight Java回溯

  class Solution {
      public boolean isAdditiveNumber(String num) {
          return dfs(num, num.length(), 0, 0, 0, 0);
      }
  
      /**
       * @param num    原始字符串
       * @param len    原始字符串长度
       * @param idx    当前处理下标
       * @param sum    前面的两个数字之和
       * @param pre    前一个数字
       * @param k      当前是处理的第几个数字
       */
      private boolean dfs(String num, int len, int idx, long sum, long pre, int k) {
          if (idx == len) {
              return k > 2;
          }
          for (int i = idx; i < len; i++) {
              long cur = fetchCurValue(num, idx, i);
              // 剪枝：无效数字
              if (cur < 0) {
                  return false;
              }
              // 剪枝：当前数字不等于前面两数之和
              if (k >= 2 && cur != sum) {
                  continue;
              }
              if (dfs(num, len, i + 1, pre + cur, cur, k + 1)) {
                  return true;
              }
          }
          return false;
      }
  
      /**
       * 获取 l ~ r 组成的有效数字
       */
      private long fetchCurValue(String num, int l, int r) {
          if (l < r && num.charAt(l) == '0') {
              return -1;
          }
          long res = 0;
          while (l <= r) {
              res = res * 10 + num.charAt(l++) - '0';
          }
          return res;
      }
  }
  

• 相关题目

  • LC842将数组拆分成斐波那契序列
  • LC415字符串相加
  • LC2两数相加

By The Way

新人LeetCoder，发布的题解有些会参考其他大佬的思路(参考资料的链接会放在最下面)，欢迎大家关注我 ~ ~ ~
如果本文有所帮助的话，希望大家可以给个三连「点赞」&「收藏」&「关注」 ~ ~ ~
也希望大家有空的时候光临我的「个人博客」。