本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
989. 数组形式的整数加法
本题来自 LeetCode：989. 数组形式的整数加法[1]
题目描述
对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。
示例 1：
输入：A = [1,2,0,0], K = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234
示例 2：
输入：A = [2,7,4], K = 181
输出：[4,5,5]
解释：274 + 181 = 455
示例 3：
输入：A = [2,1,5], K = 806
输出：[1,0,2,1]
解释：215 + 806 = 1021
示例 4：
输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
输出：[1,0,0,0,0,0,0,0,0,0,0]
解释：9999999999 + 1 = 10000000000
题目分析
水题，就不分析了。
题目解答
class Solution {
public ListInteger addToArrayForm(int[] A, int K) {
ListInteger list = new LinkedList();
int carry = 0;
int i = A.length - 1;
while(carry != 0 || i = 0 || K != 0) {
int digitA = i 0 ? 0 : A[i --];
int digitK = 0;
if(K != 0) {
digitK = K % 10;
K /= 10;
}
carry += digitA + digitK;
list.add(0, carry % 10);
carry /= 10;
}
return list;
}
}
复杂度分析：
时间复杂度：
O(max(m, n))
空间复杂度：
O(max(m, n))
415. 字符串相加
本题来自 LeetCode：415. 字符串相加[2]
题目描述
给定两个字符串形式的非负整数 num1 和 num2 ，计算它们的和。
注意：
num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
题目分析
水题，就不分析了。
题目解答
class Solution {
private static final int ZERO = 0;
public String addStrings(String num1, String num2) {
StringBuilder sb = new StringBuilder();
int m = num1.length() - 1;
int n = num2.length() - 1;
int carry = 0;
while(carry != 0 || m = 0 || n = 0) {
int digit1 = m 0 ? ZERO : getDigit(num1, m --);
int digit2 = n 0 ? ZERO : getDigit(num2, n --);
carry += digit1 + digit2;
sb.append(carry % 10);
carry /= 10;
}
return sb.reverse().toString();
}
public int getDigit(String s, int index) {
return s.charAt(index) - '0';
}
}
复杂度分析：
时间复杂度：
O(max(m, n))
空间复杂度：
O(max(m, n))
58. 最后一个单词的长度
本题来自 LeetCode：58. 最后一个单词的长度[3]
题目描述
给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串，返回其最后一个单词的长度。
如果不存在最后一个单词，请返回 0 。
说明：一个单词是指由字母组成，但不包含任何空格的字符串。
示例:
输入: "Hello World"
输出: 5
解法一
题目分析
正序遍历。
题目解答
class Solution {
public int lengthOfLastWord(String s) {
int count = 0;
boolean isNew = true;
for(int i = 0; i s.length(); i ++) {
if(s.charAt(i) == ' ') {
isNew = true;
} else {
if(isNew) {
count = 1;
isNew = false;
} else {
count ++;
}
}
}
return count;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
解法二
题目分析
倒序遍历。
题目解答
class Solution {
public int lengthOfLastWord(String s) {
int count = 0;
for(int i = s.length() - 1; i = 0; i --) {
if(s.charAt(i) == ' ') {
if(count != 0) {
break;
}
} else {
count ++;
}
}
return count;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
参考资料
数组形式的整数加法: https://leetcode-cn.com/problems/add-to-array-form-of-integer
最后一个单词的长度: https://leetcode-cn.com/problems/length-of-last-word
原文始发于微信公众号（xiaogan的技术博客）：
