大数相减

import java.util.*;
import java.math.BigInteger; // 引入BigInteger

public class Solution {
    public String substring (String num1, String num2) {
        return new BigInteger(num1)
                .subtract(new BigInteger(num2))
                .toString();
    }
}

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param num1 string字符串
# @param num2 string字符串
# @return string字符串
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/ae4d84312e384a1fa100b613f93f3fe0?tpId=196&tqId=40449&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    借鉴：
        大神：摩羯卑弥呼
    算法：
        python投机做法：
            str(int(num1) - int(num2))
        常规做法：
            设num1, num2的长度分别为m, n
            1. 计算符号
                a) 如果m > n，结果为正。如："10" - "5"。
                b) 如果m == n 且 num1的字典序更大，结果也为正。如"4" - "3"。
                c) 否则，结果为负。如"5" - "10" 或者 "3" - "4"
            2. 问题转化为"大"数 - "小"数（a - b）
                双指针i, j逆序遍历a, b：
                    逐位相减，使用borrow记录借位。
    复杂度：
        时间复杂度：O(max(m , n))
        空间复杂度：O(1)
    """

    def substring(self, num1, num2):
        # write code here
        # return str(int(num1) - int(num2))
        def solve(a, b):
            i, j = len(a) - 1, len(b) - 1
            borrow, res = 0, ""
            while i >= 0 and j >= 0:
                num = int(a[i]) - int(b[j]) - borrow
                sum = (num + 10) % 10  # 借位处理，4 - 5 = 14 - 5 = 9，需要从高位借1
                borrow = 1 if num < 0 else 0
                res = str(sum) + res
                i -= 1
                j -= 1
            while i >= 0:
                if borrow == 0:  # 没有借位，此时等于a[:i + 1] - 0，无须计算，直接拼接结果
                    res = a[:i + 1] + res
                    break
                num = int(a[i]) - borrow
                sum = (num + 10) % 10
                borrow = 1 if num < 0 else 0
                res = str(sum) + res
                i -= 1

            idx, L = 0, len(res)
            while idx < L and res[idx] == "0":
                idx += 1
            return res[idx:]

        m, n, sign = len(num1), len(num2), ""
        if m > n&nbs***bsp;m == n and num1 > num2:
            res = solve(num1, num2)
        else:
            sign = "-"
            res = solve(num2, num1)
        return "0" if res == "" else sign + res

if __name__ == "__main__":
    sol = Solution()

    # num1, num2 = "100000000", "1000000000"

    # num1, num2 = "100000000", "1"

    # num1, num2 = "429018691214", "3278729808879"

    # num1, num2 = "4904818900", "42710101024938"

    num1, num2 = "1", "1"

    res = sol.substring(num1, num2)

    print res