我需要帮助理解为什么下面问题的第二个解决方案比第一个运行更快。
该问题来自leetcode。 问题是:
给定两个非空链表,表示两个非负整数。 数字以相反的顺序存储,并且它们的每个节点包含一个数字。 将两个数字相加并将其作为链表返回。 您可以假设这两个数字除了数字0本身外不包含任何前导零。
其中一个解决方案是:
第一个解决方案运行时间约为200毫秒,而第二个解决方案运行时间为100毫秒。我可以看出两者都是O(较大列表的n)。我想第一个运行较慢的原因是因为需要进行floor和modulo操作?最初,我认为第二个会因为需要进行大量字符串类型转换而运行更慢。
该问题来自leetcode。 问题是:
给定两个非空链表,表示两个非负整数。 数字以相反的顺序存储,并且它们的每个节点包含一个数字。 将两个数字相加并将其作为链表返回。 您可以假设这两个数字除了数字0本身外不包含任何前导零。
其中一个解决方案是:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
import numpy as np
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
sum_ = ListNode(0)
root = sum_
carry_over = 0
# O(n of bigger list) - time
# if there are still numbers to be added in list 1 or list 2, do
while l1 or l2:
# if list 1 is not null and has a value
if l1 and l1.val:
# add it to our sum ListNode value
sum_.val += l1.val
if l2 and l2.val:
sum_.val += l2.val
# we might need to carry over the decimal from the previous sum
sum_.val += carry_over
# if the new sum is >= 10, then we need to carry over the decimal
carry_over = np.floor(sum_.val / 10)
# if carry over is more than zero, we need to just use the remainder. i.e. if 11, then sum at this location is 1; and we carry over 1 forward.
if carry_over > 0: sum_.val = sum_.val % 10
# type case from float to int. Why are we in float anyway?
sum_.val = int(sum_.val)
l1_next = l1 and l1.next
l2_next = l2 and l2.next
# continue, if there are more numbers
if l1_next or l2_next:
sum_.next = ListNode(0)
sum_ = sum_.next
l1 = l1.next if l1_next else None
l2 = l2.next if l2_next else None
# stop here, if no more numbers to add.
else:
if carry_over:
sum_.next = ListNode(int(carry_over))
l1, l2 = None, None
return root
另一个是:
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
# these are array representation of the linked list
input_1 = []
input_2 = []
# loop through all nodes in l1 linked list and add to input_1
while l1 is not None:
input_1.append(str(l1.val))
l1 = l1.next
while l2 is not None:
input_2.append(str(l2.val))
l2 = l2.next
# this is string numbers from l1 and l2, but in the correct order (not reversed)
input_1 = "".join(reversed(input_1))
input_2 = "".join(reversed(input_2))
# now typecast the strings to integers and add
out = str(int(input_1) + int(input_2))
# lastly, create a ListNode with this number to bbe returned
last = None
for x in out:
n = ListNode(x)
n.next = last
last = n
return last
第一个解决方案运行时间约为200毫秒,而第二个解决方案运行时间为100毫秒。我可以看出两者都是O(较大列表的n)。我想第一个运行较慢的原因是因为需要进行floor和modulo操作?最初,我认为第二个会因为需要进行大量字符串类型转换而运行更慢。