Jump Game IV
https://leetcode.com/explore/challenge/card/december-leetcoding-challenge/572/week-4-december-22nd-december-28th/3582/
解説: https://leetcode.com/problems/jump-game-iv/discuss/502699/JavaC%2B%2B-BFS-Solution-Clean-code-O(N)
1ステップごとに可能なステップをキューに入れ、dpですでに見た添え字を入れ無限ループを防ぐ。 最初に配列-1のサイズに到達した時点でのステップが最小となる。 なるほど賢い。
Beautiful Arrangement
解説 https://leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/579/week-1-january-1st-january-7th/3591/
Backtracking ただし再帰を繰り返すたびに、ループの範囲 (n) を狭めていくことで計算量を下げている。 深さ優先をする再帰関数の引数配列では、関数を呼び出す前に値を入れ、呼び終わった後に値を戻すことで、わざわざ配列を呼び出しごとに作成する無駄が減るためメモリ削減になる。
Find the Most Competitive Subsequence
解説 https://leetcode.com/problems/find-the-most-competitive-subsequence/discuss/1027527/C%2B%2BSimple-and-Short-Solution-faster-than-100
vector を stack として使う。 左にある値ほど優先順位が高いので、もしすでに入れた値よりも小さい値が現れたら、すでに入れた値を取り出し、その値を入れたほうが良い。 ただし削除できる回数は決まっている(もしこの回数以上削除してしまうと、k個の値を入れられないため)ので、この回数を超えたら削除できないようにする。 また同じ値が並んでいると削除ができなくなってしまうので、最後に先頭からk個目までの配列を取り出すようにしている。
解説 https://leetcode.com/problems/sort-the-matrix-diagonally/discuss/489749/JavaPython-Straight-Forward