class Solution {
public:
int longestSquareStreak(vector<int>& nums) {
}
};
2501. 数组中最长的方波
给你一个整数数组 nums 。如果 nums 的子序列满足下述条件，则认为该子序列是一个 方波 ：
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 <= nums.length <= 1052 <= nums[i] <= 105原站题解
golang 解法, 执行用时: 168 ms, 内存消耗: 13.2 MB, 提交时间: 2022-12-14 11:22:15
func longestSquareStreak(nums []int) (ans int) {
set := map[int]bool{}
for _, x := range nums {
set[x] = true
}
dp := map[int]int{}
var f func(int) int
f = func(x int) int {
if !set[x] {
return 0
}
if v, ok := dp[x]; ok {
return v
}
dp[x] = 1 + f(x*x)
return dp[x]
}
for x := range set {
ans = max(ans, f(x))
}
if ans == 1 {
return -1
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 264 ms, 内存消耗: 85.9 MB, 提交时间: 2022-12-14 11:21:40
# 记忆化搜索
class Solution:
def longestSquareStreak(self, nums: List[int]) -> int:
ans, s = 0, set(nums)
@cache
def dfs(x: int) -> int:
if x not in s: return 0
return 1 + dfs(x * x)
for x in s:
ans = max(ans, dfs(x))
return ans if ans > 1 else -1
golang 解法, 执行用时: 132 ms, 内存消耗: 9.5 MB, 提交时间: 2022-12-14 11:21:13
func longestSquareStreak(nums []int) (ans int) {
set := map[int]bool{}
for _, x := range nums {
set[x] = true
}
for x := range set {
cnt := 1
for x *= x; set[x]; x *= x {
cnt++
}
ans = max(ans, cnt)
}
if ans == 1 {
return -1
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 140 ms, 内存消耗: 30.8 MB, 提交时间: 2022-12-14 11:20:58
'''
暴力枚举
'''
class Solution:
def longestSquareStreak(self, nums: List[int]) -> int:
ans, s = 0, set(nums)
for x in s:
cnt = 0
while x in s:
cnt += 1
x *= x
ans = max(ans, cnt)
return ans if ans > 1 else -1