从零打卡leetcode之day 2--两数相加

前言

深知自己在算法方面上很菜,于是打算通过打卡的方式,逼自己一把。每天在leetcode上打卡,并且把自己的想法分享出来。这将是一段漫长而又艰辛的旅程。如果你也想和我一起走上一条充满艰辛的航路,那么,别犹豫了,上车吧,一起学习一起探讨。


从零打卡leetcode之day 2

题目描述:

给定两个非空链表来表示两个非负整数。
位数按照逆序方式存储,
它们的每个节点只存储单个数字。
将两数相加返回一个新的链表。

你可以假设除了数字 0 之外,
这两个数字都不会以零开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

我的想法

我靠,居然还用到了链表的知识,突然就想起了当初用c语言自学链表的那段日子,真的差点被搞死。各种指针指来指去的。

好吧,我这里需要声明一下,如果你还没接触过链表,或者对链表超级不熟悉,麻烦你先去学好链表再来刷题,因为,链表是真的贼重要啊。

正文

方法1:

说实话,看到这道题的时候,我的想法是不管三七二十一,直接把链表代表的数字给直接算出来,然后在把两个数字给加起来,最后在把得到的和拆分成链表。可谓是暴力思路又简单啊。不过感觉代码量会有点多。

例如:

(2 -> 4 -> 3) => 2 + 4 * 10 + 3 * 100 = 342

 (5 -> 6 -> 4) => 5 + 6 * 10 + 4 * 100 = 465

然后342 + 465 = 807

接着807 => 7 -> 0 -> 8

代码如下所示:

先给出链表的结构

 class ListNode {     int val;
     ListNode next;
     ListNode(int x) { val = x; }
 }
 //方法1
 public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {   
   int num1 = 0;//用来存放第一个链表代表的数字
     int num2 = 0;//用来存放第二个链表代表的数字
     int sum = 0;//存放和
     //t = 1,10,100....用来代表链表中的个位,十位,百位...
     int t = 1;//因为是从个位开始遍历的,所以初值为1
     //算第一个数字
     while(l1 != null){
         num1 = num1 + l1.val * t;
         t = t * 10;
         l1 = l1.next;
     }
     t = 1;     //算第二个数字
     while(l2 != null){
         num2 = num2 + l2.val * t;
         t = t * 10;
         l2 = l2.next;
     }     //相加
     sum = num1 + num2;     //拆分出来放进链表里;
     ListNode head  = null;//作为链表的头节点
     ListNode temp = head;//跟踪链表
     while(sum > 0) {//结束条件为sum等于0
         if(head == null){
             head = new ListNode(sum % 10);
             temp = head;
         }else{
             temp.next = new ListNode(sum % 10);
             temp = temp.next;
         }
         sum = sum / 10;
     }     //由于有可能sum一开始就为0,所以还需要在检查一下
     if(head == null){
         head = new ListNode(0);
     }     return head;
    }

大家一起探讨探讨,你们觉得这种思路可行吗?觉得可行的举个爪,不可行的站起来说说为啥不可行。

反正,我是觉得不可行,为什么?

因为题目并没有说这条链表有多长啊,假如这条链表很长的话,一个int型整数根本存不了这个数字,当然,你可能会说,我可以用long long啊。 不好意思,long long也可能存不了。你可能又会说,java或python什么的,不是有大整数咪?好吧,我没去用过这些大整数,不知道具体个什么情况,所以当作没有这么一回事处理,haha。有兴趣的可以去尝试一下。

方法2

刚才方法1已经被告知不可行了。实际上,这道题我是觉得在解法思路上还是比较简单的,我相信大家也都能想到方法2这种方法:

就是我们可以让两个数的个位数相加,十位数相加….然后个位数有进位的话,再把进位给十位数….

例如:

(1 -> 4 -> 5) + (1 -> 6 -> 4 -> 5)
(我是故意给出两条链表长度不相等的情况的)

解法如下图:

代码如下:

      int cout = 0;//用来检查是否有进位,默认没有进位
        ListNode head = null;//用来作为链表头
        ListNode temp = head;//用来跟踪链表
        //注意循环结束条件
        while(l1 != null && l2 != null){        
          if(head == null){
                head = new ListNode((l1.val + l2.val + cout) % 10);
                temp = head;
            }else{
                temp.next = new ListNode((l1.val + l2.val + cout) % 10);
                temp = temp.next;
            }            //检查是否有进位
            cout = (l1.val + l2.val + cout) / 10;
            l1 = l1.next;
            l2 = l2.next;
        }        while(l1 != null){
            temp.next = new ListNode((l1.val + cout) % 10);
            cout = (l1.val + cout) / 10;
            l1 = l1.next;
            temp = temp.next;
        }        while(l2 != null){
            temp.next = new ListNode((l2.val + cout) % 10);
            cout = (l2.val + cout) / 10;
            l2 = l2.next;
            temp = temp.next;

        }        //最后还得在检测一下时候最高位有进位
        if(cout == 1){
            temp.next = new ListNode(cout);
        }        return head;

这里需要注意的一些点:

  1. 就是第一个循环的结束条件.
  2. 当循环结束之后,还得把那条比较长的链表剩余的部分再循环一遍。
  3. 最后还得看一下是否最高位有进位。

我觉得这道题在解法思路上还是比较简单,不过并不意味着做起来简单,因为这道题如果不仔细看,还是很容易出错的,细节点不叫多。

不过

除了方法二,我是不知道还要其他什么比较好的方法了,但是我是觉得方法二里面的代码有点多,于是绞尽脑汁,各种简化,写出了一份代码比较简练的精简代码。放出来给各位看看:

public ListNode addTwoNumbers(ListNode l1, ListNode l2){
//作为头节点,且最后返回时不要这个头节点
       ListNode head = new ListNode(0);
       ListNode temp = head;//跟踪
       int cout = 0;      
      while(l1 != null || l2 != null || cout != 0){     
         if(l1 != null){
                cout += l1.val;
                l1 = l1.next;
            }            if(l2 != null){
                cout += l2.val;
                l2 = l2.next;
            }
            temp.next = new ListNode(cout % 10);
            temp = temp.next;
            cout = cout / 10;
        }       
          return head.next;
    }

先得意一下:虽然大家都能想到方法二,不过我就不信你能比我的简洁。哈哈哈

几点说明:

  1. 先把头节点直接new出来,可以省略判断语句。
  2. 以前的while循环是判断两个链表都不为空,不过我现在换了一种想法,因为i你想我,只要有一个链表是不为空的,或者只要coun=1,那么我们就得继续处理,于是乎…..

此题到此结束


原文发布于微信公众号 - 苦逼的码农(di201805)

原文发表时间:2018-08-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MyBlog

Effective.Java 读书笔记(10)关于toString

针对于java.lang.Object已经帮我们实现好了的toString方法,当我们自己定义出来的类使用这古老的toString方法的时候,通常不会返回给你一...

14440
来自专栏Java爬坑系列

【Java入门提高篇】Day15 Java泛型再探——泛型通配符及上下边界

  上篇文章中介绍了泛型是什么,为什么要使用泛型以及如何使用泛型,相信大家对泛型有了一个基本的了解,本篇将继续讲解泛型的使用,让你对泛型有一个更好的掌握和更深入...

42070
来自专栏软件测试经验与教训

Python学习笔记(13)--集合

35360
来自专栏守候书阁

js数组操作--使用迭代方法替代for循环

数组的迭代方法,这个想必大家都不陌生了,可能刚入门的人暂时还没接触到这个。但是以后的开发中,肯定会用得上的。我自身的一个使用经历就是,如果迭代方法用的适当,不但...

17030
来自专栏Golang语言社区

第九节 Go语言循环语句

干货来了!!!为了让更多的小伙伴喜欢Golang、加入Golang之中来,Golang语言社区发起人彬哥联合业界大牛共同推出了Go语言基础、进阶、提高课程,目前...

9620
来自专栏企鹅号快讯

Python数据类型之字符串第三季

Python字符串的格式化 大家可能也已经看到了 字符串在本系列课程中 常老师已经和大家一起探讨了好几节课了 何时为什么呢?? 大家别嫌磨叽(同音可能不同字)啊...

20190
来自专栏带你撸出一手好代码

编程语言函数多返回值处理方式排名

一个函数一个返回值 , 这好像跟祖宗定下的规则似的,各个时代主流编程语言几乎都严格遵守着。然而, 在实际情况下, 程序员写代码经常会碰到一个函数会返回多个返回值...

43570
来自专栏码云1024

RandomAccessFile&IO流&排序&方法论

29370
来自专栏一个会写诗的程序员的博客

《Kotin 极简教程》第7章 面向对象编程(OOP)(1)第7章 面向对象编程(OOP)《Kotlin极简教程》正式上架:

在前面的章节中,我们学习了Kotlin的语言基础知识、类型系统、集合类以及泛型相关的知识。在本章节以及下一章中,我们将一起来学习Kotlin对面向对象编程以及函...

10820
来自专栏写代码的海盗

我们是80后 golang入坑系列

现在这个系列,已经开始两极分化了。 点赞的认为风格轻松,看着不困。反之,就有人嫌写的罗里吧嗦,上纲上线。所以善意提醒,里面不只是技术语言,还有段子。专心看技术的...

36370

扫码关注云+社区

领取腾讯云代金券