大数题目

43.Multiply Strings
Given two non-negative integers num1 and num2 represented as strings,return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
给2个string，计算相乘的结果，其中不允许用内置的大数库或者将输入（string）转为整型。

思路：

假设是一个n位数与m位数相乘，则相乘的最大值为（10^n-1）*（10^m-1） 即10^(n+m)-10^n-10^m+1，显然最大值至多n+m位数
观察上图乘法运算过程。
得到以下代码。

class Solution {
public:
    string multiply(string num1,string num2) {
        string sum(num1.size()+num2.size(),'0');

        for(int i=num1.size()-1;0<=i;--i)
        {
            int carry=0;
            for(int j=num2.size()-1;0<=j;--j)
            {
                int tmp=(sum[i+j+1]-'0')+(num1[i]-'0')*(num2[j]-'0')+carry;
                sum[i+j+1]=tmp%10+'0';
                carry=tmp/10;
            }
            sum[i]+=carry;
        }
        size_t x=sum.find_first_not_of("0");

        if( string::npos!=x)
        {
            return sum.substr(x);
        }
        return "0" ;

    }
};

415 Add Strings
2个string相加。。贴代码更有意思了。。

class Solution {
public:
    string addStrings(string num1,string num2) {
        if (num1.size() < num2.size()) return addStrings(num2,num1);
        int carry = 0,i = num1.size() - 1,j = num2.size() - 1;
        for (; i >= 0 && (carry || j >= 0); i--,j--,carry /= 10) 
            num1[i] = (carry += num1[i] - '0' + (j >= 0 ? num2[j] - '0' : 0)) % 10 + '0';
        return (carry ? "1" : "") + num1;
    }
};

class Solution {
public:
    string addStrings(string num1,string num2) {
        int i=num1.size()-1;
        int j=num2.size()-1;
        string res("");
        int carry=0;
        while( i>=0 || j>=0 || carry)
        {
            long sum=0;
            if(i>=0) {sum += (num1[i]-'0');--i;}
            if(j>=0) {sum += (num2[j]-'0');--j;}
            sum+=carry;
            carry=sum/10;
            res=res+to_string(sum%10);
        }
        reverse(res.begin(),res.end());
        return res;

    }
};

66.Plus One
给了一个vector digits，里面记录了一个整型非负数的所有位，然后让你加1后会得到啥，让你返回一个vector
跟上面那题的思路没区别。。EASY级别。
我的代码。

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        vector<int> res;
        int carry=1;
        int i=digits.size()-1;
        if(i<0)
        {
            return vector<int>(1,1);
        }
        do
        {
            int tmp=digits[i]+carry;
            res.push_back(tmp%10);
            carry=tmp/10;
            --i;
        }while(i>=0);

        if(carry)
        {
            res.push_back(carry);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};