本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
66. 加一
本题来自 LeetCode：66. 加一[1]
题目描述
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
题目分析
本题比较简单，主要是判断是否需要进位，来创建正确数组的长度。
题目解答
class Solution {
public int[] plusOne(int[] digits) {
int n = digits.length;
int i = n - 1;
// 先判断出是否需要进位
while(i = 0 && digits[i] == 9) {
i --;
}
int[] result;
if(i 0) {
// 需要进位
result = new int[n + 1];
result[0] = 1;
} else {
// 不需要进位
result = new int[n];
int carry = 1;
for(int j = n - 1; j = 0; j --) {
carry = carry + digits[j];
result[j] = carry % 10;
carry /= 10;
}
}
return result;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(n)
67. 二进制求和
本题来自 LeetCode：67. 二进制求和[2]
题目描述
给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
题目分析
本题比较简单，不详细分析了。
题目解答
class Solution {
private static final int ZERO = 0;
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
int m = a.length() - 1;
int n = b.length() - 1;
int carry = 0;
while(carry != 0 || m = 0 || n = 0) {
int byteA = m 0 ? ZERO : getByte(a, m --);
int byteB = n 0 ? ZERO : getByte(b, n --);
carry += byteA + byteB;
sb.append(carry & 1);
carry = 1;
}
return sb.reverse().toString();
}
public int getByte(String s, int index) {
return s.charAt(index) - '0';
}
}
复杂度分析：
时间复杂度：
O(max(m, n))
空间复杂度：
O(max(m, n))
参考资料
原文始发于微信公众号（xiaogan的技术博客）：
