字符串相加「变题」

415. 字符串相加

public String addStrings(String num1, String num2) {
    StringBuffer sb = new StringBuffer();
    int i = num1.length() - 1, j = num2.length() - 1;
    int s = 0;
    while (i >= 0 || j >= 0) {
        int sum = s;
        if (i >= 0) sum += num1.charAt(i--) - '0';
        if (j >= 0) sum += num2.charAt(j--) - '0';
        s = sum / 10;
        sb.append(sum % 10);
    }
    if (s != 0) sb.append(s);
    return sb.reverse().toString();
}

变题一：逆序的链表相加

题目详情可见 两数相加

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy, p1 = l1, p2 = l2;
    int s = 0;
    while (p1 != null || p2 != null) {
        int sum = s;
        if (p1 != null) {
            sum += p1.val;
            p1 = p1.next;
        }
        if (p2 != null) {
            sum += p2.val;
            p2 = p2.next;
        }
        s = sum / 10;
        p.next = new ListNode(sum % 10);
        p = p.next;
    }
    if (s != 0) p.next = new ListNode(s);
    return dummy.next;
}

变题二：正序的链表相加

题目详情可见 两数相加 II

// 先反转，再相加
// 时间复杂度 : O(max(m, n))
// 空间复杂度 : O(1)
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    l1 = reverse(l1);
    l2 = reverse(l2);
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy, p1 = l1, p2 = l2;
    int s = 0;
    while (p1 != null || p2 != null) {
        int sum = s;
        if (p1 != null) {
            sum += p1.val;
            p1 = p1.next;
        }
        if (p2 != null) {
            sum += p2.val;
            p2 = p2.next;
        }
        s = sum / 10;
        p.next = new ListNode(sum % 10);
        p = p.next;
    }
    if (s != 0) p.next = new ListNode(s);
    return reverse(dummy.next);
}
private ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

// 借助栈
// 时间复杂度 : O(max(m, n))
// 空间复杂度 : O(m + n)
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Deque<ListNode> q1 = new ArrayDeque<>();
    Deque<ListNode> q2 = new ArrayDeque<>();
    while (l1 != null) {
        q1.push(l1);
        l1 = l1.next;
    }
    while (l2 != null) {
        q2.push(l2);
        l2 = l2.next;
    }
    ListNode dummy = new ListNode(-1);
    int s = 0;
    while (!q1.isEmpty() || !q2.isEmpty()) {
        int sum = s;
        if (!q1.isEmpty()) sum += q1.poll().val;
        if (!q2.isEmpty()) sum += q2.poll().val;
        s = sum / 10;
        // 头插法
        ListNode node = new ListNode(sum % 10);
        node.next = dummy.next;
        dummy.next = node;
    }
    if (s != 0) {
        ListNode node = new ListNode(s);
        node.next = dummy.next;
        dummy.next = node;
    }
    return dummy.next;
}

变题三：大数相减

题目详情可见 大数相减

import java.util.*;
public class Solution {
    public String substring (String num1, String num2) {
        // 先判断结果的正负，始终转化成大减小
        boolean negative = false;
        if (compare(num1, num2)) {
            negative = true;
            String t = num1;
            num1 = num2;
            num2 = t;
        }
        int[] res = new int[num1.length()];
        int i = num1.length() - 1, j = num2.length() - 1;
        int s = 0; // 借位
        while (i >= 0 || j >= 0) {
            int sum = -s;
            if (i >= 0) sum += num1.charAt(i) - '0';
            if (j >= 0) sum -= num2.charAt(j--) - '0';
            if (sum < 0) {
                // 需要借位
                s = 1;
                sum += 10;
            } else s = 0;
            res[i--] = sum;
        }
        StringBuffer sb = new StringBuffer();
        for (i = 0; i < num1.length(); i++) {
            if (res[i] == 0 && sb.length() == 0) continue;
            sb.append(res[i]);
        }
        if (sb.length() == 0) sb.append(0);
        return (negative ? "-" : "") + sb.toString();
    }
    // 判断两个字符串的小大，s1 小于 s2 返回 true，否则返回 false
    private boolean compare(String s1, String s2) {
        int n1 = s1.length(), n2 = s2.length();
        if (n1 == n2) return s1.compareTo(s2) < 0;
        return n1 < n2 ? true : false;
    }
}

变题四：大数相乘

题目详情可见 字符串相乘

public String multiply(String num1, String num2) {
    if (num1.equals("0") || num2.equals("0")) return "0";
    int n1 = num1.length(), n2 = num2.length();
    int[] res = new int[n1 + n2];
    for (int i = n1 - 1; i >= 0; i--) {
        int x = num1.charAt(i) - '0';
        for (int j = n2 - 1; j >= 0; j--) {
            int y = num2.charAt(j) - '0';
            int sum = res[i + j + 1] + x * y;
            res[i + j + 1] = sum % 10;
            res[i + j] += sum / 10;
        }
    }
    StringBuffer sb = new StringBuffer();
    for (int i = 0; i < n1 + n2; i++) {
        if (res[i] == 0 && i == 0) continue;
        sb.append(res[i]); 
    }
    return sb.toString();
}

变题五：大数相除

题目详情可见 大数除法

这个题的思路可以参考题目 两数相除

public class Test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String A = sc.nextLine();
        String B = sc.nextLine();
        if (A.equals("0") || B.equals("0")) {
            System.out.println("0");
            return ;
        }
        String ans = divide(A, B);
        String mod = minus(A, multiply(ans, B));
        System.out.println(ans);
        System.out.println(mod);
    }
    // 除
    private static String divide(String a, String b) {
        if (compare(a, b)) return "0";
        String ans = "1", t = b;
        while (compare(plus(t, t), a)) {
            t = plus(t, t);
            ans = plus(ans, ans);
        }
        return plus(ans, divide(minus(a, t), b));
    }
    // 加
    private static String plus(String a, String b) {
        StringBuffer sb = new StringBuffer();
        int i = a.length() - 1, j = b.length() - 1;
        int s = 0;
        while (i >= 0 || j >= 0) {
            int sum = s;
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            s = sum / 10;
            sb.append(sum % 10);
        }
        if (s != 0) sb.append(s);
        return sb.reverse().toString();
    }
    // 减
    private static String minus(String a, String b) {
        int n = a.length();
        int[] res = new int[n];
        int i = n - 1, j = b.length() - 1;
        int s = 0;
        while (i >= 0 || j >= 0) {
            int sum = -s;
            if (i >= 0) sum += a.charAt(i) - '0';
            if (j >= 0) sum -= b.charAt(j--) - '0';
            if (sum < 0) {
                s = 1;
                sum += 10;
            } else s = 0;
            res[i--] = sum;
        }
        StringBuffer sb = new StringBuffer();
        for (i = 0; i < n; i++) {
            if (res[i] == 0 && sb.length() == 0) continue;
            sb.append(res[i]);
        }
        if (sb.length() == 0) return "0";
        return sb.toString();
    }
    // 乘
    private static String multiply(String a, String b) {
        int n1 = a.length(), n2 = b.length();
        int[] res = new int[n1 + n2];
        for (int i = n1 - 1; i >= 0; i--) {
            int x = a.charAt(i) - '0';
            for (int j = n2 - 1; j >= 0; j--) {
                int y = b.charAt(j) - '0';
                int sum = res[i + j + 1] + x * y;
                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;
            }
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n1 + n2; i++) {
            if (i == 0 && res[i] == 0) continue;
            sb.append(res[i]);
        }
        return sb.toString();
    }

    private static boolean compare(String a, String b) {
        int n1 = a.length(), n2 = b.length();
        if (n1 == n2) return a.compareTo(b) < 0;
        return n1 < n2;
    }
}