数组、数学运算

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"

说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

解法1：普通竖式
1）遍历 num2 每一位与 num1 进行相乘，将每一步的结果进行累加。
2）num2 除了第一位的其他位与 num1 运算的结果需要补0

public static String multiply(String num1, String num2) {

        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        String ret = "0";

        for (int i = num1.length() - 1; i >= 0; i--) {
            // 获取num1的每一位与num2的乘积, 需补0 (低位数在前)
            StringBuilder mulResult = new StringBuilder();
            int a = num1.charAt(i) - '0';
            int carry = 0;
            for (int j = num2.length() - 1; j >= 0; j--) {
                int b = num2.charAt(j) - '0';
                int res = a * b + carry;
                mulResult.append(res % 10);
                carry = res / 10;
            }
            if (carry > 0) {
                mulResult.append(carry);
            }
            // 补0, 因为低位数在前, 所以需要转换顺序
            mulResult = mulResult.reverse();
            for (int k = 0; k < num1.length() - 1 - i; k++) {
                mulResult.append("0");
            }

            // 相加
            ret = addString2(ret, mulResult.toString());
        }

        return ret;
    }

    public static String addString2(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;

        StringBuilder res = new StringBuilder();

        int carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = 0;

            int iTh = i >= 0 ? num1.charAt(i) - '0' : 0;
            int jTh = j >= 0 ? num2.charAt(j) - '0' : 0;
            sum = iTh + jTh + carry;

            res.append(sum % 10);
            carry = sum / 10;

            i--;
            j--;
        }
        if (carry > 0) {
            res.append(carry);
        }

        return res.reverse().toString();
    }

解法2：更底层的竖式
1）将解法1中的一位数乘以多位数的过程，进一步分解成，一位数分别与另一个数的每一位数相乘求和。如下图所示。
2）还有一个关键问题，如何将乘积叠加到 res 的正确位置。其实，细心观察之后就发现，num1[i] 和 num2[j] 的乘积对应的就是 res[i+j] 和 res[i+j+1] 这两个位置。
详细讲解：https://leetcode-cn.com/problems/multiply-strings/solution/gao-pin-mian-shi-xi-lie-zi-fu-chuan-cheng-fa-by-la/

public static String multiply2(String num1, String num2) {

        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        int[] results = new int[num1.length() + num2.length()];
        for (int i = num1.length() - 1; i >= 0; i--) {
            for (int j = num2.length() - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int H = i + j;
                int L = i + j + 1;
                int sum = mul + results[L];
                results[L] = sum % 10;
                results[H] += sum / 10;
            }
        }

        // results高位可能有0
        int s = 0;
        while (results[s] == 0) {
            s++;
        }

        StringBuilder result = new StringBuilder();
        for (; s < results.length; s++) {
            result.append(results[s]);
        }

        return result.toString();
    }

两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

初等数学解法

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;

        int carry = 0;

        while (l1 != null || l2 != null || carry != 0){
            int value1 = l1 == null ? 0 : l1.val;
            int value2 = l2 == null ? 0 : l2.val;
            int sum = value1 + value2 + carry;

            carry = sum / 10;
            int value = sum % 10;
            ListNode newNode = new ListNode(value);

            current.next = newNode;
            current = current.next;

            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
        }

        return dummyHead.next;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

最大交换

数学概念
从高位开始往低位遍历，对于当前的高位数字，在低位找到最大的数字，与其交换，如果这样的数字有多个，那么取最后一个。
以上的思想，正常实现下，时间复杂度是 $O(N^2)$ 。考虑对于当前的高位数字，如何能在O(1)的时间复杂度内找到低位中最大的数字。由O(1)复杂度立马可以联想到的数据结构有HashMap的get操作，Array的下标查找等。这个最大的数字无非是0-9中的一个，所以可以利用数组下标代表0-9，数组的值保存这个数字最后出现的位置。这样我们依次从高到低遍历这个数组即可得到这个最大的数组，数组的长度为10，就可以找到，属于O(1)复杂度。

public int maximumSwap(int num) {
        char[] chars = String.valueOf(num).toCharArray();

        // 存储index对应的数在chars中的最后出现下标
        int[] last = new int[10];
        for (int i = 0; i < chars.length; i++) {
            last[chars[i] - '0'] = i;
        }

        for (int i = 0; i < chars.length - 1; i++) {
            for(int d = 9; d > chars[i] - '0'; d--){
                if(last[d] > i){
                    char temp = chars[i];
                    chars[i] = chars[last[d]];
                    chars[last[d]] = temp;
                    return Integer.valueOf(new String(chars));
                }
            }
        }
        return num;
    }

两数相除

将除法转化为减法，循环相减，如果被除数和除数都是正数，代码如下
由于被除数和除数可能异号，加一个标志位进行判断
将被除数和除数都转成正数或负数进行计算，由于在Java中，当t=Integer.MIN_VALUE时（t取相反数依旧是它本身）此时可能存在越界问题，因此都用负数进行计算
此外，当dividend=Integer.MIN_VALUE，divisor=-1时，结果越界，将该情况特殊处理
以上算法时间复杂度为O(N)，超时；所以每次循环相减的时候，采用二分法的思想，dividend每次减去 $2^n$ 个divisor（尽可能多），同时reslut每次加 $2^n$

public int divide(int dividend, int divisor) {
        boolean sign = (dividend > 0) ^ (divisor > 0);
        int result = 0;
        // 两者都转化为负数计算, 避免正数的边界问题处理
        if (dividend > 0) {
            dividend = -dividend;
        }
        if (divisor > 0) {
            divisor = -divisor;
        }
        // 优化每次
        while (dividend <= divisor) {
            int temp_result = -1;
            int temp_divisor = divisor;
            while (dividend <= (temp_divisor << 1)) {
                if (temp_divisor <= (Integer.MIN_VALUE >> 1)) { // 避免除数越界，无限循环
                    break;
                }
                temp_result = temp_result << 1;
                temp_divisor = temp_divisor << 1;
            }
            dividend = dividend - temp_divisor;
            result += temp_result;
        }
        if (!sign) {
            if (result <= Integer.MIN_VALUE) {
                return Integer.MAX_VALUE; // 特殊处理 Integer.MIN_VALUE / -1 == Integer.MAX_VALUE 的情况
            }
            result = -result;
        }
        return result;
    }

分数到小数

核心：当余数重复出现时，可以结束循环；
细节：判断正负；注意边界问题：转换成long进行计算；

 public String fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) {
        return "0";
    }
    StringBuilder fraction = new StringBuilder();
    // If either one is negative (not both)
    if (numerator < 0 ^ denominator < 0) {
        fraction.append("-");
    }
    // Convert to Long or else abs(-2147483648) overflows
    long dividend = Math.abs(Long.valueOf(numerator));
    long divisor = Math.abs(Long.valueOf(denominator));
    fraction.append(String.valueOf(dividend / divisor));
    long remainder = dividend % divisor;
    if (remainder == 0) {
        return fraction.toString();
    }
    fraction.append(".");
    Map<Long, Integer> map = new HashMap<>();
    while (remainder != 0) {
        if (map.containsKey(remainder)) {
            fraction.insert(map.get(remainder), "(");
            fraction.append(")");
            break;
        }
        map.put(remainder, fraction.length());
        remainder *= 10;
        fraction.append(String.valueOf(remainder / divisor));
        remainder %= divisor;
    }
    return fraction.toString();
}

矩形面积

    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int sum = (C - A) * (D - B) + (G - E) * (H - F);

        if(A > G || C < E || D < F || B > H){
            return sum;
        }
        int red = (Math.min(C, G) - Math.max(A, E)) * (Math.min(D, H) - Math.max(B, F));
        return sum - red;
    }