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();
}
网友评论