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

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

難易度: 中

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

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

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

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

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

例 1:

• 入力: 数値 = [4,3,6,16,8,2]
• 出力: 3
• 説明: サブシーケンス [4,16,2] を選択します。並べ替えると[2,4,16]となります。
  4 = 2 * 2.
  16 = 4 * 4.
  したがって、[4,16,2] は四角い縞です。
  長さ 4 のすべての部分列は正方形の縞ではないことがわかります。

例 2:

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

制約:

2 5 2 5

ヒント:

この制約により、可能な最長の正方形の縞の長さは 5 になります。
nums の要素をセットに保存して、存在するかどうかをすぐに確認します。

解決策:

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

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

1. クイック ルックアップにセットを使用する:

   数値をセットに保存して、要素の正方形も配列内にあるかどうかをすばやく確認します。

2. 配列を反復処理します:

   配列内の各数値について、その数値から開始して正方形のストリークを構築してみます。
   現在の数値の平方がセット内に存在するかどうかを確認し、一致する平方がなくなるまで連続を延長し続けます。

3. トラックの最大長:

   • 発生する可能性のあるすべての四角い縞の最大長を追跡します。角スジが見つからなかった場合は、-1 を返します。

4. 最適化:

   • 各要素をチェックする前に配列を並べ替えて、サブシーケンスが昇順でチェックされていることを確認します。これは、冗長なチェックを避けるのに役立ちます。

このソリューションを 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 乗がセット内にあるかどうかを確認します。そうであれば、連続記録を継続します。それ以外の場合は、連続記録を中断し、見つかった最長記録かどうかを確認します。

複雑さの分析

• 時間計算量: ソートによる O(n log n) (n は要素の数)数字で。後続のルックアップとスクエア ストリーク チェックは O(n).
です。
• 空間複雑度: O(n)、主にセットに数値を格納するため。

このソリューションは、最長の正方形のストリークを効率的に見つけます。有効なストリークが存在しない場合は -1 を返します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が配列内の最長の正方形ストリークの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。