LeetCode 2501: Longest Square Streak in an Array (Hash Set / Math)
English
Put all numbers in a set. For each value x, start a chain only when sqrt(x) is not an integer already in the set. Then square repeatedly while the value still exists in the set. Track the maximum chain length; if it is less than 2, return -1.
class Solution {
public int longestSquareStreak(int[] nums) {
java.util.Set set = new java.util.HashSet<>();
for (int x : nums) set.add((long) x);
int ans = 0;
for (long x : set) {
long r = (long) Math.sqrt(x);
if (r * r == x && set.contains(r)) continue;
int len = 0;
long cur = x;
while (set.contains(cur)) {
len++;
if (cur > 100000) break;
cur = cur * cur;
}
ans = Math.max(ans, len);
}
return ans >= 2 ? ans : -1;
}
} func longestSquareStreak(nums []int) int {
set := map[int64]bool{}
for _, x := range nums {
set[int64(x)] = true
}
ans := 0
for x := range set {
r := int64(math.Sqrt(float64(x)))
if r*r == x && set[r] {
continue
}
l, cur := 0, x
for set[cur] {
l++
if cur > 100000 {
break
}
cur = cur * cur
}
if l > ans {
ans = l
}
}
if ans < 2 {
return -1
}
return ans
}class Solution {
public:
int longestSquareStreak(vector& nums) {
unordered_set st(nums.begin(), nums.end());
int ans = 0;
for (long long x : st) {
long long r = sqrt((long double)x);
if (r * r == x && st.count(r)) continue;
int len = 0;
long long cur = x;
while (st.count(cur)) {
++len;
if (cur > 100000) break;
cur = cur * cur;
}
ans = max(ans, len);
}
return ans >= 2 ? ans : -1;
}
}; class Solution:
def longestSquareStreak(self, nums: List[int]) -> int:
st = set(nums)
ans = 0
for x in st:
r = int(x ** 0.5)
if r * r == x and r in st:
continue
cur = x
l = 0
while cur in st:
l += 1
if cur > 100000:
break
cur = cur * cur
ans = max(ans, l)
return ans if ans >= 2 else -1var longestSquareStreak = function(nums) {
const st = new Set(nums.map(BigInt));
let ans = 0;
for (const x of st) {
const r = BigInt(Math.floor(Math.sqrt(Number(x))));
if (r * r === x && st.has(r)) continue;
let len = 0;
let cur = x;
while (st.has(cur)) {
len++;
if (cur > 100000n) break;
cur = cur * cur;
}
ans = Math.max(ans, len);
}
return ans >= 2 ? ans : -1;
};中文
先把所有数字放进哈希集合。对于每个数字 x，只有当它的整数平方根不在集合中时，才把它当作链起点，避免重复统计。然后不断把当前值平方并检查是否仍在集合中，统计链长度。最后若最大长度小于 2，返回 -1。
class Solution {
public int longestSquareStreak(int[] nums) {
java.util.Set set = new java.util.HashSet<>();
for (int x : nums) set.add((long) x);
int ans = 0;
for (long x : set) {
long r = (long) Math.sqrt(x);
if (r * r == x && set.contains(r)) continue;
int len = 0;
long cur = x;
while (set.contains(cur)) {
len++;
if (cur > 100000) break;
cur = cur * cur;
}
ans = Math.max(ans, len);
}
return ans >= 2 ? ans : -1;
}
} func longestSquareStreak(nums []int) int {
set := map[int64]bool{}
for _, x := range nums {
set[int64(x)] = true
}
ans := 0
for x := range set {
r := int64(math.Sqrt(float64(x)))
if r*r == x && set[r] {
continue
}
l, cur := 0, x
for set[cur] {
l++
if cur > 100000 {
break
}
cur = cur * cur
}
if l > ans {
ans = l
}
}
if ans < 2 {
return -1
}
return ans
}class Solution {
public:
int longestSquareStreak(vector& nums) {
unordered_set st(nums.begin(), nums.end());
int ans = 0;
for (long long x : st) {
long long r = sqrt((long double)x);
if (r * r == x && st.count(r)) continue;
int len = 0;
long long cur = x;
while (st.count(cur)) {
++len;
if (cur > 100000) break;
cur = cur * cur;
}
ans = max(ans, len);
}
return ans >= 2 ? ans : -1;
}
}; class Solution:
def longestSquareStreak(self, nums: List[int]) -> int:
st = set(nums)
ans = 0
for x in st:
r = int(x ** 0.5)
if r * r == x and r in st:
continue
cur = x
l = 0
while cur in st:
l += 1
if cur > 100000:
break
cur = cur * cur
ans = max(ans, l)
return ans if ans >= 2 else -1var longestSquareStreak = function(nums) {
const st = new Set(nums.map(BigInt));
let ans = 0;
for (const x of st) {
const r = BigInt(Math.floor(Math.sqrt(Number(x))));
if (r * r === x && st.has(r)) continue;
let len = 0;
let cur = x;
while (st.has(cur)) {
len++;
if (cur > 100000n) break;
cur = cur * cur;
}
ans = Math.max(ans, len);
}
return ans >= 2 ? ans : -1;
};