题目描述
给你一个整数数组 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
解法
方法一：哈希表 + 枚举
我们先用哈希表记录数组中的所有元素，然后枚举数组中的每个元素作为子序列的第一个元素，将该元素不断平方，并判断平方后的结果是否在哈希表中，如果在，则将平方后的结果作为下一个元素，继续判断，直到平方后的结果不在哈希表中，此时判断子序列的长度是否大于 $1$，如果是，则更新答案。
时间复杂度 $O(n \times \log \log M)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\textit{nums}$ 的长度，而 $M$ 为数组 $\textit{nums}$ 中的元素的最大值。
方法二：记忆化搜索
与方法一类似，我们先用哈希表记录数组中的所有元素。然后设计一个函数 $\textit{dfs}(x)$，表示以 $x$ 为第一个元素的方波的长度。那么答案就是 $\max(\textit{dfs}(x))$，其中 $x$ 为数组 $\textit{nums}$ 中的元素。
函数 $\textit{dfs}(x)$ 的计算过程如下：
- 如果 $x$ 不在哈希表中，则返回 $0$。
- 否则，返回 $1 + \textit{dfs}(x^2)$。
过程中我们可以使用记忆化搜索，即使用哈希表记录函数 $\textit{dfs}(x)$ 的值，避免重复计算。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\textit{nums}$ 的长度。
| class Solution:
def longestSquareStreak(self, nums: List[int]) -> int:
@cache
def dfs(x):
if x not in s:
return 0
return 1 + dfs(x * x)
s = set(nums)
ans = max(dfs(x) for x in nums)
return -1 if ans < 2 else ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | class Solution {
private Map<Integer, Integer> f = new HashMap<>();
private Set<Integer> s = new HashSet<>();
public int longestSquareStreak(int[] nums) {
for (int v : nums) {
s.add(v);
}
int ans = 0;
for (int v : nums) {
ans = Math.max(ans, dfs(v));
}
return ans < 2 ? -1 : ans;
}
private int dfs(int x) {
if (!s.contains(x)) {
return 0;
}
if (f.containsKey(x)) {
return f.get(x);
}
int ans = 1 + dfs(x * x);
f.put(x, ans);
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
public:
int longestSquareStreak(vector<int>& nums) {
unordered_set<long long> s(nums.begin(), nums.end());
int ans = 0;
unordered_map<int, int> f;
function<int(int)> dfs = [&](int x) -> int {
if (!s.count(x)) return 0;
if (f.count(x)) return f[x];
long long t = 1ll * x * x;
if (t > INT_MAX) return 1;
f[x] = 1 + dfs(x * x);
return f[x];
};
for (int& v : nums) ans = max(ans, dfs(v));
return ans < 2 ? -1 : ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | func longestSquareStreak(nums []int) (ans int) {
s := map[int]bool{}
for _, v := range nums {
s[v] = true
}
f := map[int]int{}
var dfs func(int) int
dfs = func(x int) int {
if !s[x] {
return 0
}
if v, ok := f[x]; ok {
return v
}
f[x] = 1 + dfs(x*x)
return f[x]
}
for _, v := range nums {
if t := dfs(v); ans < t {
ans = t
}
}
if ans < 2 {
return -1
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | function longestSquareStreak(nums: number[]): number {
const set = new Set(nums);
const cache = new Map<number, number>();
const dfs = (x: number): number => {
if (cache.has(x)) return cache.get(x)!;
if (!set.has(x)) return 0;
cache.set(x, 1 + dfs(x ** 2));
return cache.get(x)!;
};
for (const x of set) dfs(x);
const ans = Math.max(...cache.values());
return ans > 1 ? ans : -1;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | function longestSquareStreak(nums) {
const set = new Set(nums);
const cache = new Map();
const dfs = x => {
if (cache.has(x)) return cache.get(x);
if (!set.has(x)) return 0;
cache.set(x, 1 + dfs(x ** 2));
return cache.get(x);
};
for (const x of set) dfs(x);
const ans = Math.max(...cache.values());
return ans > 1 ? ans : -1;
}
|
方法三：计数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | function longestSquareStreak(nums: number[]): number {
const cnt: Record<number, number> = {};
const squares = new Set<number>();
for (const x of new Set(nums)) {
cnt[x] = (cnt[x] ?? -1) + 1;
cnt[x ** 2] = (cnt[x ** 2] ?? -1) + 1;
}
for (const key in cnt) {
const x = +key;
if (cnt[x] || cnt[x ** 2]) {
squares.add(x);
}
}
if (squares.size <= 1) return -1;
const iterator = squares[Symbol.iterator]();
let [max, c, x] = [0, 0, iterator.next().value];
while (x !== undefined) {
if (squares.has(x)) {
squares.delete(x);
x **= 2;
c++;
} else {
max = Math.max(max, c);
x = iterator.next().value;
c = 0;
}
}
return max;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | function longestSquareStreak(nums) {
const cnt = {};
const squares = new Set();
for (const x of new Set(nums)) {
cnt[x] = (cnt[x] ?? -1) + 1;
cnt[x ** 2] = (cnt[x ** 2] ?? -1) + 1;
}
for (const key in cnt) {
const x = +key;
if (cnt[x] || cnt[x ** 2]) {
squares.add(x);
}
}
if (squares.size <= 1) return -1;
const iterator = squares[Symbol.iterator]();
let [max, c, x] = [0, 0, iterator.next().value];
while (x !== undefined) {
if (squares.has(x)) {
squares.delete(x);
x **= 2;
c++;
} else {
max = Math.max(max, c);
x = iterator.next().value;
c = 0;
}
}
return max;
}
|