[LeetCode] 2501. Longest Square Streak in an Array

2501. Longest Square Streak in an Array

• Hardness: \(\color{orange}\textsf{Medium}\)
• Ralated Topics: Array、Hash Table、Binary Search、Dynamic Programming、Sorting
• \(\color{blue}\textsf{Weekly Contest 323}\)

一、題目

You are given an integer array nums. A subsequence of nums is called a square streak if:

• The length of the subsequence is at least 2, and
• after sorting the subsequence, each element (except the first element) is the square of the previous number.
  Return the length of the longest square streak in nums, or return -1 if there is no square streak.
  A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

• Input: nums = [4,3,6,16,8,2]
• Output: 3
• Explanation: Choose the subsequence [4,16,2]. After sorting it, it becomes [2,4,16].

• 4 = 2 * 2.
• 16 = 4 * 4.
  Therefore, [4,16,2] is a square streak.
  It can be shown that every subsequence of length 4 is not a square streak.

Example 2:

• Input: nums = [2,3,5,6,7]
• Output: -1
• Explanation: There is no square streak in nums so return -1.

Constraints:

• 2 <= nums.length <= 10^5
• 2 <= nums[i] <= 10^5

二、分析

• 先將 num 排序過後，遍歷所有的數字，並在遍歷的當下將數值存進 map 中，再找尋有沒有符合題意條件的數值在 map 中。
• 令一個 dp(n)，代別 nums[n] 所具有的 longestSquareStreak，其中
  • if (map.count(sqrt(nums[i]))) dp[i] = dp[map[sqrt(nums[i])]] + 1
  • 需注意檢查 sqrt(nums[i]) * sqrt(nums[i] == nums[i]

三、解題

1. DP

• Time complexity: \(O(n\log n)\)
• Space complexity: \(O(n)\)

int longestSquareStreak(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    unordered_map<int,int> map;
    sort(nums.begin(), nums.end());
    int res = -1;
    for (int i = 0; i < nums.size(); i++) {
        int target = sqrt(nums[i]);
        if (target * target == nums[i]) {
            if (map.count(target)) {
                dp[i] = dp[map[target]] + 1;
                res = max(dp[i], res);
            }    
        }
        map[nums[i]] = i;
    }
    return res;
}

回目錄 Catalog