LeetCode_两数相加

两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

算法实现（方法一）

package leetCode;

import java.util.LinkedList;

/**
 * Author: Rupert Tears
 * Date: Created in 20:16 2022/11/2
 * Description: Thought is already is late, exactly is the earliest time.
 * 两数相加
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * <p>
 * example:
 * 2——4——3
 * 5——6——4
 * 7——0——8
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[7,0,8]
 * 解释：342 + 465 = 807.
 * <p>
 * 输入：l1 = [0], l2 = [0]
 * 输出：[0]
 * <p>
 * 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
 * 输出：[8,9,9,9,0,0,0,1]
 * <p>
 * 每个链表中的节点数在范围 [1, 100] 内
 * 0 <= Node.val <= 9
 * 题目数据保证列表表示的数字不含前导零
 */
public class Two {
    public static void main(String[] args) {
        LinkedList<Integer> l1 = new LinkedList<>();
        l1.add(9);
        l1.add(9);
        l1.add(9);
        l1.add(9);
        l1.add(9);
        l1.add(9);
        l1.add(9);
        System.out.println(l1);
        LinkedList<Integer> l2 = new LinkedList<>();
        l2.add(9);
        l2.add(9);
        l2.add(9);
        l2.add(9);
        System.out.println(l2);
        System.out.println(addTwoNumbers(l1, l2));

    }

    /**
     * Author: Rupert-Tears
     * CreateTime: 20:21 2022/11/2
     * Description: 两数之和
     * 解题思路：先将链表中的值倒序取出，然后求和，再倒序装入
     */
    public static LinkedList<String> addTwoNumbers(LinkedList<Integer> l1, LinkedList<Integer> l2) {
        LinkedList<Integer> r1 = new LinkedList<>();
        LinkedList<Integer> r2 = new LinkedList<>();
        for (int size = l1.size(), i = 0; i < size; i++) {
            int tmp = l1.removeLast();
            r1.add(tmp);
        }
        for (int size = l2.size(), i = 0; i < size; i++) {
            int tmp = l2.removeLast();
            r2.add(tmp);
        }

        // 将列表中的数转化为 int 类型
        // [3, 4, 2]  ==> 342
        String str1 = r1.toString().substring(1);   // 去除[
        String str2 = str1.substring(0, str1.length() - 1);    // 去除]
        String str3 = str2.replaceAll(",", "");  // 去除分割符号 ,
        String str4 = str3.replaceAll("\\s+", "");   // 去除空格
        int v1 = Integer.parseInt(str4);

        String str12 = r2.toString().substring(1);   // 去除[
        String str22 = str12.substring(0, str12.length() - 1);    // 去除]
        String str32 = str22.replaceAll(",", "");  // 去除分割符号 ,
        String str42 = str32.replaceAll("\\s+", "");   // 去除空格
        int v2 = Integer.parseInt(str42);

        // 运算 807
        int sum = v1 + v2;

        // 倒序装入列表 [7,0,8]
        LinkedList<String> result = new LinkedList<>();
        String sumStr = sum + "";
        for (int i = 0; i < sumStr.length(); i++) {
            // 插入头部
            result.addFirst(String.valueOf(sumStr.charAt(i)));
        }

        return result;
    }

}

相关知识 LinkedList

简介

链表（LinkedList）是一种常见的数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是每一个节点里存到下一个节点的地址。

链表可以分为单向链表和双向链表。

一个单项链表包含两个值：当前节点的值和指向下一个节点的链接。

一个双向链表由三个整数值：当前节点的值、向后的节点链接、前向的节点链接。

应用场景

• 需要循环迭代来访问列表中的某些元素。
• 需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作。

代码示例

package dataStructure;

/**
 * Author: Rupert Tears
 * Date: Created in 20:43 2022/11/2
 * Description: Thought is already is late, exactly is the earliest time.
 */
public class LinkedList {
    public static void main(String[] args) {
        // 创建一个简单的链表实例
        java.util.LinkedList<String> list = new java.util.LinkedList<>();
        list.add("Google");
        list.add("Baidu");
        list.add("Weibo");
        // 在列表开头添加元素
        list.addFirst("Apple");
        // 在列表尾部添加元素
        list.addLast("End");
        // 移除头部元素
        list.removeFirst();
        // 移除尾部元素
        list.removeLast();
        // 获取头部元素
        System.out.println(list.getFirst());
        // 获取尾部元素
        System.out.println(list.getLast());

        // 输出列表
        System.out.println(list);

        System.out.println(list.size());
        //  size 迭代列表中元素
        for (int size = list.size(), i = 0; i < size; i++) {
            System.out.println(list.get(i));
        }

        // foreach 迭代元素
        for (String str : list) {
            System.out.println(str);
        }

    }
}

算法实现（方法二）

测试类

public static void main(String[] args) {
    ListNode listNode1 = new ListNode(1);
       ListNode listNode2 = new ListNode(3, listNode1);
       ListNode listNode3 = new ListNode(6, listNode2);    // 631 节点

       ListNode listNode21 = new ListNode(2);
       ListNode listNode22 = new ListNode(3, listNode21);
       ListNode listNode23 = new ListNode(6, listNode22);    // 632 节点
       ListNode listNode24 = new ListNode(9, listNode23);
       ListNode listNode25 = new ListNode(9, listNode24);

       ListNode result = sum(listNode3, listNode25);
       while (result != null) {
           System.out.println(result.val);
           result = result.next;
       }
   }

方法

/**
 * Author: Rupert-Tears
 * CreateTime: 14:29 2022/11/11
 * Description: 链表方式求解
 * 第一步：按位求和
 * 第二部：进位
 * 第三部：处理特殊情况
 * 1. 长度问题
 * 2. 末尾进位
 */
public static ListNode sum(ListNode l1, ListNode l2) {
    // 接收参数值头节点
    ListNode head1 = l1;
    ListNode head2 = l2;


    // l1 + l2 (l1 为基准)
    while (head1 != null) {
        if (head2 != null) {
            // head1 存储求和值
            head1.val += head2.val;
            // 进行下一位运算
            head2 = head2.next;
        }
        // 若l1 下一位为空,l2还有值（l1.length < l2.length）
        if (head1.next == null && head2 != null) {
            head1.next = head2;
            break;
        }
        // 更新head1
        head1 = head1.next;
    }
    // 进位操作（分组方法）
    merge(l1);
    return l1;
}

/**
 * Author: Rupert-Tears
 * CreateTime: 15:10 2022/11/11
 * Description: 进位操作
 * 因为要对下一位操作，对象直接选择链表
 * 遍历链表，判断是否需要进位，然后保留余数，下一位+1
 */
public static void merge(ListNode listNode) {
    while (listNode != null) {
        if (listNode.val >= 10) {
            // 赋值余数
            listNode.val = listNode.val % 10;
            // 判断是不是末尾
            if (listNode.next == null) {
                // 末端新建节点，初始值为0
                listNode.next = new ListNode(0);
            }
            // 下一位 进 1
            listNode.next.val += 1;
        }
        listNode = listNode.next;
    }
}

package dataStructure;

/**
 * Author: Rupert Tears
 * Date: Created in 14:32 2022/11/11
 * Description: Thought is already is late, exactly is the earliest time.
 */
public class ListNode {
    // 节点值
    public int val;
    // 下一个节点
    public ListNode next;

    // 赋值
    public ListNode(int val) {
        this.val = val;
    }

    // 构建下一个节点
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

}

反思

• 首先，理解清晰题目考察的方向。暴力破解可行，但应该是最坏的打算！
• 明确解题的思路，即算法实现的步骤。
• 分阶段实现，测试。