【データ構造とアルゴリズムテーマセット】(Python実現)7-2一元多項式の乗算と加算

21838 ワード

この問題は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))