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

  • Người tạo chủ đề Người tạo chủ đề _Gia_Cat_Luong_
  • Ngày bắt đầu Ngày bắt đầu
Trạng thái
Không mở để trả lời thêm.
noobdev đã nói:
Mã: 
class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        heap = [(0, (0, 0))]
        visited = set()

        while heap:
            obs, (r, c) = heapq.heappop(heap)
            if (r, c) == (rows - 1, cols - 1):
                return obs + grid[r][c]
            if (r, c) in visited:
                continue
            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:
                    heapq.heappush(heap, (obs + grid[rd][cd], (rd, cd)))
        
        return rows + cols - 1

Lúc đầu ngồi chạy DFS ngu người :beat_brick:
Nhấp để mở rộng...
Nhìn condition vài toán 10^5 mà cũng chơi DFS đc à @@
 
Swift: 
import DequeModule
class Solution {
    func minimumObstacles(_ grid: [[Int]]) -> Int {
       
        let m = grid.count
        let n = grid[0].count
        var visited = Array(repeating: Array(repeating: false, count: n), count: m)
        var queues: Deque<(Int, Int, Int)> = [] // r, c, cost
        queues.append((0, 0, 0)) // begin at (0, 0) // grid[0][0] == 0

        let dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        while queues.count > 0 {
            let (r, c, cost) = queues.removeFirst()
            if r == m-1 && c == n-1 {
                return cost
            }
            if visited[r][c] { continue }
            visited[r][c] = true
            for (dR, dC) in dir {
                let newR = r + dR
                let newC = c + dC
                if newR >= 0 && newR < m && newC >= 0 && newC < n && !visited[newR][newC] {
                    if grid[newR][newC] == 0 {
                        queues.prepend((newR, newC, cost))
                    } else {
                        queues.append((newR, newC, cost + 1))
                    }
                }
            }
        }
        return -1
    }
}
 
0 1 Bfs hay thế nhỉ, nhìn editorial hiểu ý tưởng mà chưa nghĩ ra implement thế nào. Để mai thử code theo cái ý tưởng đó xem ok ko :ah:

via theNEXTvoz for iPhone
 
Python: 
class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        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 and (xx, yy) not in visited:
                    heappush(heap, (dis + grid[xx][yy], xx, yy))
 
Sửa lần cuối:
Java: 
class Solution {
    public int minimumObstacles(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] directions = {
                { -1, 0 },
                { 0, 1 },
                { 1, 0 },
                { 0, -1 }
        };

        int[][] visited = new int[m][n];
        for (int[] v : visited) {
            Arrays.fill(v, Integer.MAX_VALUE);
        }

        Deque<int[]> queue = new ArrayDeque<>();
        queue.offerLast(new int[] { 0, 0, 0 });
        visited[0][0] = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.pollFirst();
            int cost = current[0];
            int row = current[1];
            int col = current[2];

            if (row == m - 1 && col == n - 1) {
                return cost;
            }

            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];

                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                    int newCost = cost + grid[newRow][newCol];
                    if (newCost < visited[newRow][newCol]) {
                        visited[newRow][newCol] = newCost;
                        if (grid[newRow][newCol] == 1) {
                            queue.offerLast(new int[] { newCost, newRow, newCol });
                        } else {
                            queue.offerFirst(new int[] { newCost, newRow, newCol });
                        }
                    }
                }
            }
        }

        return -1;
    }
}
 
Mắt Xích Yếu đã nói:
ủa bfs = pq là dijkstra hả bác
JkpvuKo.png
Nhấp để mở rộng...
kinh bác này ko biết dijkstra mà tự nghĩ ra dijkstra từ bfs + heap, đầu óc ngang hàng người có giải Turing rồi
 
JavaScript: 
var minimumObstacles = function(grid) {
    const directions = [[0,1],[0,-1],[1,0],[-1,0]];
    const m = grid.length;
    const n = grid[0].length;
    const minObstaclesTo = Array.from({ length: m }, () => Array(n).fill(Number.MAX_SAFE_INTEGER));
    minObstaclesTo[0][0] = 0;
    const pq = new PriorityQueue({compare: (a, b)=>{
        return a[0] - b[0];
    }});
    pq.enqueue([0, 0, 0]);
    const isValidMove = (x, y) => {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    while(!pq.isEmpty()){
        const [minObstacle, x, y] = pq.dequeue();
        if(x === m - 1 && y === n - 1) return minObstacle;
        for(const [dx, dy] of directions){
            const newX = x + dx;
            const newY = y + dy;
            if(isValidMove(newX, newY)){
                const newObstacle = minObstacle + grid[newX][newY];
                if(newObstacle < minObstaclesTo[newX][newY]){
                    minObstaclesTo[newX][newY] = newObstacle;
                    pq.enqueue([newObstacle, newX, newY]);
                }
            }
        }
    }
    return -1;
};
 
noobdev đã nói:
Mã: 
class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        heap = [(0, (0, 0))]
        visited = set()

        while heap:
            obs, (r, c) = heapq.heappop(heap)
            if (r, c) == (rows - 1, cols - 1):
                return obs + grid[r][c]
            if (r, c) in visited:
                continue
            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:
                    heapq.heappush(heap, (obs + grid[rd][cd], (rd, cd)))
      
        return rows + cols - 1

Lúc đầu ngồi chạy DFS ngu người :beat_brick:
Nhấp để mở rộng...
Đọc lời giải bác này, thế hoá ra djkstra ko cần relaxation à mn
template mới này có chuẩn bài không?


Python: 
def dijkstra():  # Dijkstra to find shortest distance of paths from node `0` to any other nodes
    minHeap = [(0, 0)]  # dist, node
    dist = [float('inf')] * (n + 1)
    dist[0] = 0
    visited = set()
    while minHeap:
        d, u = heappop(minHeap)
        dist[u] = d
        if u in visited:
            continue
        for w, v in graph[u]:
            if v not in visited:
                heappush(minHeap, (dist[u] + w, v))
    return dist
 
freedom.9 đã nói:
0 1 Bfs hay thế nhỉ, nhìn editorial hiểu ý tưởng mà chưa nghĩ ra implement thế nào. Để mai thử code theo cái ý tưởng đó xem ok ko :ah:

via theNEXTvoz for iPhone
Nhấp để mở rộng...
e implement cái 0 1 BFS thì bị TLE :beat_brick:
C#: 
public class Solution
{
    public int MinimumObstacles(int[][] grid)
    {
        var m = grid.Length;
        var n = grid[0].Length;
        int[][] dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        var result = new int[m][];
        var deque = new LinkedList<int[]>();
        for (int i = 0; i < m; i++)
        {
            result[i] = new int[n];
            Array.Fill(result[i], int.MaxValue);
        }

        deque.AddFirst([0, 0, 0]);
        while (deque.Count > 0)
        {
            var node = deque.First.Value;
            deque.RemoveFirst();
            int cost = node[0], row = node[1], col = node[2];
            result[row][col] = cost;
            foreach (var dir in dirs)
            {
                var _row = row + dir[0];
                var _col = col + dir[1];
                if (0 <= _row && _row < m && 0 <= _col && _col < n
                    && result[_row][_col] == int.MaxValue)
                {
                    if (grid[_row][_col] == 0)
                    {
                        deque.AddFirst([cost, _row, _col]);
                    }
                    else
                    {
                        deque.AddLast([cost + 1, _row, _col]);
                    }
                }
            }
        }

        return result[^1][^1];
    }
}

Edit: như này thì ko TLE :confident:
C#: 
public class Solution
{
    public int MinimumObstacles(int[][] grid)
    {
        var m = grid.Length;
        var n = grid[0].Length;
        int[][] dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        var result = new int[m][];
        var deque = new LinkedList<int[]>();
        for (int i = 0; i < m; i++)
        {
            result[i] = new int[n];
            Array.Fill(result[i], int.MaxValue);
        }

        deque.AddFirst([0, 0, 0]);
        result[0][0] = 0;
        while (deque.Count > 0)
        {
            var node = deque.First.Value;
            deque.RemoveFirst();
            int cost = node[0], row = node[1], col = node[2];
            foreach (var dir in dirs)
            {
                var _row = row + dir[0];
                var _col = col + dir[1];
                if (0 <= _row && _row < m && 0 <= _col && _col < n
                    && result[_row][_col] == int.MaxValue)
                {
                    if (grid[_row][_col] == 0)
                    {
                        result[_row][_col] = cost;
                        deque.AddFirst([cost, _row, _col]);
                    }
                    else
                    {
                        result[_row][_col] = cost + 1;
                        deque.AddLast([cost + 1, _row, _col]);
                    }
                }
            }
        }

        return result[^1][^1];
    }
}
 
Sửa lần cuối:
freedom.9 đã nói:
Python: 
class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        visitedAt = [[inf for _ in range(n)] for _ in range(m)]
        visitedAt[0][0] = 0
        minHeap = []
        heapq.heappush(minHeap, (0, 0, 0))
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        while minHeap:
            cost, x, y = heapq.heappop(minHeap)
            if visitedAt[x][y] < cost:
                continue

            if x == m - 1 and y == n - 1:
                return cost

            for dx, dy in directions:
                nx = x + dx
                ny = y + dy
                if nx >= m or nx < 0 or ny >= n or ny < 0:
                    continue

                newCost = cost + grid[nx][ny]
                if newCost < visitedAt[nx][ny]:
                    visitedAt[nx][ny] = newCost
                    heapq.heappush(minHeap, (newCost, nx, ny))

        return -1
Nhấp để mở rộng...
Điều kiện if(visitedAt[x][y] < cost) là để tránh trường hợp process lại 1 node mà mình đã dequeue trước đó với cost nhỏ hơn đúng không bác? Code trong editorial thì không thấy check case này. E thử return -1 nếu condition này xảy ra thì thấy nó vẫn pass hết test case. E có nhờ chatgpt gen ra test case để trigger condition đó nhưng cũng không ra :v Em nghĩ case này có thể không bao giờ xảy ra với đồ thị chỉ có 0 và 1.
 
utilsx đã nói:
Điều kiện if(visitedAt[x][y] < cost) là để tránh trường hợp process lại 1 node mà mình đã dequeue trước đó với cost nhỏ hơn đúng không bác? Code trong editorial thì không thấy check case này. E thử return -1 nếu condition này xảy ra thì thấy nó vẫn pass hết test case. E có nhờ chatgpt gen ra test case để trigger condition đó nhưng cũng không ra :v Em nghĩ case này có thể không bao giờ xảy ra với đồ thị chỉ có 0 và 1.
Nhấp để mở rộng...
này để tránh process các out date data ở heap đó:

1732784707340.png


lần đầu dist = 3 được update trước (theo path A->C->B) cho nên khi gặp (3, 'B'), nó sẽ dùng giá trị tối ưu này để đi đến D

nhưng trước đó khi process A đã push vào heap giá trị (4, 'B'), nên khi gặp gía trị này không phải giá trị tốt ưu nên loại bỏ.

Chú ý:
  • heap lưu cả các giá trị bao gồm cả chưa tối ưu (out date)
  • dist chỉ lưu các giá trị tối ưu
 
Tinh Hoa Đông Lào đã nói:
này để tránh process các out date data ở heap đó:

Xem tệp đính kèm 2805082

lần đầu dist = 3 được update trước (theo path A->C->B) cho nên khi gặp (3, 'B'), nó sẽ dùng giá trị tối ưu này để đi đến D

nhưng trước đó khi process A đã push vào heap giá trị (4, 'B'), nên khi gặp gía trị này không phải giá trị tốt ưu nên loại bỏ.

Chú ý:
  • heap lưu cả các giá trị bao gồm cả chưa tối ưu (out date)
  • dist chỉ lưu các giá trị tối ưu
Nhấp để mở rộng...
Bác thử xem có thể gen test case khiến trường hợp outdate đó xảy ra ở bài này không? Đồ thị ở bài này e nghĩ nó đặc biệt hơn trường hợp tổng quát.
 
Bài nay khó phết, tối ưu mãi kết hợp hỏi GPT vài đoạn mới ra final :shame:, beat được 100%
1732785551269.png
C: 
int minimumObstacles(int** grid, int gridSize, int* gridColSize) {
    if (!gridSize || !gridColSize[0]) return 0;
    int m = gridSize;
    int n = gridColSize[0];
    
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    
    int* dist = malloc(m * n * sizeof(int));
    int* q0 = malloc(m * n * sizeof(int));
    int* q1 = malloc(m * n * sizeof(int));
    
    for (int i = 0; i < m * n; i++) {
        dist[i] = 0x3f3f3f3f;
    }
    
    int f0 = 0, r0 = 0;
    int f1 = 0, r1 = 0;
    
    dist[0] = 0;
    q0[r0++] = 0;
    
    while (f0 < r0 || f1 < r1) {
        int curr;
        if (f0 < r0) {
            curr = q0[f0++];
        } else {
            curr = q1[f1++];
        }
        
        int x = curr / n;
        int y = curr % n;
        
        if (x == m - 1 && y == n - 1) {
            int ans = dist[curr];
            free(dist);
            free(q0);
            free(q1);
            return ans;
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                int npos = nx * n + ny;
                int ncost = dist[curr] + grid[nx][ny];
                
                if (ncost < dist[npos]) {
                    dist[npos] = ncost;
                    if (grid[nx][ny] == 0) {
                        q0[r0++] = npos;
                    } else {
                        q1[r1++] = npos;
                    }
                }
            }
        }
    }
    
    free(dist);
    free(q0);
    free(q1);
    return -1;
}
 
Trạng thái
Không mở để trả lời thêm.
AD · 970×250

Chủ đề tương tự

Thach Sanh Mat Riu
Điều gì xảy ra nếu bạn uống nước chè xanh mỗi ngày?
2
Trả lời
22
Lượt xem
2K
dattenmoi
D
megume
thảo luận Hôm nay, buổi bình minh của AI robot đã đến
Trả lời
4
Lượt xem
1K
Toc Hong
Toc Hong
Lộc Tục
(Dịch) Cuộc điều tra của CBC/Radio-Canada tiết lộ công ty Việt Nam nhắm vào người Canada bằng tin giả AI để kiếm lời
2
Trả lời
30
Lượt xem
5K
dukeng995
dukeng995
Ti Amo
[Dịch] Công ty Việt Nam dùng tin giả do AI tạo ra để kiếm tiền — nhắm vào độc giả Canada
Trả lời
0
Lượt xem
1K
Ti Amo
Ti Amo
Gấu Ted
Độc giả ngày càng tin nhà báo hơn thương hiệu báo chí
Trả lời
10
Lượt xem
915
giayasics
giayasics
AD · 300×600

Thống kê chủ đề

Ngày tạo
_Gia_Cat_Luong_,
Người trả lời cuối
Vipluckystar,
Trả lời
17.755
Lượt xem
1.215.557
AD · 300×600

Chia sẻ trang này

AD · 300×600
Quay lại
Lên đầu trang