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

class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int:
        d, start, res, dp = defaultdict(int), 0, 0, [0] * (len(word) + 1)
        for i in range(len(word) - 1, -1, -1):
            if word[i] in 'aeiou': dp[i] = 1 + dp[i + 1]
        
        for i in range(len(word)):
            d[word[i]] += 1
            
            while all(d[v] >= 1 for v in 'aeiou') and (cons := (i - start + 1) - sum(d[v] for v in 'aeiou')) >= k:
                if cons == k:
                    res += (1 + dp[i+1])
                d[word[start]] -= 1
                start += 1
        return res

class Solution {
    public long countOfSubstrings(String word, int k) {
        int n = word.length();
        Map<Character, Integer> vowels = new HashMap();
        vowels.put('a',0);
        vowels.put('e',1);
        vowels.put('i',2);
        vowels.put('o',3);
        vowels.put('u',4);
        int[] freq=new int[5];
        Set<Character> set = new HashSet();
        int cntConsonant=0;
        long res=0;
        int l =0;
        int[] next = new int[n];
        int last =n;
        for(int i =n-1 ; i >=0;i--){
            char c = word.charAt(i);
            next[i]=last;
            if(!isVowel(c)) {
                last = i;
            }
        }
        for(int r =0;r<n;r++ ){
            char c = word.charAt(r);
            if(!isVowel(c)) cntConsonant++;
            else{
                freq[vowels.get(c)]++;
                set.add(c);
            }
             while (l < r && cntConsonant > k) {
                char cc = word.charAt(l);
                if (isVowel(cc)) {
                    if (--freq[vowels.get(word.charAt(l))] == 0) set.remove(word.charAt(l));
                } else {
                    cntConsonant--;
                }
                l++;
            }
            while (l < r && set.size()== 5 && cntConsonant == k) {
                res += (next[r] - r);
                char cc = word.charAt(l);
                if (isVowel(cc)) {
                    if (--freq[vowels.get(word.charAt(l))] == 0) set.remove(word.charAt(l));
                } else {
                    cntConsonant--;
                }
                l++;
            }
        }
        return res;
    }

    boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:

        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1

        dirs = [(0, -1), (-1, 0), (0, 1), (1, 0)]
        pq = [(0, 0, 0)]
        m, n, visisted = len(grid), len(grid[0]), set((0, 0))

        while pq:
            time, u, v = heapq.heappop(pq)

            if u == m - 1 and v == n - 1:
                return time
            
            for dir in dirs:
                u1, v1 = u + dir[0], v + dir[1]
                if u1 >= m or u1 < 0 or v1 >= n or v1 < 0 or (u1, v1) in visisted:
                    continue
                visisted.add((u1, v1))
                heapq.heappush(pq, (max(time + 1, grid[u1][v1] + (1 - (grid[u1][v1] - time) & 1) ), u1, v1))

        return -1

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumTime = function (grid) {
    if (grid[0][1] > 1 && grid[1][0] > 1) {
        return -1;
    }
    const m = grid.length, n = grid[0].length;
    const q = new MinPriorityQueue();
    const nextOf = (i, j) => {
        return [[0, 1], [0, -1], [1, 0], [-1, 0]]
            .map(([ii, jj]) => [i + ii, j + jj])
            .filter(([ii, jj]) => ii >= 0 && ii < m && jj >= 0 && jj < n);
    };
    q.enqueue([0, 0], 0);
    grid[0][0] = -1;
    while (!q.isEmpty()) {
        const { element: [i, j], priority: p } = q.dequeue();
        if (i === m - 1 && j === n - 1) {
            return p;
        }
        for (const [ii, jj] of nextOf(i, j)) {
            if (grid[ii][jj] >= 0) {
                const k = Math.max(
                    p + 1,
                    grid[ii][jj] + ((grid[ii][jj] & 1) ^ ((ii + jj) & 1))
                );
                grid[ii][jj] = -1;
                q.enqueue([ii, jj], k);
            }
        }
    }
};

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1
        m, n = len(grid), len(grid[0])
        visited = set()
        visited.add((0, 0))
        heap = []
        heapq.heappush(heap, (0, 0, 0))
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        while heap:
            cost, r, c = heapq.heappop(heap)
            if r == m - 1 and c == n - 1:
                return cost
            for dx, dy in directions:
                nx = dx + r
                ny = dy + c
                neighborCost = cost + 1
                if nx < 0 or nx >= m or ny < 0 or ny >= n or (nx, ny) in visited:
                    continue
                if neighborCost < grid[nx][ny]:
                    diff = grid[nx][ny] - neighborCost
                    neighborCost = grid[nx][ny] + diff%2
                visited.add((nx, ny))
                heapq.heappush(heap, (neighborCost, nx, ny))   
        return -1

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        INF = 10**9
        vectors = [
            (-1, 0), (0, 1), (1, 0), (0, -1)
        ]


        m = len(grid)
        n = len(grid[0])

        next_moves = 0
        for (x, y) in vectors:
            if x < 0 or x >= m or y < 0 or y >= n:
                continue
            
            if grid[x][y] <= 1:
                next_moves += 1
        if next_moves == 0:
            return -1

        d = [[INF] * n for _ in range(m)]
        d[0][0] = 0
        h = [(0, (0, 0))]

        while h:
            c, (u, v) = heappop(h)
            if c != d[u][v]:
                continue
            
            if u == m-1 and v == n-1:
                return c

            for (vx, vy) in vectors:
                x, y = u + vx, v + vy

                if x < 0 or x >= m or y < 0 or y >= n:
                    continue
                
                if d[u][v] + 1 >= grid[x][y]:
                    cost = d[u][v] + 1
                elif d[u][v] & 1:
                    cost = grid[x][y]
                    if cost & 1:
                        cost += 1
                else:
                    cost = grid[x][y]
                    if not cost & 1:
                        cost += 1
                
                
                if cost < d[x][y]:
                    d[x][y] = cost
                    heappush(h, (cost, (x, y)))
        return d[m-1][n-1]