はむこの勉強記録

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

Leetcode 490-456 考察ラッシュ

hamko.hatenadiary.jp

488. Zuma Game (Hard)

概要:文字列sが与えられる。文字集合Sを使って、以下の操作を繰り返す。操作「集合Sの要素xを取り出し、sのどこかに挿入する。sの中で、3個以上連続して同じ文字があればそれらを全て削除する」。この時、結果として考えられる最小値を求めよ。|s|<=20, |S|<=5, 文字種類5種類以下

考察:わからん

486. Predict the Winner

概要:ポイント性の2人ゲームをする。数列aが共有されている。人1から交互に手番が来る。操作「aの先頭か末尾の数字をpopしてその点数を得る」をaが終わるまで続ける。人1は負けないか?|a|<=20、a[i]<=1e7

考察:わからない。全探索できるけど、全探索情報から必勝法を見つける方法ってあるのだろうか?

483. Smallest Good Base

概要:整数nがbase bで全て1だった。最小のbを求めよ。

考察:3乗くらいまでを場合分けしてアドホックに調べて、4乗以降はbを下から全探索。

482. License Key Formatting

概要:文字列sの-を消して、全部大文字にして、k文字ずつに分解してください。

考察:えぇ…(やるだけすぎる)

481. Magical String

概要:Down vote多すぎるので見ていない

考察:いいえ

480. Sliding Window Median

概要:数列aが与えられる。[i:i+k)の中央値をiについて全列挙せよ。

考察:Wavelet Matrixのquantileで殴る。

477. Total Hamming Distance

概要:数の集合Sが与えられる。Sのペアを考えて、それらのハミング距離の総和を求めよ。

考察:bit独立でsum(#0*#1)

474. Ones and Zeroes

概要:二値文字列集合Sが与えられる。Sの部分集合Tを、'0'をm個、'1'をn個で構成できるとする。|T|を最大化せよ。|S|<=600, n, m<=100

考察:二次元ナップザックなのでDP[i][j][h] = i個見て、j個0を使って、h個1を使った時の最大個数。

473. Matchsticks to Square

概要:長さa_iの棒がn個与えられる。正方形を作れるか?n<=15, a_i<=1e9

考察:4つに分ける方法は19C4くらいなので全探索

468. Validate IP Address

概要:Down voteがひどいのでやらない

考察:いいえ。

467. Unique Substrings in Wraparound String

概要:円環アルファベット文字列a[0:26)=[‘a’:‘z’]を想定する。文字列sが与えられる。sには、aの相違連続部分列が何個含まれるか?|s|<=10000

考察:すぐにはわからない…。前処理で、各文字について、どこまで連続できるかを持っておく。長さを全探索して、連続限界以下かつ各文字について新出ならばカウント。

良い典型

466. Count The Repetitions

概要:文字列s1, s2が与えられる。n1, n2が与えられる。s2mn2がs1*n1の部分文字列であるという。最大のmを求めよ。

考察:全然わからない。二分探索したい気持ちにはなるけど…

464. Can I Win

概要:n言ったら勝ちゲームをする。kまで言えるが、数字の再利用は許されない。勝者はどちらか。k<=20, n<=300

考察:わからない…ゲーム系弱いんだよなあ…k<=20なので、状態は220*300である。メモリが大きいPCならばギリギリ全探索できる。

460. LFU Cache (Hard)

概要:LFU Cache(k)を実装せよ。

考察:読解がキツイのでいいや

457. Circular Array Loop

概要:長さnの円環すごろくがある。i番目には数字a[i]が書いてあり、ここに止まるとa[i]だけ前後に進む。ループはあるか?時間O(n), 空間O(1)で書け。

考察:空間O(n)なら、全てから初めて遷移を試すだけ。あとはめんどいのでSCCしちゃうという手もある。空間O(1)はよくわからない。

456. 132 Pattern

概要:数列aが与えられる。a[i]<a[k]<a[j] (i<j<k)なるi, j, kは存在するか?

考察:jを全探索したい。すると、①[0:k)の最小値<a[k] ②(k,n)の中でa[k]未満の最大値を持ってくればいい。こういうのはWavelet MatrixでO(log n)でできるので、O(n log n)でできる…が、普通どうやればいいのかわからない。