陣列中最長的方形條紋

2501。數組中最長的方形條紋

難度：中

主題：陣列、雜湊表、二分查找、動態規劃、排序

給你一個整數數組 nums。 nums 的子序列稱為 square streak 如果：

• 子序列的長度至少為2，且
• 子序列進行排序後，每個元素（第一個元素除外）都是前一個數的平方。

回傳最長方形條紋的長度（以nums為單位），如果沒有方形條紋，則回傳-1。

子序列 是一個數組，可以透過刪除一些元素或不刪除任何元素而從另一個數組派生出來，而不更改剩餘元素的順序。

範例1：

• 輸入： nums = [4,3,6,16,8,2]
• 輸出： 3
• 解釋： 選擇子序列 [4,16,2]。排序後變成[2,4,16]。
  • 4 = 2 * 2.
  • 16 = 4 * 4。
  • 因此，[4,16,2] 是一條方形條紋。
  • 可以證明，每個長度為 4 的子序列都不是方形條紋。

範例2：

• 輸入： nums = [2,3,5,6,7]
• 輸出： -1
• 解釋： nums 中沒有方形條紋，因此傳回 -1。

約束：

• 2 5
• 2 5

提示：

1. 在限制條件下，最長方形條紋的長度可能為 5。
2. 將 nums 的元素儲存在一個集合中，以快速檢查它是否存在。

解：

我們需要辨識 nums 陣列中最長的方形條紋。方形條紋是一個子序列，其中每個後續元素都是前一個元素的平方，並且它的長度必須至少為兩個元素。

解決方法如下：

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
?>

解釋：

• 排序：對 nums 進行排序確保我們可以按升序檢查序列。
• 集合查找：使用 array_flip 為 $numSet 建立一個類似集合的結構，以 $nums 作為鍵，允許快速存在性檢查。
• 循環遍歷每個數字：對於nums中的每個num，檢查目前數字的平方是否在集合中。如果是，則繼續連勝。否則，打破連勝並檢查它是否是找到的最長連勝。

複雜性分析

• 時間複雜度: O(n log n) 由於排序，其中 n 是元素數量數字。隨後的查找和方形條紋檢查是 O(n).
• 空間複雜度：O(n)，主要用於儲存集合中的nums。

此解決方案有效地找到最長的方形條紋，如果不存在有效條紋，則返回 -1。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是陣列中最長的方形條紋的詳細內容。更多資訊請關注PHP中文網其他相關文章！