一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1400|回复: 4
收起左侧

[算法题] 请教一题addictive number (附代码)

[复制链接] |试试Instant~ |关注本帖
zzx04025 发表于 2016-1-11 03:49:59 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
请教大家一题addictive number, 我是用c++写的。然而不知道怎么贴代码, 就只能复制粘贴了,希望不要嫌弃==
问题主要是这个边界的处理,我本来写的是 i<num.size() 和 j<=num.size()-i, 但就一直是rumtime error,然后参考别人的答案改过来也不知道为什么, 求请教。
class Solution {
public:
    bool isAdditiveNumber(string num) {
        if (num.empty()) return false;
        for (int i=1; i<=num.size()/2; i++){
            for(int j=1; j<=(num.size()-i)/2; j++){
                if (dfs(num, i+j, num.substr(0,i), num.substr(i, j)))
                    return true;
            }
        }
        return false;
    }

    bool dfs(string num, int st, string first, string second){
        //if (st == num.size()) return true;
        //if ((first.size()>1 && first[0]=='0') || (second.size()>1 && second[0]=='0')) return false;
        unsigned long long f = stoi(first);
        unsigned long long s = stoi(second);
        if (to_string(f)!= first || to_string(s)!=second) return false;
        string sum = to_string(f + s);
        if (st+sum.size() > num.size()) return false;
        if (sum != num.substr(st, sum.size())) return false;
        if (sum.size() + st == num.size()) return true;
        return dfs (num, st+sum.size(), second, sum);
    }
};

stellari 发表于 2016-1-11 09:27:53 | 显示全部楼层
如果数字N是additive的,那表示N应该至少能够被分成3个数a, b, c,且c一定大于a。如果a超过了N的位数的一半,那说明c也一定会超过N的位数的一半,这是不可能的。所以a一定不会超过N的位数的一半。同理,c也一定大于b,所以b一定不会超过N除去a以后剩下部分的一半。

另外,这题题目叫“additive”,不是“addictive”,注意拼写。
回复 支持 反对

使用道具 举报

 楼主| zzx04025 发表于 2016-1-12 12:50:13 | 显示全部楼层
stellari 发表于 2016-1-11 09:27
如果数字N是additive的,那表示N应该至少能够被分成3个数a, b, c,且c一定大于a。如果a超过了N的位数的一半 ...

谢谢你的回复。 我能理解你的解释,可是为什么按照我的写就有runtime error啊==
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-16 12:43:36 | 显示全部楼层
楼主,原因是因为你用的是stoi啊

string to integer 所以返回值最大是2147483647,即便你把它赋值给一个u long long它也还是这么大啊。

你那个边界不改的话,很容易就搞出10几位的string,就超过stoi能处理的范围了

如果你改用stol,用你原来的边界是能ac的

string to long和string to int是两个不同的函数啊
回复 支持 反对

使用道具 举报

 楼主| zzx04025 发表于 2016-1-18 01:53:09 | 显示全部楼层
dietpepsi 发表于 2016-1-16 12:43
楼主,原因是因为你用的是stoi啊

string to integer 所以返回值最大是2147483647,即便你把它赋值给一个 ...

谢谢楼上的回复, 在你讲之前还不知道有stol这个函数==
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 21:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表