キューはFIFO（先入れ先出し）のデータ構造です。 キューがもつ操作は add(item)：要素を追加する remove()：先頭の要素を削除する peek(): 先頭の要素を返す isEmpty(): キューが空の場合にTure class Queue(): class Node(): def __init__(self, data): se…

問題 連結リストとある値xが与えられたときにxの前にxよりも小さい値が、後にxよりも大きい値が来るようにする。 考え方 xよりも小さい数のリストと大きい数のリストを作り、最後にくっつける。 時間計算量はO(N) コード例 import random class Node(): def …

問題 間のnodeだけ与えられたときにそれを削除する 考え方 削除したいnodeが次のnodeに当たるように書き換えれば良い コード例 class Node(): def __init__(self, d): self.data = d self.next = None def appendToTail(self, d): end = Node(d) n = self wh…

問題 単方向連結リストにおいて末尾から数えてk番目の要素を返す。 考え方 連結リストの長さがわからないという前提で考える。 ランナーテクニックを利用する。 ２つのポインタを用意する。 前からk番目からスタート 初めからスタート １つ目のポインタが最…

問題 ハノイの塔 ３つの塔とN枚のサイズの異なる円盤がある。１つの塔から別の塔に移動させる。 １度に１つの円盤しか動かせない。 塔の一番上の円盤だけ移動できる 円盤はそれよりも大きいものの上にしか置けない。 考え方 まずは具体的にやってみる。塔をs…