tags: leetcode 問題 Explore Problems アイデア 空でない配列のそれぞれの要素が1つの非負整数を表現しているとします．このとき，この配列に1を足した数を表現する配列を返せという問題です．ただし，配列の先頭の要素が最上位の数を表します． 例えば，[1…

tags: leetcode 問題 Explore Problems アイデア 配列の中で最も大きな要素が他のどの要素よりも少なくとも2倍はあるかどうか探せ．あれば，そのindexを，なければ-1を返せという問題です． 最も大きな数を変数に格納すれば良いです． 配列の大きさは[1, 50]…

tags: leetcode 問題 Explore Problems アイデア valを持つノードのポインタを返せという問題です．見つからない場合はNULLを返します． 再帰的探索すれば良いです． 解法 base case 現在のノードのみを見て，そのノードの保持する値がvalと同じなら，そのノ…

tags: leetcode 問題 Explore Problems アイデア 空でない整数の配列が与えられた時に，1つ以外は2回現れ，その1つは1回のみ現れる．その際の1つだけ現れるものを見つけろという問題です． アルゴリズムは線形時間に解けないといけず，追加の記憶領域を使わ…

tags: leetcode めちゃくちゃ久々に問題を解きます． 関係ないですが，インターン2社行くことになりそうです^^ 問題 Explore Problems アイデア 配列内に複数回出てくる数があるかどうかを探せという問題です． これは連想配列を使えば簡単に解くことが出来…

tags: leetcode 旅行で東京を離れていました．何もしていませんでした．何もしないと本当に何がしたいか自ずと分かってくるので良いかも知れません． 問題 Explore Problems アイデア Trieとは文字列を高速に検索するためのN-aryの木構造のことです．応用先…

tags: leetcode 問題 Explore Problems アイデア HashMapを実装せよという問題．この手の問題ってHash関数を決めるのが面倒だし，この手の問題はコードで実装するというより口頭で説明出来れば良い気がする． だから，実装は適当です． put(key, value): Has…

tags: leetcode 学科の研究室の選抜(？)の第一段階に自分の名前がなくて萎えています． 研究室に顔を出しても入れなかったらどうしようか…と思い鬱．とりあえず実装をします． 問題 Explore Problems アイデア 組み込みライブラリを使わずにHashSetを設計せ…

tags: leetcode こういう実装系の問題をやっていきたいのでやっている系です． 次にHash系とTrieを実装したら，多分普通の問題を解きます． 問題 Explore Problems アイデア Circular Queueとは要するにFIFOで，最後の部分が先頭に繋がっているようなデータ…

tags: leetcode インターンの応募ってこの時期多いのか中々返信が来ないですよね 待っている間に出来ることはたくさんあると思うんですが，私は待たされている状態にパフォーマンスが落ちるので出来ればあっちから連絡が欲しいですね(笑)←笑(笑) 問題 Explor…

tags: leetcode 問題 Explore Problems アイデア 二分木のイテレータを作れという問題です． next()とhasNext()というメソッドが時間，空間計算量を平均でそれぞれ$O(1)$，$O(h)$となるようにするという制約があります 解法1 木を配列に変換して，そこからノ…

tags: leetcode 志望度の高かったインターンに落ちて気持ちが萎えています．でも逆にやりたいことがはっきりしました． 問題 Explore Problems アイデア ある要素よりも左の要素の和と右の要素の和が等しい要素のindexを返せという問題です． 解法 最初に配…

tags: leetcode 問題 Explore Problems アイデア N-ary木の深さを測る問題です． 基本的に二分木と同じように解けます．(繰り返し文を使う必要があるかどうかくらいです) 解法1(recursive) 再帰関数を使ってDFSをして，深さを求めます． 根がないなら$0$ そ…

tags: leetcode Classicalの意味を一回辞書で調べてほしいと思う日々． 問題 Explore Problems アイデア 深さごとにノードの値をまとめて配列に入れ，それらの配列を1つの配列に格納します． 単にBFSをするという問題ですね．それにはQueueを使うのが便利で…

tags: leetcode 問題 Explore Problems アイデア おさらいをすると二分木の場合はPreorder, Inorder, Postorder traversalはそれぞれ根のノードがいつ探索されるかで分類されており， Preorder(根→左→右) Inorder(左→根→右) Postorder(左→右→根) 今回は2つよ…

tags: leetcode 最近カップ中本にハマってしまいました． 問題 Explore Problems アイデア おさらいをすると二分木の場合はPreorder, Inorder, Postorder traversalはそれぞれ根のノードがいつ探索されるかで分類されており， Preorder(根→左→右) Inorder(左…

tags: leetcode 問題 Explore Problems アイデア 与えられた木の根から葉までのたどる際に，与えられた値となるような経路はあるかという問題です． 解法 与えられた値にノードの値の合計がなるということは，与えられた値からノードの値を引いて$0$になるか…

tags: leetcode 問題 Explore Problems アイデア 与えられた木が左右対称な木か判断する問題です． これは与えられた木の部分木も左右対称となるので，その結果を用いて解くことにします． 解法1(recursive) 下の図のようになっているかを再帰的に関数を使っ…

tags: leetcode 風邪は治ったけど，花粉症がキツイ． 次の総理大臣は花粉症を撲滅してほしい． 問題 Explore Problems アイデア 木を探索する際の順序として以下の図ように Inorder(左→根→右) Preorder(根→左→右) Postorder(左→右→根) があります ノードが5…

tags: leetcode 非常に久しぶりです． 案の定，風邪を引いていました．皆さんも季節の変わり目には気を付けて下さい^_^(コロナじゃなくてよかったーーーーーー) 問題 Explore Problems アイデア 木を探索する際の順序として以下の図ように Inorder(左→根→右)…

tags: leetcode 問題 Explore Problems アイデア 要素数がn + 1の整数の配列が与えられた時，要素は[1, n]であり，鳩の巣原理より少なくとも1つの要素は重複しています． このうち，重複している要素を探せというもの． 注意点は 配列を操作してはいけない．…

tags: leetcode 問題 Explore Problems アイデア 既に昇順に整列した整数の配列を与えられた時，足すとある目的の数になるような2つの数を探せという問題．ただし，同じ要素を2回使ってはいけないのと，1-indexedなことに注意． 有名なTwo Sumを改題したもの…

tags: leetcode 問題 Explore Problems アイデア 2つの配列の共通部分を求めます． ただし，同じ要素でも複数個あれば複数個を答えの配列に格納します． 解法 この問題は2つの配列に重複した要素を重複した回数を考慮して答えの配列に入れます． この場合，…

tags: leetcode 問題 Explore Problems アイデア 2つの配列のintersection(交叉･共通部分)を求めよという問題． このような問題ではsetを使うと楽に求めることが可能です 解法 nums1をstd::unordered_setに変換します std::unordered_setはハッシュ，std::se…

tags: leetcode 問題 Explore Problems アイデア 整列済み配列をある点で回転させた配列の最小の要素を見つけるという問題．要素に重複がないという問題は以前やったことがありますが，今回は重複を認めます． 解法 以下のように分類して同じように解けます…

tags: leetcode 問題 Explore Problems アイデア 文字の入った整列済みの配列の中からtargetよりも大きい中で最小の文字を見つけるという問題です． 数字の形が変わっただけでただ比較すれば良いだけです． 解法 zより大きいのはaであるように大きさは循環す…

tags: leetcode 問題 Explore Problems アイデア 与えられた正整数numが平方数か調べます．sqrtは使ってはいけないようです． 大きい数の平方数は大きくなるという単調性を活かして二分探索が出来ると考えられます． 解法 探索する範囲の左端を1として右端を…

tags: leetcode 問題 Explore Problems アイデア 整列済みの配列とkとxが与えられた時に，xに最も近いk個の要素を見つけるという問題．返り値の配列は昇順で出来るだけ小さい要素から入れます． 整列済みなので二分探索が使えそうです． 解法 x以上の最小の…

tags: leetcode 問題 何故かExploreだと名前が"Search for a Range"になっていますが, 同じ問題です Explore Problems アイデア 昇順に整列された配列のうち, targetと一致するものの始点と終点を求めろというもの. 対数時間で求めよという指定から二分探索…

tags: leetcode 問題 Explore Problems 前にやったある点を起点にして回転している配列の問題の考え方が利用できそうですね アイデア 与えられる配列は昇順な配列の一部を回転したものです 真ん中にある値が増加する数列の始点の左側にあるのか右側にあるの…