【记录帖】(No.002)从零打卡刷Leetcode

写在前边:

小詹一直觉得自己编程能力不强,想在网上刷题,又怕不能坚持。不知道有木有和小伙伴和小詹一样想找个人一起刷题呢?欢迎和小詹一起定期刷leetcode,每周一周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!欢迎小伙伴们把自己的思路在留言区分享出来噢~


前期回顾:(附上使用频繁的排序算法python版)第一期的题目,有小伙伴分享了新的更优方法,可以看往期的置顶留言。

【记录帖】(No.001)从零打卡刷Leetcode

程序员面试必备之排序算法汇总(上)

程序员面试必备之排序算法汇总(下)

No.2 Add Two Numbers

原题:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

题目大意:给出两个链表,存储非负数,两个链表都是按倒序方式存储数字(个位,十位,百位……)要求将两个链表相加并以链表形式返回。

例如:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

那么在分析之前,先回顾下链表的基础知识概念吧(大佬跳过,主要是小詹自己数据结构基础不行)

① 什么是链表?

举个例子:在我们存储一大波数据时,我们很多时候是使用数组,但是当我们执行插入操作的时候就非常麻烦,有一堆数据1,2,3,5,6,7我们要在3和5之间插入4,如果用数组,我们会怎么做?当然是将5之后的数据往后退一位,然后再插入4,这样非常麻烦,效率也非常低,但是如果用链表,我就直接在3和5之间插入4就行。

链表由一个个节点连接而成,节点结构如下:

其中data部分(数据域)存储数据,next部分(指针域)存储指针,指向下一个节点。任一个链表开始于头指针head,头结点的数据域可以不存储数据。

② 链表基本操作?

初始化链表、链表长度、插入、删除、新增、查找、逆序。具体就不展开了~


回到本题上来~有多少人第一反应是这样子的?举起你的hand:

def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        len_max = max(len(l1),len(l2))
        carry = 0 #表示进位,例如9+8 = 17,carry = 1,默认进位为0
        for i in range(len_max):
            l3[i] = l1[i] + l2[i] + carry
            if l1[i] + l2[i] > 10:
                carry = 1
            else:
                carry = 0
        return l3

以上应该挺好懂的吧,就不去具体讲了(反正这个代码是不对的)

错在哪呢?爱思考的小伙伴应该注意到了,其实思路没有大的问题,毕竟加法我们还是学过的~主要有以下几个小问题:

链表不同于列表数组之类的,不能用len()获取长度

★ 加法计算思考不全面,我们考虑到了存在的进位情况,但是没考虑到链表长度不等,即两个加数位数不等(比如三位数加五位数)

经过对错误代码的反思,我们考虑将题目拆分为两个情况,以三位数加五位数为例,前三位数和前三位数按照我们已有的思路进行处理,第四位第五位则是另一种情况;具体就是:前三位数范围内,对应位进行相加操作时附加上低位的进位;第四位第五位只用将该位加上低位的进位即可(或者理解成另一个三位数的高位为0)具体代码实现如下:

 def _addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        #指定到链表头节点
        p = dummy = ListNode(-1)
        #进位标志,低位有进位时为1,默认为0
        carry = 0
        #当两个链表的同一位置同时不为空时(即小詹举例的低三位数)
        while l1 and l2:
            #p.next为指针所指 l1.val为对应的数据
            p.next = ListNode(l1.val + l2.val + carry)
            #除法和求模运算获取p.next的十位个位
            carry = p.next.val / 10
            p.next.val %= 10
            p = p.next
            l1 = l1.next
            l2 = l2.next
        res = l1 or l2 #或运算即对应小詹举得高位例子(第四位第五位)
        while res:
            p.next = ListNode(res.val + carry)
            carry = p.next.val / 10
            p.next.val %= 10
            p = p.next
            res = res.next
        if carry:
            p.next = ListNode(1)
        return dummy.next#返回该链表

是不是觉得完事了?敲完代码心里那个舒坦,然而……运行发现有点小错误,这里小詹先不揭秘,下期小詹再告诉大家上述程序在哪一个位置需要调整下才可以噢,找到的小伙伴留言区留下你的看法,第一个答对的有红包噢!而排除了错误的运行效果还比较可观:

原文发布于微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MyBlog

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

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

14440
来自专栏码云1024

RandomAccessFile&IO流&排序&方法论

29170
来自专栏BaronTalk

Java8新特性第3章(Stream API)

Stream作为Java8的新特性之一,他与Java IO包中的InputStream和OutputStream完全不是一个概念。Java8中的Stream是对...

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

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

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

42570
来自专栏大史住在大前端

javascript基础修炼(2)——What's this(上)

this是javascript关键字之一,是javascript能够实现面向对象编程的核心概念。用得好能让代码优雅高端,风骚飘逸,用不好也绝对是坑人坑己利器。我...

9910
来自专栏雪胖纸的玩蛇日常

4. 高等数学——元素和极限

  假设我们知道了整数的定义,像-3,1,17这些都属于整数Z。然后有理数则是两个整数相除q/p ,q,p属于Z,则是有理数Q。

10520
来自专栏写代码的海盗

我们是80后 golang入坑系列

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

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

React极简教程: Hello,World!React简史React安装Hello,World

A programming paradigm is a fundamental style of computer programming. There are...

9510
来自专栏C语言及其他语言

[每日一题]宏定义

前面题目主要是自定义函数的题,相信经过这些题目的训练,大家对自定义函数的理解想必更近了一步。接下来呢,我们主要来练习跟自定义函数异曲同工的宏定义,先看看下面这题...

36160
来自专栏Coding迪斯尼

面试算法:在海量数据中快速查找第k小的条目

17740

扫码关注云+社区

领取腾讯云代金券