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

LeetCodeについて

Leetcodeはデータ構造やアルゴリズムについて学習できるサイトです。

外資IT企業の面接で出題されるコーディング試験に近い問題が多く用意されており、ブラウザ上で実際にコーディングしながら解答することができます。

無料プランでも相当数の練習ができ、プレミアムプランでは特定の企業で出題された問題を中心に練習することもできます。

Google,Amazon,Meta,Appleなどの有用な試験対策として必ずと言って良い程に挙げられます。

LeetCodeで解答するための基礎知識

Pythonを使用するという前提で、解答時に必要なことを整理します。

正確さや網羅性よりも、とにかく早くLeetcodeで解答するために必要なことをまとめます。

解答の作成はクラスと関数を書く

Leetcodeの解答欄には、解答用のクラスとその内部に関数が用意されています。

クラスはPythonがもつ機能で、オブジェクト指向でプログラムを組むときなどに使用されます。

あるオブジェクト(データなど)とその振る舞い(データがどのように加工されるか)を決めます。

関数には解答に必要な入力と解答(返り値)の型が指定されているので、それらを使って解答のコードを書きます。

入力の受け取り方

Atcoderでは入力を受け取るために数行コードを書きますが、Leetcodeでは解答用のクラスの中にある関数に入力が用意されており、その変数をそのまま使用できます。

解答は返り値として返す

クラス内にある関数に解答コードを書くことができたら、returnで返り値を用意して解答とします。

稀に入力された変数内のデータを変更するだけの問題もあります。

returnがないとエラーになります。

解答は型ヒントで指定された型で返す

型ヒントはPythonが持つ機能です。

関数の返り値はintやリストですよ。と最初に型を書いておくことで、コードを読みやすさや変更をしやすくなります。

Leetcodeでは、型ヒントで指定された型で解答をしなければエラーになります。

データ構造

Leetcodeや、その先のコーディング面接で出題されるデータ構造について整理します。

連結リスト

連結リストは鎖のように繋がったリストです。

連結リストは、各要素とそれらを入れる箱(リスト)がある訳ではないです。

各要素が次の要素の場所を示す情報を持つことで数珠のように繋がったものを作り上げます。

※関連記事：連結リストの概要・イメージ・実装・使い方を整理

C言語では、変数などがコンピューターのメモリ上のどこに保持されているかを示すポインタという機能がありますが、Pythonにはポインタはないため、次の要素をそのまま保持するように見えています。

・解答欄に連結リストの各ノードのクラスが定義されています。

※実際にはコメントアウトされている

# 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はリスト型に見える

これは各ノードのvalだけを集めて表示している。実際にはvalとnextを持っており、nextには次のノードが保持されている。

[1,2,3,4,5]

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

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

初めて見た時はわけがわからないが、valには値、nextには次ノード(valとnext)が含まれており、ノードがマトリョーシカのように入れ子構造になっている。

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)

・ListNode(2)

→valは2

→nextはListNode(3)

・ListNode(3)

→valは3

→nextはListNode(4)

・ListNode(4)

→valは4

→nextはListNode(5)

・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:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

Leetcodeでは、二分木の各ノードはval, left, rightを持ちます。

valにはそのノードの値、leftには左の子ノード、rightには右の子ノードが入ります。

leftとrightは、valのようにint型の値を持たず、別のTreeNodeのインスタンスを持ちます。

インスタンスは、TreeNodeのようなクラスが実際の値を持ったものです。二分木の全てのノードはTreeNodeという設計図を元に作られたインスタンスです。

それぞれが値と左右の子を持ちます。

左右の子は、さらに値と左右の子を持ちます。根に近いノードがより多くの子ノードを内包しています。