Algorithm Notes
  • Introduction
  • Search & Backtracking 搜索与回溯
    • Tree 与 BackTracking 的比较
    • Subsets, Combination 与 Permutation
    • Subsets & Combinations & Combination Sum
    • 枚举法
    • N 皇后 + 矩阵 Index Trick
    • Sudoku 数独 + 矩阵 Index Trick
    • Word Ladder I & II
    • Number of ways 类
    • DFS flood filling
    • Strobogrammatic 数生成
    • String 构造式 DFS + Backtracking
    • Word Pattern I & II
    • (G) Binary Watch
    • (FB) Phone Letter Combination
    • 常见搜索问题的迭代解法
  • String,字符串类
    • 多步翻转法
    • Substring 结构和遍历
    • Palindrome 问题
    • Palindrome Continued
    • String / LinkedList 大数运算
    • 序列化与压缩
    • 5/24 String 杂题
    • Knuth–Morris–Pratt 字符串匹配
    • Lempel–Ziv–Welch 字符串压缩算法
    • (G) Decode String
    • (G) UTF-8 Validation
  • Binary Tree,二叉树
    • 各种 Binary Tree 定义
    • LCA 类问题
    • 三序遍历,vertical order
    • Post order traversal 的应用
    • Min/Max/Balanced Depth
    • BST
    • 子树结构
    • Level Order traversal
    • Morris 遍历
    • 修改结构
    • 创建 / 序列化
    • 子树组合,BST query
    • 路径与路径和
    • NestedInteger 类
    • (FB) 从 Binary Tree Path 看如何递归转迭代
    • (FB) Binary Tree Path 比较路径大小
    • 比较好玩的 Binary Tree 概率题
  • Segment & Fenwick Tree,区间树
    • Segment Tree 基础操作
    • Segment Tree 的应用
    • Fenwick Tree (Binary Indexed Tree)
    • Range Sum Query 2D - Immutable
  • Union-Find,并查集
    • Union-Find,并查集基础
    • Union-Find, 并查集应用
  • Dynamic Programming, 动态规划
    • 6/20, 入门 House Robber
    • 7/12, Paint Fence / House
    • 6/24, 滚动数组
    • 6/24, 记忆化搜索
    • 6/24, 博弈类 DP
    • 博弈类DP, Flip Game
    • 6/25, 区间类DP
    • 6/27, subarray 划分类,股票
    • 7/2, 字符串类
    • Bomb Enemies
    • 8/2,背包问题
    • (G) Max Vacation
    • (11/4新增) AST 子树结构 DP
  • LinkedList,链表
    • 6/9, LinkedList,反转与删除
    • 6/11, LinkedList 杂题
    • (FB) 链表的递归与倒序打印
  • LinkedIn 面经,算法题
    • 6/17, LinkedIn 面经题
    • 6/28, LinkedIn 面经题
    • 7/6, LinkedIn 面经
    • Shortest Word Distance 类
    • DFA Parse Integer
  • Two Pointers,双指针
    • 3 Sum, 3 Sum Closest / Smaller, 4 Sum
    • 对撞型,灌水类
    • 对撞型,partition类
    • Wiggle Sort I & II
    • 双指针,窗口类
    • 双指针,窗口类
    • Heap,排序 matrix 中的 two pointers
  • Bit & Math,位运算与数学
    • Bit Manipulation,对于 '1' 位的操作
    • Math & Bit Manipulation, Power of X
    • 坐标系 & 数值计算类
    • Add Digits
    • 用 int 做字符串 signature
  • Interval 与 扫描线
    • Range Addition & LCS
    • 7/5, Interval 类,扫描线
  • Trie,字典树
    • 6/9, Trie, 字典树
  • 单调栈,LIS
    • 4/13 LIS
    • 栈, 单调栈
    • Largest Divisible Subset
  • Binary Search 类
    • Matrix Binary Search
    • Array Binary Search
    • Find Peak Element I & II
    • **Median of Two Sorted Arrays
  • Graph & Topological Sort,图 & 拓扑排序
    • 有向 / 无向 图的基本性质和操作
    • 拓扑排序, DFS 做法
    • 拓扑排序, BFS 做法
    • Course Schedule I & II
    • Alien Dictionary
    • Undirected Graph, BFS
    • Undirected Graph, DFS
    • 矩阵,BFS 最短距离探索
    • 欧拉回路,Hierholzer算法
    • AI, 迷宫生成
    • AI, 迷宫寻路算法
    • (G) Deep Copy 无向图成有向图
  • 括号与数学表达式的计算
  • Iterator 类
  • Majority Element,Moore's Voting
  • Matrix Inplace Operations
  • 常见数据结构设计
  • (G) Design / OOD 类算法题
  • 随机算法 & 数据结构
  • (FB) I/O Buffer
  • (FB) Simplify Path, H-Index I & II
  • (FB) Excel Sheet, Remove Duplicates
  • Integer 的构造,操作,序列化
  • Frequency 类问题
  • Missing Number 类,元素交换,数组环形跳转
  • 8/10, Google Tag
  • (FB) Rearrange String k Distance Apart
  • Abstract Algebra
    • Chap1 -- Why Abstract Algebra ?
    • Chap2 -- Operations
    • Chap3 -- The Definition of Groups
Powered by GitBook
On this page
  • Add Binary
  • Add Two Numbers
  • Multiply Strings

Was this helpful?

  1. String,字符串类

String / LinkedList 大数运算

PreviousPalindrome ContinuedNext序列化与压缩

Last updated 4 years ago

Was this helpful?

  • 当问题非常简单的时候,解题重点就从优化时间复杂度变成了优化代码简洁性。

我就不回头看自己那么挫的第一个 AC 答案了。。贴个论坛的(加上我自己的改动)里面有几个很巧妙的优化使代码变得简洁易懂。

这题代码简洁的重点在于处理“终止条件”,因为两个 string 很可能长度不一,也有可能两个 string 加完了之后还有进位没处理。

这段代码给出的答案是:

  • 输入长短不一就都放在 while loop 里,在读取字符时把短的做 padding.

  • While loop 里三个 'OR' 的条件保证了三种不同情况下都会继续读取,而其他两个自动 pad 0.

public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sum = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        while (i >= 0 || j >= 0 || carry == 1) {
            int digitA = i < 0 ? 0 : a.charAt(i--) - '0';
            int digitB = j < 0 ? 0 : b.charAt(j--) - '0';
            sum.append((digitA + digitB + carry) % 2);
            carry = (digitA + digitB + carry) / 2;
        }
        return sum.reverse().toString();
    }
}

上题完全一样的思路应用在链表上就是这样了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;

        int carry = 0;
        while(l1 != null || l2 != null || carry > 0){
            int num1 = (l1 == null) ? 0 : l1.val;
            int num2 = (l2 == null) ? 0 : l2.val;

            ListNode node = new ListNode((num1 + num2 + carry) % 10);
            carry = (num1 + num2 + carry) / 10;

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

            head.next = node;
            head = head.next;
        }

        return dummy.next;
    }
}

又进阶了, 这次是乘法,比加法复杂。下面的代码是我写的略为粗糙的第一版。

这题的时间复杂度不会低于 O(mn)O(mn)O(mn) ,因为毕竟每个 digit 都要和另外的 string 相乘一次。 所以把运算拆成两部分,一部分是 longer string 与单数位乘法,另一个是一个数位结束之后,两数相加。每一个数位上的结果乘出来之后要对应的做 0 padding,代表左位移。

提交时候遇到的一个 bug 是 "9133" x "0" 的情况,要记得在 multiply() 函数中如果输入是 0 就直接返回 "0",这是乘法和加法运算的一个不同之处,否则会返回“0000”.

public class Solution {
    public String multiply(String num1, String num2) {
        String longStr = (num1.length() > num2.length()) ? num1 : num2;
        String shortStr = (num1.length() > num2.length()) ? num2 : num1;

        String rst = "";

        int index = 0;
        while(shortStr.length() - 1 - index >= 0){
            int num = shortStr.charAt(shortStr.length() - 1 - index) - '0';
            String cur = multiplyOne(longStr, num);
            for(int i = index; i > 0; i--){
                cur += "0";
            }

            rst = addTwo(rst, cur);
            index ++;
        }

        return rst;
    }

    private String multiplyOne(String src, int num){
        if(num == 0) return "0";

        StringBuilder sb = new StringBuilder();
        int carry = 0;
        for(int i = src.length() - 1; i >= 0; i--){
            int digit = src.charAt(i) - '0';
            sb.append((digit * num + carry) % 10);
            carry = (digit * num + carry) / 10;
        }
        if(carry > 0) sb.append(carry);

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

    private String addTwo(String num1, String num2){
        StringBuilder sb = new StringBuilder();
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;
        while(i >= 0 || j >= 0 || carry > 0){
            int digit1 = (i >= 0) ? num1.charAt(i--) - '0': 0;
            int digit2 = (j >= 0) ? num2.charAt(j--) - '0': 0;
            sb.append((digit1 + digit2 + carry) % 10);
            carry = (digit1 + digit2 + carry) / 10;
        }

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

前面的做法对于每一个 digit 都做了一个乘法和加法操作,并没有特别好的利用到乘法的特点,中间操作过多而且生成了好多不必要的 String.

下面的解法是九章算法的,简洁高效。

  • 两个位数为 m 和 n 的数字相乘,乘积不会超过 m + n 位。

  • 乘法操作从右往左计算时,每次完成相加就确定了当前 digit.

  • 同一个 digit 多次修改,用 int[ ].

public class Solution {
    public String multiply(String num1, String num2) {
        if(num1 == null || num2 == null) return null;

        int maxLength = num1.length() + num2.length();
        int[] nums = new int[maxLength];
        int i, j, product, carry;

        for(i = num1.length() - 1; i >= 0; i--){
            // 中间部分相当于多位数乘一位数,起始 carry 为 0
            carry = 0;
            for(j = num2.length() - 1; j >= 0; j--){
                int a = num1.charAt(i) - '0';
                int b = num2.charAt(j) - '0';

                product = nums[i + j + 1] + a * b + carry;
                nums[i + j + 1] = product % 10;
                carry = product / 10;
            }
            // 循环结束,最左面为当前最高位数,如果 carry 还有就设过去
            nums[i + j + 1] = carry;
        }
        StringBuilder sb = new StringBuilder();
        int index = 0;
        while(index < maxLength - 1 && nums[index] == 0) index ++;
        while(index < maxLength) sb.append(nums[index++]);

        return sb.toString();
    }
}

Add Binary
Add Two Numbers
Multiply Strings