字符串相乘

給定兩個以字符串形式表示的非負整數(shù) num1 和 num2，返回 num1 和 num2 的乘積，它們的乘積也表示為字符串形式。

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

說明：
num1 和 num2 的長度小于110。
num1 和 num2 只包含數(shù)字 0-9。
num1 和 num2 均不以零開頭，除非是數(shù)字 0 本身。
不能使用任何標準庫的大數(shù)類型（比如 BigInteger）或直接將輸入轉(zhuǎn)換為整數(shù)來處理。

解法1：普通豎式
1）遍歷 num2 每一位與 num1 進行相乘，將每一步的結(jié)果進行累加。
2）num2 除了第一位的其他位與 num1 運算的結(jié)果需要 補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 (低位數(shù)在前)
            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, 因為低位數(shù)在前, 所以需要轉(zhuǎn)換順序
            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中的一位數(shù)乘以多位數(shù)的過程，進一步分解成，一位數(shù)分別與另一個數(shù)的每一位數(shù)相乘求和。如下圖所示。
2）還有一個關鍵問題，如何將乘積疊加到 res 的正確位置。其實，細心觀察之后就發(fā)現(xiàn)，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();
    }

兩數(shù)相加

給出兩個 非空 的鏈表用來表示兩個非負的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲的，并且它們的每個節(jié)點只能存儲 一位 數(shù)字。
如果，我們將這兩個數(shù)相加起來，則會返回一個新的鏈表來表示它們的和。
您可以假設除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭。

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

初等數(shù)學解法

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;
        }
    }

最大交換

數(shù)學概念
從高位開始往低位遍歷，對于當前的高位數(shù)字，在低位找到最大的數(shù)字，與其交換，如果這樣的數(shù)字有多個，那么取最后一個。
以上的思想，正常實現(xiàn)下，時間復雜度是。考慮對于當前的高位數(shù)字，如何能在O(1)的時間復雜度內(nèi)找到低位中最大的數(shù)字。由O(1)復雜度立馬可以聯(lián)想到的數(shù)據(jù)結(jié)構(gòu)有HashMap的get操作，Array的下標查找等。這個最大的數(shù)字無非是0-9中的一個，所以可以利用數(shù)組下標代表0-9，數(shù)組的值保存這個數(shù)字最后出現(xiàn)的位置。這樣我們依次從高到低遍歷這個數(shù)組即可得到這個最大的數(shù)組，數(shù)組的長度為10，就可以找到，屬于O(1)復雜度。

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

        // 存儲index對應的數(shù)在chars中的最后出現(xiàn)下標
        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;
    }

兩數(shù)相除

• 將除法轉(zhuǎn)化為減法，循環(huán)相減，如果被除數(shù)和除數(shù)都是正數(shù)，代碼如下
• 由于被除數(shù)和除數(shù)可能異號，加一個標志位進行判斷
• 將被除數(shù)和除數(shù)都轉(zhuǎn)成正數(shù)或負數(shù)進行計算，由于在Java中，當t=Integer.MIN_VALUE時（t取相反數(shù)依舊是它本身）此時可能存在越界問題，因此都用負數(shù)進行計算
• 此外，當dividend=Integer.MIN_VALUE，divisor=-1時，結(jié)果越界，將該情況特殊處理
• 以上算法時間復雜度為O(N)，超時；所以每次循環(huán)相減的時候，采用二分法的思想，dividend每次減去個divisor（盡可能多），同時reslut每次加

public int divide(int dividend, int divisor) {
        boolean sign = (dividend > 0) ^ (divisor > 0);
        int result = 0;
        // 兩者都轉(zhuǎn)化為負數(shù)計算, 避免正數(shù)的邊界問題處理
        if (dividend > 0) {
            dividend = -dividend;
        }
        if (divisor > 0) {
            divisor = -divisor;
        }
        // 優(yōu)化每次
        while (dividend <= divisor) {
            int temp_result = -1;
            int temp_divisor = divisor;
            while (dividend <= (temp_divisor << 1)) {
                if (temp_divisor <= (Integer.MIN_VALUE >> 1)) { // 避免除數(shù)越界，無限循環(huán)
                    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;
    }

分數(shù)到小數(shù)

• 核心：當余數(shù)重復出現(xiàn)時，可以結(jié)束循環(huán)；
• 細節(jié)：判斷正負；注意邊界問題：轉(zhuǎn)換成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;
    }