📖本篇内容：leetcode每日一题leetcode每日一题306. 累加数 DFS暴搜你掌握了没~
📆 最近更新：2022年1月9日 leetcode每日一题1629. 按键持续时间最长的键 今天玩点好玩的字符串匹配模拟
🙊个人简介：一只二本院校在读的大三程序猿，本着注重基础，打卡算法，分享技术作为个人的经验总结性的博文博主，虽然可能有时会犯懒，但是还是会坚持下去的，如果你很喜欢博文的话，建议看下面一行~（疯狂暗示QwQ）
🌇 点赞 👍 收藏 ?留言 📝 一键三连 关爱程序猿，从你我做起
写在前面
今日个由于小付从重庆回四川，社区的嬢嬢们就登门拜访喊我跑去做核酸，说实话哈，毕竟被捅了那么多次喉咙了，但是每次被捅都一样想吐…所幸忍住了不然早饭溢出，就跟着当场社死。那咱们言归正传，今天的力扣题，稍微有点难度，但是思想应该很简单，如果觉得可以，请一定要好好写哦，没准蓝桥杯也能刷着类似的题呢，话不多说，冲冲冲！
题目
- 累加数
累加数 是一个字符串，组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 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 <= 35
num 仅由数字（0 - 9）组成
思路
这道题的整体难点就在于：
- 如果当前的这个字符为
0时，需要进行判别下一位数字，是否会出现02这种数字，如果出现则直接返回false，反之继续进行判定数字之和是否符合对应的条件。然后通过递归来实现DFS的暴搜。
代码实现
class Solution {
public boolean isAdditiveNumber(String num) {
//获取字符串长度
int n = num.length();
//转换成字符数组便于操作 检查
char[] numsChar = num.toCharArray();
//开始遍历前两个`数字`中的第一个数字
for (int i = 0 ; i< n-1;i++){
//如果处于第一个位置的字符为`0` 那么这个字符串就是0xxxxx的一个字符串所以第三位必须与第二位相同
if (numsChar[0] == '0' && i > 0)return false;
//开始遍历第二个数字
for (int j = i+1;j< n-1;j++){
//找到了第一个数字的下一位即i+1 进行判断是否还会出现`0x`的数字，出现就跳出当前循环继续
if (numsChar[i+1] == '0' && j > i+1)continue;
//这里用到Long高精度数的判定
//获取得到第一个数字与第二个数字用来进行判断 左闭右开哦~
Long pre = Long.parseLong(num.substring(0,i+1));
Long cur = Long.parseLong(num.substring(i+1,j+1));
//通过暴搜递归获得结果
if (dfs(numsChar,pre,cur,num,n,j+1))return true;
}
}
return false;
}
//暴搜方法
public boolean dfs (char[] numsChar,Long pre,Long cur ,String num,int n,int now){
//如果当前能判断到最后一个数字时，则肯定是累加数
if (now == n)return true;
//遍历下一个数字是否满足条件
for (int i = now;i<n;i++){
//老样子来或判断当前是否可能出现·0x·的数字
if (numsChar[now] == '0' && i > now)return false;
//获取下一个数字
Long next = Long.parseLong(num.substring(now,i+1));
//进行条件判断，如果正确就递归进行到底。
if (next > pre + cur)return false;
if (next == pre + cur){
if (dfs(numsChar,cur,next,num,n,i+1))
return true;
break;
}
}
return false;
}
}
执行结果
写在最后
2022-1-10小付坚持打卡了哦~
今天的暴搜DFS算比较好掌握的一种解法题
其实和动态规划有点沾边
多多理解 多刷刷题 总会理解的
最后
每天进步点 每天收获点
愿诸君 事业有成 学有所获
如果觉得不错 别忘啦一键三连哦~