2022/01/10 - 306. 累加数

306. 累加数 - Medium

Description¶

306. 累加数

累加数 是一个字符串，组成它的数字可以形成累加序列。

一个有效的 累加序列 必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。

说明：累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

提示：

1 <= num.length <= 35
num 仅由数字（0 - 9）组成

因为题目限制了num的长度最长为35，所以做加法的时候很可能会出现溢出，所以我们需要引入高精度计算来计算。

引自 OI-WIKI 中对高精度计算的解释：

高精度计算

在平常的实现中，高精度数字利用字符串表示，每一个字符表示数字的一个十进制位。因此可以说，高精度数值计算实际上是一种特别的字符串处理。

读入字符串时，数字最高位在字符串首（下标小的位置）。但是习惯上，下标最小的位置存放的是数字的 最低位，即存储反转的字符串。这么做的原因在于，数字的长度可能发生变化，但我们希望同样权值位始终保持对齐（例如，希望所有的个位都在下标 [0]，所有的十位都在下标 [1]……）；同时，加、减、乘的运算一般都从个位开始进行（回想小学的竖式运算～），这都给了「反转存储」以充分的理由。

Wikipedia: https://zh.wikipedia.org/wiki/高精度计算

Solution¶

Java DFS

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    String num;
    public boolean isAdditiveNumber(String n) {
        int len = n.length();
        num = n;
        return dfs(0, len);
    }

    private boolean dfs(int u, int len) {
        int n = list.size();
        if (u == len) return n >= 3;
        List<Integer> cur = new ArrayList<>();
        int max = num.charAt(u) == '0' ? u + 1 : len;
        for (int i = u; i < max; i++) {
            cur.add(0, num.charAt(i) - '0');
            if (n < 2 || check(list.get(n - 2), list.get(n - 1), cur)) {
                list.add(cur);
                if (dfs(i + 1, len)) return true;
                list.remove(list.size() - 1);
            }
        }
        return false;
    }

    // 使用List来做高精度加法
    private boolean check(List<Integer> a, List<Integer> b, List<Integer> c) {
        List<Integer> ans = new ArrayList<>();
        int sum = 0;
        for (int i = 0; i < a.size() || i < b.size(); i++) {
            if (i < a.size()) sum += a.get(i);
            if (i < b.size()) sum += b.get(i);
            ans.add(sum % 10);
            sum /= 10;
        }
        if (sum > 0) ans.add(sum);
        boolean ok = ans.size() == c.size();
        for (int i = 0; i < c.size() && ok; i++) {
            if (ans.get(i) != c.get(i)) ok = false;
        }
        return ok;
    }
}

2022/01/10 - 306. 累加数

Description¶

Solution¶

评论