【面试高频题】难度 2/5,回溯 + 高精度的经典结合
题目描述
这是 LeetCode 上的 306. 累加数 ,难度为 中等。
Tag : 「回溯算法」、「高精度」
累加数 是一个字符串,组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3
个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。
给你一个只包含数字 '0'-'9'
的字符串,编写一个算法来判断给定输入是否是 累加数 。如果是,返回 true
;否则,返回 false
。
说明:累加序列里的数 不会 以 0
开头,所以不会出现 1
, 2
, 03
或者 1
, 02
, 3
的情况。
示例 1:
输入:"112358"
输出:true
解释:累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
示例 2:
输入:"199100199"
输出:true
解释:累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
提示:
- 1<=num.length<=351 <= num.length <= 351<=num.length<=35
num
仅由数字(0
-9
)组成
进阶:你计划如何处理由过大的整数输入导致的溢出?
回溯 + 高精度加法
给定的 numsnumsnums 的长度只有 353535,且要求序列的第三个数开始由前两个数相加而来。
容易想到通过 DFS
爆搜每个数的分割点,同时利用累加数的特性(第三个数起,每个数均由为前两数之和)进行剪枝。
具体的,我们可以实现一个 boolean dfs(int u)
函数,入参为当前决策到 numnumnum 的哪一位,返回值为决策结果(序列)是否为累加数序列,爆搜过程中的分割数序列存放到 listlistlist 中。
由于是 从位置 uuu 作为开始位置决策如何分割出当前数 xxx,我们可以枚举当前数的结束位置,范围为 [u,n−1][u, n - 1][u,n−1],但需要注意分割数不能包含前导零,即如果 num[u]=0num[u] = 0num[u]=0,则当前数只能为 000。
同时,一个合法的分割数必然满足「其值大小为前两数之和」,因此当前数 xxx 能够被添加到 listlistlist 的充要条件为:
- listlistlist 长度不足 222,即 xxx 为序列中的前两数,不存在值大小的约束问题,xxx 可以被直接到 listlistlist 并继续爆搜;
- listlistlist 长度大于等于 222,即 xxx 需要满足「其值大小为前两数之和」要求,以此条件作为剪枝,满足要求的 xxx 才能追加到 listlistlist 中并继续爆搜。
最后,在整个 DFS
过程中我们需要监测「当前数」与「前两数之和」是否相等,而分割数长度最大为 353535,存在溢出风险,我们需要实现「高精度加法」,实现一个 check
函数,用于检查 a + b
是否为 c
,其中 a
、b
和 c
均为使用「逆序」存储数值的数组(最高位对应个位,举个 🌰,a=35a = 35a=35,则有 [5, 3]
)。
若爆搜过程能顺利结束(得到长度至少为 333 的序列),则说明能够拆分出累加数序列,返回 True
,否则返回 False
。
至此,我们解决了本题,并通过引入「高精度」来回答了「进阶」部分的问题。
代码:
class Solution {
String num;
int n;
List<List<Integer>> list = new ArrayList<>();
public boolean isAdditiveNumber(String _num) {
num = _num;
n = num.length();
return dfs(0);
}
boolean dfs(int u) {
int m = list.size();
if (u == n) return m >= 3;
int max = num.charAt(u) == '0' ? u + 1 : n;
List<Integer> cur = new ArrayList<>();
for (int i = u; i < max; i++) {
cur.add(0, num.charAt(i) - '0');
if (m < 2 || check(list.get(m - 2), list.get(m - 1), cur)) {
list.add(cur);
if (dfs(i + 1)) return true;
list.remove(list.size() - 1);
}
}
return false;
}
boolean check(List<Integer> a, List<Integer> b, List<Integer> c) {
List<Integer> ans = new ArrayList<>();
int t = 0;
for (int i = 0; i < a.size() || i < b.size(); i++) {
if (i < a.size()) t += a.get(i);
if (i < b.size()) t += b.get(i);
ans.add(t % 10);
t /= 10;
}
if (t > 0) ans.add(t);
boolean ok = c.size() == ans.size();
for (int i = 0; i < c.size() && ok; i++) {
if (c.get(i) != ans.get(i)) ok = false;
}
return ok;
}
}
- 时间复杂度:爆搜的复杂度为指数级别,且存在剪枝操作,分析时空复杂度意义不大
- 空间复杂度:爆搜的复杂度为指数级别,且存在剪枝操作,分析时空复杂度意义不大
最后
这是我们「刷穿 LeetCode」系列文章的第 No.306
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
转载自:https://juejin.cn/post/7254492693278900280