Leetcode - Math Operations

Reimplementation of Math Operations

This post records math operation between numbers and stirngs reimplemented on Leetcode.

Number Math

Leetcode 29. Divide Two Integers

Bit Manipulation(Binary Base)

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend == INT_MIN && divisor == -1){
            return INT_MAX;
        }
        long long dvd = labs(dividend), dvs = labs(divisor), result = 0;
        int sign = (dividend > 0) ^ (divisor > 0) == 0 ? 1 : -1;
        while(dvd >= dvs){
            long long temp = dvs, mul = 1;
            while(temp << 1 <= dvd){
                temp <<= 1;
                mul <<= 1;
            }
            dvd -= temp;
            result += mul;
        } 
        return sign*result;
    }
};

Leetcode 50. Pow(x, n)

class Solution {
public:
    double myPow(double x, int n) {
        double num = 1;
        long long nn = n;
        if(nn < 0) nn = -nn;
        while(nn>0){
            if(nn%2==1){
                num = num * x;
                nn--;
            }
            else{
                x = x*x;
                nn/=2;
            }
        }
        if(n < 0){
            num = 1.0/num;
        }
        return num;
    }
};

String Math

Leetcode 67. Add Binary

class Solution {
public:
    string addBinary(string a, string b) {
        int la = a.size();
        int lb = b.size();
        int lmin = min(la,lb);
        int c = 0;
        string rts;
        for (int i=0; i<lmin; i++){
            int tmpres = a[la-i-1] - '0' + b[lb-i-1] - '0' + c;
            if (tmpres >= 2){
                c = 1;
                tmpres -= 2;
            }else{
                c = 0;
            }
            rts = to_string(tmpres) + rts;
        }
        if (lmin == lb){
            for(int i=0; i<la-lmin; i++){
                int tmpres = a[la-lmin-i-1] - '0'+c;
                if (tmpres >= 2){
                    c = 1;
                    tmpres -= 2;
                }else{
                    c = 0;
                }
                rts = to_string(tmpres) + rts;
            }
        }else{
            for(int i=0; i<lb-lmin; i++){
                int tmpres = b[lb-lmin-i-1] - '0'+c;
                if (tmpres >= 2){
                    c = 1;
                    tmpres -= 2;
                }else{
                    c = 0;
                }
                rts = to_string(tmpres) + rts;
            }
        }
        if (c == 1){
            rts = to_string(1) + rts;
        }
        return rts;
    }
};

Leetcode 43. Multiply Strings

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        
        vector<int> res(num1.size()+num2.size(), 0);
        
        for (int i = num1.size()-1; i >= 0; i--) {
            for (int j = num2.size()-1; j >= 0; j--) {
                res[i + j + 1] += (num1[i]-'0') * (num2[j]-'0');
                res[i + j] += res[i + j + 1] / 10;
                res[i + j + 1] %= 10;
            }
        }
        
        int i = 0;
        string ans = "";
        while (res[i] == 0) i++;
        while (i < res.size()) ans += to_string(res[i++]);
        
        return ans;
    }
};

Leetcode 2575. Find the Divisibility Array of a String

class Solution {
public:
    vector<int> divisibilityArray(string word, int m) {
        int n = word.size();
        vector<int> res(n, 0);
        long long cur = 0;
        for (int i = 0; i < n; ++i) {
            cur = (cur * 10 + word[i] - '0') % m;
            res[i] = cur == 0;
        }
        return res;
    }
};