概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
300. Longest Increasing Subsequence
整数の配列numsが与えられたとき、LIS（最長増加部分配列）の長さを返せ。
（部分配列の中でも値が昇順になっていること）
制約
1 <= nums.length <= 2500-104 <= nums[i] <= 104
解説
まず初めに部分配列の最小の末尾を長さ毎に格納するための配列と増加部分配列の長さを記録する変数を用意します。
LengthOfLIS
// LISの末尾の内最小を長さ毎の配列に入れる配列を用意する
int[] tails = new int[nums.Length];
// 最大のLISの長さを計測するための変数を用意
int tailsLength = 0;一番長い部分配列を求めるにはできるだけ小さい値が入っているほど、次の値を増加部分配列に追加しやすいからです。
例えば[4,5,6,3]といった配列が渡された場合、[3,5,6]が最小の末尾の部分配列になります。
長さが2となる増加部分配列は[4,5], [5,6]の2パターンです。そのうち配列の末尾が低いのは[4,5]なので末尾の5を配列の[1]に加えます。
| 長さ | 候補 | 最小の末尾 |
|---|---|---|
| 1 | | 4 |
| 2 | [4, 5], [5, 6] | 5 |
| 3 | [4, 5, 6] | 6 |
次にバイナリサーチを使用して、最小末尾配列を作成していきます。
まずは渡された配列から一つずつ番号を一つずつ取り出していきます。
数字を取り出したら最小末尾配列のすべてを探索範囲とします。
LengthOfLIS
// 配列からLISの先頭とする値を一つずつ取り出す
foreach (var currentNo in nums)
{
// LISの値を確認する初回の範囲を定める
var lowIndex = 0;
var highIndex = tailsLength;
}次に範囲の中央を比較して取り出した番号のほうが大きければ中央から先を、小さければ中央よりも前を探索範囲として繰り返します。
LengthOfLIS
// 配列からLISの先頭とする値を一つずつ取り出す
foreach (var currentNo in nums)
{
...
// 範囲が1になるまで繰り返す
while (lowIndex != highIndex)
{
// LIS検索範囲の中央のインデックスを割り出す
int tailsIndex= (lowIndex + highIndex) / 2;
// 検索した中央の値が取り出した値よりも小さければ検索範囲を中央の次からに変更
if (tails[tailsIndex] < currentNo)
{
lowIndex = tailsIndex + 1;
}
// 小さければ中央までとする
else
{
highIndex = tailsIndex;
}
}
}探索範囲が1となれば番号を格納する箇所が確定するので番号を格納し、格納場所が末尾でなければ新規追加となるので長さを再記録します。
LengthOfLIS
// 配列からLISの先頭とする値を一つずつ取り出す
foreach (var currentNo in nums)
{
...
// 範囲が一つになった箇所に番号を格納
tails[lowIndex] = currentNo;
// 上書きじゃなければLISの新規追加となるのでサイズをインクリメント
if (lowIndex == tailsLength)
{
tailsLength++;
}
}最後に長さを返して解答終了です。
ソースコード
Solution.cs
public class Solution {
public int LengthOfLIS(int[] nums)
{
// LISの末尾の内最小を長さ毎の配列に入れる配列を用意する
int[] tails = new int[nums.Length];
// 最大のLISの長さを計測するための変数を用意
int tailsLength = 0;
// 配列からLISの先頭とする値を一つずつ取り出す
foreach (var currentNo in nums)
{
// LISの値を確認する初回の範囲を定める
var lowIndex = 0;
var highIndex = tailsLength;
// 範囲が1になるまで繰り返す
while (lowIndex != highIndex)
{
// LIS検索範囲の中央のインデックスを割り出す
int tailsIndex = (lowIndex + highIndex) / 2;
// 検索した中央の値が取り出した値の方が大きければ検索範囲を中央の次からに変更
if (tails[tailsIndex] < currentNo)
{
lowIndex = tailsIndex + 1;
}
// 小さければ中央までとする
else
{
highIndex = tailsIndex;
}
}
// 範囲が一つになった箇所に番号を格納
tails[lowIndex] = currentNo;
// 上書きじゃなければLISの新規追加となるのでサイズをインクリメント
if (lowIndex == tailsLength)
{
tailsLength++;
}
}
return tailsLength;
}
}