[LeetCode] 415 Add Strings && 67 Add Binary && 43 Multiply Strings

这些题目是高精度加法和高精度乘法相关的，复习了一下就做了，没想到难住自己的是C++里面string的用法。

原题地址：

415 Add Strings：https://leetcode.com/problems/add-strings/description/

67 Add Binary： https://leetcode.com/problems/add-binary/description/

43 Multiply Strings：https://leetcode.com/problems/multiply-strings/description/

题目&解法：

1.Add String

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

The length of both num1 and num2 is < 5100.
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.

高精度加法其实很简单，先把传入的string颠倒一下，然后相加，遇到大于10的进位。自己的写法有点复杂，多了许多无谓的if判断条件，因此在网上找到了一份非常简洁的代码，不得不说从中学到了许多，比如len1和len2的使用，while处||，循环里面再判断i是否分别小于len1,len2，比我原来的代码不知道高到哪儿去了；还有用了flag来储存进位，还有val变量的使用：

class Solution {

public:

string reverse(string num) {

    int len = num.size();

    for (int i = ; i <= (len - ) / ; i++) {

        char temp = num[i];

        num[i] = num[len - i - ];

        num[len - i - ] = temp;

    }

    return num;

}

string addStrings(string num1, string num2) {

    string ans;

    num1 = reverse(num1);

    num2 = reverse(num2);

    int i = , len1 = num1.size(), len2 = num2.size(), flag = ;

    while (i < len1 || i < len2) {

        int val = ;

        if (i < len1) val += num1[i] - '';

        if (i < len2) val += num2[i] - '';

        ans += (val + flag) %  + '';

        flag = (val + flag) / ;

        i++;

    }

    if (flag) ans += '';

    ans = reverse(ans);

    return ans;

}

};

值得注意的是，其实reverse函数是不需要自己写的，可以直接调用：

void reverse(s.begin(), s.end());

2.Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

这里其实用的就是高精度加法的思想，直接把上面的代码中的10改为2就行了。

3.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.

这题就是高精度乘法了，具体的原理省略掉，说一些我认为以后复习时，比较容易让我重新记起的点：

（1）要先对传入的字符串进行颠倒（这个高精度加法和乘法都一样的）

（2）要明白，num1[i]与num2[j]相乘，影响的肯定是结果的i+j位（先不管进位）（都从第0位算起）

（3）进位要先处理当前位的下一位，再处理当前位，像这样：

a[i + j + ] += a[i + j] / ;

a[i + j] %= ;

（4）我们不知道结果究竟有几位，因此要进行判断，以前我的做法是先循环一遍，遇到为0的就break；现在想到一种简单一点的方法：

int flag = a[num1.size() + num2.size() - ];

int len = flag ==  ? num1.size() + num2.size() -  : num1.size() + num2.size();

for (int i = len - ; i >= ; i--) {

    ans += a[i] + '';

}

完整代码如下：

class Solution {

public:

   string reverse(string num) {

    int len = num.size();

    for (int i = ; i <= (len - ) / ; i++) {

        char temp = num[i];

        num[i] = num[len - i - ];

        num[len - i - ] = temp;

    }

    return num;

}

string multiply(string num1, string num2) {

    string ans = "";

    if (num1 == "" || num2 == "") {

        return "";

    }

    int a[] = {};

    num1 = reverse(num1);

    num2 = reverse(num2);

    for (int i = ; i < num1.size(); i++) {

        for (int j = ; j < num2.size(); j++) {

            a[i + j] += (num1[i] - '') * (num2[j] - '');

            a[i + j + ] += a[i + j] / ;

            a[i + j] %= ;

        }

    }

    int flag = a[num1.size() + num2.size() - ];

    int len = flag ==  ? num1.size() + num2.size() -  : num1.size() + num2.size();

    for (int i = len - ; i >= ; i--) {

        ans += a[i] + '';

    }

    return ans;

}

};

这里最重要的是那个双层循环的地方，实在不能理解这个算法的话，记住那个地方吧。。。。。。

巴特西

[LeetCode] 415 Add Strings && 67 Add Binary && 43 Multiply Strings

最新文章

热门文章