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

freedom.9 · 27/11/24

sang cty mới bận quá, mãi mới ngoi lên thớt đc :doubt:

JavaScript:

function shortestDistanceAfterQueries(n: number, queries: number[][]): number[] {
    const g: Map<number, number[]> = new Map();
    for (let i = 0; i < n - 1; i++) {
        if (!g.has(i)) {
            g.set(i, []);
        }
        g.get(i)?.push(i + 1);
    }

    const bfs = () => {
        const arr: number[] = Array(n).fill(-1);
        arr[0] = 0;
        const q: number[] = [0];

        let idx = 0;
        while (idx < q.length) {
            const node = q[idx++];
            if (g.has(node)) {
                for (const nei of g.get(node)!) {
                    if (arr[nei] === -1) {
                        arr[nei] = arr[node] + 1;
                        q.push(nei);
                    }
                }
            }
        }
        return arr[n - 1];
    }
    const res: number[] = [];
    for (const [u, v] of queries) {
        if (!g.has(u)) {
            g.set(u, []);
        }
        g.get(u)?.push(v);
        res.push(bfs());
    }

    return res;
};

Vẫn chưa thấy cái cạc nào à Á Nô

via theNEXTvoz for iPhone

LmaoSuVuong · 27/11/24

Tinh Hoa Đông Lào đã nói:
Cơm thêm Q3- Sep 08, 24: https://leetcode.com/problems/reach-end-of-array-with-max-score/
- gần 40 phút mới code ra
Xem tệp đính kèm 2804045

Python:

class Solution: def findMaximumScore(self, nums: List[int]) -> int: n = len(nums) dp = [-1] * n stack = [0] for i in range(1, len(nums)): while stack and nums[i] > nums[stack[-1]]: j = stack.pop() dp[j] = i stack.append(i) @cache def f(i): if i >= n - 1: return 0 if dp[i] == -1: return nums[i] * (n - 1 - i) else: return nums[i] * (dp[i] - i) + f(dp[i]) return f(0)

bài này bác dry run vài index là nhìn ra mà. tham lam lỏ

anoldvozer1710.v2 · 27/11/24

freedom.9 đã nói:
Vẫn chưa thấy cái cạc nào à Á Nô

via theNEXTvoz for iPhone

culi code húp mì tôm qua ngày, lấy đâu ra cạc mà phát

freedom.9 · 28/11/24

anoldvozer1710.v2 đã nói:
culi code húp mì tôm qua ngày, lấy đâu ra cạc mà phát

Toy mà là MOD toy sẽ ra rule ông nào vô topic này luyện 6 tháng có offer mới mà ko phát cạc là bị ban 6 tháng :doubt:

freedom.9 · 28/11/24

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

nchhnchh · 28/11/24

Python:

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n,maxVal = len(grid), len(grid[0]), 100001
        minObs = [[maxVal] * n for _ in range(m)]
        minObs[0][0] = 0

        q = deque([(0, 0, 0)])
        while q:
            obs, u, v = q.popleft()
            if u - 1 >= 0 and minObs[u-1][v] == maxVal:
                minObs[u - 1][v] = obs + grid[u-1][v]
                if grid[u-1][v]:
                    q.append((minObs[u - 1][v], u - 1, v))
                else:
                    q.appendleft((minObs[u - 1][v], u - 1, v))
            if u + 1 < m and minObs[u+1][v] == maxVal:
                minObs[u+1][v] = obs + grid[u+1][v]
                if grid[u+1][v]:
                    q.append((minObs[u+1][v], u+1, v))
                else:
                    q.appendleft((minObs[u+1][v], u+1, v))
            if v - 1 >= 0 and minObs[u][v - 1] == maxVal:
                minObs[u][v - 1] = obs + grid[u][v-1]
                if grid[u][v-1]:
                    q.append((minObs[u][v - 1], u, v - 1))
                else:
                    q.appendleft((minObs[u][v - 1], u, v - 1))
            if v + 1 < n and minObs[u][v+1] == maxVal:
                minObs[u][v+1] = obs + grid[u][v+1]
                if grid[u][v+1]:
                    q.append((minObs[u][v+1], u, v+1))
                else:
                    q.appendleft((minObs[u][v+1], u, v+1))
        return minObs[m - 1][n - 1]

anoldvozer1710.v2 · 28/11/24

mở lên thấy Hard thì cút thôi :doubt:

chiyeuemthoi · 28/11/24

hard thui cop z :shame:

manhduydl · 28/11/24

Có group zalo hay mess luyện leetcode không mọi người, cho mình tham gia với. Tự làm 1 mình không có động lực

thanbaiks · 28/11/24

JavaScript:

var minimumObstacles = function (grid) {
    const m = grid.length, n = grid[0].length;
    let q1 = new Queue(), q2 = new Queue(), step = 0;
    q1.enqueue([0, 0], 0);
    grid[0][0] = -1;
    const nextOf = (u, v) => {
        return [[-1, 0], [1, 0], [0, -1], [0, 1]]
            .map(([i, j]) => [u + i, v + j])
            .filter(([i, j]) => i >= 0 && i < m && j >= 0 && j < n);
    };
    while (true) {
        while (!q1.isEmpty()) {
            const [i, j] = q1.dequeue();
            if (i === m - 1 && j === n - 1) {
                return step;
            }
            for (const [u, v] of nextOf(i, j)) {
                if (grid[u][v] === -1) {
                    continue;
                }
                (grid[u][v] ? q2 : q1).enqueue([u, v]);
                grid[u][v] = -1;
            }
        }
        step++;
        [q1, q2] = [q2, q1];
    }
};

thangkc89 · 28/11/24

Bài này dijkstra chưa chắc đã giòn đâu :hungry:

Python:

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

        m = len(grid)
        n = len(grid[0])
        d = [[INF] * n for _ in range(m)]

        d[0][0] = 0

        q = [(0, 0)]
        q_index = 0

        vectors = [
            (-1, 0), (0, 1), (1, 0), (0, -1)
        ]
        while q_index < len(q):
            (u, v) = q[q_index]
            q_index += 1

            q2 = [(u, v)]
            q2_index = 0

            while q2_index < len(q2):
                (x, y) = q2[q2_index]
                q2_index += 1

                for (vx, vy) in vectors:
                    i, j = x + vx, y + vy
                    if i < 0 or i >= m or j < 0 or j >= n or d[i][j] <= d[x][y] + grid[i][j]:
                        continue
                    
                    if grid[i][j] == 0:
                        d[i][j] = d[x][y]
                        q2.append((i, j))
                    else:
                        d[i][j] = d[x][y] + 1
                        q.append((i, j))
        return d[m-1][n-1]

chiyeuemthoi · 28/11/24

manhduydl đã nói:
Có group zalo hay mess luyện leetcode không mọi người, cho mình tham gia với. Tự làm 1 mình không có động lực

lam o day thi sao ?

noobdev · 28/11/24

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:

Mắt Xích Yếu · 28/11/24

Java:

class Solution {
    public int minimumObstacles(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[2]-b[2]);
        int[][] visited = new int[m][n];
        int[][] directions = new int[][]{{-1,0},{0,-1},{1,0},{0,1}};
        for(int[] row:visited){
            Arrays.fill(row,-1);
        }
        pq.add(new int[]{m-1,n-1,0});
        while(!pq.isEmpty()){
            int[] cell = pq.poll();
            for(int[] dir:directions){
                int i = cell[0]+dir[0];
                int j = cell[1]+dir[1];
                if(i>=0 && i<m && j>=0 && j<n){
                    int remove = cell[2];
                    if(grid[i][j]==1) {
                        remove+=1;
                    }
                    if(visited[i][j]==-1 || visited[i][j]>remove){
                        pq.add(new int[]{i,j,remove});
                        visited[i][j]=remove;
                    }
                }
                if(i==0 && j==0) return visited[0][0];
            }
        }
        return visited[0][0];
    }
}

Mắt Xích Yếu · 28/11/24

thangkc89 đã nói:

Bài này dijkstra chưa chắc đã giòn đâu :hungry:

Python:

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

        m = len(grid)
        n = len(grid[0])
        d = [[INF] * n for _ in range(m)]

        d[0][0] = 0

        q = [(0, 0)]
        q_index = 0

        vectors = [
            (-1, 0), (0, 1), (1, 0), (0, -1)
        ]
        while q_index < len(q):
            (u, v) = q[q_index]
            q_index += 1

            q2 = [(u, v)]
            q2_index = 0

            while q2_index < len(q2):
                (x, y) = q2[q2_index]
                q2_index += 1

                for (vx, vy) in vectors:
                    i, j = x + vx, y + vy
                    if i < 0 or i >= m or j < 0 or j >= n or d[i][j] <= d[x][y] + grid[i][j]:
                        continue
                  
                    if grid[i][j] == 0:
                        d[i][j] = d[x][y]
                        q2.append((i, j))
                    else:
                        d[i][j] = d[x][y] + 1
                        q.append((i, j))
        return d[m-1][n-1]

ủa bfs = pq là dijkstra hả bác

thangkc89 · 28/11/24

Mắt Xích Yếu đã nói:
ủa bfs = pq là dijkstra hả bác

thay cái queue thành min heap theo khoảng cách từ source là thành dijkstra rồi bác

noobdev · 28/11/24

thangkc89 đã nói:

Bài này dijkstra chưa chắc đã giòn đâu :hungry:

Python:

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

        m = len(grid)
        n = len(grid[0])
        d = [[INF] * n for _ in range(m)]

        d[0][0] = 0

        q = [(0, 0)]
        q_index = 0

        vectors = [
            (-1, 0), (0, 1), (1, 0), (0, -1)
        ]
        while q_index < len(q):
            (u, v) = q[q_index]
            q_index += 1

            q2 = [(u, v)]
            q2_index = 0

            while q2_index < len(q2):
                (x, y) = q2[q2_index]
                q2_index += 1

                for (vx, vy) in vectors:
                    i, j = x + vx, y + vy
                    if i < 0 or i >= m or j < 0 or j >= n or d[i][j] <= d[x][y] + grid[i][j]:
                        continue
                   
                    if grid[i][j] == 0:
                        d[i][j] = d[x][y]
                        q2.append((i, j))
                    else:
                        d[i][j] = d[x][y] + 1
                        q.append((i, j))
        return d[m-1][n-1]

Quả 0-1 BFS thì đúng là khoai thật :beat_brick:

interview mà dính bài này chắc Dijitra cũng ko được accepted

LmaoSuVuong · 28/11/24

noobdev đã nói:
Quả 0-1 BFS thì đúng là khoai thật interview mà dính bài này chắc Dijitra cũng ko được accepted

dc chứ, em có cách nào tốt hơn ko- em không

noobdev · 28/11/24

LmaoSuVuong đã nói:
dc chứ, em có cách nào tốt hơn ko- em không

Xem tệp đính kèm 2804528

Giới hạn DNA rồi =((

luiz · 28/11/24

Dùng BFS priority queue mà beat được có 20% perfomance

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

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Member

Đã tốn tiền

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này