LeetCode306.累加数：「DFS (回溯) & 高精度加法」&「非递归」

浏览次数 : 次 2022-01-10

博文字数统计 : 2.9k字 | 阅读所需时长 : 12分

× 文章目录

1. LeetCode306.累加数：「DFS (回溯) & 高精度加法」&「非递归」

LeetCode306：累加数
- 时间：2022-01-10
- 力扣难度：Medium
- 个人难度：Medium+
- 数据结构：字符串、决策树
- 算法：DFS、回溯、高精度加法

LeetCode306.累加数：「DFS (回溯) & 高精度加法」&「非递归」

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;
    }
}

相关题目

本文作者： Chthollists
发布时间： 2022-01-10 22:36:12
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode306.累加数：「DFS (回溯) & 高精度加法」&「非递归」
本文链接： https://chthollists.github.io/post/b63af80b.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！