概述
Add Two Numbers 难度为Medium，这一题目简单来说即给出两个序列，代表两个整数，模拟加法运算。
分析
这一题难度个人认为依然不大，即把正常加法的算式过程用程序表示。需要特殊处理的是进位这一操作。
正常的加法竖式运算，需要将最低位对其，然后开始从低位向高位计算。
再具体一些，考虑一个加法运算，两个数相加，一个数字长度为n，一个数字为m，m>n，那么，和的字符个数至多为m+1。
对于进位值的计算，其实就是将当前位数的值以及前期的进位值相加，除以10即为进位制。
这一解法可以在O(n)的时间复杂度上解决问题。
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
* 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) {
Map<Integer, Integer> lm1 = new HashMap<>();
Map<Integer, Integer> lm2 = new HashMap<>();
ListNode l = l1;
int idx = 0;
while (l != null) {
lm1.put(idx, l.val);
++idx;
l = l.next;
}
l = l2;
idx = 0;
while (l != null) {
lm2.put(idx, l.val);
++idx;
l = l.next;
}
Map<Integer, Integer> longer = (lm1.size() > lm2.size() ? lm1 : lm2);
Map<Integer, Integer> shorter = (lm1.size() <= lm2.size() ? lm1 : lm2);
int lengthGap = longer.size() - shorter.size();
ListNode result = new ListNode(0);
ListNode resultRef = result;
int carryVal = 0;
for (int i = 0; i < longer.size(); ++i) {
int nowVal = 0;
if (i >= shorter.size()) {
nowVal = longer.get(i) + carryVal;
} else {
nowVal = longer.get(i) + shorter.get(i) + carryVal;
}
carryVal = (nowVal / 10);
resultRef.val = (nowVal >= 10 ? nowVal % 10 : nowVal);
if (i != longer.size() - 1) {
resultRef.next = new ListNode(carryVal);
resultRef = resultRef.next;
} else {
if (carryVal > 0) {
resultRef.next = new ListNode(carryVal);
resultRef = resultRef.next;
}
resultRef.next = null;
}
}
return result;
}
}
|