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

import numpy as np

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1[0])

        a = np.pad(img1, ((0, 0), (0, n - 1))).ravel()
        b = np.pad(img2, ((0, 0), (0, n - 1))).ravel()

        tmp = int(2**(np.ceil(np.log2(2 * len(a) - 1))))
        return round(np.fft.irfft(np.fft.rfft(a, tmp) * np.conj(np.fft.rfft(b, tmp)), n=tmp).max())

class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        final int n = img1.length;
        int maxOverlap = 0;

        for (int dr = -n + 1; dr <= n - 1; dr++) {
            for (int dc = -n + 1; dc <= n - 1; dc++) {
                int overlap = 0;

                int rStart = Math.max(0, -dr);
                int rEnd = Math.min(n - 1, n - 1 - dr);
                int cStart = Math.max(0, -dc);
                int cEnd = Math.min(n - 1, n - 1 - dc);

                for (int r = rStart; r <= rEnd; r++) {
                    for (int c = cStart; c <= cEnd; c++) {
                        if (img1[r + dr][c + dc] == 1 && img2[r][c] == 1) {
                            overlap++;
                        }
                    }
                }
                maxOverlap = Math.max(maxOverlap, overlap);
            }
        }
        return maxOverlap;
    }
}

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        def render(img: list[list[int]], x: int, y: int) -> list[list[int]]:
            new_img = [[0] * n for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    new_i = i - x
                    new_j = j - y
                    pos_val = 0
                    if new_i >= 0 and new_i < n and new_j >= 0 and new_j < n:
                        pos_val = img[new_i][new_j]
                    new_img[i][j] = pos_val
            return new_img
        
        def countOverlap(img1: list[list[int]], img2: list[list[int]]) -> int:
            res = 0
            for i in range(n):
                for j in range(n):
                    res = res + img1[i][j] * img2[i][j]
            
            return res
        
        res = 0
        for i in range(1 - n, n):
            for j in range(1 - n, n):
                new_img = render(img1, i, j)
                res = max(res, countOverlap(new_img, img2))

        return res

class Solution {
    public:
        bool isRectangleOverlap(const std::vector<int> &rec1, const std::vector<int> &rec2) {
            return !(rec2[0] >= rec1[2] || rec2[1] >= rec1[3] || rec2[2] <= rec1[0] || rec2[3] <= rec1[1]);
        }
};

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        if (rec1[2] > rec2[0] && rec2[2] > rec1[0]
                && rec1[3] > rec2[1] && rec2[3] > rec1[1]) {
            return true;
        }
        return false;
    }
}

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        if rec1[0] >= rec2[2] or rec2[0] >= rec1[2] or rec1[1] >= rec2[3] or rec2[1] >= rec1[3]:
            return False
        
        return True

function isRectangleOverlap(rec1: number[], rec2: number[]): boolean {
    return !(
        rec1[2] <= rec2[0] ||
        rec2[2] <= rec1[0] ||
        rec1[3] <= rec2[1] ||
        rec2[3] <= rec1[1]   
    );
}

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        def isPalindrome(s: str) -> bool:
            n = len(s)
            for i in range(math.floor(n / 2) + 1):
                if s[i] != s[n - 1 - i]:
                    return False
            return True
        res = 0
        n = len(s)
        l = 0
        while l < n:
            r = l + k - 1 # right pointer
            if r > n - 1:
                break
            found = False
            while r < n:
                for i in range(l, r - k + 2):
                    tmp = s[i:r + 1]
                    if isPalindrome(tmp):
                        l = r + 1
                        found = True
                        res += 1
                        break
                if found:
                    break
                r += 1
            if not found:
                break
           
        return res

class Solution {
    public int numberOfSets(int n, int k) {
        final long MOD = 1_000_000_007L;

        long[][] dp = new long[n][k + 1];
        long[][] prefix = new long[n][k + 1];

        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
            prefix[i][0] = i + 1;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j];

                dp[i][j] += prefix[i - 1][j - 1];
                dp[i][j] %= MOD;

                prefix[i][j] = (prefix[i - 1][j] + dp[i][j]) % MOD;
            }
        }

        return (int) dp[n - 1][k];
    }
}