tags: 情報 ROT13とは? 前に触れたことがあるんですが, 暗号化の手法です アルファベットを13文字分ずらす手法のことをROT13言います 今回はROT13を拡張子, 13以外でも利用できるようにしてC++で実装します 実装 実装は下のrotのようにしました C++をよく分…

tags: 情報 Pythonのsplitメソッド Pythonにはsplitという組み込みメソッドがあり, これを使うことで指定した区切り文字で文字列を区切ることが出来ます 例えば txt = "eeic is wonderful" x = txt.split() print(x) # ['eeic', 'is', wonderful] このように…

tags: leetcode 問題 Explore Problems $2$から$9$までの数を含む文字列が与えられたとき, その数が表現できるであろう全てのありうる文字の順列を返せ 数字から文字への対応(電話のボタンのような)は下のように与えられている. $1$はどんな文字列とも対応し…

tags: leetcode 問題 Explore Problems 異なる整数の集まりを与えられたとき, 全てのありうる順列を返せ 解法(recursive) 与えられた配列の順番を色々変えれば良いわけです 下のように全ての添字の組み合わせで要素を交換すれば全てのありうる配列を生成でき…

tags: leetcode 問題 Explore Problems 幅が$1$のヒストグラムのバーの高さを表した非負整数が$n$個与えられたとき, ヒストグラムの最も広い長方形の領域を見つけろ 解法(recursive) まずはナイーブに考えます そうすると長方形の左端と右端の組み合わせを全…

tags: leetcode 問題 Explore Problems 二分木が与えられた時, そのノードの値の層ごとの順番での走査を返せ(つまり, 左から右へ, 層ごとに) 解法1(recursive) 再帰的な構造を使います(無限回目) 返り値の二次元配列を用意します この配列をretとしてret[d][…

tags: 情報 要約 AtCoderはデータ構造とアルゴリズムを勉強するのに効率が良いと思って始めた 効率よく勉強するのが目的なら他によい手段が見つかった AtCoderは良いサービス LeetCodeの方が自分には向いてそう 始めた理由 始めたのはデータ構造とアルゴリズ…

tags: leetcode 問題 Explore Problems 二分木を与えられた時, そのノードの値のinorder traversalを返せ 追加: 再帰的な解法はありきたりである. 反復的に解くことはできるか? 解法1(recursive) 木の探索順序 木を探索する際の順序として以下の図ように Ino…

tags: leetcode 問題 Explore Problems $n$組のかっこが与えられた時に, 全ての適切なかっこの組み合わせを全て生成する関数を作れ 解法(recursive) 左右のかっこの個数がそれぞれ$n$個である文字列を生成するという問題です 下のように空の文字列に(と)を繋…

tags: leetcode 問題 Explore Problems 二分木を与えられた時, 最大深度を見つけろ 最大震度は根から最も遠い葉までの最長の通り方で通るノードの数である 注意 葉は子のいないノードである 解法(recursive) 二分木の再帰的な構造から再帰関数を使って問題を…

tags: leetcode 問題 Explore Problems あなたは階段を上がっている. 最上段へたどり着くのに$n$段が必要である. 毎回あなたは$1$段もしくは$2$段上がることができる. 異なる方法で何回最上段まで上がることができるか? 注意 与えられる$n$は正の整数である.…

tags: leetcode 問題 Explore Problems 2つの二分木を与えられた時に, それらが同じかどうかを調べる関数を書け 2つの二分木は構造的に同じでノードが同じ値を持っていたら同じとみなされる 解法(recursive) 二分木は再帰的なデータ構造を持つので再帰的に解…

tags: leetcode 問題 Explore Problems 整数$n$と$k$が与えられた時, $1 \dots n$から考えられる全ての$k$個の数を返せ 解法 再帰的に解きます 二次元配列resと一次元配列tmpを用意します 再帰関数を使ってtmpに数を入れます 基底はnum == kとなるときで, こ…

tags: leetcode 問題 Explore Problems 空のセルを埋めることで数独パズルを解くプログラムを書け, 数独の解答は次の規則を全て満たす必要がある. 各行で1-9の数字がそれぞれ1回だけ出てくる. 各列で1-9の数字がそれぞれ1回だけ出てくる, 9x9の格子の中にあ…

tags: 情報 satoru-takeuchi.hatenablog.com mizchi.hatenablog.com 流行りなのかな?ということで考えてみます プログラミング歴 こんなのでも情報系の学部に所属しています 大学1年冬...アルゴリズムの授業でPythonを扱った. 二次元配列が分からなかったの…

tags: leetcode 問題 Explore Problems n-queensパズルはどの2つのクイーンもお互いに攻撃できない位置にnxnのチェス盤にn個のクイーンを配置する問題です 整数nを与えられた時, n-queensパズルへの異なる解答の数を返せ 解法 有名な問題ですね "N-Queens II…

tags: leetcode 問題 Explore Problems $m \times n$行列からある値を取り出す効率的なアルゴリズムを書け.この行列は以下の特徴がある 各行の整数は昇順に左から右へ整列されている 各列の整数は昇順に上から下へ整列されている 解法1(recursive) 再帰的に…

tags: leetcode 問題 Explore Problems 二分木を与えられた時, それが正しい二分探索木(BST)か決めなさい BSTが以下のように定義されると仮定しなさい あるノードの左部分木はそのノードの値よりも小さい値のノードしか持っていない あるノードの右部分着は…

tags: leetcode 問題 Explore Problems 整数の配列numsを受け取った時, 降順に配列を整列せよ 制約: $$ |nums| \in [1, 50000] $$ $$ nums[i] \in [-50000, 50000] $$ 解法 色々な解法が考えられます. この問題が"Recursion"の一種として取り上がられている…

tags: leetcode 問題 Explore Problems 整数$n$が与えられた時, $1 \dots n$を保持する構造的に一意なBST(2分探索木)を生成して, 配列に入れて返せ [root, root's left, root's right,...]のようにBSTは表示されています 解法 この問題は動的計画法(DP)を用…

tags: leetcode 問題 Explore Problems 最初の行では0と書く.そして,全ての次の行で前の行の0を01と置き換え, 1を10と置き換える. 行NとindexKが与えられた時, 行NのK番目の記号を返せ.(indexは$1$から始まる) 注意: $N \in [1, 30], N \in \mathbb{N}$ $K \…

tags: その他 ダラダラ過ごさないように自分用に書きます 生産性とは 別に子供がいくら産めるかとかそういう話ではないです ここでは自分が時間当たりでこなせるタスクが多いことを生産性が高いとします 十分な睡眠が取れている 必要なこと 夜中に飲み会をし…

tags: leetcode 問題 Explore Problems 2つの整列済みのリストを合併し, 新しいリストとして返せ. 2つのリストの先頭のノードを切り出して新しいリストは作られます 解法1(iterative) この解法ではdummyというポインタを作ります.このポインタが指す先をtail…

tags: leetcode 問題 Explore Problems $x^{n}$を計算するpow(x, n)を実装せよ 注意: $$ -100.0 < x < 100.0 $$ $$ n \in [- 2^{31}, 2^{31}) $$ 解法1(recursive) 愚直に実装するとxをn回掛ける必要があるので時間計算量が$O(n)$となり効率が悪いです 改善…

tags: leetcode 問題 Explore Problems フィボナッチ数列とはある数が前の2つの数を足した数であるような数列で, $0$, $1$から始まるようなものである.つまり F(0) = 0, F(1) = 1 F(N) = F(N-1) + F(N - 2), for N > 1 $N$が与えられた時, F(N)を求めろ 解法…

tags: leetcode 問題 Explore Problems 片方向リストを反転させよ 追加: recursiveとiterative両方で実装せよ 解法1(recursive) 以前の文字列の問題と同じです 反転された部分と反転されていない部分に分けます 反転された部分に反転されていない部分の先頭…

tags: leetcode 問題 Explore 普通 非負整数のindex, $k \leq 3$を与えられた時, パスカルの三角形の$k$番目の段を返せ 0段目から始まることに注意せよ 追加: 余分に$O(k)$メモリだけを使うようにアルゴリズムを最適化できるか? 解法1 最適化を気を付けなけ…

tags: leetcode 問題 Explore 普通 非負整数numRowsが与えられた時, パスカルの三角形(Pascal's triangle)の最初のnumRows段を生成せよ 解法1(recursive) まずパスカルの三角形ってなんだよって思いますよね パスカルの三角形 下の図のような数列を三角形状…

tags: leetcode 問題 Explore 普通の 連結リストが与えられ, 全ての隣り合った2つのノードを交換し先頭のノードを返せ リストのノードの値は変更してはいけなく,ノード自身を変えることだけができる 解法1 連結リスト まずは連結リストが何かを理解する必要…

tags: leetcode ということで今回からはRecursion Iの問題を扱おうと思います 再帰関数 再帰関数に関係する問題を解くので前回の再帰関数に関して扱った記事を読んでくれると再帰関数について苦手意識がなくなっていいかもしれません propyon.hateblo.jp 再…