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.
freedom.9 đã nói:
Bài này mình đoán đoán tí thôi rồi thấy có vẻ match với hint nên code thử xem, chứ nhìn thấy rating 2k9 sợ quá.
Vẽ cái graph ra thì thấy nếu source và destination nó bị disconnect bởi các cạnh -1 thì có 2 trường hợp.
1) Nối 1 cạnh -1 vào mà nó giảm distance xuống, nghĩa là cái cạnh -1 nó contribute vô đường đi ngắn nhất.
2) Nối 1 cạnh -1 vào mà distance ko giảm xuống, nghĩa là cạnh -1 đấy nó ko contribute vô đường đi ngắn nhất.
Rồi tới bước chọn value cho các cạnh -1, nếu chọn value là 1 mà distance giảm xuống vẫn lớn hơn target thì tiếp tục tìm cạnh khác, vì 1 là số nhỏ nhất mà vẫn ko ăn thua nên bỏ qua cạnh vừa rồi.
Còn nếu chọn value là 1 mà distance giảm xuống nhỏ hơn target thì việc còn lại chỉ cần tăng cái weight lên cho nó match với target là xong, các cạnh còn lại mark là 2*10^9 để nó khỏi contribute vô kết quả.
Nhấp để mở rộng...
nghe hay quá, lát nghỉ trưa code theo xem đc ko
aTiUJyS.png
 
đúng ra mình phải thành thật các bạn à, mình bài khó cop sol không phải vì mình xác định chỉ dành thời gian công sức vừa đủ để chuẩn bị cho pv, hay là biết tự lượng sức mình gì, như người đời có câu bóp d@i thì chọn bi vừa tay, không, mình không cao cả dzậy, bài khó cop sol là vì mình muốn có chút thời gian ăn chơi trác táng, thưởng hoa hút mật, đời ngắn lắm hardcore làm gì :(
 
small-lambda đã nói:
đúng ra mình phải thành thật các bạn à, mình bài khó cop sol không phải vì mình xác định chỉ dành thời gian công sức vừa đủ để chuẩn bị cho pv, hay là biết tự lượng sức mình gì, như người đời có câu bóp d@i thì chọn bi vừa tay, không, mình không cao cả dzậy, bài khó cop sol là vì mình muốn có chút thời gian ăn chơi trác táng, thưởng hoa hút mật, đời ngắn lắm hardcore làm gì :(
Nhấp để mở rộng...
YRsvqtB.png
Giống tập gym thôi, muốn cơ to phải nâng tạ vượt sức mình để làm rách cơ, gây viêm sưng thì khi nó lành lại cơ mới sẽ to hơn cơ cũ. Não không bị hành hạ thì làm sao lên trình được
eDmLMZm.png
Mình xl thế thôi mình mở sol lên đọc đây :burn_joss_stick:
 
Cố Trường Ca đã nói:
YRsvqtB.png
Giống tập gym thôi, muốn cơ to phải nâng tạ vượt sức mình để làm rách cơ, gây viêm sưng thì khi nó lành lại cơ mới sẽ to hơn cơ cũ. Não không bị hành hạ thì làm sao lên trình được
eDmLMZm.png
Mình xl thế thôi mình mở sol lên đọc đây :burn_joss_stick:
Nhấp để mở rộng...
Không giống như các tế bào khác, tế bào thần kinh không sinh sản hoặc tái tạo. Chúng không được thay thế khi chúng chết.
xài nhiều hết sớm chứ có phải cơ đâu mà bú thịt bò là tái tạo dc
V092S5K.gif
 
Cố Trường Ca đã nói:
YRsvqtB.png
Giống tập gym thôi, muốn cơ to phải nâng tạ vượt sức mình để làm rách cơ, gây viêm sưng thì khi nó lành lại cơ mới sẽ to hơn cơ cũ. Não không bị hành hạ thì làm sao lên trình được
eDmLMZm.png
Mình xl thế thôi mình mở sol lên đọc đây :burn_joss_stick:
Nhấp để mở rộng...
Nâng cho mỏi cơ thôi, lúc hồi phục chính là lúc phát triển cơ bắp. Chứ nâng đến rách cơ là hỏng cmnr :sweat:
Tương tự, bắt thằng lớp 1 học sách lớp 12 thì có hiểu cái đ gì đâu mà lên trình đc.
 
LmaoSuVuong đã nói:
Không giống như các tế bào khác, tế bào thần kinh không sinh sản hoặc tái tạo. Chúng không được thay thế khi chúng chết.
xài nhiều hết sớm chứ có phải cơ đâu mà bú thịt bò là tái tạo dc
V092S5K.gif
Nhấp để mở rộng...
Em xin lỗi, múa rìu qua mắt thợ rồi
UKiCiKh.png
Bác tha cho em nha
Người quan sát cô đơn đã nói:
Nâng cho mỏi cơ thôi, lúc hồi phục chính là lúc phát triển cơ bắp. Chứ nâng đến rách cơ là hỏng cmnr :sweat:
Tương tự, bắt thằng lớp 1 học sách lớp 12 thì có hiểu cái đ gì đâu mà lên trình đc.
Nhấp để mở rộng...
Rách ở đây là mức độ vi mô chứ có phải là nó rách hẳn đâu. Tiếng anh nó gọi là micro tears. Cái lớp 1 lớp 12 fen nói hiển nhiên rồi, tập tạ cũng nâng dần chứ ai lại nhảy cóc thế chấn thương s :doubt:
 
Bác @LmaoSuVuong khiêm tốn quá, em đăng hộ bác í
Java: 
class Solution {
    public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0], v = edges[i][1];
            graph[u].add(new int[]{v, i});
            graph[v].add(new int[]{u, i}); // Construct graph with edge indices
        }

        int[][] dist = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i != source) {
                dist[i][0] = dist[i][1] = Integer.MAX_VALUE;
            }
        }

        dijkstra(graph, edges, dist, source, 0, 0);
        int delta = target - dist[destination][0];
        if (delta < 0) return new int[][]{}; // Not possible to reach the target

        dijkstra(graph, edges, dist, source, delta, 1);
        if (dist[destination][1] < target) return new int[][]{}; // Still not possible

        for (int[] edge : edges) {
            if (edge[2] == -1) edge[2] = 1; // Set remaining -1 edges to 1
        }
        return edges;
    }

    private void dijkstra(List<int[]>[] graph, int[][] edges, int[][] dist, int source, int delta, int run) {
        int n = graph.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.add(new int[]{source, 0});
        dist[source][run] = 0;

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];
            int d = current[1];

            if (d > dist[u][run]) continue;

            for (int[] neighbor : graph[u]) {
                int v = neighbor[0], edgeIndex = neighbor[1];
                int weight = edges[edgeIndex][2];

                if (weight == -1) weight = 1; // Initially consider -1 as 1

                if (run == 1 && edges[edgeIndex][2] == -1) {
                    // Calculate the required weight adjustment for the second run
                    int newWeight = delta + dist[v][0] - dist[u][1];
                    if (newWeight > weight) {
                        edges[edgeIndex][2] = weight = newWeight; // Update edge weight
                    }
                }

                if (dist[v][run] > dist[u][run] + weight) {
                    dist[v][run] = dist[u][run] + weight;
                    pq.add(new int[]{v, dist[v][run]});
                }
            }
        }
    }
}
 
Cố Trường Ca đã nói:
Bác @LmaoSuVuong khiêm tốn quá, em đăng hộ bác í
Java: 
class Solution {
    public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0], v = edges[i][1];
            graph[u].add(new int[]{v, i});
            graph[v].add(new int[]{u, i}); // Construct graph with edge indices
        }

        int[][] dist = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i != source) {
                dist[i][0] = dist[i][1] = Integer.MAX_VALUE;
            }
        }

        dijkstra(graph, edges, dist, source, 0, 0);
        int delta = target - dist[destination][0];
        if (delta < 0) return new int[][]{}; // Not possible to reach the target

        dijkstra(graph, edges, dist, source, delta, 1);
        if (dist[destination][1] < target) return new int[][]{}; // Still not possible

        for (int[] edge : edges) {
            if (edge[2] == -1) edge[2] = 1; // Set remaining -1 edges to 1
        }
        return edges;
    }

    private void dijkstra(List<int[]>[] graph, int[][] edges, int[][] dist, int source, int delta, int run) {
        int n = graph.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.add(new int[]{source, 0});
        dist[source][run] = 0;

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];
            int d = current[1];

            if (d > dist[u][run]) continue;

            for (int[] neighbor : graph[u]) {
                int v = neighbor[0], edgeIndex = neighbor[1];
                int weight = edges[edgeIndex][2];

                if (weight == -1) weight = 1; // Initially consider -1 as 1

                if (run == 1 && edges[edgeIndex][2] == -1) {
                    // Calculate the required weight adjustment for the second run
                    int newWeight = delta + dist[v][0] - dist[u][1];
                    if (newWeight > weight) {
                        edges[edgeIndex][2] = weight = newWeight; // Update edge weight
                    }
                }

                if (dist[v][run] > dist[u][run] + weight) {
                    dist[v][run] = dist[u][run] + weight;
                    pq.add(new int[]{v, dist[v][run]});
                }
            }
        }
    }
}
Nhấp để mở rộng...
1725034622478.png
 
Bài hôm qua.
C-like: 
struct UnionFind {
    id: Vec<usize>,
    count: usize,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            id: Vec::from_iter(0..n),
            count: n,
        }
    }

    fn find(&mut self, i: usize) -> usize {
        let id_i = self.id[i];
        if self.id[id_i] != id_i {
            self.id[i] = self.find(id_i);
        }
        self.id[i]
    }

    fn union(&mut self, i: usize, j: usize) {
        let id_i = self.find(i);
        let id_j = self.find(j);
        if id_i != id_j {
            self.id[id_i] = id_j;
            self.count -= 1;
        }
    }
}

impl Solution {
    pub fn remove_stones(stones: Vec<Vec<i32>>) -> i32 {
        let n = stones.len();
        let uf = &mut UnionFind::new(n);

        for i in 0..n {
            let (x_i, y_i) = (stones[i][0], stones[i][1]);
            for j in (i + 1)..n {
                let (x_j, y_j) = (stones[j][0], stones[j][1]);
                if x_i == x_j || y_i == y_j {
                    uf.union(i, j);
                }
            }
        }

        (n - uf.count) as i32
    }
}
 
Ủa bài daily nay bị điên hả ae, giống bài mấy 2 3 hôm trước. Mà submit xong thì ko đc tính là sao :ah:
 
Trạng thái
Không mở để trả lời thêm.

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
1K
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
842
giayasics
giayasics

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.212.974

Chia sẻ trang này

Quay lại
Lên đầu trang