tags: leetcode 問題 Explore Problems アイデア ｢ダイアル式の鍵で，4桁の暗証番号が0000から始まったときに，targetの番号になるのに最短で何回ダイアルを回せばよいのか｣という問題です． ただし，deadendsにある数字を経由しては行けないです． 全探索す…

tags: leetcode 問題 Explore Problems アイデア ｢2つの単一方向リストの共通部分がどこノードから始まるのかを探せ｣という問題です． 普通に1つ1つノードを辿っていけば良いでしょう． 解法 2つのリストをそれぞれA，Bとします． この際，それぞれのリスト…

tags: leetcode 問題 Explore Problems アイデア ｢kという整数と整数の配列を与えられたとき，i-j=kかつnums[i]==nums[j]となるようなiとjとなるものがあるかどうかを探す｣問題です． 解法 連想配列を用意します．(map[num[index]] = index) 0 <= i < nums.l…

tags: CMU DB Slides Notes Video 授業 久々! めっちゃ久々に授業を受ける.まぁ色々あったのですが,3月中に終わらせられるように爆速で視聴していきたいです() query executionについて先週は暑かった. 今回は複数スレッドでのquery executionについてやるっ…

tags: leetcode この問題はRustが使えなかったのでC++です． 問題 Explore Problems アイデア 以前やった問題と同じです． propyon.hateblo.jp 循環するような点を探す問題ではFloyd's cycleが使えます． 解法 2つのポインタを使います．一方(fast)はもう一…

tags: leetcode C++よりもRustの方が書いていて楽しいのでRustで書けそうな問題はRustで書いていくことにします． (コーディングインタビューで使われる程度のC++の文法ならば，普段から使っていなくてもなんとかなると楽観視しています) 問題 Explore Probl…

tags: leetcode 問題 Explore Problems アイデア 2つのレストラン名の格納された配列が与えられます． このときに，最も小さいindexの合計を持つ共通したレストランを探し，それらを配列に入れて返せという問題です． 連想配列が使えそうです． 解法 最初に…

tags: leetcode 問題 Explore Problems アイデア 文字列sとtが与えられた時に，isomorphicかどうか調べろという問題です． isomorphicとはsの文字がtの文字へ一対一に写像出来るということです． ただし，2種類の文字が同じ文字に写像されることはなく，ある…

tags: leetcode 問題 Explore Problems アイデア 与えられた2桁数がhappy numberかどうか返せという問題です． happy numberとは 各桁の2乗の和から出来た数をnext_numとします next_numが1になるときhappy numberです． next_numの各桁の2乗の和が1になるま…

tags: 情報 動機 Terminal周りを適当に使っていたのですが，これを改善すれば生産性が上がるのではということで改善してみます． Terminal emulator alacrittyというemulatorを使うことにしました． 理由は描画が早いらしいからです．公式サイトを見てどうこ…

tags: leetcode 問題 Explore Problems アイデア 連結リストが与えられたとき，循環がないかを返せという問題です． 追加の課題として これを$O(1)$のメモリで解くことがあります． この問題は末尾の次のノードに今まで訪れたことがあるかを調べればよく， …

tags: leetcode 問題 Explore Problems アイデア 島を1が縦横に繋がったものと考えて，0を海と考えます．このときに，島の数を返せという問題です． 蟻本の冒頭に類題がありました．DFS，BFSを使って解くことが可能です． 解法1(DFS･再帰) 現在の位置が島な…

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: CMU DB Slides Notes Video インターンの面接でScalaがやりたいということを言ったら，｢うちではもうScala扱ってないんだよね｣的なことを言われてしまいながらも内容的には全然やりたかいので｢別にScalaじゃなくてもいい｣と若干矛盾する発言をしてしま…

tags: CMU DB Slides Notes Video 雨の日の次の日の花粉症はひどいですね…生物兵器ですあれは… 授業 JOINが必要な理由．情報の繰り返しを避けるため．JOINにより情報の損失なしで元々のtuplesを再構築できる． inner equijoinアルゴリズムで組み合わせる2つ…

tags: CMU DB Slides Notes Video Homework Released: Join Algorithms Project Released: Hash Index また宿題が...(未だに手が付けられないが，私はやるのでしょうか…？) 授業 QUERYは木構造になっており，葉の結果が根の方に上がっていき，根の結果がQUER…

tags: CMU DB Slides Notes Video 今回はConcurrent(並行)とParallel(並列)という概念が登場します．前者は複数のタスクを同時に実行状態にすること，後者は複数を同時にすることという違いがあるっぽいです．1 授業 今までに話していたのはsingle-threaded…

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

tags: CMU DB Slides Notes Video 風邪でやらなくなってから時間が空いたけど再開．継続出来る人はすごい(しみじみ) 授業 More B+ Trees キーに複製対する対処法は tupleにrecord IDを付け加える 葉に新たなtupleを付け加えて複製キーを持てるようにする 大…