Leetcode(2)
记:这几天内心十分焦虑,研究生的日子一天天过去,感觉毫无收获,每天刷个题来压压惊.
2.Add Two Number
·错误示例
·思路
写两个函数将一个数从List转化为int, 相加后再从int转化为List返回.
·伪代码:
1.构造两个函数分别代表: 一个数字从int转化为List和从List转化为int.
2.输入两个数L1和L由List表示,得I1=listConvertInt(L1)和L2=listConvertInt(L2);
3.返回L3 = intConvertList(L1 + L2);
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int i = listConvertInt(l1);
int j = listConvertInt(l2);
return intConvertList(j + i);
}
public int listConvertInt(ListNode l1) {
int i = 0;
int j = 1;
ListNode temp = l1;
while (temp != null) {
i += temp.val * j;
j *= 10;
temp = temp.next;
}
return i;
}
public ListNode intConvertList(int i) {
int temp = i;
int val;
ListNode head = new ListNode(0);
ListNode curr = head;
while (temp != 0) {
val = temp % 10;
temp /= 10;
ListNode next = new ListNode(val);
curr.next = next;
curr = next;
}
if (head.next != null) {
head = head.next;
}
return head;
}
}
·结果
报错的原因很简单,java的int是4个字节也就是其表示范围是:(-2^31,2^31-1);(-2147483648,2147483647)。该输入相加后得到的数已经为11位。long也不行。想着可以用Java的大数或者转化为String解决这个问题,感觉更麻烦了。只能用俩个链表模拟加法运算了.
·正确答案
·思路
设置一个carry代表当前位相加后的溢出进位,因为链表正好是反向的,刚刚好可以模拟两数从低位相加到高位的操作过程.
·伪代码:
1.将当前的结点初始化为返回列表的哑结点(头部空结点)
2.将当前进位carry初始化为0
3.将p和q分别初始化为l1和l2的头部
4.遍历列表l1和l2直至到达它们的尾端
·将x设置为结点p的值。如果p已经到达l1的末尾,则将其值设置为0
·将y设置为结点q的值。如果q已经到达l2的末尾,则将其值设置为0
·设定sum = x + y + carry
·更新进位的值,carry = sum\10
·创建一个数值为(sum mod 10)的新结点n,并将其设置为当前结点curr的下一节点,然后将当前结点curr前进到下一节点n
·同时,将p和q前进到下一个结点
5.检查carry = 1 是否成立,如果成立,则向返回列表追加一个含有数字1的新结点
6.返回哑节点的下一个结点
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
int carry = 0;
ListNode p = l1;
ListNode q = l2;
ListNode curr = head;
while(p != null || q != null){
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = x + y + carry;
carry = sum / 10;//后插法
curr.next = new ListNode(sum % 10);
curr = curr.next;
if(p != null) p = p.next;
if(q != null) q = q.next;
}
if(carry == 1){
curr.next = new ListNode(1);
}
return head.next;
}
·结果
执行用时 : 10 ms, 在Add Two Numbers的Java提交中击败了100.00% 的用户
内存消耗 : 47.1 MB, 在Add Two Numbers的Java提交中击败了20.73% 的用户
小结
该题解复杂度分析
·时间复杂度:O(max(m,n)),m,n分别代表l1和l2的长度
·空间复杂度:O(max(m,x)),新列表的长度最多为max(m.n)+1
根据官方的答案我又自己看着伪代码敲了一遍收获很多.
- 敲代码前最好要写伪代码
- 适当应用 ? 三元运算符来简化代码
- 参数最好别混用(其实只用head就够了不需要curr)
总结与思考
我觉得对于我来说不宜多刷宜精刷题。
1.考虑怎样能降低空间复杂度?
2.如果链表中的数字是按照顺序存储会怎样?