thảo luận Leetcode mỗi ngày

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        int ans = 0;

        int[] dp = new int[n];

        for (int row = 0; row < m; row++) {
            int[] nextDp = new int[n];
            for (int col = 0; col < n; col++) {
                if (row > 0 && col > 0 && matrix[row][col] == 1) {
                    nextDp[col] = Math.min(Math.min(nextDp[col - 1], dp[col]), dp[col - 1]) + 1;
                } else {
                    nextDp[col] = matrix[row][col];
                }

                ans += nextDp[col];
            }
            dp = nextDp;
        }

        return ans;
    }
}

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        items = set(nums)
        visited = set()
        def dfs(num):
            streak = 0
            while num in items:
                visited.add(num)
                num*=num
                streak += 1
            return streak
        ans = -1
        for start in nums:
            if start not in visited:
                ans = max(ans, dfs(start))
        return -1 if ans == 1 else ans

class Solution {
    public int longestSquareStreak(int[] nums) {
        Arrays.sort(nums);
        Map<Integer, Integer> appear = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int squareRoot = (int) Math.sqrt(nums[i]);
            if (squareRoot * squareRoot == nums[i]) {
                appear.put(
                    nums[i],
                    appear.getOrDefault(squareRoot, 0) + 1
                );
            } else {
                appear.put(nums[i], 1);
            }
        }

        int longestSquareStreak = -1;
        for (Map.Entry<Integer, Integer> pair : appear.entrySet()) {
            if (pair.getValue() > 1) {
                longestSquareStreak = Math.max(longestSquareStreak, pair.getValue());
            }
        }

        return longestSquareStreak;
    }
}

import math
class Solution:
    def reserve_count_square(self, num: int, count_square: dict, mark_nums: set):
        if num in count_square:
            return count_square[num]
        sqr_num = math.isqrt(num)
        if sqr_num ** 2 != num or sqr_num not in mark_nums:
            count_square[num] = 1
            return 1
        count_square[num] = self.reserve_count_square(sqr_num, count_square, mark_nums) + 1
        return count_square[num]

    def longestSquareStreak(self, nums: List[int]) -> int:
        count_square = {}
        mark_nums = set(nums)
        for num in nums:
            self.reserve_count_square(num, count_square, mark_nums)
        result = -1
        # print(count_square)
        for num in nums:
            result = max(count_square[num] if count_square[num] > 1 else -1, result)
        return result

function longestSquareStreak(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let max = 0;

    const bs = (target: number, start: number): number => {
        let l = start, r = n - 1;
        while (l <= r) {
            const m = l + Math.floor((r - l) / 2);
            if (nums[m] === target) return m;
            else if (nums[m] < target) l = m + 1;
            else r = m - 1;
        }
        return -1;
    };

    for (let i = 0; i < n; i++) {
        let cur = nums[i];
        let streak = 1;

        while (true) {
            const next = bs(cur * cur, i + 1);
            if (next === -1) break;
            streak++;
            cur = nums[next];
        }

        if (streak > 1) {
            max = Math.max(max, streak);
        }
    }

    return max > 1 ? max : -1;
}

function longestSquareStreak(nums: number[]): number {
    const set = new Set(nums);
    let max = 0;

    for (const num of nums) {
        let streak = 0;
        let cur = num;

        while (set.has(cur)) {
            streak++;
            cur *= cur;
        }

        if (cur > 1) {
            max = Math.max(max, streak);
        }
    }

    return max > 1 ? max : -1;
}

class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        set<int> visiteds;
        long long square;
        long long max = nums[nums.size() - 1];
        int streak = 0;
        int streak_max = -1;
        int pos;
        for (int i = 0; i < nums.size(); ++i) {          
            if (visiteds.find(i) != visiteds.end())
                continue;
            streak = 1;
            square = nums[i];
            square *= square;
            pos = i;
            while (square <= max && (pos = binarySearch(nums, pos + 1, nums.size() - 1, (int)square)) != -1) {
                visiteds.insert(pos);
                streak++;
                square *= square;
            }
            if (streak > 1 && streak > streak_max)
                streak_max = streak;
        }
        return streak_max;
    }
private:
    int binarySearch(vector<int>& arr, int low, int high, int x)
    {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] < x)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return -1;
    }
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSquareStreak = function(nums) {
    nums.sort((u, v) => u - v);
    const dp = [];
    let ans = -1;
    for (const n of nums) {
        const m = Math.trunc(n ** (1/2));
        if (m * m === n && dp[m] != null) {
            dp[n] = dp[m] + 1;
            ans = Math.max(ans, dp[n]);
        } else {
            dp[n] = 1;
        }
    }
    return ans;
};

class Solution {
    public int longestSquareStreak(int[] nums) {
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        for (int i = 0; i < nums.length; i++) {
            int currStreak = 0;
            long num = nums[i];
            while (num < 10e5) {
                if (set.contains((int) num)) {
                    currStreak++;
                    num *= num;
                } else break;
            }
            ans = Math.max(ans, currStreak);
        }
        return ans < 2 ? -1 : ans;
    }
}

class Solution {
    public int longestSquareStreak(int[] nums) {
        int n = nums.length;
        int res = 0;
        Arrays.sort(nums);
        HashMap<Integer, Integer> map = new HashMap();
        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int sqrt = (int) Math.sqrt(num);
            if ((sqrt * sqrt == num) && map.containsKey(sqrt)) {
                count[i] = count[map.get(sqrt)] + 1;
            } else {
                count[i] = 1;
            }
            map.put(num, i);
            res=Math.max(res, count[i]);
        }
        return res==1?-1:res;
    }
}

class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        unordered_set<long long> s(nums.begin(), nums.end());
        long long ans = 1;
        for (int e : nums) {
            long long count = 0, t = e;
            while (s.find(t) != s.end()) count++, t = t*t;
            ans = max(ans, count);
        }
        return ans == 1 ? -1 : ans;
    }
};

class Solution {
    func longestSquareStreak(_ nums: [Int]) -> Int {
        let setN = Set(nums)
        var result = 0
        for num in nums {
            var cur = 1
            var num = num*num
            while num <= 100_000 && setN.contains(num) {
                cur += 1
                num = num*num
            }
            result = max(result, cur)
        }
        return result > 1 ? result : -1
    }
}

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        squareSet = set()
        for num in nums:
            if (int(num ** (1/2))) ** 2 == num:
                squareSet.add(num)
        result = 1
        for num in nums:
            count, curr = 1, num
            while curr ** 2 in squareSet:
                curr **= 2
                count += 1
            result = max(result, count)
        
        if result == 1:
            result = -1
        return result