当前位置:网站首页>【LeetCode】306.累加数(思路+题解)
【LeetCode】306.累加数(思路+题解)
2022-08-11 05:33:00 【sakamotoen】
【LeetCode】306.累加数(思路+题解)
记录个人解题思路与代码,欢迎和谐讨论
一、题目
累加数 是一个字符串,组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。
给你一个只包含数字 '0'-'9'
的字符串,编写一个算法来判断给定输入是否是 累加数 。如果是,返回 true
;否则,返回 false
。
说明:累加序列里的数 不会 以 0 开头,所以不会出现 1, 2, 03
或者 1, 02, 3
的情况。
来源:力扣(LeetCode)
链接:源力扣地址
示例 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)组成
二、思路
这道题的解法是经典的回溯算法,回溯算法类似与枚举的搜索尝试,主要是在搜索尝试中寻找问题的解。在本题中,我们设两个待加数字为a与b,结果为c,那么在此问题中搜索即是搜索a与b,尝试判断其是否等于c。在提示中题目强调了num字符串的最长长度为35,那么就意味着可以出现长度为17的数字,其大小远大于int类型支持的位数,因此在算法中采用 long long int类型来保存过程中出现的数字。
除此之外,在问题中强调不会出现以0开头的数字,那么就要求在此之中必须能够判断字符串转出来的数字是否合法。由于在问题中可以看出不会出现复数,那么我们可以通过编写一个字符串转long long int 的函数顺便判断了这个数字是否合法,非法则返回-1.
随后在判断中,如遇到a+b>c
的情况,可能是由于进位产生的,因此我们再给c补一位再重新判断是否相等,若a+b<c
则显然是出现了搜索错误,因此直接将b的长度++进行新一轮搜索即可。
最后看看效果:
三、代码
代码如下:
class Solution {
private:
long long int getNum(const string num, int pos, int len) {
//字符串转ll数字,如果非法返回-1;
if (pos != 0 and len != 1 and num[pos] == '0')
return -1;
return stoll(num.substr(pos, len), NULL, 10);
}
public:
bool isAdditiveNumber(string num) {
if (num.size() < 3) return 0;
int a_len = 1;
bool a_f = true;
while (a_len <= floor(num.size() / 2) and a_f) {
int a_pos = 0;
int b_pos = a_pos + a_len;
int b_len = 1;
bool b_f = true;
while (b_len <= floor((num.size() - a_len) / 2) and a_f and b_f) {
int c_pos = b_pos + b_len;
int c_len = max(a_len, b_len);
bool c_f = true;
long long int a = getNum(num, a_pos, a_len);
if (a == -1) {
a_f = false;
break;
}
long long int b = getNum(num, b_pos, b_len);
if (b == -1) {
b_f = false;
break;
}
int a_len_temp = a_len;
int b_len_temp = b_len;
while (c_pos + c_len <= num.size()) {
if (c_len > (max(a_len_temp, b_len_temp) + 1) and c_f)
break;
long long int c = getNum(num, c_pos, c_len);
if (c == -1) {
c_f = false;
break;
}
if (a + b == c) {
a = b;
b = c;
a_len_temp = b_len_temp;
b_len_temp = c_len;
c_pos = c_pos + c_len;
}
else if (a + b > c)
++c_len;
else if (a + b < c)
break;
if (c_pos == num.size())
return 1;
}
++b_len;
}
++a_len;
}
return 0;
}
};
边栏推荐
- ansible批量安装zabbix-agent
- 查看CPU和其他硬件温度的软件
- 文本三剑客——grep过滤
- uboot sets the default bootdelay
- AUTOMATION DAY06( Ansible进阶 、 Ansible Role)
- vnc远程桌面安装(2021-10-20日亲测可用)
- Threatless Technology-TVD Daily Vulnerability Intelligence-2022-7-19
- buildroot嵌入式文件系统中vi显示行号
- SECURITY DAY05 (Kali system, scanning and caught, SSH basic protection, service SECURITY)
- Apache APISIX 默认密钥漏洞复现
猜你喜欢
随机推荐
ETCD容器化搭建集群
解决8080端口被占用问题
windows10安全中心显示“修正未完成”
2022年全国职业技能大赛网络安全竞赛试题B模块自己解析思路(6)
AUTOMATION DAY07( Ansible Vault 、 普通用户使用ansible)
Django QuerySet.order_by() SQL注入漏洞复现
Basic use of Slurm
SSL证书部署后,为什么还是显示不安全?
Apache APISIX 默认密钥漏洞复现
buildroot setup dhcp
Threatless Technology-TVD Daily Vulnerability Intelligence-2022-7-22
树莓派设置静态IP地址
照片的35x45,300dpi怎么弄
Raspberry Pi set static IP address
Threatless Technology-TVD Daily Vulnerability Intelligence-2022-7-29
无胁科技-TVD每日漏洞情报-2022-7-29
(一)软件测试理论(0基础了解基础知识)
本地yum源搭建
SECURITY DAY06( iptables防火墙 、 filter表控制 、 扩展匹配、nat表典型应用 )
文本三剑客——sed 修改、替换