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

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1
        heap = [(0 ,0 ,0)] # time, r, c
        visited = set()
        while heap:
            time, r, c = heapq.heappop(heap)
            if (r, c) == (rows - 1, cols - 1):
                return time
            if (r, c) in visited:
                continue
            #We have to mark visited here because we need to re-visit all neis if we dont have enough time to move.
            visited.add((r, c))
            for rd, cd in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
                if 0 <= rd < rows and 0 <= cd < cols and (rd, cd) not in visited:
                    wait = 1 if (grid[rd][cd] - time) % 2 == 0 else 0
                    next_time = max(time + 1, grid[rd][cd] + wait)
                    heapq.heappush(heap, (next_time, rd, cd))
        return -1

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1
        m, n, visited, heap  = len(grid), len(grid[0]), set(), [(0, 0, 0)]
        while heap:
            dis, x, y = heappop(heap)
            if (x, y) == (m - 1, n - 1): return dis
            if (x, y) in visited: continue
            visited.add((x, y))
            for xx, yy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if m > xx > -1 < yy < n:
                    heappush(heap, (dis + max(0, (grid[xx][yy] - dis) & ~1) + 1, xx, yy))

class Solution {
    public int minimumTime(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        int[][] dirs = new int[][] { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

        if(grid[1][0]>1 && grid[0][1]>1) return -1;
        pq.add(new int[] { 0, 0,0});
        while (!pq.isEmpty()) {
            int[] cell = pq.poll();
            int t = cell[2];  
            if(cell[0] == m - 1 && cell[1] == n - 1){
                return t;
            }
            for (int[] dir : dirs) {
                int i = cell[0] + dir[0];
                int j = cell[1] + dir[1];
               
                if (i >= 0 && i < m && j >= 0 && j < n && !visited[i][j]) {
                    if (t >= grid[i][j]) {
                        pq.add(new int[] { i, j, t+1});
                    }else{
                        pq.add(new int[]{i,j,grid[i][j]+(grid[i][j]-t+1)%2});
                    }
                    visited[i][j]= true;
                }
            }

        }
        return -1;
    }
}

public class Solution
{
    private int[][] moves = [[0, 1], [1, 0], [0, -1], [-1, 0]];

    public int MinimumTime(int[][] grid)
    {
        int m = grid.Length, n = grid[0].Length;
        var res = new int[m][];
        for (int i = 0; i < m; i++)
        {
            res[i] = new int[n];
            Array.Fill(res[i], int.MaxValue);
        }

        if (grid[1][0] > 1 && grid[0][1] > 1) return -1;
        var queue = new Queue<int[]>();
        res[0][0] = 0;
        queue.Enqueue([0, 0, 0, -1, -1, -1]);
        while (queue.TryDequeue(out var cur))
        {
            int time = cur[0], row = cur[1], column = cur[2];
            int prevtime = cur[3], prevrow = cur[4], prevcolumn = cur[5];
            if (prevrow >= 0 && prevtime > res[prevrow][prevcolumn] && time > res[row][column])
            {
                continue;
            }
            foreach (var move in moves)
            {
                var _row = row + move[0];
                var _column = column + move[1];

                if (_row >= 0 && _row < grid.Length && _column >= 0 && _column < grid[0].Length)
                {
                    var plus = 1;
                    if (time + 1 < grid[_row][_column])
                    {
                        var gap = grid[_row][_column] - res[row][column];
                        plus = gap + (gap % 2 == 1 ? 0 : 1);
                    }

                    if (time + plus >= res[_row][_column]) continue;
                    res[_row][_column] = time + plus;
                    queue.Enqueue([time + plus, _row, _column, time, row, column]);
                }
            }
        }

        return res[^1][^1];
    }
}

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        def get_nexts(pos):
            res = []
            res.append((pos[0] - 1, pos[1])) if pos[0] > 0 else None
            res.append((pos[0], pos[1] - 1)) if pos[1] > 0 else None
            res.append((pos[0] + 1, pos[1])) if pos[0] < len(grid) - 1 else None
            res.append((pos[0], pos[1] + 1)) if pos[1] < len(grid[0]) - 1 else None
            return res

        def bfs():
            queue = []
            visited = set()
            depth = {}
            heapq.heappush(queue, (0, (0, 0)))
            visited.add((0, 0))
            depth[(0, 0)] = 0

            while len(queue) > 0:
                _, curr = heapq.heappop(queue)
                if curr == (len(grid) - 1, len(grid[0]) - 1):
                    return depth[curr]
                for next in get_nexts(curr):
                    if next not in visited:
                        visited.add(next)
                        depth_add = max(0, grid[next[0]][next[1]] - 1 - depth[curr])
                        if depth_add % 2 != 0:
                            depth_add += 1
                        depth[next] = depth[curr] + 1 + depth_add
                        heapq.heappush(queue, (depth[next], next))
            return -1

        if grid[1][0] > 1 and grid[0][1] > 1:
            return -1
        return bfs()

class Solution {
    public int minimumTime(int[][] grid) {
        if (grid[0][1] > 1 && grid[1][0] > 1) {
            return -1;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] directions = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

        boolean[][] visited = new boolean[m][n];

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        pq.add(new int[] { grid[0][0], 0, 0 });

        while (!pq.isEmpty()) {
            int[] current = pq.poll();

            int cost = current[0], x = current[1], y = current[2];

            if (x == m - 1 && y == n - 1) {
                return cost;
            }

            if (visited[x][y])
                continue;
            visited[x][y] = true;

            for (int[] dir : directions) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                int newCost = cost + 1;

                if (newX < 0 || newX >= m || newY < 0 || newY >= n || visited[newX][newY]) {
                    continue;
                }

                if (newCost < grid[newX][newY]) {
                    int diff = grid[newX][newY] - newCost;
                    newCost = grid[newX][newY] + diff % 2;
                }
                pq.add(new int[] { newCost, newX, newY });
            }
        }

        return -1;

    }
}

class Solution {
    public long countGood(int[] nums, int k) {
        int  n= nums.length;
        long ans =  0;
        int l =0;
        int cur_pair =0;
        HashMap<Integer, Integer> freq = new HashMap();
        for(int r = 0;r<nums.length;r++){
            int num = nums[r];
            freq.put(num, freq.getOrDefault(num, 0)+1);
            cur_pair+= freq.get(num)-1;
            while(l<r && cur_pair>=k){
                ans += n-r;

                freq.put(nums[l], freq.get(nums[l])-1);
                cur_pair-= freq.get(nums[l]);
                l++;
            }
        }
        return ans;
    }
}