leetcode_两数相加

2019-02-05

首先申明，自己是打算练一下python和一些基础的编程技巧才做的，如果是c纯算法的话我可吃不消

题目

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

1
2
3

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

这题首先让我困扰的就是python怎么写链表，和c不一样,python没有专门的指针概念,在python中每个变量都是指针，隐式地包含了指向/嵌套关系

结合了一些网上的分析，最后好的办法是创建一个类，链接如下：

https://blog.csdn.net/hjxu2016/article/details/79714783 ；

https://www.cnblogs.com/yuanmingzhou/p/9661152.html

定义ListNode节点

class ListNode(object):
    __slots__ = ('item', 'next')  
    # 仅允许绑定这两个属性，__slots__定义的属性仅对当前类起作用，对继承的子类是不起作用

    def __init__(self, item):
        self.item = item
        self.next = None
    def getItem(self):
        return self.item
    def getNext(self):
        return self.next
    def setItem(self, newitem):
        self.item = newitem
    def setNext(self, newnext):
        self.next = newnext

定义SinglelinkedList单向链表

class SingleLinkedList(object):
    def __init__(self):
        self._head = None  # 初始化链表为空表
        self._size = 0
    def isEmpty(self):
        return self._head == None
    def add(self, item):   # 在链表前端添加Node
        temp = ListNode(item)
        temp.setNext(self._head)
        self._head = temp
    def append(self, item):  # 在链表末尾添加Node
        temp = ListNode(item)
        if self.isEmpty():
            self._head = temp
        else:
            current = self._head
            while current.getNext() != None:
                current = current.getNext()
            current.setNext(temp)
    def serach(self, item):   # 在链表中搜索Node
        current = self._head
        flag = False
        while current != None and not flag:
            if current.getItem() == item:
                flag = True
            else:
                current = current.getNext()
        return flag
    def index(self, item):  # 检测索引位置
        current = self._head
        count = 0
        found = None
        while current != None and not found:
            count += 1
            if current.getItem() == item:
                found = True
            else:
                current = current.getNext()
        if found:
            return count
        else:
            raise ValueError('Not fond {item}'.format(item=item))
    def remove(self, item):   # 在链表中删除Node
        current = self._head
        pre = None
        while current != None:
            if current.getItem() == item:
                if not pre:
                    self._head = current.getNext()
                else:
                    pre.setNext(current.getNext())
                break
            else:
                pre = current
                current = current.getNext()
    def insert(self, pos, item):  # 插入元素
        current = self._head
        if pos == 1:
            self.add(item)
        if pos < 1:
            raise ValueError('pos must not less than 1')
        else:
            temp = ListNode(item)
            count = 1
            pre = None
            current = self._head
            while count < pos:
                count += 1
                pre = current
                if current.getNext():
                    current = current.getNext()
                else:
                    raise ValueError('pos is too big')
            pre.setNext(temp)
            temp.setNext(current)

解题

题目其实是给了部分定义的，我们可以省力不少

# leetcode
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        p = ListNode(0)
        pos = p
        carry = 0
        while(l1 or l2):
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            s = carry +x + y
            carry = s // 10  # carry 表示是否有进位
            pos.next = ListNode(s%10)
            pos = pos.next
            if l1 != None:
                l1 = l1.next
            ifl2 != None:
                l2 = l2.next
        if carry > 0:
            pos.next = ListNode(1)
        return p.next

最后其实不断地p.next是可以从低位到高位全部输出的，主要的收获就是python可能弄个节点的类，之前没试过

本文作者： xiaoyuyu
本文链接： http://woaixiaoyuyu.github.io/2019/02/05/leetcode-%E4%B8%A4%E6%95%B0%E7%9B%B8%E5%8A%A0/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！