LeetCode_Subject2

lpc0828

基础很差这道题折腾了这么久 我相信后面的题目会做的越来越好！！！！！！！！
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
下面这个是给的链表类

[Java] 纯文本查看 复制代码

public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

[color=rgba(var(--grey-9-rgb),1)]输入：[color=rgba(var(--grey-9-rgb),1)]l1 = [2,4,3], l2 = [5,6,4]
[color=rgba(var(--grey-9-rgb),1)]输出：[color=rgba(var(--grey-9-rgb),1)][7,0,8]
[color=rgba(var(--grey-9-rgb),1)]解释：[color=rgba(var(--grey-9-rgb),1)]342 + 465 = 807.
[color=rgba(var(--grey-9-rgb),1)]

[color=rgba(var(--grey-9-rgb),1)]题目的大概意思就是两个倒序链表相加，结果也得是倒序的
[color=rgba(var(--grey-9-rgb),1)]

基础较差 啪！上来就是一个循环！很快啊！下面是车祸现场！

[Java] 纯文本查看 复制代码

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        boolean a = true;
        boolean b = true;
        boolean c = true;
        ListNode listNode1 = l1;
        ListNode listNode2 = l2;
        ListNode listNode3 = new ListNode();
        StringBuffer buffer1 = new StringBuffer();
        StringBuffer buffer2 = new StringBuffer();
        while (a) {
            buffer1.append(listNode1.val);
            listNode1 = listNode1.next;
            if (listNode1 == null || listNode1.next == null) {
                buffer1.append(listNode1 == null ? "" : listNode1.val);
                a = false;
            }
        }

        while (b) {
            buffer2.append(listNode2.val);
            listNode2 = listNode2.next;
            if (listNode2 == null || listNode2.next == null) {
                buffer2.append(listNode2 == null ? "" : listNode2.val);
                b = false;
            }
        }
        Long result = Long.parseLong(buffer1.reverse().toString()) + Long.parseLong(buffer2.reverse().toString());
        String s = new StringBuffer(result.toString()).reverse().toString();
        List<String> list = Stream.iterate(0, n -> ++n).limit(s.length())
                .map(n -> "" + s.charAt(n))
                .collect(Collectors.toList());
        List<Integer> collect = list.stream().map(o -> {
            return Integer.parseInt(o);
        }).collect(Collectors.toList());

        return test(collect, listNode3);
    }

    public static ListNode test(List<Integer> collect, ListNode listNode) {
        Integer integer = collect.get(0);
        if (integer != null) {
            ListNode listNode1 = new ListNode();
            collect.remove(0);
            if (collect.size() == 0) {
                listNode.val = integer;
                return listNode;
            }
            listNode.val = integer;
            listNode.next = test(collect, listNode1);
            return listNode;
        }
        return null;
    }

先把它俩循环出来 挨个把数字取出来 然后计算总和 再把它们包装到链表类里面 完美！但是！
提示：
每个链表中的节点数在范围 [1, 100] 内[color=rgba(var(--grey-7-rgb),1)]0 <= Node.val <= 9题目数据保证列表表示的数字不含前导零
题目没有这么笨尽管我用了long double 也没法装的下这么大的数字

咨询了一位好大哥，用递归试试
什么是递归呢

[Java] 纯文本查看 复制代码

public static ListNode l11 = new ListNode(666);

    public static ListNode test1(ListNode l1, ListNode l2, int 进位) {
        if (l1.next != null || l2.next != null) {
            // 每两位和进位的和
            int sum = l1.val + l2.val + 进位;
            // 十 分离个位十位 是要进位的值
            int 进 = sum / 10 % 10;
            // 个 是当前对象的值
            int a = sum % 10;
            test2(l11, a);
            test1(l1.next, l2.next, 进);
        } else {
            // 最后一位的和
            int sum = l1.val + l2.val + 进位;
            // 十 分离个位十位
            int ten = sum / 10 % 10;
            //个
            int a = sum % 10;
            // 最后一个对象
            if (ten == 0) {
                test2(l11, a);
            } else {
                test2(l11, a);
                test2(l11, ten);
            }

        }
        return l11;
    }

    public static void test2(ListNode l1, int a) {
        if (l1.next != null) {
            test2(l1.next, a);
        } else {
            // 找到它的最后一位 放进去
            if (l11.val == 666) {
                l11 = new ListNode(a);
            } else {
                l1.next = new ListNode(a);
            }

        }
    }

用的办法也是很笨 但是没法通过官方LeetCode的提交校验，我现在都不知道为什么

用它的测试用例测试代码 结果是对的 用了它的提交校验  就错了
莫得办法搞不出来，我去看了官方的代码，其实没必要用这么大阵仗 还用递归 while循环就可以实现了

[Java] 纯文本查看 复制代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }

申明两个链表对象 第一个对象用来装整个返回值对象，第二个对象用来装返回值对象最深处的 next==null的对象 （在做题的时候我一直脑海里面有这个想法 ，但是没写出来）申明一个装进位的值 循环里面一级一级的拆 l1,l2同步进行 当第一次取得时候head还是null 需要new 到head上面
之后每次就放到tail得next里面 操作完之后 需要把l1,l2的上一级丢掉 l1=l1.next;l2=l2.next;
当它计算到最后一位的时候 如果进位大于0 那就得再给tail的next赋值

学到的东西 是对递归有了一个概念 想问题的时候应该再细一点 这道题就是小题大做了
希望未来越来越好！！！！
吃过午饭再回味回味 下午开始第三题！！！

vethenc

你着火了

lpc0828

vethenc 发表于 2021-2-22 13:14
你着火了

块给我下下火

aristan

写的真好，可惜我是学C的，java的多多少少有点不懂

SpeII

感觉用纯数学的方法更简单

[Java] 纯文本查看 复制代码

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        StringBuilder sb3 = new StringBuilder();
        while (l1 != null) {
            sb1.append(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            sb2.append(l2.val);
            l2 = l2.next;
        }
        BigInteger b1 = new BigInteger(sb1.reverse().toString());
        BigInteger b2 = new BigInteger(sb2.reverse().toString());
        BigInteger sum = b1.add(b2);
        int i1 = Integer.parseInt(sb3.append(sum).reverse().toString());
        ListNode head = new ListNode();
        ListNode cur = head;
        int firstbit;
        int tens = cardinalNum(lengthNum(sum.longValue()));
        do {
            firstbit = i1 / tens;
            cur.next = new ListNode(firstbit);
            cur = cur.next;
            i1 = i1 - firstbit * tens;
            tens = tens / 10;
        } while (i1 > 0);

        return head.next;
    }

    public static int cardinalNum(int count) {
        int tens = 1;
        for (int i = 0; i < count - 1; i++) {
            tens *= 10;
        }
        return tens;
    }

    public static int lengthNum(Long num) {
        int count = 0; //计数
        while (num >= 1) {
            num /= 10;
            count++;
        }
        return count;
    }

nj001

处理数组或者链表之类用循环即可简单解决大多数问题，递归是屠龙术可以解决更复杂的问题，缺点是太耗资源，不过递归可以优化成循环

lpc0828

nj001 发表于 2021-2-22 20:54
处理数组或者链表之类用循环即可简单解决大多数问题，递归是屠龙术可以解决更复杂的问题，缺点是太耗资源， ...

太对了哥

lpc0828

SpeII 发表于 2021-2-22 16:50
感觉用纯数学的方法更简单[mw_shl_code=java,true]public static ListNode addTwoNumbers(ListNode l1, Lis ...

纯数学的方式 虽然可以 但是不符合题目了  节点数的范围是[0,100]
太长了 用普通的数字类型没法接收