tags: leetcode 問題 Explore Problems アイデア 重複した文字を持たない最長の文字列の長さを返せという問題です． 今まで現れた文字列を保持するデータ構造を使えば良さそうです． 解法 文字列のある部分を開始地点と終了地点までを見て，今までに現れた文…
tags: leetcode 問題 Explore Problems アイデア Jというジュエリーである宝石の種類を表現する文字列とSという持っている宝石を表現する文字列が与えられます．持っている宝石のうち，ジュエリーであるものの個数を返せという問題です． 解法 setでJの宝石…
tags: leetcode 問題 Explore Problems アイデア 二分木が与えられたとき，全ての同じ構造の部分木を返せという問題です． 解法 連想配列を使います． trees[あるノードの部分木] = あるノード helperという関数内関数を使って左部分木，右部分木に対して再…
tags: leetcode 問題 Explore Problems アイデア 縦，横，斜めそれぞれに1-9が重複していないかを確かめます． おそらくやるだけです… 解法 書きます． 計算量 ボードの1辺の長さを$N$とします．($N=9$ですが) 時間計算量 is_validメソッドは$O(N)$必要です…
tags: leetcode 問題 Explore Problems アイデア 文字列の配列が与えられた時，アナグラム(文字の位置を入れ替えて全く同じ文字列になる文字列群)をまとめて二次元配列で返せという問題です． …これと同じ問題を某社の面接で解かされました(なお前回は解けな…
tags: leetcode 問題 Explore Problems アイデア 昇順にソート済みの配列が与えられた時，高さのバランスが取れたBSTに変換しろという問題です． ソートした配列の中心の値よりも，右側は大きく，左側は小さいということを利用してやります． 解法 配列の中…
tags: その他 現在 題名のままです．少なくとも春学期の間に2つインターンの予定がありました． 片方は今年中の募集を取りやめ，もう片方はインターン受け入れをpendingという状況です． (留年しちゃったので)仕事をたくさんするつもりだったのですがしょう…
tags: leetcode 問題 Explore Problems アイデア 二分木が与えられるので，その木が高さがバランス木かどうかを判定しろという問題です． 高さがバランスとは 左右部分木の全てのノードの高さの差が1しかない ことを言うらしいです． 高さを求めることと，bo…
tags: leetcode 問題 Explore Problems アイデア 整数の配列numsが与えられたとき，abs(nums[i] - nums[j]) <= tかつabs(i - j) <= kであるようなiとjがあるかを探せという問題です． 解法 まずtは非負なのでその時点でFalseを返します 連想配列cache[numをt…
tags: leetcode 問題 Explore Problems アイデア BSTを与えられた時に，LCAを探せという問題です． LCA(lower common ancestor)とはあるノードpとqが与えられたときに，pとqを子として持つ，もしくはそのノード自身として持つノードのことです． 解法 LCAは…
tags: leetcode 問題 Explore Problems アイデア 配列のk番目に大きい要素を常に返すようなクラスを作れという問題です． 必要なのはk番目に大きい値なのでそれより小さい値は使わなくても良いです． また，配列を常に整列していれば時間計算量を効率化出来…
tags: leetcode 問題 Explore Problems アイデア 二分木を文字列に変換し，その文字列を二分木に戻すメソッドを書けという問題です． どのような変換の仕方でも良いようですが，メソッド間で使える変数を使ってその状態を保持しないようにしろとのことです．…
tags: leetcode スクリプト言語ってろくな言語がないような気がするのは私だけでしょうか… JS，Python，Shell script…Rubyがもっと海外で使われていればこうなっていなかったのか… 問題 Explore Problems アイデア 二分木を与えられた時，この木の2つのノー…
tags: leetcode 問題 Explore Problems アイデア 二分木が与えられた時に，あるノードと同じ深さにある右のノードをポインタnextで指せという問題です． 使用するメモリは定数倍でないといけないらしいですが，再帰ならセーフらしいです．今回は再帰の分がセ…
tags: leetcode 問題 Explore Problems アイデア 完全二分木が与えられた時に，あるノードと同じ深さにある右のノードをポインタnextで指せという問題です． 使用するメモリは定数倍でないといけないらしいですが，再帰ならセーフらしいです．今回は再帰の分…
tags: leetcode 最近の疑問としてPythonの関数内関数は出来るだけ使わない方がいいのかということがあります…(便利そうだし今後はもう少し使うことにしようかな…？) 問題 Explore Problems アイデア preorderのBSTとinorderのBSTが与えられた時に，BSTを構築…
tags: leetcode 問題 Explore Problems アイデア BSTのノードを削除せよという問題です．典型的な問題なのでやるだけ？ 解法(recursive) rootが空ならrootを返します． root.val == keyのとき 右の部分木がなければ，左部分木を返せば良いです． 右の部分木…
tags: leetcode 問題 Explore Problems アイデア 配列内の0を全て末尾の方に移せという問題です． 末尾の要素と交換をすれば良いですね． 大事なのは与えられた配列を操作することは許されていますが，新たにメモリ内に配列を作ってコピーしてはいけないとい…
tags: leetcode 30-Day LeetCoding Challengeが始まったので問題を解いていきます 問題 Problems アイデア 整数列が与えられるので，その部分数列の和が最大と成る配列を探せという問題です． 解法 Kadane's Algorithm 配列の全ての要素を走査します． 今ま…
tags: leetcode 問題 Explore Problems アイデア inorderのBSTとpostorderのBSTが与えられた時に，BSTを構築しろという問題です． 木の探索順序 木を探索する際の順序として以下の図ように Inorder(左→根→右) Preorder(根→左→右) Postorder(左→右→根) があり…
tags: leetcode 問題 Explore Problems 実際のコーディングテストでPython3を使うことが多いことから，Python3で書くことに… 発言に一貫性がないという点で自分は一貫性がある？ アイデア BSTに新たな値を挿入しろという問題です． その値はBST内に存在しな…
tags: 進捗報告 進捗リンク 1-3 数学関連 院試の前に留年して勉強する気がなくなったので 物理関連 留年して研究室に配属されずやる気が失せた CS 留年してやる気() 過去問は見たけど解いていない．暇だし解く． コンパイラは多少進んだ．DBMSは授業見終わっ…
tags: CMU DB Slides Video 授業 決定支援システムとは管理，処理のために働くアプリケーション． STAR vs SNOWFLAKE SCHEMA normalization 少ないストレージ空間を専有する． 非正規化されたデータモデルは整合性と一貫性の違反を負う可能性がある． query …
tags: CMU DB Slides Video 授業 OLTP vs OLAP On-line Transaction Processing(OLTP) 短命な読み書きtxn 小さなfootprint(稼働時に占有，消費する資源) 繰り返し処理 On-line Analytical Processing(OLAP) 長寿な読み込み専用クエリ 複雑な結合 探索的なク…
tags: CMU DB Slides Notes Video Homework 授業 distributed DBMSs parallel DB ノードは物理的にそれぞれ近い ノードは高速なLANで繋がれている ノード間の通信費用は小さいと仮定して良い distributed DB ノードは物理的にそれぞれ遠い ノードは公共のネ…
tags: CMU DB Slides Notes Video 授業 ARIES Algorithms for Recovery and Isolation Exploiting Semanticsの略称．1990年台初頭にIBMの研究所で開発された．全てのシステムがARIESを原著論文通りに定義はしていないが，十分似ている． ARIES recovery prot…
tags: CMU DB Slides Notes Video 授業 crash recovery DBの一貫性，txnの原子性，失敗に関わらない永続性を保証する．DBMSと失敗を分類する必要がある． recovery algorithmは2つの部分から成る 通常のtxtの間の，通常のDBMSが失敗から回復できるように保証…
tags: CMU DB Slides Notes Video 授業 multi-version concurrency control multi-version concurrency control(MVCC)とは単なる並行制御プロトコルよりも大きな概念．DBMSのデザインと実装の全ての側面を含む． DBMSはDB内の単一の論理オブジェクトの複数の…
tags: CMU DB Slides Notes Video 授業 timestamp ordering concurrency control timestamp ordering(t/o)とは楽観的な並行制御プロトコルのクラス．DBMSはトランザクションの衝突が稀だと仮定する． timestampを利用して，直列性を決定する． 各トランザク…
tags: CMU DB Slides Notes Video 授業 transaction locks DBMSは一元化されたlock managerを持っている。 shared lock 同じオブジェクトを同時に見る複数のトランザクションを許す 同時に1つのトランザクションだけが排他的なlockを持つことが可能 exclusiv…
