配列内の最長の正方形ストリーク-PHPチュートリアル-php.cn

配列内の最長の正方形ストリーク

Susan Sarandon

リリース： 2024-10-30 02:38:28

オリジナル

877 人が閲覧しました

Longest Square Streak in an Array

2501。配列内の最長の正方形ストリーク

難易度: 中

トピック: 配列、ハッシュテーブル、二分探索、動的プログラミング、ソート

整数配列 nums が与えられます。次の場合、num の部分列は square streak と呼ばれます:

サブシーケンスの長さが少なくとも 2 であり、かつ
後サブシーケンスを並べ替えると、各要素 (最初の要素を除く) は前の数値の平方になります。

最長の正方形ストリークの長さを数値で返します。正方形ストリークがない場合は -1 を返します。

サブシーケンスは、残りの要素の順序を変更せずに、一部の要素を削除するか、要素をまったく削除しないことによって、別の配列から派生できる配列です。

例 1:

入力: 数値 = [4,3,6,16,8,2]
出力: 3
説明: サブシーケンス [4,16,2] を選択します。並べ替えると[2,4,16]となります。

例 2:

入力: 数値 = [2,3,5,6,7]
出力: -1
説明: nums には四角い縞模様がないため、-1 を返します。

制約:

ヒント:

解決策:

nums 配列内の最長の正方形のストリークを特定する必要があります。正方形のストリークは、後続の各要素が前の要素の 2 乗であるサブシーケンスであり、少なくとも 2 要素の長さである必要があります。

解決策のアプローチは次のとおりです:

クイックルックアップにセットを使用する:
配列を反復処理します:
トラックの最大長:
- 発生する可能性のあるすべての四角い縞の最大長を追跡します。角スジが見つからなかった場合は、-1 を返します。
最適化:
- 各要素をチェックする前に配列を並べ替えて、サブシーケンスが昇順でチェックされていることを確認します。これは、冗長なチェックを避けるのに役立ちます。

このソリューションを PHP で実装してみましょう: 2501。配列内の最長の正方形ストリーク

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function longestSquareStreak($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$nums1 = [4, 3, 6, 16, 8, 2];
echo longestSquareStreak($nums1) . "\n";  // Output: 3

$nums2 = [2, 3, 5, 6, 7];
echo longestSquareStreak($nums2) . "\n";  // Output: -1
?>

ログイン後にコピー

説明：

並べ替え: 数値を並べ替えることで、シーケンスを昇順でチェックできるようになります。
Set Lookup: array_flip を使用すると、$nums をキーとして $numSet のセットのような構造が作成され、高速な存在チェックが可能になります。
各数値をループします: nums の各数値について、現在の数値の 2 乗がセット内にあるかどうかを確認します。そうであれば、連続記録を継続します。それ以外の場合は、連続記録を中断し、見つかった最長記録かどうかを確認します。