Leetcode学习之路(Python3.8)-2. 两数相加

原创
2020/08/28 13:32
阅读数 72

1.题目:

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

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

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

  • 示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出:7 -> 0 -> 8

原因:342 + 465 = 807

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/add-two-numbers 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2.思路分析

我的思路是先把两个加数的单链表转成正确的数字,然后把相加的结果再转回单链表。

  • 知识点1-单链表
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

注意*:Python 中没有单链表的结构定义,只能自己实现。了解该题的单链表用法就行。
  • 单链表转换成数字
def listNode_To_Number(listNodeParameter):
    firstTempList = []
    #用循环把单链表的数据取出来放firstTempList里
    while listNodeParameter != None:
        #str()是为了方便下面的join()使用
        firstTempList.append(str(listNodeParameter.val))
        listNodeParameter = listNodeParameter.next
    #用join()把列表转成连续字符串,[::-1]反向字符串,再转成int型
    resultNumber = int(''.join(firstTempList)[::-1])
    return resultNumber
  • 知识点2-Python join() 方法用于将序列中的元素以指定的字符连接生成一个新的字符串
strList = ['1', '2', '3']
print('-'.join( strList ))#以 - 连接显示新字符串
print(''.join( strList ))#无分隔显示新字符串

#注意:
numberList = [1, 2, 3]
print(''.join( numberList ))#join()没办法处理非字符序列
  • 输出结果:
1-2-3
123
TypeError: sequence item 0: expected str instance, int found
  • 知识点3-Python 反转字符串
#第一种反转方法
#reversed 函数返回一个反转的迭代器。
#reversed(seq)  seq--要转换的序列,可以是 tuple, string, list 或 range。
seqList = ['1', '2', '3']
print(list(reversed(seqList)))

#第二种反转方法
#seq[::-1]  seq--要转换的序列,可以是 tuple, string, list、等(前面几个类型是验证过可以转换的,其他的有待验证(~ ̄▽ ̄)~)。
print(seqList[::-1])
  • 输出结果:
['3', '2', '1']
['3', '2', '1']
  • 数字转换成单链表
def Number_To_listNode(numberOfParameter):
    ResList = ListNode(int(numberOfParameter[0]))
    resultListNode = ResList
    for i in range(1, len(numberOfParameter)):
        ResList.next = ListNode(int(numberOfParameter[i]))
        ResList = ResList.next
    return resultListNode
  • 思考:
    单链表的操作可以参考网上大神们关于 Python 单链表的操作,感觉自己不是很讲得清楚,就不误人子弟了。

3.完整示例

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def listNode_To_Number(listNodeParameter):
            firstTempList = []
            while listNodeParameter != None:
                firstTempList.append(str(listNodeParameter.val))
                listNodeParameter = listNodeParameter.next
            resultNumber = int(''.join(firstTempList)[::-1])
            return resultNumber


        def Number_To_listNode(numberOfParameter):
            ResList = ListNode(int(numberOfParameter[0]))
            resultListNode = ResList
            for i in range(1, len(numberOfParameter)):
                ResList.next = ListNode(int(numberOfParameter[i]))
                ResList = ResList.next
            return resultListNode

        resultSum = listNode_To_Number(l1) + listNode_To_Number(l2)
        return Number_To_listNode(str(resultSum)[::-1])
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部