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

afatnan · 18/8/23

Hehe toàn solution O(n^2 + v). Giờ nó tăng n lên 1000000 thì time out kĩ :look_down:

. Giải solution O(n + v) cho chất

Python:

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        adj_edges = [0 for node in range(n)]

        for node1, node2 in roads:
            adj_edges[node1] += 1
            adj_edges[node2] += 1


        first_max_edges = 0
        second_max_edges = 0
        first_max_nodes = []
        second_max_nodes = []

        for node in range(n):
            if adj_edges[node] > first_max_edges:
                second_max_edges = first_max_edges
                second_max_nodes = first_max_nodes
                first_max_edges = adj_edges[node]
                first_max_nodes = [node]

            elif adj_edges[node] == first_max_edges:
                first_max_nodes.append(node)

            elif adj_edges[node] > second_max_edges:
                second_max_edges = adj_edges[node]
                second_max_nodes = [node]

            elif adj_edges[node] == second_max_edges:
                second_max_nodes.append(node)

        # print(first_max_edges, first_max_nodes)
        # print(second_max_edges, second_max_nodes)
       

        if len(first_max_nodes) == 1:
            max_node = first_max_nodes[0]
            total_edges_2_cities = first_max_edges + second_max_edges
            roads = set([tuple(road) for road in roads])
           
            # print(max_node)

            for node in second_max_nodes:
                if (node, max_node) not in roads \
                    and (max_node, node) not in roads:
                   
                    return total_edges_2_cities
           
            return total_edges_2_cities - 1


        total_edges_2_cities = first_max_edges * 2
        total_edges_max_nodes = 0
        first_max_nodes = set(first_max_nodes)

        for node1, node2 in roads:
            if node1 in first_max_nodes \
                and node2 in first_max_nodes:

                total_edges_max_nodes += 1
       
        if total_edges_max_nodes * 2 \
            == len(first_max_nodes) * (len(first_max_nodes) - 1):

            total_edges_2_cities -= 1
   
        return total_edges_2_cities

Tai vi de bai bao len(roads) la O(n^2) roi nen ko muon toi uu phan sau nua.

Violet_7 · 18/8/23

Hover đã nói:
for node1, node2 in roads:
if node1 in first_max_nodes \
and node2 in first_max_nodes:

total_edges_max_nodes += 1

Sao thím không dừng luôn khi không connect mà tính cái này làm gì nhỉ?

Sao dừng thím, em cần đếm số cạnh các max_node connect vs nhau mà

Violet_7 · 18/8/23

afatnan đã nói:
Tai vi de bai bao len(roads) la O(n^2) roi nen ko muon toi uu phan sau nua.

Thì làm kia cho chất :big_smile:

. nếu n lên 1 củ thì cách kia timeout

Hover · 18/8/23

Violet_7 đã nói:
Sao dừng thím, em cần đếm số cạnh các max_node connect vs nhau mà

Thím đếm rồi check nó có fully connected không thì đổi lại chỉ cần 1 cái không connect là break được còn gì.

NahSama · 18/8/23

bài hôm nay với constraint như vậy + logic bth tính ra ez thôi chứ. Chủ đề graph chứ thấy nó là array đúng hơn

Java:

class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        int[] cnt = new int[n];
        Set<Integer> set = new HashSet<>();
        for (int[] road: roads) {
            cnt[road[0]]++;
            cnt[road[1]]++;
            set.add(road[0] * 1000 + road[1]);
            set.add(road[1] * 1000 + road[0]);
        }

        int max = 0;
        for (int i = 0; i < cnt.length - 1; i++) {
            for (int j = i + 1; j < cnt.length; j++) {
                int k = 0;
                if (set.contains(i * 1000 + j) || set.contains(j * 1000 + i)) k = -1;
                max = Math.max(max, cnt[i] + cnt[j] + k);
            }
        }

        return max;
    }
}

anoldvozer1710.v2 · 18/8/23

Violet_7 đã nói:

Hehe toàn solution O(n^2 + v). Giờ nó tăng n lên 1000000 thì time out kĩ :look_down:

. Giải solution O(n + v) cho chất

Python:

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        adj_edges = [0 for node in range(n)]

        for node1, node2 in roads:
            adj_edges[node1] += 1
            adj_edges[node2] += 1


        first_max_edges = 0
        second_max_edges = 0
        first_max_nodes = []
        second_max_nodes = []

        for node in range(n):
            if adj_edges[node] > first_max_edges:
                second_max_edges = first_max_edges
                second_max_nodes = first_max_nodes
                first_max_edges = adj_edges[node]
                first_max_nodes = [node]

            elif adj_edges[node] == first_max_edges:
                first_max_nodes.append(node)

            elif adj_edges[node] > second_max_edges:
                second_max_edges = adj_edges[node]
                second_max_nodes = [node]

            elif adj_edges[node] == second_max_edges:
                second_max_nodes.append(node)

        # print(first_max_edges, first_max_nodes)
        # print(second_max_edges, second_max_nodes)
        

        if len(first_max_nodes) == 1:
            max_node = first_max_nodes[0]
            total_edges_2_cities = first_max_edges + second_max_edges
            roads = set([tuple(road) for road in roads])
            
            # print(max_node)

            for node in second_max_nodes:
                if (node, max_node) not in roads \
                    and (max_node, node) not in roads:
                    
                    return total_edges_2_cities
            
            return total_edges_2_cities - 1


        total_edges_2_cities = first_max_edges * 2
        total_edges_max_nodes = 0
        first_max_nodes = set(first_max_nodes)

        for node1, node2 in roads:
            if node1 in first_max_nodes \
                and node2 in first_max_nodes:

                total_edges_max_nodes += 1
        
        if total_edges_max_nodes * 2 \
            == len(first_max_nodes) * (len(first_max_nodes) - 1):

            total_edges_2_cities -= 1
    
        return total_edges_2_cities

Mình nghĩ worst case thì cũng tựa tựa nhau thôi mà nhỉ. Vd làm theo cách của thím, trong trường hợp tất cả các node đều nối với nhau chẳng hạn :byebye:

via theNEXTvoz for iPhone

Violet_7 · 18/8/23

Hover đã nói:
Thím đếm rồi check nó có fully connected không thì đổi lại chỉ cần 1 cái không connect là break được còn gì.

Thế thì check thế cần O(n^2) mà thím

Hover · 18/8/23

anoldvozer1710.v2 đã nói:
Mình nghĩ worst case thì cũng tựa tựa nhau thôi mà nhỉ. Vd làm theo cách của thím, trong trường hợp tất cả các node đều nối với nhau chẳng hạn

via theNEXTvoz for iPhone

Uh nhưng best case thì nó tốt hơn cách kia, nên nếu implement được thì vẫn nên làm. Mà code cũng nhanh mà.

Hover · 18/8/23

Violet_7 đã nói:
Thế thì check thế cần O(n^2) mà thím

Ý mình là có thể break được sớm hơn, còn worst case thì dĩ nhiên là O(n^2) như nhau.

Violet_7 · 18/8/23

anoldvozer1710.v2 đã nói:
Mình nghĩ worst case thì cũng tựa tựa nhau thôi mà nhỉ. Vd làm theo cách của thím, trong trường hợp tất cả các node đều nối với nhau chẳng hạn

via theNEXTvoz for iPhone

Khác chứ nhỡ số node nhiều cạnh ít thì sao :sweat:

Hover · 18/8/23

Violet_7 đã nói:
Thế thì check thế cần O(n^2) mà thím

Mà thím xem có đang hiểu nhầm ý mình không nhé. :pudency:

Violet_7 · 18/8/23

Hover đã nói:
Ý mình là có thể break được sớm hơn, còn worst case thì dĩ nhiên là O(n^2) như nhau.

Worst case của mình là O(n + v) mà. Sao O(n^2 + v) đc. Bài này n=100 thì nó giống chứ n = 1 củ thì nó khác đấy :look_down:

Hover · 18/8/23

Violet_7 đã nói:
Thế thì check thế cần O(n^2) mà thím

À sorry. Hiểu ý thím rồi. Nhưng mình có thể compare maxNodeCount ^ 2 và edge.size để quyết định đi flow nào. Chứ luôn đi theo edge ko phải cách tốt thím ạ. Đi theo node còn có break early nữa.

Violet_7 · 18/8/23

Hover đã nói:
À sorry. Hiểu ý thím rồi. Nhưng mình có thể compare maxNodeCount ^ 2 và edge.size để quyết định đi flow nào. Chứ luôn đi theo edge ko phải cách tốt thím ạ. Đi theo node còn có break early nữa.

MaxNodeCount có thể bằng n nên cách đó ko tối ưu

Hover · 18/8/23

Violet_7 đã nói:
MaxNodeCount có thể bằng n nên cách đó ko tối ưu

Thì mình compare rồi mới chạy thì luôn đi hướng tối ưu thím. Thay vì tự assume là edge < maxNodeCount^2. Edge cũng có thể là n^2 mà.

Violet_7 · 18/8/23

Hover đã nói:
Thì mình compare rồi mới chạy thì luôn đi hướng tối ưu thím. Thay vì tự assume là edge < maxNodeCount^2. Edge cũng có thể là n^2 mà.

Thì đó. Cách mình là O(n + v) mặc dù trong nhiều case ko tối ưu hơn mấy O(n^2 + v) nhưng vẫn tối ưu hơn đoạn n và n^2 và trong 1 số case thì vẫn là tối ưu hơn rất nhiều (ví dụ case n và v đều là 1 củ) :big_smile:

. Thế nên ms beat 100% :beauty:

Hover · 18/8/23

Violet_7 đã nói:
Thì đó. Cách mình là O(n + v) mặc dù trong nhiều case ko tối ưu hơn mấy O(n^2 + v) nhưng vẫn tối ưu hơn đoạn n và n^2 và trong 1 số case thì vẫn là tối ưu hơn rất nhiều (ví dụ case n và v đều là 1 củ) . Thế nên ms beat 100%

Thím thêm đoạn if nữa thì chắc chắn vẫn beat 100% thôi. :beauty:

freedom.9 · 18/8/23

Hover đã nói:
Đề bài mình thấy ghi rất rõ và đọc hiểu dễ mà thím.
Network rank = tổng số cạnh unique đi đến 2 thành phố, chỉ thế thôi, đừng nên giả định thêm gì cả.

Còn tại sao code thím vẫn accept thì do disjoint set thím code sai rồi, thím thử tìm xem sai ở đâu nhé

. Mà disjoint set thím cài đặt cách hơi đơn giản quá, nên tập cài tối ưu luôn cho quen tay

À mình biết sai đâu rồi, qua chưa init default values cho set, nên kết quả thằng nào cũng được ktra connected hết

Do mình sida chứ ko phải đề, lần sau đọc kĩ hơn

via theNEXTvoz for iPhone

midnight_sun · 18/8/23

Mã:

func maximalNetworkRank(n int, roads [][]int) int {
    graph := make(map[string]bool)

    for _, item := range roads {
        graph[fmt.Sprintf("%d-%d", item[0], item[1])] = true
        graph[fmt.Sprintf("%d-%d", item[1], item[0])] = true
    }

    result := 0

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            rank := 0

            if graph[fmt.Sprintf("%d-%d", i, j)] {
                rank--
            }

            for k := 0; k < n; k++ {
                if graph[fmt.Sprintf("%d-%d", i, k)] {
                    rank++
                }
                if graph[fmt.Sprintf("%d-%d", j, k)] {
                    rank++
                }
            }
            
            if rank > result {
                result = rank
            }
        }
    }
    
    return result
}

Bleach & Sarcasm · 19/8/23

Violet_7 đã nói:
Thì đó. Cách mình là O(n + v) mặc dù trong nhiều case ko tối ưu hơn mấy O(n^2 + v) nhưng vẫn tối ưu hơn đoạn n và n^2 và trong 1 số case thì vẫn là tối ưu hơn rất nhiều (ví dụ case n và v đều là 1 củ) . Thế nên ms beat 100%

đề cho số lượng road có thể lên tới O(n^2) nên O(n+v) cũng là O(n^2) thoy mà, chắc mấy test case có ít v nên mới beat 100% được

n=1 củ thì v 10^12 chạy gì nổi

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

Senior Member

Member

Member

Member

Senior Member

Senior Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này