leetcode02两数相加

2018年8月17日 发表评论 阅读评论

一、题目

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。你可以假设除了数字 0 之外,这两个数字都不会以零开头。示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

二、题目分析

最初的并未看清链表的提示。只是将其当成一个数组来处理了,按数组的思想处理的代码和执行结果如下:

#!/usr/bin/env python
# coding=utf8
# ===============================================================================
#   Copyright (C) 2018 www.361way.com site All rights reserved.
#
#   Filename      :02.py
#   Author        :yangbk <itybku@139.com>
#   Create Time   :2018-08-16 19:00
#   Description   :
# ===============================================================================
l1 = [2,4,3]
l2 = [5,6,4]
def addstr(l):
  a = ''
  for i in l:
    i = str(i)
    a = a + i
  return a
n1 = addstr(l1)
n2 = addstr(l2)
n3 = int(n1) + int(n2)
print n1,n2,n3
print  list(''.join(str(n3)[::-1]))
[root@localhost leetcode]# python 02.py
243 564 807
['7', '0', '8']

不过将代码提交后,不通过。

三、链表(Linked lists)

上面题目提到了一个非常有用的概念链表,其一般只存在于更底层的高级语言中,如C、JAVA、Golang等。其一般都是和指针相关的。而且上面提到的是单向链表,这里就截图一个C++实现的单向链表的示意图:

linked lists

单向链表很简单,链表的创建就是添加结点到链表的最后,开始是添加一个结点到head结点后面,然后添加一个结点到上次添加的结点后面,每次新建的结点的指针总是指向NULL指针。

更多链表相关内部可以参考:

链表

链表(单向、双向、单向循环、双向循环)学习过程总结

C语言通用双向循环链表操作函数集

python 数据结构之单链表的实现

四、功能实现

对位相加,设置进位位,重点在于如何写单链表。其代码如下:

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        nHead, flag = ListNode(0), 0
        head = nHead
        while flag or l1 or l2:
            node = ListNode(flag)
            if l1:
                print node.val
                node.val += l1.val
                print node.val
                print '---------'
                l1 = l1.next
            if l2:
                node.val += l2.val
                l2 = l2.next
            print node.val
            print '***********'
            flag = node.val // 10
            node.val %= 10
            print flag,node.val
            print '========'
            head.next, head = node, node
        return nHead.next

上面加了很多print代码,主要方便打印相关信息。实际执行的时候并不需要。上面的代码只是做了进位处理,并没有反转操作。实现执行的时候打印出来结果如下:

listnode

如何反向逆转代码如下:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
def reverse(head):
    if head is None or head.next is None:
        return head
    pre = None
    cur = head
    h = head
    while cur:
        h = cur
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    return h
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        newl1=reverse(l1)
        newl2=reverse(l2)
        nHead, flag = ListNode(0), 0
        head = nHead
        while newl1 or newl2 or flag:
            node = ListNode(flag)
            if newl1:
                node.val += newl1.val
                newl1 = newl1.next
            if l2:
                node.val += newl2.val
                newl2 = newl2.next
            flag = node.val // 10
            node.val %= 10
            head.next, head = node, node
        newHead = reverse(nHead)
        print newHead.val
        print newHead.next.val
        print newHead.next.next.val
l1 = ListNode(2)
l1.next = ListNode(4)
l1.next.next = ListNode(3)
l2 = ListNode(5)
l2.next = ListNode(6)
l2.next.next = ListNode(4)
p = Solution()
p.addTwoNumbers(l1, l2)

上面的关于链表部分的代码不是我写的,来自互联网。因为python里不存在指针的概念。而且之前在使用python的时候也从没有关系过链表,其对链表的实现不同于其他高级语言。




本站的发展离不开您的资助,金额随意,欢迎来赏!

You can donate through PayPal.
My paypal id: itybku@139.com
Paypal page: https://www.paypal.me/361way

  1. yarving
    2018年8月24日20:08 | #1

    想知道你的python文件头部注释是自动生成的还是手动填写的啊

    • admin
      2018年8月28日10:24 | #2

      vim配置自动生成的

  1. 本文目前尚无任何 trackbacks 和 pingbacks.