1.二进制求和（67-易）
给你两个二进制字符串，返回它们的和（用二进制表示）。输入为 非空 字符串且只包含数字 1 和 0。
示例：
输入: a = "11", b = "1" 输出: "100"
思路：
- 使用StringBuilder进行字符串拼接，最后结果不要忘记进行反转
- 对当前位a、b加和sum取余和取模分别计算当前位的拼接值和进位值carry
- 都遍历结束注意判断是否存在进位值
代码：
public String addBinary(String a, String b) { StringBuilder ans = new StringBuilder(); int carry = 0; for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) { int sum = carry; sum += i >= 0 ? a.charAt(i) - '0' : 0; sum += j >= 0 ? b.charAt(j) - '0' : 0; ans.append(sum % 2); carry = sum / 2; } ans.append(carry == 1 ? carry : ""); return ans.reverse().toString(); }
2.加一（66 - 易）
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。
示例：
输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123。
思路：注意进位分为下边三种情况：
- 末位无进位，则末位加一即可：因为末位无进位，前面也不可能产生进位，比如 45 => 46
- 末位有进位，但在中间位置进位停止：则需要找到进位的典型标志，即为当前位 %10后为 0，则前一位加 1，直到不为 0 为止，比如 499 => 500
- 末位有进位，并且一直进位到最前方导致结果多出一位：对于这种情况，需要在第 2 种情况遍历结束的基础上，进行单独处理，比如 999 => 1000
ps：模拟加法应该进行倒序遍历。
代码：
public int[] plusOne(int[] digits) { int len = digits.length; for(int i = len - 1; i >= 0; i--) { digits[i]++; digits[i] %= 10; if(digits[i]!=0) return digits; } digits = new int[len + 1]; digits[0] = 1; return digits; }
3.单链表加1（369-中）
题目描述：用一个 非空 单链表来表示一个非负整数，然后将这个整数加一。 你可以假设这个整数除了 0 本身，没有任何前导的 0。 这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。
示例：
输入: [1,2,3] 输出: [1,2,4]
思路：****类似数组+1，注意反转链表，一般有三种情况：
- 尾部不为9，直接+ 1；
- 尾部为9，进位
- 全部为9，需要新建一个链表头
还有一种快慢指针（双指针）的解法，比较巧妙：
- fast.val != 9，慢指针移动到当前快指针处
- fast.val = 9，慢指针原地不动
- 遍历结束，慢指针的值加一，慢指针后续所有节点值设置为0！
代码：
public class Solution003 { /** * 链表加一，正向输出 */ public static class ListNode { int val; ListNode next; public ListNode() { } public ListNode(int val) { this.val = val; } public ListNode(int val, ListNode next) { this.val = val; this.next = next; } } public static void main(String[] args) { // 测试 1->4->3->2->NULL ListNode node = new ListNode(9); node.next = new ListNode(9); // ListNode head = plusOne(node); ListNode head = plusOne_1(node); while (head != null) { System.out.print(head.val); head = head.next; } } public static ListNode plusOne(ListNode head) { ListNode reverseHead = reverse(head); ListNode cur = reverseHead; ListNode lastNode = null; int add = 0, c = 1; while (cur != null) { int sum = cur.val + add + c; add = c = 0; if (sum == 10) { cur.val = 0; add = 1; } else { cur.val = sum; } if (cur.next == null) { lastNode = cur; } cur = cur.next; } // 特判，需要新建头结点的情况 if (add > 0) { lastNode.next = new ListNode(add); } return reverse(reverseHead); } public static ListNode plusOne_1(ListNode head) { if (head == null) { return null; } ListNode slow = new ListNode(0); ListNode fast = head; slow.next = fast; while (fast != null) { if (fast.val != 9) { slow = fast; } fast = fast.next; } slow.val += 1; ListNode cur = slow.next; while (cur != null) { cur.val = 0; cur = cur.next; } return slow.next == head ? slow : head; } public static ListNode reverse(ListNode head) { if (head == null) { return null; } ListNode pre = null, next; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } }
4.链表求和（面试题 02.05）
给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。链表不能修改
进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912 进阶： 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 即7243 + 564 输出：7 -> 8 -> 0 -> 7 即7807
思路：对于原问题，常规解法，注意组织结果链表使用虚拟节点（结果要求逆序）。
进阶问题：
- 使用两个栈，倒序的取出链表的值
- 使用头插法组织新链表！（结果要求正序）
代码：原问题
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int sum, carry = 0; ListNode dummyHead = new ListNode(0); ListNode pre = dummyHead; while (l1 != null || l2 != null || carry > 0) { sum = carry; sum += l1 != null ? l1.val : 0; sum += l2 != null ? l2.val : 0; carry = sum / 10; pre.next = new ListNode(sum % 10); pre = pre.next; l1 = l1 != null ? l1.next : l1; l2 = l2 != null ? l2.next : l2; } return dummyHead.next; }
进阶问题：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Stack<Integer> stack1 = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); while (l1 != null) { stack1.push(l1.val); l1 = l1.next; } while (l2 != null) { stack2.push(l2.val); l2 = l2.next; } int carry = 0; ListNode head = null; while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) { int sum = carry; sum += (stack1.isEmpty() ) ? 0 : stack1.pop(); sum += (stack2.isEmpty() ) ? 0 : stack2.pop(); carry = sum / 10; ListNode node = new ListNode(sum % 10); // 头插节点构造链表 node.next = head; head = node; } return head; }
5.面试题 17.01. 不用加号的加法
设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。
思路：本题不能使用运算符进行求解，考察点是位运算：
- 运算：相同为0，不同为1。两个数异或，**ab 计算不考虑进位的二进制加法结果**
- &运算：两个都是1与的结果为1，否则为0。a&b 计算所有进位的位，左移（<<）再异或就是进一位的结果，以此类推
代码：
public int add(int a, int b) { int tmp; while (b != 0) { tmp = a ^ b; b = (a & b) << 1; a = tmp; } return a; }
6.字符串相加（415 - 易）
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。不能使用库函数等。
思路：与上面类似，模拟竖向加法，注意：StringBuilder可以显著提高效率。
代码：
public String addStrings(String num1, String num2) { StringBuilder ans = new StringBuilder(""); int i = num1.length() - 1, j = num2.length() - 1; int carry = 0, sum; while (i >= 0 || j >= 0 || carry != 0) { sum = carry; sum += i >= 0 ? num1.charAt(i) - '0' : 0; sum += j >= 0 ? num2.charAt(j) - '0' : 0; ans.append(sum % 10); carry = sum / 10; i--; j--; } return ans.reverse().toString(); }
6.字符串相减（面试题补充）
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的差。
注意：
- num1 和num2 都只会包含数字 0-9
- num1 和num2 都不包含任何前导零
- 你不能使用任何內建 BigInteger 库
思路：本题与上题唯一不同的是大数相减可能产生负数，分两步：
- 判断两个字符串的大小（对应大数）
- 模拟相减（根据大小），返回结果
注意细节：
- 相减过后，前导0要去除
- 对于字符串
"0"，不需加负号
ps：compareTo()方法依次比较两个字符串的大小，不同则返回对应字符的ascii码差值，停止；当一方比较完成则比较长度。
代码：
public class Solution001 { public static void main(String[] args) { // String num1 = "121", num2 = "120"; String num1 = "119", num2 = "123"; System.out.println(num1.compareTo(num2)); System.out.println(subString(num1, num2)); } public static String subString(String num1, String num2) { String ans = null; if (isLess(num1, num2)) { ans = sub(num2, num1); if (ans != "0") { StringBuilder sb = new StringBuilder(ans); sb.insert(0, '-'); ans = sb.toString(); } } else { ans = sub(num1, num2); } return ans; } // 比较两个数的大小 public static boolean isLess(String num1, String num2) { return num1.compareTo(num2) < 0; } public static String sub(String num1, String num2) { StringBuilder sb = new StringBuilder(); int i = num1.length() - 1, j = num2.length() - 1; int borrow = 0; while (i >= 0 || j >= 0) { int x = i >= 0 ? num1.charAt(i) - '0' : 0; int y = j >= 0 ? num2.charAt(j) - '0' : 0; sb.append((x - borrow - y + 10) % 10); borrow = x - borrow - y < 0 ? 1 : 0; i--; j--; } String tmp = sb.reverse().toString(); //删除前导0，注意边界是res.size()-1！！防止当res为"0000"时，删为""的清空 int start = 0; for (int pos = 0; pos < tmp.length(); pos++) { if (tmp.charAt(pos) != '0') { start = pos; break; } } return tmp.substring(start); } }
7.36进制加法（高频面试题）
36进制由0-9，a-z，共36个字符表示。
要求按照加法规则计算出任意两个36进制正整数的和，如1b + 2x = 48 （解释：47+105=152 )要求：不允许使用先将36进制数字整体转为10进制，相加后再转回为36进制的做法
思路：本题是上一题字符串相加的延伸，本题是36进制的大数字符串相加，输出结果为36进制数。
- getChar：拼接时，将数值转换为36进制字符
- getInt：将36进制字符转换为数值
代码：
public class Solution { public static void main(String[] args) { String a = "1b", b = "2x", c; // System.out.println(getInt('z')); // System.out.println(getChar(35)); c = add36Strings(a, b); System.out.println(c); } public static String add36Strings(String num1, String num2) { StringBuilder ans = new StringBuilder(); int i = num1.length() - 1, j = num2.length() - 1; int carry = 0, sum; while (i >= 0 || j >= 0 || carry != 0) { sum = carry; sum += i >= 0 ? getInt(num1.charAt(i)) : 0; sum += j >= 0 ? getInt(num2.charAt(j)) : 0; ans.append(getChar(sum % 36)); carry = sum / 36; i--; j--; } return ans.reverse().toString(); } public static int getInt(char c) { if (c >= '0' && c <= '9') { return c - '0'; } else { return c - 'a' + 10; } } public static char getChar(int a) { if (a <= 9) { return (char)(a + '0'); } else { return (char)(a - 10 + 'a'); } } }
7.补充：字符串相乘（43 - 中）
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的乘积。不能使用库函数等。
思路：模拟惩罚的计算过程，将被乘数与乘数的没一位相乘，然后调用两个字符串相加。
参考leetcode题解，在两数相乘时，乘数某位与被乘数某位相乘，与产生结果的位置的规律来完成。具体规律如下：
- 乘数 num1 位数为 M，被乘数 num2 位数为 N， num1 x num2 结果 ans 最大总位数为 M+N
- num1[i] x num2[j] 的结果为 tmp(位数为两位，"0x","xy"的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]。
算法流程
代码：
public String multiply(String num1, String num2) { if (num1.equals("0") || num2.equals("0")) { return "0"; } int m = num1.length(), n = num2.length(); int[] arr = new int[m + n]; for (int i = m - 1; i >= 0; i--) { int n1 = num1.charAt(i) - '0'; for (int j = n - 1; j >= 0; j--) { int n2 = num2.charAt(j) - '0'; int sum = arr[i + j + 1] + n1 * n2; arr[i + j + 1] = sum % 10; arr[i + j] += sum / 10; // 记录进位值 } } StringBuilder ans = new StringBuilder(); for (int i = 0; i < m + n; i++) { if (i == 0 && arr[i] == 0) continue; ans.append(arr[i]); } return ans.toString(); }
