[TIL]20210731

アルゴリズム#アルゴリズム#

接続リスト:

データは線形であり、物理的な順序でメモリに格納されていないため、新しいノードを動的に挿入、削除することは簡単で、管理が容易です.しかし,欠点は配列と異なり物理的順序がないことである.特定のインデックスにアクセスするには、インデックス全体を順番に読み込む必要があります.
前5章の説明によると、Pythonでは、基本的にダイナミックアレイ(Dynamic Array)を使用してリストを作成する.使用時に固定されたセルが満たされている場合は、新しいダブルクリック(セルを長くして完全にコピー)を作成することで、配列を動的に管理します.△煩雑な知識、再分配の比率を成長因子と呼び、Pythonは初期に2倍、全体で1.125倍増加する.
通常使用されるリスト(ダイナミック配列)とは異なり、接続リストはノード間の接続であり、ノード内部はパラメータと(次のノードを指す)nextポインタで構成されています.
また、この構造のため、メモリに順番に積み重ねられたリストとは異なり、インデックスナビゲーションを行うには、各ノードにアクセスし、次のポインタを順番に追跡する必要があります.

234. Palindrome Linked List (leetcode)

    def isPalindrome(self, head: ListNode) -> bool:
        q:List=[]
            
        
        while head is not None:
            q.append(head.val)
            head =head.next
        
        while len(q)>1:
            if q.pop(0) != q.pop():
                return False
        return True

接続リストの現在のノードに格納されているパラメータを.valで呼び出し、.nextを使用してnextポインタに沿って次のノードにアクセスします.
その後popを使用し、Pythonはpop(n)を使用してn番目の値をpopすることができる.その後、pop()は元のように最後の値を取得します.
ここでpopの問題は、pop(0)などの最後尾でない値を呼び出すと、ポップアップ値の後にあるすべての値が1つのスペースに移動し、時間的複雑度O(n)を生成することである.
これに対してDequeの対策があります.デックは二重接続リスト構造であり,両方の方向で抽出すると時間的複雑度O(1)が生じる.(Darkの詳細は後で)
dakeを適用するには、2行のコードを変更するだけです.q:Deque = collections.deque() if q.popleft() != q.pop():活気に満ちた草

    def isPalindrome(self, head: ListNode) -> bool:
        rev = None
        slow = fast = head
        
        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
        if fast: ## head가 홀수일때. 가운댓 값은 slow와 rev를 비교할때 없어야하니까.
            slow = slow.next
            
        while rev and rev.val == slow.val: ## rev랑 slow를 비교하는데, 같은 값이 안나오면
            slow, rev = slow.next, rev.next ## rev나 slow에 값이 남도록 설계됨. 
        return not rev

Runnerで解くこれは主に接続リストの解に使用され、2つのポインタを使用します.クイックランナとスローランナです.クイックアシストはhead値の2つのグリッドをスキップし、whileを使用してパリティ/ホールを区別しながらスローアシストとrev値を調整します.スローランナーは1つのグリッドを移動し、自分の現在の値をrevに保存できます.
rev, rev.next, slow = slow, rev, slow.nextは、作成されたように、複数の割り当てによって作成されなければならないことに注目すべきである.(複数の割当てが重要)このコードをrev, rev.next = slow, rev slow = slow.next形式に変更すると、コードが正常に動作しません.
rev=1、slow=2->3の場合rev, rev.next, slow = slow, rev, slow.nextコードの場合
rev=2->3, rev.next=1,slow=3,--->rev=2->3でrevではありません.next=1はrev=2->1を表す.rev, rev.next = slow, rev slow = slow.nextコードの場合、最初の行rev=2->3、rev.next=1-->rev=2->1.2行目は、1行目のrev=slowに基づいてrevを行う.次は1
上のコードはすぐにはわかりにくいので、分かりやすいコードを書きました.

a=[2,1]
b=[3,5]
a[1]=2
b[1]=a[1]
print(a,b)
--> [2, 2] [3, 2]

a=[2,1]
b=[3,5]
a[1], b[1]=2, a[1]
print(a,b)
--> [2, 2] [3, 1]

複数の割当てを行う場合、a[1]が2に変更される前に1をb[1]に代入し、そうでない場合はa[1]=2の場合に代入する.
Pythonはオブジェクトであるため、変数に値を格納するのではなく、値の位置(参照)を変数に格納します.
前回TILで書いたのを覚えていますが、>>> id(5)とa=5, >>> id(a)の値は同じです.

21. Merge Two Sorted Lists (leetcode)

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if (not l1) or (l2 and l1.val > l2.val):
            l1, l2 = l2, l1
        if l1:
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1

優先度の高い演算子は비교연산(>, =, <) > not > and > orです.
この問題は再帰関数を用いた.
...才能を最も説明しやすい絵のようだ.


F 1が終了するとF 2が呼び出され、F 2が終了すると、F 1を繰り返し呼び出す一定の条件のコードが「再帰」と理解されるのは容易である.
l 1未満のl 1またはl 2値がない場合は、l 2値とl 1値を交換します.また、l 1が存在する場合、l 1の次のノードはまた1つの関数を実行し、このとき関数においても自分の次のノードを実行して関数を得る.
また,変数交換においてPythonは前述した複数の割当てから一時変数を作成する必要がないため,非常に便利である.
cに対して、交換する

temp=a
a=b
b=temp

利用する.

206. Reverse Linked List (leetcode)

エラーに答えました.接続リストを返すので間違っています.

    def reverseList(self, head: ListNode) -> ListNode:
        q:List=[]
        
        while head is not None:
            q.append(head.val)
            head=head.next
            
        q=q[::-1]
        return q

普通のリストではなく、リターンを接続リストとすべきです.

    def reverseList(self, head: ListNode) -> ListNode:
        def reverse(node:ListNode,prev:ListNode = None):
            if not node:
                return prev
            next, node.next = node.next, prev
            return reverse(next, node)
        return reverse(head)

頭の中だけで理解するのは難しいので論理を描きました.

node.next=Aの場合、node=1,2,3は後ろにある数字のnode=1,Aに置き換えられます.

    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None
        
        while node:
            next,node.next= node.next, prev
            prev, node = node, next
            
        return prev

このコードは重複構造を使用しています.
そして、これも頭の中で論理を描くのは難しい.

2. Add Two Numbers (leetcode)

    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None

        while node:
            next, node.next = node.next, prev
            prev, node = node, next

        return prev

    def toList(self, node: ListNode) -> List:
        list: List = []
        while node:
            list.append(node.val)
            node = node.next
        return list

    def toReversedLinkedList(self, result: str) -> ListNode:
        prev: ListNode = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node

        return node

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        a = self.toList(self.reverseList(l1))
        b = self.toList(self.reverseList(l2))

        resultStr = int(''.join(str(e) for e in a)) + \
                    int(''.join(str(e) for e in b))
                    
        return self.toReversedLinkedList(str(resultStr))

ええ、論理自体は簡単です.コードを実行するとaddTwoNumbers関数が実行されます.[接続リスト](Connection List)状態で、[逆方向](Inverse)および[一般ダイナミックリスト](General Dynamic List)に設定します.その後、resultStorでリストをマージし、intの値に変換して加算します.
次にintをstrに変換し、toReversedLinkedListでintを接続リストに変換します.
この問題は君が望んでいるものではないそうだ.

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        root = head = ListNode(0)
        
        carry=0
        while l1 or l2 or carry:
            sum=0
            if l1:
                sum +=l1.val
                l1= l1.next
            if l2:
                sum+=l2.val
                l2= l2.next
                
            carry, val = divmod(sum+carry,10)
            head.next = ListNode(val)
            head=head.next
            
        return root.next

これも論理的に描かれていますでもなぜルートに戻るの?nextをするかどうかは疑問ですが、まず本専用のハブで話題を開きました.後で修正しましょう.
数値リストを単一の値に結合します.
仮にa=[1,2,3,4,5]
リストを単一の値にマージする場合、''.join(e) for e in a)コードが使用されます.
しかし、他の方法があります.
まず.''.join(map(str, a))2番目
`functools.reduce(lambda x, y : 10 * x + y, a, 0)
このコードはreduce(計算する式、代入リスト、初期値)から構成されているようです.
xプラス1,yプラス2,-->10+2
xプラス12,yプラス3,-->120+3
xプラス123,yプラス4,-->123+4
xは1234、yは5、-->1234+5
簡単で実行しやすいコードのようです.
決して頭の中だけを回ってはいけない.必ず手でコードしなければならない.
パルイン228 pまで完了した.