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: その他 動機 一般的に大学3年生にもなると就職とか研究が気になってきますよね． 僕の場合は ｢東大だし情報系だし就活は別に何もしなくてなんとかなるでしょ(笑)｣ と思って生きていたのですが，留年しそうになって考えが変わりました． というのも留年…

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

tags: 情報 shallow copyとdeep copyの違いとか曖昧だけど必要になったら毎回ググればえーやろ^^ という精神で生きていたらググれない状況でそれを聞かれて破滅しました．こんなのも分からず生きていてごめんなさい...と思いましたが，他人がこれを知らなく…

tags: 情報 もう電気回路なんてしないなんて言わないよ絶対(なんて言わないよ絶対) 1 電気回路←うわぁ 前回インターンしようと思った会社のCTOが電気系でうわぁ...と思ったら案の定落ちていました． もう電気のことなんか考えたくもないのでC言語の話をしま…

tags: 情報 関数型プログラミングがしたい 業務で関数型プログラミングがしたいです．理由は書いていて楽しいからです． それだけの理由で仕事先を探しているのです1が，仕事を見つけるためにはスキルが必要です． ということでScalaのスキルを身につけるべ…

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: CMU DB Slides Notes Video 今回はB+木について扱うようです． 授業 データ構造は internal meta-data core data storage temporary data structures table indexes に使われる．今回はtable indexesについて扱う． table indexはテーブルの特性の複製…

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: CMU DB Slides Notes Video Homework 宿題も出てきた．これは確実にやらない． 授業 ページから読み書きをする実行エンジンをどう支えるかについて話す． Hash Tables Trees data organizationとconcurrencyを考え出てデザインする必要がある． ハッシ…

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

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

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

tags: CMU DB Slides Notes Video Project 授業 復習としてOLTPとOLAPの話 ETL(extract transform load) 今回はDBMSがメモリをどう扱い，ディスクからデータを行き来するように動かすかという問題について扱う 空間制御 一緒に使われるページをディスク上で…

tags: CMU DB Slides Notes Video 授業 宿題の話をしているけど見た感じ次の授業までなさそう...？ ProjectとHomeworkというものがあり，前者はコードを書き，後者は筆記問題を解くというものっぽいです(なのでやるなら前者だけですかね) 前回の復習 前回の…