• 力扣LeatCode算法题-两数之和（二）

    力扣算法题第二题，两数相加算法题：

    要求：

    1. //给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
    2. //如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
    3. //您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
    4. //示例：
    5. //输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    6. //输出：7 -> 0 -> 8
    7. //原因：342 + 465 = 807

    很多时候不是做不出题目，而是题意没有审清。

    我们再来看下题目要求：

    我们所指的的个位是在链头，百位是在链尾，所以思路是要转过来。

    使用了最简单的一种，不考虑0和超过百位的算法。

    1. public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
    2.         //创建一个和值
    3.         ListNode sun_end = new ListNode(-1,new ListNode(-1,new ListNode(-1)));
    4.         //测试数据：[1,2,3] [1,9,9]
    5.         if((l1.val+l2.val)>=10 ){
    6.             //1.判断个位,个位相加>10,个位进位，十位+1。
    7.             sun_end.val=l1.val+l2.val-10;
    8.             //2.十位相加
    9.             if((l1.next.val+l2.next.val+1)>=10){
    10.                 //十位进位
    11.                 sun_end.next.val =l1.next.val+l2.next.val+1-10;
    12.                 //3.百位相加，默认百位不进位
    13.                 sun_end.next.next.val =l1.next.next.val+l2.next.next.val+1;
    14.             }else{
    15.                 //个位进位，十位不进位，默认百位不进位
    16.                 sun_end.next.next.val =l1.next.next.val+l2.next.next.val+1;
    17.                 //十位不进位，默认百位不进位
    18.                 sun_end.next.next.val =l1.next.next.val+l2.next.next.val;
    19.             }
    20.         }else {
    21.             //判断个位,个位相加<10,个位不进位，十位不加1。
    22.             //1.1 否则个位相加不进位,只考虑相加在3位数以内
    23.             sun_end.val=l1.val+l2.val;
    24.             //2.十位相加
    25.             if((l1.next.val+l2.next.val+1)>=10){
    26.                 //个位相加不进位,十位进百位
    27.                 sun_end.next.val =l1.next.val+l2.next.val-10;
    28.                 //3.百位相加，默认百位不进位
    29.                 sun_end.next.next.val =l1.next.next.val+l2.next.next.val+1;
    30.             }else{
    31.                 //个位不进位，十位不进位，默认百位不进位
    32.                 sun_end.next.val =l1.next.val+l2.next.val;
    33.                 //十位不进位，默认百位不进位
    34.                 sun_end.next.next.val =l1.next.next.val+l2.next.next.val;
    35.             }
    36.         }
    37.         System.out.println("sun1="+sun_end.val);
    38.         System.out.println("sun2="+sun_end.next.val);
    39.         System.out.println("sun3="+sun_end.next.next.val);
    40.         return sun_end;
    41.     }

    以上这种办法只适用于两个都是百位数相加，且和不超过千位，无法通过leatcode算法考验。

    所以整合出第三种办法：

    循环进制计算法

    1. public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    2.         //创建一个和值
    3.         ListNode sun_header = new ListNode(-1);
    4.         ListNode sun_end = sun_header;//用来调整链接指针下标的next指向
    5.         int carry =0;//用来标识进位
    6.         //用一个while循环去判断“个十百”位相加是否大于10，
    7.         while (l1!=null || l2!=null || carry !=0){
    8.             if(l1!=null){
    9.                 carry+=l1.val;
    10.                 l1=l1.next;
    11.             }
    12.             if(l2!=null){
    13.                 carry+= l2.val;
    14.                 l2=l2.next;
    15.             }
    16.             sun_end.next=new ListNode(carry%10);//取余： 比如个位6+6=12%=2,个位=2，十位=1.
    17.             sun_end=sun_end.next;//移动下一个节点sun_end有三个链结构
    18.             carry/=10;//超过1则进位器+1。=0则不进位
    19.             //sun_end.val=carry%10;
    20.         }
    21.         System.out.println("sun1="+sun_header.next.val);
    22.         System.out.println("sun2="+sun_header.next.next.val);
    23.         System.out.println("sun3="+sun_header.next.next.next.val);
    24.         return sun_header.next;//sun_header有四个链结构
    25.     }

    这段代码如果要在leatcode上运行，需要去掉static静态方法。因为这是我在idea上测试写的方法。

    大家理解起来很抽象。我画图给大家解释下。

    每一个listNode就相当于一个回形针（ListNode sun_header = new ListNode(-1)），每个回形针是 listNode。

    第一个回形针取值直接用var取值，如：l1.var = 2;

    第二个回形针取值直接用l1.next.var，需要next移动到下一个回形针上，如：l2.next.var=6

    第四个回形针取值则用3个next。如： sun_header.next.next.next.var=8.

    就这么简单，低位相加>10，就进位。

    附上所有代码，可以在任何编译器中运行。

    1. package com.zhm.test;
    2.  
    3. import org.junit.Test;
    4.  
    5. import java.util.Arrays;
    6.  
    7. /**
    8.  * @Author bige
    9.  * @Date: 2022/11/16 18:11
    10.  * @ApiNote:两数相加
    11.  */
    12. public class Leatcode_test2 {
    13.     //给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
    14.     //如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
    15.     //您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
    16.     //示例：
    17.     //输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    18.     //输出：7 -> 0 -> 8
    19.     //原因：342 + 465 = 807
    20.     public static int[] addTwoNumbers(int[] l1, int[] l2) {
    21.         //测试数据：[1,2,3] [1,9,9]
    22.         //int[] sun =new int[5];
    23.         int[] sun =new int[l1.length];
    24.         //想法和思路
    25.         //1.个位相加>10则向10位
    26.         if((l1[l1.length-1]+l2[l2.length-1])>10){
    27.             sun[l1.length-1] =l1[l1.length-1]+l2[l2.length-1]-10;
    28.             //2.十位相加+1
    29.             if((l1[l1.length-2]+l2[l2.length-2]+1)>10){
    30.                 //十位进位
    31.                 sun[l1.length-2] =l1[l1.length-2]+l2[l2.length-2]+1-10;
    32.                 //3.百位相加，默认百位不进位
    33.                 sun[l1.length-3] =l1[l1.length-3]+l2[l2.length-3]+1;
    34.             }else{
    35.                 //个位进位，十位不进位，默认百位不进位
    36.                 sun[l1.length-2] =l1[l1.length-2]+l2[l2.length-2]+1;
    37.                 //十位不进位，默认百位不进位
    38.                 sun[l1.length-3] =l1[l1.length-3]+l2[l2.length-3];
    39.             }
    40.  
    41.         }else {
    42.             //1.1 否则个位相加不进位,只考虑相加在3位数以内
    43.             sun[l1.length] =l1[l1.length]+l2[l2.length];
    44.             //2.十位相加
    45.             if((l1[l1.length-2]+l2[l2.length-2]+1)>10){
    46.                 //个位不进位，十位进位
    47.                 sun[l1.length-2] =l1[l1.length-2]+l2[l2.length-2]-10;
    48.                 //3.百位相加，默认百位不进位
    49.                 sun[l1.length-3] =l1[l1.length-3]+l2[l2.length-3]+1;
    50.             }else{
    51.                 //个位不进位，十位不进位，默认百位不进位
    52.                 sun[l1.length-1] =l1[l1.length-1]+l2[l2.length-1];
    53.                 //十位不进位，默认百位不进位
    54.                 sun[l1.length-2] =l1[l1.length-2]+l2[l2.length-2];
    55.             }
    56.         }
    57.  
    58.         //2.十位相加>10则向百位+1
    59.         return sun;
    60.     }
    61.  
    62.  
    63.     //采用了符合leatcode题意的格式ListNode
    64.      public static class ListNode {
    65.          int val;
    66.          ListNode next;
    67.          ListNode() {}
    68.          ListNode(int val) { this.val = val; }
    69.          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    70.  
    71.     }
    72.  
    73.     public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
    74.         //创建一个和值
    75.         ListNode sun_end = new ListNode(-1,new ListNode(-1,new ListNode(-1)));
    76.         //测试数据：[1,2,3] [1,9,9]
    77.         if((l1.val+l2.val)>=10 ){
    78.             //1.判断个位,个位相加>10,个位进位，十位+1。
    79.             sun_end.val=l1.val+l2.val-10;
    80.             //2.十位相加
    81.             if((l1.next.val+l2.next.val+1)>=10){
    82.                 //十位进位
    83.                 sun_end.next.val =l1.next.val+l2.next.val+1-10;
    84.                 //3.百位相加，默认百位不进位
    85.                 sun_end.next.next.val =l1.next.next.val+l2.next.next.val+1;
    86.             }else{
    87.                 //个位进位，十位不进位，默认百位不进位
    88.                 sun_end.next.next.val =l1.next.next.val+l2.next.next.val+1;
    89.                 //十位不进位，默认百位不进位
    90.                 sun_end.next.next.val =l1.next.next.val+l2.next.next.val;
    91.             }
    92.         }else {
    93.             //判断个位,个位相加<10,个位不进位，十位不加1。
    94.             //1.1 否则个位相加不进位,只考虑相加在3位数以内
    95.             sun_end.val=l1.val+l2.val;
    96.             //2.十位相加
    97.             if((l1.next.val+l2.next.val+1)>=10){
    98.                 //个位相加不进位,十位进百位
    99.                 sun_end.next.val =l1.next.val+l2.next.val-10;
    100.                 //3.百位相加，默认百位不进位
    101.                 sun_end.next.next.val =l1.next.next.val+l2.next.next.val+1;
    102.             }else{
    103.                 //个位不进位，十位不进位，默认百位不进位
    104.                 sun_end.next.val =l1.next.val+l2.next.val;
    105.                 //十位不进位，默认百位不进位
    106.                 sun_end.next.next.val =l1.next.next.val+l2.next.next.val;
    107.             }
    108.         }
    109.         System.out.println("sun1="+sun_end.val);
    110.         System.out.println("sun2="+sun_end.next.val);
    111.         System.out.println("sun3="+sun_end.next.next.val);
    112.         return sun_end;
    113.     }
    114.  
    115.     public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    116.         //创建一个和值
    117.         ListNode sun_header = new ListNode(-1);
    118.         ListNode sun_end = sun_header;//用来调整链接指针下标的next指向
    119.         int carry =0;//用来标识进位
    120.         //用一个while循环去判断“个十百”位相加是否大于10，
    121.         while (l1!=null || l2!=null || carry !=0){
    122.             if(l1!=null){
    123.                 carry+=l1.val;
    124.                 l1=l1.next;
    125.             }
    126.             if(l2!=null){
    127.                 carry+= l2.val;
    128.                 l2=l2.next;
    129.             }
    130.             sun_end.next=new ListNode(carry%10);//取余： 比如个位6+6=12%=2,个位=2，十位=1.
    131.             sun_end=sun_end.next;//移动下一个节点sun_end有三个链结构
    132.             carry/=10;//超过1则进位器+1。=0则不进位
    133.             //sun_end.val=carry%10;
    134.         }
    135.         System.out.println("sun1="+sun_header.next.val);
    136.         System.out.println("sun2="+sun_header.next.next.val);
    137.         System.out.println("sun3="+sun_header.next.next.next.val);
    138.         return sun_header.next;//sun_header有四个链结构
    139.     }
    140.  
    141.     public static void main(String[] args) {
    142.         //采用数组格式去测试
    143.         int[] l1={1,2,3};
    144.         int[] l2={1,2,9};
    145.         //int[] result = addTwoNumbers(l1,l2);
    146.         //System.out.println(Arrays.toString(result));
    147.  
    148.         
    149.         //采用单链表格式去测试数据
    150.         //ListNode newHead = new ListNode(-1);
    151.         ListNode list1 = new ListNode(2,new ListNode(4,new ListNode(3)));
    152.         ListNode list2 = new ListNode(5,new ListNode(6,new ListNode(4)));
    153.         //System.out.println(list1.toString());
    154.         //addTwoNumbers1(list1,list2);
    155.         addTwoNumbers(list1,list2);
    156.     }
    157. }

  • 相关阅读:
    PTA 7-82 三个整数排序
    Vue3 实现路由vue-router效果
    postman 获取HTML 里name=token 的值
    GIS工具maptalks开发手册(三)03——官网示例之添加图层和移除图层
    git多平台多账号公钥配置
    MySQL的安装与配置
    keycloak~资源的远程授权
    浏览器从输入url到渲染页面发生了什么？
    AVProVideo☀️十、来给视频设置封面
    Postgresql 重装
  • 原文地址：https://blog.csdn.net/feipo_zhm/article/details/127898272