累加数

累加数

 


 

变量简洁正确完整思路
dfs,全局ok判断
fori作为第二个开头,forj作为第二个结尾,计算后从k=j+1开始找,
<add就继续找,=add dfs,>addreturn,以下是未处理溢出的初步代码,防止前置0用了很多continue
class Solution {
public:
    bool ok=false;
    bool isAdditiveNumber(string num) {
        int n=num.size();
        for(int i=1;i<n;i++){
            if(i-1>0&&num[0]==0)continue;
            int num1=stoi(num.substr(0,i));
            for(int j=i;j<n;j++){
                if(j>i&&num[i]==0)continue;
                int num2=stoi(num.substr(i,j-i+1));
                //cout<<num1<<‘ ‘<<num2<<endl;
                for(int k=j+1;k<n;k++){
                    if(k>j+1&&num[j+1]==0)continue;
                    int num3=stoi(num.substr(j+1,k-j));
                    //cout<<num1<<‘ ‘<<num2<<‘ ‘<<num3<<endl;
                    if(num1+num2==num3){
                        dfs(num2,num3,k,num);
                    }else if(num1+num2<num3)break;
                }
            }
        }
        return ok;
    }
    void dfs(int num1,int num2,int end,string num){
        if(end==num.size()-1){
            ok=true;
            return;
        }
        if(ok)return;
        for(int i=end+1;i<num.size();i++){
            if(i>end+1&&num[end+1]==0)continue;
            int num3=stoi(num.substr(end+1,i-end));
            //cout<<num1<<‘ ‘<<num2<<‘ ‘<<num3<<‘ ‘<<end<<endl;
            if(num1+num2==num3){
                dfs(num2,num3,i,num);
            }else if(num1+num2<num3)break;
        }
    }
};

处理溢出方法:数字用字符串表示,定义比较字符串大小的函数
class Solution {
public:
    bool ok=false;
    bool isAdditiveNumber(string num) {
        int n=num.size();
        for(int i=1;i<n;i++){
            if(i-1>0&&num[0]==0)continue;
            string num1=num.substr(0,i);
            //int num1=stoi(num.substr(0,i));
            for(int j=i;j<n;j++){
                if(j>i&&num[i]==0)continue;
                string num2=num.substr(i,j-i+1);
                //int num2=stoi(num.substr(i,j-i+1));
                //cout<<num1<<‘ ‘<<num2<<endl;
                for(int k=j+1;k<n;k++){
                    if(k>j+1&&num[j+1]==0)continue;
                    string num3=num.substr(j+1,k-j);
                    //int num3=stoi(num.substr(j+1,k-j));
                    //cout<<num1<<‘ ‘<<num2<<‘ ‘<<num3<<endl;
                    string tmp=addString(num1,num2);
                    if(tmp==num3){
                        dfs(num2,num3,k,num);
                    }else if(tmp<num3)break;
                }
            }
        }
        return ok;
    }
    void dfs(string num1,string num2,int end,string num){
        if(end==num.size()-1){
            ok=true;
            return;
        }
        if(ok)return;
        for(int i=end+1;i<num.size();i++){
            if(i>end+1&&num[end+1]==0)continue;
            string num3=num.substr(end+1,i-end);
            //int num3=stoi(num.substr(end+1,i-end));
            //cout<<num1<<‘ ‘<<num2<<‘ ‘<<num3<<‘ ‘<<end<<endl;
            string tmp=addString(num1,num2);
            if(tmp==num3){
                dfs(num2,num3,i,num);
            }else if(tmp<num3)break;
        }
    }
    string addString(string num1,string num2){
        int i=num1.size()-1,j=num2.size()-1,add=0;
        string ans;
        while(i>=0||j>=0||add>0){
            int a=i>=0?num1[i]-0:0;
            int b=j>=0?num2[j]-0:0;
            int tmp=a+b+add;
            ans.push_back(tmp%10+0);
            add=tmp/10;
            i--,j--;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

 

累加数

上一篇:Codeforces Round #737 (Div. 2)-C


下一篇:L1-012 计算指数