はむこの勉強記録

http://bit.ly/2ktf20t の写し

LeetcodeのMySQL問題 Easyを5問解いた

概要

データベース問題を5問解きました。今、MySQLを構築する必要があるのだが、そもそもMySQLって何ができるのかよくわからなかったのと、データベース扱えないのはハムスターとしてどうだろうかと思ったので。

計算量を気にしてはいけないという知見が得られた。

leetcode 175. Combine Two Tables

https://leetcode.com/submissions/detail/109297935/

概要：人と住所のリストを全列挙せよ。しかし、人に対して必ずしも住所が割り当てられているとは限らないので、わからない場合は住所としてNULLを出力せよ。

解法：何がなんでも片方のキーを全部出力したい場合は、OUTER JOINTを使う。

leetcode 181. Employees Earning More Than Their Managers

https://leetcode.com/submissions/detail/109299369/

概要：人には、給料があり、上司がいたりいなかったりする。上司より給料が高い人を全列挙せよ。

解法：ポインタ使ってO(n)でできそう（これは罠で競技プログラミングではなくデータベースやぞ）。ポインタ？なにそれおいしいの？？というデータベースさんなので、inner jointでO(n2)でテーブルの直積を作って、くっつけたレコードが上司関係だったら確認する。こういう非直感的なのはつらい。

leetcode 182. Duplicate Emails

https://leetcode.com/submissions/detail/109300798/

概要：人はメールアドレスを登録している。複数人に登録されているメールアドレスを列挙せよ。

解法：unordered setを使ってO(n)でできそう（これは罠で競技プログラミングではなく以下省略）。setとは？？表しか使えませんが…？？？ｗｗという感じなので、inner jointでO(n2)でテーブルの直積を作って、くっつけたレコードのidが違うのにメアドが同じメアドをひたすら集める。idは重複し得るので、select distinctで重複除外する。

leetcode 196. Delete Duplicate Emails

https://leetcode.com/submissions/detail/109302333/

概要：人はメールアドレスを登録している。重複メールアドレスがあったら、IDが大きい物を削除してユニークにせよ。

解法：下からなめていって、unordered setのcountが1以上だったら削除、を繰り返してO(n)でできそう（これは罠で以下省略）。相変わらず非効率が好きなので、inner jointでO(n2)でテーブルの直積を作って、くっつけたレコードのid大きいのにメアドが同じものをひたすら集めたテーブルを作る。この直積の中で、大きいidが集まっているテーブルの方を全削除する。

leetcode 595. Big Countries

https://leetcode.com/submissions/detail/109303889/

概要：300万km2の面積と2500万人以上の人口を持つ国を全列挙せよ。

解法：これは流石にselect whereするだけ

ちょっと早い数列aの全列挙 where sum(a) == x && a <= b, given x, b

Topcoder 691 Div.1 Medで、「数列aの全列挙 where sum(a) == x && a <= b, given x, b」が必要だったが、頭の良い実装方法がわからず、3回くらい実装方針変えたりめちゃくちゃ大変だったので、メモ。

|a|=10なので、rep(i0, min(x, b0)) rep(i1, min(x-i1, b1)) …としても良かったのだが、流石に舐めくさっている。以下のような状態を持って、可逆な再帰を組んだ：「ちょうどi個を見終えて、残りがsで、現在の配列がaである場合。」。また、前処理でimosして、先を全部集めても無理なら枝刈りをいれるようにした。

ideone.com

github.com

500万個ヒットに対して、僕のがローカルで大体2s。kmjpさんの実装と速度比較してみたら、kmjpさんのが大体3sくらいだった。ちょっと早い。もっと早い列挙ください。

kmjp.hatenablog.jp