leetcode
tags: leetcode 問題 Explore Problems 今回からいらないかなということで問題文は省きます アイデア peak elementという隣の要素よりも大きい要素を探すという問題です. ただし, どのpeak elementでも良いです 対数時間で計算する必要があります 下の図のよ…
tags: leetcode 問題 Explore Problems あなたはプロダクトマネジャーで現在新しい製品を開発するようにチームを指揮している. 不幸なことにあなたの製品の最新版が品質管理に落ちてしまった. それぞれのバージョンはその前のバージョンに基づいて開発されて…
tags: leetcode 問題 Explore Problems 昇順で整列された配列が既に知らないある場所で回転していると仮定しなさい (つまり, [0,1,2,4,5,6,7]は[4,5,6,7,0,1,2]になっているかも知れない) 探索する目標の値が与えられる. もし配列内に見つかったらそのインデ…
tags: leetcode 問題 Explore Problems 我々は推測ゲームをしている. ゲームは次のようである. 私が$1$から$n$の数を1つ選ぶ. 私がどの数を選んだかを推測しなければならない. 間違って推測するごとに, その数が高いか低いかを教える. 予め定義された3つの可…
tags: leetcode 問題 Explore Problems int sqrt(int x)を実装せよ xの平方根を計算し返せ. xは非負整数だと保証されている 返り値は整数であるから, 小数は切り捨てられ結果の整数部分だけが返される アイデア 全探索 全ての数を$0$から試すと答えは出ます …
tags: leetcode 問題 Explore Problems 整列された(降順に)$n$個の要素を持つ整数列numsとtargetという値を与えられたとき, numsにあるtargetを探す関数を書け. もしtargetが存在するならそのインデックスを返し, そうでなければ-1を返せ アイデア 真ん中の…
tags: leetcode 今回から解答はC++だけにしようと思います というのもPythonという言語が好きじゃない(主にポインタ操作が出来ないので挙動が分かりにくい点)からです C++の方が勉強していて楽しいというのもありますし, 言語仕様をしっかり知っているかで各…
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: 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: 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: 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) まずパスカルの三角形ってなんだよって思いますよね パスカルの三角形 下の図のような数列を三角形状…
