数字十进制位,四则运算编程技巧及力扣题目总结

Category： DSA

写在前面

最近力扣周赛出了很多关于数字位数的题, 顾名思义, 就是对一个大整数的每一个十进制位进行操作, 由于之前对这方面的内容不太熟悉, 真正写的时候就吃亏了. 下面写一下这方面的常用的一些技巧, 例如取出任意整数的每一位等等.

取出整数的每一位

通过对10取余或者整除, 可以从个位到最高位依次得到每一个位的值, 如下:

n = 12345
ans = []
while n:
    ans.append(n % 10)
    n //= 10
print(ans)
# [5, 4, 3, 2, 1]

上面的是数学方法, 速度比较快, 下面是一个基于字符串的方法, 虽然慢但是直观(我初刷lc时候钟爱这种方法)

n = 12345
s = str(n)
ans = [int(c) for c in s]
print(ans)
# [1, 2, 3, 4, 5]

这种技巧虽然方便, 但是在遇到要对每一位进行加减等操作的时候, 还是比较麻烦的, 因为要考虑进位借位的情况.

从各个位组成的数组(字符串)中还原整数

这个技巧是上面的技巧的逆操作, 比较直观, 直接取第$i$位然后乘以$10^i$之后相加即可.(这里用的下标为n-1-i是为了从低位到高位开始还原)

s = '12345'
ans = 0
for i in range(n := len(s)):
    ans += int(s[n - 1 - i]) * 10**i
print(ans, type(ans))
# 12345 <class 'int'>

当然不止这一种方法, 还有一种正向(高位到低位)遍历的方法:

s = '12345'
ans = 0
for c in s:
    ans = int(c) + ans * 10
print(ans, type(ans))
# 12345 <class 'int'>

这里比较推荐第二种, 因为很多字符串遍历用的都是正序.

LC-8: 字符串转整数

8. 字符串转换整数 (atoi);

class Solution {
public:
    int strToInt(string str) {
        string num{};
        bool flg{};
        for (auto c: str) {
            if (flg && !isdigit(c)) break;
            if (c == ' ') continue;
            if (c != '-' && c != '+' && !isdigit(c) && !flg) return 0;
            flg = true, num += c;
        }
        long long ans{};
        if (num == "") return 0;
        flg = false;
        for (int i{}; i < num.size(); ++i)
            if (num[i] == '-') flg = true;
            else if (num[i] == '+') flg = false;
            else {
                if (!flg && ans > INT_MAX) return INT_MAX;
                else if (flg && ans > INT_MAX) return INT_MIN;
                ans = ans * 10 + (num[i] - '0');
            }
        ans = (flg) ? -ans : ans;
        if (ans > INT_MAX) return INT_MAX;
        else if (ans < INT_MIN) return INT_MIN;
        return ans;
    }
};

反转每一个十进制位

这里的题型需要综合上面的两个技巧, 总体来看并不难.

7. 整数反转 - 力扣（LeetCode）;(上面两种方法均可)

class Solution:
    def reverse(self, x: int) -> int:
        tmp = []
        neg = False
        if x == 0:
            return x
        if x < 0:
            x = -x
            neg = True
        while x:
            tmp.append(x % 10)
            x //= 10
        dig = 0
        for i in tmp:
            dig = dig * 10 + i
        if neg:
            dig = -dig
        return dig if -2**31 <= dig <= 2**31 - 1 else 0

C++版(原地反转, 空间复杂度$O(1)$)

class Solution {
public:
    int reverse(int x) {
        long i{}, ans{}, num = x;
        bool neg = false;
        if (num < 0) num = -num, neg = true;
        while (num) i = num % 10, ans = 10l * ans + i, num /= 10;
        ans = neg ? -ans : ans;
        return ans > INT_MAX || ans < INT_MIN ? 0 : ans;
    }
};

采用数学做法会快一些, 而字符串相对简洁一些.

各位求和

258. 各位相加 - 力扣（LeetCode）;(可以模拟做, 不过有更简便的取余方法)

需要了解一个结论, 任何数的各位数相加之后只取个位数的话所得到的值一定是这个数对9取余得到的余数.

并且对于C++和Python, 两者的%运算符含义并不相同, 比较如下:

C++: 取余, 让商向0靠近取整
- $-10\%3=-1$, 也即$-10=-3\times3+(-1)$, 余数满足$0\leq -1 \leq 3$.
Python: 取模, 让商向无穷小靠近取整
- $-10\%3=2$, 也即$-10=-4\times3+2$, 余数满足$0\leq2\leq 3$.

[深入浅出C语言]理解取整、取余和取模;

所以, 针对上述结论, 不同语言用在这道题上的实现方法不一样:

Python:

class Solution:
    def addDigits(self, num: int) -> int:
        return (num - 1) % 9 + 1 if num else 0

而C/C++:

class Solution {
public:
    int addDigits(int num) {
        return (num - 1) % 9 + 1;
    }
};

逐位加法

链表存数

2. 两数相加;

简单直观, 又臭又长的烂代码:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto ans = new ListNode, cur(ans), h1(l1), h2(l2);
        int tmp, carry{};
        while (h1 && h2) {
            tmp = h1->val + h2->val + carry;
            if (tmp < 10)
                cur->next = new ListNode(tmp), carry = 0;
            else {
                cur->next = new ListNode(tmp - 10);
                carry = 1;
            }
            cur = cur->next;
            h1 = h1->next;
            h2 = h2->next;
        }
        while (h1) {
            tmp = h1->val + carry;
            if (tmp < 10)
                cur->next = new ListNode(tmp), carry = 0;
            else
                cur->next = new ListNode(tmp - 10), carry = 1;
            h1 = h1->next;
            cur = cur->next;
        }
        while (h2) {
            tmp = h2->val + carry;
            if (tmp < 10)
                cur->next = new ListNode(tmp), carry = 0;
            else
                cur->next = new ListNode(tmp - 10), carry = 1;
            h2 = h2->next;
            cur = cur->next;
        }
        if (carry) cur->next = new ListNode(carry);
        return ans->next;
    }
};

官方的代码: (有改动)

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto ans = new ListNode, cur(ans);
        int tmp, carry{}, n1, n2;
        while (l1 || l2) {
            n1 = l1 ? l1->val : 0;
            n2 = l2 ? l2->val : 0;
            tmp = n1 + n2 + carry;
            cur->next = new ListNode(tmp % 10);
            carry = tmp / 10;
            cur = cur->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        if (carry) cur->next = new ListNode(carry);
        return ans->next;
    }
};

直接加

415. 字符串相加 - 力扣（LeetCode）;(两数从低位到高位逐位相加, 模拟竖式计算, 需要注意进位补零)

思路和第二题一样.

class Solution {
public:
    string addStrings(string num1, string num2) {
        int m = num1.size(), n = num2.size();
        string ans;
        for (int i{m - 1}, j{n - 1}, carry{}; ~i || ~j || carry;) {
            int t1 = i >= 0 ? num1[i--] - '0' : 0;
            int t2 = j >= 0 ? num2[j--] - '0' : 0;
            int tmp = t1 + t2 + carry;
            ans += (tmp % 10 + '0');
            carry = tmp / 10;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

逐位乘法

43. 字符串相乘 - 力扣（LeetCode）;(需要用到乘法竖式计算的模拟);

做这个题之前先做一下字符串相加.

class Solution {
public:
    string addStrings(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 x = i >= 0 ? num1[i] - '0' : 0;
            int y = j >= 0 ? num2[j] - '0' : 0;
            int result = x + y + add;
            ans.push_back(result % 10 + '0');
            add = result / 10;
            --i, --j;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0"s;
        string ans{"0"s};
        int m = num1.size(), n = num2.size();
        for (int i{n - 1}; i >= 0; --i) {
            string cur{};
            for (int j = n - 1; j > i; j--) cur.push_back(0);

            int carry{}, y = num2[i] - '0';
            for (int j{m - 1}; j >= 0; --j) {
                int prod{(num1[j] - '0') * y + carry};
                cur.push_back(prod % 10);
                carry = prod / 10;
            }
            while (carry) cur.push_back(carry % 10), carry /= 10;

            reverse(cur.begin(), cur.end());
            for (auto &c : cur) c += '0';
            ans = addStrings(ans, cur);
        }
        return ans;
    }
};

利用vector改进版:

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0"s;
        int m = num1.size(), n = num2.size();
        int p{1}, N = m + n; // p: 乘完一步, 往前移动
        vector<int> ans(N);
        for (int i{n - 1}; i >= 0; --i) {
            vector<int> cur(N);
            int carry{}, y = num2[i] - '0', idx{N - p};
            for (int j{m - 1}; j >= 0; --j) {
                int prod{(num1[j] - '0') * y + carry};
                cur[idx--] = prod % 10, carry = prod / 10;
            }
            ++p;
            while (carry) cur[idx] = carry % 10, carry /= 10;
            // 合并入ans数组
            for (int i = N - 1, add{}; i >= 0; --i) {
                int tmp{ans[i] + cur[i] + add};
                ans[i] = tmp % 10;
                add = tmp / 10;
            }
        }
        int i{};
        while (ans[i] == 0) ++i; // 略过前导零
        string s{};              // 放字符串的结果
        while (i < N) s.push_back(ans[i++] + '0');
        return s;
    }
};

利用C-style数组改进版:

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0"s;
        int m = num1.size(), n = num2.size();
        int p{1}, N = m + n; // p: 乘完一步, 往前移动
        int ans[N], cur[N];
        memset(ans, 0, sizeof(ans));
        for (int i{n - 1}; i >= 0; --i) {
            memset(cur, 0, sizeof(cur));
            int carry{}, y = num2[i] - '0', idx{N - p};
            for (int j{m - 1}; j >= 0; --j) {
                int prod{(num1[j] - '0') * y + carry};
                cur[idx--] = prod % 10, carry = prod / 10;
            }
            ++p;
            while (carry) cur[idx] = carry % 10, carry /= 10;
            // 合并入ans数组
            for (int i = N - 1, add{}; i >= 0; --i) {
                int tmp{ans[i] + cur[i] + add};
                ans[i] = tmp % 10;
                add = tmp / 10;
            }
        }
        int i{};
        while (ans[i] == 0) ++i; // 略过前导零
        string s{};              // 放字符串的结果
        while (i < N) s.push_back(ans[i++] + '0');
        return s;
    }
};

更快的方法: (优化竖式)

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0"s;
        int m = num1.size(), n = num2.size();
        int N = m + n, arr[N];
        memset(arr, 0, sizeof(arr));

        for (int i = m - 1; i >= 0; i--) {
            int x = num1[i] - '0';
            for (int j = n - 1; j >= 0; j--)
                arr[i + j + 1] += x * (num2[j] - '0');
        }
        // 处理进位
        for (int i = N - 1; i > 0; i--) arr[i - 1] += arr[i] / 10, arr[i] %= 10;

        string ans;
        for (int i = arr[0] == 0; i < N; ++i) ans.push_back(arr[i] + '0');
        return ans;
    }
};

快速乘法

这里算是插一个题外话了, 但是不得不提, 因为下面的除法就要用了(限定不能使用乘法运算符). 思路就是下面的快速幂算法, 迭代思路需要点技巧.

int mul(int a, int b) {
    int ans{};
    bool sgn = (a > 0) ^ (b > 0);
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b) {
        if (b & 1) ans += a;
        a += a;
        b >>= 1;
    }
    return sgn ? -ans : ans;
}

递归:

int mul(int a, int b) {
    if (!a || !b) return 0;
    bool sgn = (a > 0) ^ (b > 0);
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    function<int(int, int)> f = [&](int a, int b) {
        if (b == 1) return a;
        int y{f(a, b >> 1)};
        return b % 2 ? y + a + y : y + y;
    };
    return sgn ? -f(a, b) : f(a, b);
}

快速幂

50. Pow(x, n);剑指 Offer 16. 数值的整数次方;

class Solution {
public:
    double myPow(double x, int n) {
        function<double(long)> f = [&](long n) {
            if (n == 0) return 1.;
            double y{f(n >> 1)};
            return n % 2 ? y * y * x : y * y;
        };
        if (n == 1) return x;
        long m = 1l * n;
        return n > 0 ? f(m) : 1 / f(-m);
    }
};

经典的迭代法(二进制表示计入贡献):

class Solution {
public:
    double myPow(double x, int n) {
        long m = 1l * n;
        bool isNeg{m < 0};
        m = isNeg ? -m : m;
        double ans{1}, y{x};
        while (m) ans *= (m & 1) ? y : 1, y *= y, m >>= 1;
        return isNeg ? 1 / ans : ans;
    }
};

逐位除法

29. 两数相除 - 力扣（LeetCode）;(终极boss)剑指 Offer II 001. 整数除法;

二分查找简单一些, 如下:(后来发现不满足题意说的不能使用long和乘法)

class Solution {
public:
    int divide(int dividend, int divisor) {
        bool flg1{}, flg2{};
        long dvd = dividend, dvs = divisor;
        if (dvd < 0) dvd = -dvd, flg1 = true;
        if (dvs < 0) dvs = -dvs, flg2 = true;

        long l{}, r = dvd, mid{};
        while (l <= r) {
            mid = (l + r) >> 1;
            if (dvs * mid <= dvd)
                l = mid + 1;
            else
                r = mid - 1;
        }
        long ans = (flg1 != flg2 ? 1 - l : l - 1);
        return ans > INT32_MAX || ans < INT32_MIN ? INT32_MAX : ans;
    }
};

满足题意的方法(用到了倍增乘, 有点像快速幂, 两倍两倍减去):

【宫水三叶】对限制条件的两种理解，以及两种倍增实现;

class Solution {
    constexpr static int LMT = INT_MIN >> 1; // half
public:
    int divide(int a, int b) {
        if (a == INT_MIN && b == -1)
            return INT_MAX; // Overflow
        bool isNeg = (a > 0) ^ (b > 0);
        if (a > 0)
            a = -a;
        if (b > 0)
            b = -b; // map to [INT_MIN, 0]
        int ans{}, c, d;
        while (a <= b) {
            c = b, d = -1;
            while (c >= LMT && c >= a - c)
                c += c, d += d;
            ans += d, a -= c;
        }
        return isNeg ? ans : -ans;
    }
};

上篇位运算常用技巧与力扣题型总结

下篇图论力扣题型总结