Pythonアルゴリズム(三、1)チェーンテーブル

1、一つのチェーンテーブルが回文構造であるかどうかを判断する
チェーンテーブルのヘッダノードheadを指定し、チェーンテーブルが返信構造であるかどうかを判断します.たとえば、1->2->1でtrueを返します.1->2->2->1、trueを返します.15->6->15、trueを返します.1->2->3でfalseを返します.ステップアップ:チェーンテーブル長がNの場合、時間的複雑度はO(N)に達し、余分な空間的複雑度はO(1)に達する.
構想1:遍歴中、すべての結果をスタックに入れ、逆順序と元の構造が同じかどうかを確認し、空間複雑度o(N)
考え方2:中間後ろの結果をスタックに入れて、一緒に比較して、0(N/2)
考え方3:遅いポインタは中間位置を指し、要素を空にし、速いポインタは中間の1つを指し、後ろの要素を前に指します.空間複雑度o(1)

from queue import LifoQueue


class Node:
    def __init__(self, data, next=None):
        self.value = data
        self.next = next

class IsPalindromeList:
    def stack_method(self, head):
        stack_ = LifoQueue()
        cur = head
        while cur is not None:
            stack_.put(cur)
            cur = cur.next
        while head is not None:
            if head.value != stack_.get().value:
                return False
            head = head.next
        return True

    # need n/2 extra space
    def stack_method2(self, head):
        if head == None or head.next is None:
            return True
        right = head.next
        cur = head
        while cur.next is not None and cur.next.next is not None:
            right = right.next
            cur = cur.next.next

        stack_ = LifoQueue()
        while right is not None:
            stack_.put_nowait(right)
            right = right.next
        while not stack_.empty():
            if head.value != stack_.get().value:
                return False
            head = head.next
        return True

    # need O(1) extra space
    def no_stack_method(self, head):
        if head == None or head.next == None:
            return True
        n1 = head
        n2 = head
        while n2.next != None and n2.next.next != None:  # find mid node
            n1 = n1.next  # mid node
            n2 = n2.next.next  # end node

        n2 = n1.next  # right part first node
        n1.next = None  # mid.next-> None
        while n2 != None:  # right part revert
            n3 = n2.next  # save next node
            n2.next = n1  # next of right node convert
            n1 = n2  # n1 move
            n2 = n3  # n2 move
            # n2.next, n1 = n1, n2
        n3 = n1  # save last node
        n2 = head  # left first node
        res =True
        while n1 != None and n2 != None:
            if n1.value != n2.value:
                res = False
                break
            n1 = n1.next
            n2 = n2.next
        # final recover linked list
        n1 = n3.next
        n3.next = None
        while n1 != None:
            n2 = n1.next
            n1.next = n3
            n3 = n1
            n1 = n2
        return res

    def print_linked_list(self, node):
        print('Linked List: ')
        while node != None:
            print(node.value, ' ')
            node = node.next
        print()

    def main(self):
        head = Node(1)
        head.next = Node(2)
        head.next.next = Node(3)
        head.next.next.next = Node(1)
        self.print_linked_list(head)
        print(self.stack_method(head) , ' | ')
        print(self.stack_method2(head) , ' | ')
        print(self.no_stack_method(head) , ' | ')
        self.print_linked_list(head)
        print("1=========================")

        head = Node(1)
        head.next = Node(2)
        head.next.next = Node(3)
        head.next.next.next = Node(2)
        head.next.next.next.next = Node(1)
        self.print_linked_list(head)
        print(self.stack_method(head) , ' | ')
        print(self.stack_method2(head) , ' | ')
        print(self.no_stack_method(head) , ' | ')
        self.print_linked_list(head)
        print("2=========================")

a = IsPalindromeList()
a.main()

2、オランダ国旗チェーンの問題
構想1:ノードを配列構造に直接入れ,並べ替えた後,接続を遍歴する.空間複雑度O(N)
構想2:空間複雑度o(1)は,6つの変数タグstartとendの変数less,eq,moreを用意し,もう1つの一時タグの次の数を用意する.

遍歴、対応する値を対応する遍歴の下

に掛ける.

最後に3つの変数を

に接続する.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next


class SmallerEqualBigger:
    def list_partition1(self, head, pivot):
        if head is None:
            return head
        cur = head
        i = 0
        while cur is not None:
            i += 1
            cur = cur.next
        node_arr = [i for i in range(i)]  #        
        i = 0
        cur = head
        for i in range(len(node_arr)):
            node_arr[i] = cur
            cur = cur.next
        self.arr_partition(node_arr, pivot)
        for i in range(1, len(node_arr)):
            node_arr[i-1].next = node_arr[i]
        node_arr[i-1].next = None
        return node_arr[0]

    def arr_partition(self, node_arr, pivot):
        small = -1
        big = len(node_arr)
        index = 0
        while index != big:
            if node_arr[index].value < pivot:
                small += 1
                node_arr[small], node_arr[index] = node_arr[index], node_arr[small]
                index += 1
            elif node_arr[index].value == pivot:
                index += 1
            else:
                big -= 1
                node_arr[big], node_arr[index] = node_arr[index], node_arr[big]

    def list_partition2(self, head, pivot):
        sh, st, eh, et, bh, bt, next = [None for _ in range(7)]
        while head != None:
            next = head.next
            head.next = None
            if head.value < pivot:
                if sh is None:
                    sh,st = head,head
                else:
                    sh.next, st = head, head
            elif head.value == pivot:
                if eh is None:
                    eh,et = head,head
                else:
                    eh.next, et = head,head
            else:
                if bh is None:
                    bh,bt = head,head
                else:
                    bh.next,bt = head,head
            head = next
        if st is not None:
            st.next = eh
            et = st if et is None else et  #          
        if et is not None:
            et.next = bh

        # return sh if sh is not None else eh if eh is not None else bh
        if sh is not None:
            return sh
        else:
            if eh is not None:
                return eh
            else:
                return bh


    def print_linked_list(self, node):
        print('Linked List: ')
        while node != None:
            print(node.value, '')
            node = node.next
        print()

    def main(self):
        head1 = Node(7)
        head1.next = Node(9)
        head1.next.next = Node(1)
        head1.next.next.next = Node(8)
        head1.next.next.next.next = Node(5)
        head1.next.next.next.next.next = Node(2)
        head1.next.next.next.next.next.next = Node(5)
        self.print_linked_list(self.list_partition1(head1, 5))
        self.print_linked_list(self.list_partition2(head1, 5))
        

SmallerEqualBigger().main()

3、ランダムポインタノードを含むチェーンテーブルをコピーする
ノードクラスのvalueはノード値であり、nextポインタは通常の単一チェーンテーブルのnextポインタと同様に、次のノードを指します.randポインタはノードクラスに追加されたポインタで、チェーンテーブルのいずれかのノードを指したり、nullを指したりすることができます.Nodeノードタイプからなるループレス単一チェーンテーブルのヘッダノードheadを指定します.このチェーンテーブル内のすべての構造のコピーを完了し、コピーした新しいチェーンテーブルのヘッダノードを返す関数を実装します.ステップアップ:追加のデータ構造を使用せず、有限数の変数のみを使用し、時間的複雑度O(N)内で元の問題を実現する関数を完了します.
構想1:ハッシュテーブルを用意し,元のノードと新しいノードをkv形式で格納し,遍歴する
構想2:元のノードを複製して、1、チェーンテーブルを再構築するのは1->1’->2->2’->3->3’2、一度に2つのノードを取り出して、もしノード1と1’ならば、主にrandポインタの問題を取得して、ここで1のrandポインタは3で、3のnextポインタは3’3で、それから1’のrandポインタを3’に設定して、順次すべての複製を完成することができます

class Node:
    def __init__(self, value, next=None, rand=None):
        self.value = value
        self.next = next
        self.rand = rand


class CopyListWithRandom:
    def copy_random_linked(self, head):
        map = {}
        cur = head
        while cur is not None:
            map[cur] = Node(cur.value)
            cur = cur.next
        cur = head
        while cur is not None:
            map[cur].next = map[cur.next] if cur.next is not None else None
            map[cur].rand = map[cur.rand] if cur.next is not None else None
            cur = cur.next
        return map[head]

    def copy_random_linked2(self, head):
        if head is None:
            return None
        cur = head
        # 1-1'-2-2'-3-3'-None
        while cur is not None:
            nor_next = cur.next
            cur.next = Node(cur.value)
            cur.next.next = nor_next  #   1'->2
            cur = nor_next
        cur = head
        #     node rand
        while cur is not None:
            nor_next = cur.next.next
            cur_copy = cur.next
            cur_copy.rand = cur.rand.next if cur.rand is not None else None
            cur = nor_next
        res = head.next
        cur = head
        while cur is not None:
            old_node = cur.next.next
            copy_node = cur.next
            cur.next = old_node
            copy_node.next = old_node.next if old_node is not None else None
            cur = old_node
        return res



    def print_linked_list(self, node):
        print('Linked List: ')
        while node != None:
            print(f'next: {node.value}, rand: {node.rand.value if node.rand is not None else None}')
            node = node.next
        print()

    def main(self):

        """
        next: 1->2->3->None
        random: 1->3, 2->1, 3->None

        """
        head1 = Node(1)
        head1.next = Node(2)
        head1.next.next = Node(3)

        head1.rand = head1.next.next
        head1.next.rand = head1
        head1.next.next.rand = None

        self.print_linked_list(self.copy_random_linked(head1))
        self.print_linked_list(self.copy_random_linked2(head1))


CopyListWithRandom().main()

4、二つの単一チェーンテーブルの交差問題
単一チェーンテーブルにはリングがあるかもしれないし、リングがないかもしれない.2つの単一チェーンテーブルのヘッダノードhead 1およびhead 2が与えられ、この2つのチェーンテーブルは交差するか、交差しないかのいずれかである.2つのチェーンテーブルが交差している場合は、交差する最初のノードを返します.交差しない場合はnullを返します.要求:チェーンテーブル1の長さがN、チェーンテーブル2の長さがM、時間複雑度がO(N+M)、余分な空間複雑度がO(1)に達してください.
まず、ループがあるかどうかを判断します.
考え方1:ハッシュ表を用意し、まずAチェーン表を遍歴してハッシュ表に入れ、Bチェーン表が存在するかどうかを遍歴すればよい
考え方2:2つの変数、1つの遅いポインタ、1つの速いポインタを準備します

速い針は毎回2歩歩いて、遅い針は1歩

歩きます

はすぐにリングにぶつかって、それから速いポインタはheadに戻って、速くゆっくり歩いて1歩ずつリングに入る位置です.逆にNoneが無環

に遭遇する
a、無環の場合

は、head 1の長さ、end 1、head 2の長さ、end 2

の4つの変数を用意する.

end 1はend 2に等しいリングであり、長いチェーンテーブルを別の長さに等しくしてから、一緒に遍歴すると同じ点

が見つかる.
b、一有環、一無環、交差不可能、単鎖表の定義に背く
c、すべて環の情況があって、交点の3種類の情況:交差がなくて、1つの交点、2つの交点

の交点:4つの変数を用意し,ループの有無を判断し始めると,入ループノードloop,loop 1,2が等しい

が得られる.

無交点または2つの交点:loop 1と2は等しくなく、loop 1からloop 2に遭遇したか否かを遍歴して判断する

を継続する.

class Node:
    def __init__(self, data, next=None):
        self.value = data
        self.next = next


class GetIntersectNode:
    def get_intersect_node(self, head1, head2):
        if head1 is None or head2 is None:
            return None
        loop1 = self.get_loop_node(head1)
        loop2 = self.get_loop_node(head2)
        #    
        if loop1 is None and loop2 is None:
            return self.no_loop(head1, head2)
        #    
        elif loop1 is not None and loop2 is not None:
            return self.both_loop(head1, loop1, head2, loop2)
        #         
        return None

    def get_loop_node(self, head):
        if head is None or head.next is None or head.next.next is None:
            return None
        n1 = head.next  # slow pointer
        n2 = head.next.next  # fast pointer
        while n1 != n2:
            if n2.next is None or n2.next.next is None:
                return None
            n2 = n2.next.next
            n1 = n1.next
        n2 = head
        #         
        while n1 != n2:
            n1 = n1.next
            n2 = n2.next
        return n1

    def no_loop(self, head1, head2):
        if head1 is None and head2 is None:
            return None
        cur1 = head1
        cur2 = head2
        n = 0
        while cur1.next is not None:
            n += 1
            cur1 = cur1.next
        while cur2.next is not None:
            n -= 1
            cur2 = cur2.next
        if cur1 != cur2:
            return None
        cur1 = head1 if n > 0 else head2  #    
        cur2 = head2 if cur1 == head1 else head2  #    ，  
        n = abs(n)
        while n != 0:
            n -= 1
            cur1 = cur1.next
        while cur1 != cur2:
            cur1, cur2 = cur1.next, cur2.next
        return cur1

    def both_loop(self, head1, loop1, head2, loop2):
        cur1 = None
        cur2 = None
        if loop1 == loop2:
            cur1,cur2,n = head1,head2,0
            while cur1 != loop1:
                n += 1
                cur1 = cur1.next
            while cur2 != loop2:
                n -= 1
                cur2 = cur2.next
            cur1 = head1 if n>0 else head2
            cur2 = head2 if cur1==head1 else head1
            n = abs(n)
            while 0 != n:
                n -= 1
                cur1 = cur1.next
            while cur1 != cur2:
                cur1 = cur1.next
                cur2 = cur2.next
            return cur1
        else:
            cur1 = loop1.next
            while cur1 != loop1:
                if cur1 == loop2:
                    return loop1
                cur1 = cur1.next
            return None

    def main(self):
        #  、   
        # 1-2-3-4-5-6-7-None
        head1 = Node(1)
        head1.next = Node(2)
        head1.next.next = Node(3)
        head1.next.next.next = Node(4)
        head1.next.next.next.next = Node(5)
        head1.next.next.next.next.next = Node(6)
        head1.next.next.next.next.next.next = Node(7)

        # 0-9-8-6-7-None
        head2 = Node(0)
        head2.next = Node(9)
        head2.next.next = Node(8)
        head2.next.next.next = head1.next.next.next.next.next  # 8->6
        print(self.get_intersect_node(head1, head2).value)  # 6

        #    
        # 1->2->3->4->5->6->7->4...
        head3 = Node(1)
        head3.next = Node(2)
        head3.next.next = Node(3)
        head3.next.next.next = Node(4)
        head3.next.next.next.next = Node(5)
        head3.next.next.next.next.next = Node(6)
        head3.next.next.next.next.next.next = Node(7)
        head3.next.next.next.next.next.next = head3.next.next.next # 7->4

        # 0->9->8->2...
        head4 = Node(0)
        head4.next = Node(9)
        head4.next.next = Node(8)
        head4.next.next.next = head3.next # 8->2
        print(self.get_intersect_node(head3, head4).value)  # 2

        #     
        # 0->9->8->6->4->5->6..
        head5 = Node(0)
        head5.next = Node(9)
        head5.next.next = Node(8)
        head5.next.next.next = head3.next.next.next.next.next # 8->6
        print(self.get_intersect_node(head3, head5).value)  # 6
        # 6，2，6


GetIntersectNode().main()