【LeetCode】解答前に知っておくと役に立つかもしれない情報【Python】

データ構造

LeetCodeにおける連結リストの各ノードの定義

・解答欄にクラスが定義されている　※実際にはコメントアウトされている

# Definition for singly-linked list.
 class ListNode:
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next

# Definition for singly-linked list.

class ListNode:

def __init__(self, val=0, next=None):

self.val = val

self.next = next

・inputはリスト型に見える

[1,2,3,4,5]

1	[1,2,3,4,5]

・↑こちらのinputを解答欄でprintしてみると以下のように出力される

ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}}}}

1	ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}}}}

分解してみると↓のようになっており、連結リストの先頭は2番目以降の要素を抱えた入れ子構造のようになっている

ListNode(1)のvalは1,nextはListNode(2)のval

ListNode(2)のvalは2,nextはListNode(3)のval

ListNode(3)のvalは3,nextはListNode(4)のval

ListNode(4)のvalは4,nextはListNode(4)のval

ListNode(5)のvalは5,nextはNone

連結リストの作成

#連結リストの各ノードの定義
class ListNode:
     def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

#リストから連結リストを作成
class Solution(object):        
    def test(self, head: ListNode) -> ListNode:
        list = [1,2,3,4,5]
        _ = ListNode(0)
        for i in list:
            _.next = ListNode(i)
            _= _.next

#連結リストの各ノードの定義

class ListNode:

def __init__(self, val=0, next=None):

self.val = val

self.next = next

#リストから連結リストを作成

class Solution(object):

def test(self, head: ListNode) -> ListNode:

list = [1,2,3,4,5]

_ = ListNode(0)

for i in list:

_.next = ListNode(i)

_= _.next

何か違う気がする。要確認

連結リストの中央の要素の取得

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, val=0, next=None):

# self.val = val

# self.next = next

#連結リストの各ノードの定義
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

#中央の要素の取得
class Test:
    def getMid(self, head):
        #一度に1個、2個進む2種類のポインタを作成
        slow, fast = head, head.next
        #fast、fastの次のノードがある限り繰り返す
        while fast and fast.next:
            #slowポインタは次の要素へ
            slow = slow.next
            #fastポインタは次の次の要素へ
            fast = fast.next.next
        #slowポインタを返す
        return slow

#連結リストの各ノードの定義

class ListNode:

def __init__(self, val=0, next=None):

self.val = val

self.next = next

#中央の要素の取得

class Test:

def getMid(self, head):

#一度に1個、2個進む2種類のポインタを作成

slow, fast = head, head.next

#fast、fastの次のノードがある限り繰り返す

while fast and fast.next:

#slowポインタは次の要素へ

slow = slow.next

#fastポインタは次の次の要素へ

fast = fast.next.next

#slowポインタを返す

return slow

slowポインタは毎回1つ、fastポインタは毎回2つ進むことで、

fastポインタが連結リストの終端に到着したときに、slowポインタはちょうど連結リストの中央の要素を持っていることになる。

二分木

LeetCodeにおける二分木の各ノードの定義

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Definition for a binary tree node.

class TreeNode: