キューは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…

スタックの実装です。 スタックのデータ構造はLIFO（後入れ先出し）です。 スタックは以下の操作ができます。 pop: スタックの一番上のデータを削除する push: スタックの一番上にデータを追加する peek: スタックの一番上の要素を返す isEmpty: スタックが…

問題 ある集合の全ての部分集合を返す 考え方 再帰的に考える。 N-1この要素の全ての部分集合がわかっているときに、次の部分集合はどうなるか？ N個目の要素を加えたsubsetsを元のsubsetsに加えれば良い。 f(n) = f(n-1) + {f(n-1), set[n]} コード例 def a…

問題 ソートされた配列からA[i] = iとなるindexを探す。配列が重複した値を持つ場合にどうするか。 考え方 2分探索的な方法で探す。 重複した値がある時は少しややこしくて、結局両側を探すしかない。ただし、探す範囲は mid > A[mid]ならば、左側はindexが0…

問題 Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded. You can assume that the messages are decodable. For example, '001' is not allowed. 考え方 stringが与えられた時のデコード方…

問題 r行c列のグリッドに障害物がいくつかある。左上から右下にいく経路を探索する。ただし、動ける方向は右と下のみ。 考え方 グリッド (i,j)にたどり着けるかどうかをTrue or Falseで格納する。flg[i][j]は左側flg[i][j-1]と上側flg[i-1][j]を見れば到達で…

問題 n段の階段を上がるときに、１ステップで１段、２段、３段のどれかであがれるときに考えられる上がり方の合計は？ 考え方 n段目にはn-1段目から１段で、n−２段目からは2段、n-3段目には３段であがれる。 つまり、f(n) = f(n-1) + f(n-2) + f(n-3)である…

毎回探して迷子になるのでまとめました。CUDA Toolkitのまとめです。 最新版 ダウンロードページ https://developer.nvidia.com/cuda-downloads 必要な条件 Installation Guide Linux :: CUDA Toolkit Documentation 現在のリリース一覧 https://developer.n…

問題 ソートされていない連結リストから重複した要素を削除する。 考え方 一度出てきた値はhash tableに保存しておいて、もう一度出たら削除する。 一度リスト全体を見ればいいので、時間計算量はO(N) コード例 # 双方向連結リスト class LinkedList(): def …

連結リストの性質 要素の追加と先頭からの要素の削除が一定時間でできます。 k番目の要素にアクセスするにはk回計算が必要になります。 単方向連結リスト pythonでの実装です。 class Node(): def __init__(self, d): self.data = d self.next = None def ap…

KerasでbackendにTensorlfowを使っていると、GPUメモリを全て食ってしまう。 Kerasのバックエンドに使っているTensoflowに設定を加える。 tf.ConfigProtoで設定を加えたら好きなように制限できる。 以下の設定だと必要な分だけ確保してくれる。 import tenso…

問題 Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree. 実装 再帰的に実装します。Noneでなければ展開するようにしています…

内容 lispで使うcar, cdrをpythonで実装してみました。 def cons(a, b): def pair(f): return f(a, b) return pair def car(pair): def f(a, b): return a return pair(f) def cdr(pair): def f(a, b): return b return pair(f) if __name__ == "__main__": …

問題 ２つの文字列str1, str2が与えられた時に、str2がstr1を回転させたものであるか調べる。 例えば str1 = "apple" str2 = "pplea" ならtrue である。 考え方 回転させたものなら str2 + str2としたものの中にstr1が含まれるはずである。 ただし、str1.len…

問題 M*N の行列において、(i, j)が0なら、その行iと列jを全て０にする。 考え方 (0, 0)から０の成分を見つけて、変換していくと全て０に変わってしまうので、まずは０の成分のある位置を格納する。 何個あるかわからないので、可変長配列(C++ではvector型)…

問題 N*Nの行列を90度回転させる 考え方 あまりたくさんのメモリを使いたくないので、１つの値だけを保持して回転させたい。 回転させると(i, j) -> (j, N-i)に移る。移った先を考えると、 (j, N-i)-> (N-i, N-j) (N-i, N-j) -> (N-j, i) (N-j, i) -> (i, j)…

問題 文字列を圧縮する。同じ文字が続いた数を使って表現する。 例：abbccccddd -> a1b2c4d3 とする。ただし、圧縮した方が、文字数が増えている場合は元の文字列を変えす。 考え方 元の文字列を１つずつ進んでいく。sに文字を入れて、s == str[i]である時に…

問題 ２つの文字列が与えられた際に、１回の変換(文字の追加、削除、置き換え）で等しくなるか 考え方 文字列の長さが等しい時は１文字だけ違ったら、置き換えで対応できます。 str1[i] != str2[i]となる数を判定して、これが１以下ならture。 文字列の長さ…

問題 整数を要素にもつarrayから、どれか１つの要素を除いた積のarrayを出力する。 ただし、割り算は使えない。 考え方 arrayの長さをNとする。 単純に全て計算するとの時間計算量がかかる。 出来るだけ前の値を用いて計算したい。 前の変数までの積と次の変…

問題 文字列から回文が作れるか判定する 考え方 文字の数を数えて、文字の種類Mに対して、M-1個の文字が偶数回出れば良い。 アクセスを早くするためにhashを利用する。 計算量 文字列の長さをN、文字の種類をMとする。N >= M である。 hashに記録する際にはO…

エラー内容 環境:MacOS Mojave 文字列を出力するだけのC++のコードをコンパイル > g++ -std=gnu++11 sample.cpp とすると、以下のwarningが出る warning: section "__textcoal_nt" is deprecated.section __TEXT,__textcoal_nt,coalesced,pure_instructions …

やること 例えば以下のようなファイルを考えて、これを１列目の数字が昇順になるように並べます。 sample.txt 13 0.8 48 7.9 33 14.1 63 19.3 25 20.6 14 22.6 29 24.8 68 28 47 32.9 94 35.1 やることはまず１列目の最大値を求めて、次に１列目を並び替えま…

Macのリモートから『画面共有』で作業をしていて最近気づいたが、ログイン先がマルチディスプレイの状態でリモートから入ると、『画面共有』の画面の中に全て入るのでめちゃくちゃ見にくい。 矢印もめっちゃ小さくなる。