Leetcode(2)

JAVA学习网 2019-04-02 14:18:02

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;
    }
}

·结果

1554035208266

​ 报错的原因很简单,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

根据官方的答案我又自己看着伪代码敲了一遍收获很多.

  1. 敲代码前最好要写伪代码
  2. 适当应用 ? 三元运算符来简化代码
  3. 参数最好别混用(其实只用head就够了不需要curr)

总结与思考

我觉得对于我来说不宜多刷宜精刷题。

1.考虑怎样能降低空间复杂度?

2.如果链表中的数字是按照顺序存储会怎样?

阅读(2635) 评论(0)