LeetCodeを解いてみる配信 2020-06-01

LeetCodeを解く配信を始めてます。
https://www.youtube.com/watch?v=KrhM06muekcwww.youtube.com

最初になんか楽器を練習して、人が集まったらLeetCodeを始めてる感じ。
あと、今日はVSTエフェクトをモリモリかけてみたのでそのテストでもあった。

残りより大きくなる要素を最小限に取り出す

最初はeasy
Minimum Subsequence in Non-Increasing Order - LeetCode
動画では9:15くらいから
配列からいくつかの要素をとってきて、その合計が残りの合計よりも大きくなる最小要素数の部分列を得るというものです。
ソートして総合計の半分以上になるまで要素をとっていく作戦です。 速さ97.22%で100%じゃなかったけど、あきらめ。

昇順・降順にならぶ3要素をすべて取り出す

次は前回やったmediumの問題が遅かったのでメモ化で速くしようという回 Count Number of Teams - LeetCode
動画では23:07くらいから。
24msで17.45%と結構遅かったので再帰をキャッシュして速くしようとした。
引数を範囲を考えつつひとつのlongにまとめてキーにする作戦。
それでも7msで60.21%とかだった。
discussionみてたら3重ループでやってるのがあったのでマネしてみたら16msで遅かった。
もっと見たら2重ループでやってるのがあって、たぶんこれが速いんだけど、配信中に理解できなそうだったのであきらめ。 Python short solution, >97.70%, O(n2) - LeetCode Discuss

二つの配列の片方を順番いれかえでもう片方と同じ並びにできるか

もうひとつeasy Make Two Arrays Equal by Reversing Sub-arrays - LeetCode
動画では45:50くらいから。
問題としては、配列の一部をとりだして逆順にするという操作を繰り返してもう片方の配列と同じ並びにできるかというものだけど、結局のところその操作で任意の並びにできることが示せれば、両者が同じ要素をもっているか判定するだけでいける。
で、n-1要素が任意に並べ替えれるなら、n番目にくるべきものをn-1番目にもってきてn番目の要素と入れ替えれば任意の並べ替えができることを利用して、2要素ならひっくり返すだけというのが示せるのですべての要素数で任意の並びにできることがわかる。
ということで、あとは数値が1000までなので1000要素の配列を用意して最初の配列で各要素の分をインクリメント、2番目の配列の各要素の分をデクリメントして、すべてが0なら同じ要素をもってるって判断。