【データ構造とアルゴリズムテーマセット】(Python実現)7-2一元多項式の乗算と加算
この問題は4番目のテストポイントに長い間詰まっていた.「ゼロ多項式と定数多項式が入力されています」は、最後に追加されたif...elseのいくつかです.通過した
class ListNode:
def __init__(self,coef,exp):
self.coef = coef
self.exp = exp
self.next = None
def list2LinkList(lst):
if lst[0]==0:
return 0
head = ListNode(0,0)
tail = head
for i in range(1,len(lst),2):
node = ListNode(lst[i],lst[i+1])
# print(node.coef,node.expon)
tail.next = node
tail = node
return head.next
def add(lst1,lst2):
h1 = lst1
h2 = lst2
addRes = []
while h1 and h2:
e1 = h1.exp
e2 = h2.exp
if e1<e2:
if h2.coef!=0:
addRes.append(h2.coef)
addRes.append(e2)
h2 = h2.next
elif e1>e2:
if h1.coef!=0:
addRes.append(h1.coef)
addRes.append(e1)
h1 = h1.next
else:
if (h1.coef+h2.coef)!=0:
addRes.append(h1.coef+h2.coef)
addRes.append(e1)
h1 = h1.next
h2 = h2.next
while h1:
if h1.coef!=0:
addRes.append(h1.coef)
addRes.append(h1.exp)
h1 = h1.next
while h2:
if h2.coef!=0:
addRes.append(h2.coef)
addRes.append(h2.exp)
h2 = h2.next
return [0,0] if len(addRes)==0 else addRes
def mul(lst1,lst2):
h1 = lst1
h2 = lst2
p = ListNode(0,0)
tail = p
while h2: # lst1 lst2 , p
node = ListNode(h1.coef*h2.coef,h1.exp+h2.exp)
tail.next = node
tail = node
h2 = h2.next
h1 = h1.next
while h1: # lst1 lst2
h2 = lst2
tail = p
while h2:
c = h1.coef*h2.coef
e = h1.exp+h2.exp
#print(c,e)
while tail.next and tail.next.exp>e: #
tail = tail.next
if tail.next and tail.next.exp == e:
if tail.next.coef+c!=0:
tail.next.coef += c
else:
tail.next = tail.next.next
else:
t = ListNode(c,e)
t.next = tail.next
tail.next = t
tail = tail.next
h2 = h2.next
h1 = h1.next
mulRes = []
p = p.next
while p:
if p.coef!=0:
mulRes.append(p.coef)
mulRes.append(p.exp)
p = p.next
return [0,0] if len(mulRes)==0 else mulRes
def printFun(lst):
ls = [str(i) for i in lst]
print(' '.join(ls))
#
lst1=list(map(int,input().split()))
lst2=list(map(int,input().split()))
if len(lst1)==1 and len(lst2)==1:
printFun([0,0])
printFun([0,0])
elif len(lst1)==1 and len(lst2)>1:
printFun([0,0])
printFun(lst2[1:])
elif len(lst1)>1 and len(lst2)==1:
printFun([0,0])
printFun(lst1[1:])
else:
L1 = list2LinkList(lst1)
L2 = list2LinkList(lst2)
printFun(mul(L1,L2))
printFun(add(L1,L2))