inohilog

/var/log/inohiro

LeetCode Weekly Contest 58 に参加

メールでお知らせが来て、見たところ PDT に優しい時間帯(18:30-20:00)だったので初参加。AtCoder と同じように4問、だんだん難易度が上がっているように見える(正解すると得られるポイントが大きくなるように設定されていた)。

724. Find Pivot Index

難易度は Easy。数字の配列が与えられて、ある位置ではその右側のすべての要素と、左側のすべての要素の和が等しくなる位置(Pivota Index)を探す。完全に難しく考えすぎて、時間を消費してしまった。0番目の要素から見ていくような単純なやり方では解けないようになっているだろうと邪推してしまい、最初に配列の真ん中に行って、右側と左側の和を比較しながらインデックスをずらして、Pivot Index を見つける方法を考えた。

↑のやり方を実装していると、無駄に実装が複雑になり(もっと良い書き方はあったはずだが)、単純に 0 番目の要素から、左右の和を比較するアルゴリズムを書いたら解けた... 難易度 Easy だったので、段順な実装をまず試してみるべきだったな...

725. Split Linked List in Parts

難易度は Medium。Linked List が渡されて、それを展開し、指定された要素数の配列(配列の配列になる)を作る。配列の要素の個数はなるべく等しくなるようにし、要素数が異なる場合は差が1になるようにする。 問題を間違えて理解していた...

Linked List を配列に展開するのは簡単にできたが、結局解けなかった。配列に展開したあと、指定された要素数の配列になるようにやってみたが、うまくいかず。公式の解説はなかったが、Python 版の正解をアップロードしている人がいたので、それを参考に書いた。

とりあえず問題をまちがえて理解していることがわかった。木を作ってバランスさせるのかな、とか思ってたけどわりと愚直なやり方で良かった。ポインタの繋ぎ変えとかは数をこなさないと、このままでは解ける気がしないな。

あと2問は着手できず...