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.
HIL đã nói:
Naive solution, F#
Mã: 
// Defines the signature for the `cook`-function,
// although this is not strictly necessary
// thanks to the powerful type-inference system in F#
type Cook = string list -> string list list -> string list -> string list

let rec cook: Cook =
    fun recipes ingredientSets supplies ->
        let recipes = List.zip recipes ingredientSets
        let canCook = List.except supplies >> List.isEmpty
        let completed, pending = recipes |> List.partition (snd >> canCook)

        match completed with
        | [] -> []
        | completed ->
            let completed = completed |> List.map fst

            match pending with
            | [] -> completed
            | pending ->
                let newRecipes, newIngredients = pending |> List.unzip
                let newSupplies = completed |> List.append supplies

                cook newRecipes newIngredients newSupplies |> List.append completed
Nhấp để mở rộng...
Viết bằng F# thì test kiểu gì nhỉ? Vì leetcode không hỗ trợ F#.
Mấy cái CP thì chỉ có kattis là hỗ trợ F#, trước đây toàn bộ solution submit lên đó mình viết bằng F#
 
Java: 
class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        Map<Integer, List<Integer>> graph = buildReverseGraph(edges);
        List<List<Integer>> ancestors = new ArrayList<>();
        for (int i  = 0; i < n; i++) {
            boolean[] isVisited = new boolean[n];
            List<Integer> ancestor = new ArrayList<>();
            dfs(i, graph, isVisited);
            for (int node = 0; node < n; node++) {
                if (isVisited[node] == true) {
                    ancestor.add(node);
                }
            }
            ancestors.add(ancestor);
        }
        return ancestors;
    }

    public Map<Integer, List<Integer>> buildReverseGraph(int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            var adjVertexs = graph.getOrDefault(edge[1], new ArrayList<>());
            adjVertexs.add(edge[0]);
            graph.put(edge[1], adjVertexs);
        }
        return graph;
    }

    public void dfs(int vertex, Map<Integer, List<Integer>> graph, boolean[] isVisited) {
        for (int nextVertex : graph.getOrDefault(vertex, new ArrayList<>())) {
            if (!isVisited[nextVertex]) {
                isVisited[nextVertex] = true;
                dfs(nextVertex, graph, isVisited);
            }
        }
    }
 
Thay HashMap bằng Vec mà sao vẫn chậm vãi.
Mã: 
impl Solution {
    pub fn get_ancestors(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        use std::collections::HashSet;
        let n = n as usize;
        let mut ancestors_: Vec<Option<HashSet<usize>>> = vec![None; n + 1];
        let graph = {
            let mut graph = vec![HashSet::<usize>::new(); n + 1];
            for edge in edges {
                graph[edge[1] as usize].insert(edge[0] as usize);
            }
            graph[n] = (0..n).collect();
            graph
        };

        fn ancestors_of(i: usize, acs: &mut Vec<Option<HashSet<usize>>>, graph: &[HashSet<usize>]) {
            if acs[i].is_some() {
                return;
            }

            let mut acs_i = graph[i].clone();
            for &j in graph[i].iter() {
                ancestors_of(j, acs, graph);
                if let Some(ref acs_j) = acs[j] {
                    acs_i = HashSet::union(&acs_i, &acs_j).copied().collect();   
                }
            }
            acs[i] = Some(acs_i);
        }
        ancestors_of(n, &mut ancestors_, &graph);
        ancestors_.pop();
        ancestors_.into_iter().map(|s| {
            let mut v: Vec<_> = unsafe { s.unwrap_unchecked() }.into_iter().map(|i| i as i32).collect();
            v.sort_unstable();
            v
        }).collect()
    }
}
 
JavaScript: 
var getAncestors = function(n, edges) {
    const graph = {};
    for (const [from, to] of edges) {
        if (from in graph === false)
            graph[from] = [];
        graph[from].push(to);
    }

    const dfs = (node, parent) => {
        if (node in graph === false) return;
        for (const neighbor of graph[node]) {
            if (res[neighbor].has(parent)) continue;
            res[neighbor].add(parent);
            dfs(neighbor, parent);
        }
    }

    const res = Array.from({ length: n }, () => new Set());

    for (let i = 0; i < n; i++) {
        dfs(i, i);
    }

    return res.map(x => [...x].sort((a, b) => a - b));
};
 
billy_don đã nói:
Bài hay cho anh em luyện graph:
Nhấp để mở rộng...
Java: 
class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Map<String, Boolean> hasSupplies = new HashMap<>();
        for (String supply : supplies) {
            hasSupplies.put(supply, true);
        }
        Map<String, List<String>> ingredientTree = buildIngredientTree(recipes, ingredients);

        List<String> canMake = new ArrayList<>();
        for (String recipe : recipes) {
            if (canCreateThis(recipe, ingredientTree, hasSupplies, new HashMap<>())) {
                canMake.add(recipe);
            }
        }

        return canMake;
    }

    public Map<String, List<String>> buildIngredientTree(String[] recipes, List<List<String>> ingredients) {
        Map<String, List<String>> ingredientTree = new HashMap<>();

        for (int i = 0; i < recipes.length; i++) {
            for (String ingredient : ingredients.get(i)) {
                List<String> require = ingredientTree.getOrDefault(recipes[i], new ArrayList<>());
                require.add(ingredient);
                ingredientTree.put(recipes[i], require);
            }
        }

        return ingredientTree;
    }

    public boolean canCreateThis(String recipe, Map<String, List<String>> ingredientTree, Map<String, Boolean> hasSupplies, Map<String, Boolean> isVisited) {
        if (hasSupplies.get(recipe) != null) {
            return hasSupplies.get(recipe);
        }

        if (null != isVisited.get(recipe)) {
            return false;
        }

        boolean canCreate = (ingredientTree.get(recipe) != null);
        for (String ingredient : ingredientTree.getOrDefault(recipe, new ArrayList<>())) {
            if (null == isVisited.get(ingredient)) {
                isVisited.put(ingredient, true);
                canCreate &= canCreateThis(ingredient, ingredientTree, hasSupplies, isVisited);
            }
        }

        hasSupplies.put(recipe, canCreate);
        return canCreate;
    }
}
Các bác debug giúp em với, em không rõ sai chỗ nào mà không pass được.
 
nhẩm nhẩm viết kiểu tính transitive closure cho từng vertex worst case là O(n^3) khi gặp graph dạng mỗi vertex i có edge tới tất cả các vertex j thỏa mãn i < j, mà không rõ tại sao lại nhanh hơn cách viết reverse graph rồi dp này nọ nhỉ 🤔

có khi gà quá nên không thấy được sự tinh túy chăng 😔

transitive closure hạ đẳng:

Screenshot 2024-06-29 161352.png


dp thượng đẳng:

Screenshot 2024-06-29 161918.png
 
Sửa lần cuối:
small-lambda đã nói:
nhẩm nhầm viết kiểu tính transitive closure cho từng vertex worst case là O(n^3) khi gặp graph dạng mỗi vertex i có edge tới tất cả các vertex j thỏa mãn i < j, mà không rõ tại sao lại nhanh hơn cách viết reverse graph rồi dp này nọ nhỉ 🤔

có khi gà quá nên không thấy được sự tinh túy chăng 😔

transitive closure hạ đẳng:

Xem tệp đính kèm 2553521

dp thượng đẳng:

Xem tệp đính kèm 2553534
Nhấp để mở rộng...
Ko sao đâu, sinh viên trường tốp còn sai huống chi người thường
 
billy_don đã nói:
Ko sao đâu, sinh viên trường tốp còn sai huống chi người thường
Nhấp để mở rộng...
bỏ học được hơn bảy năm rồi nên không rõ câu sv trường tốp là chỉ ai, giờ mà tự nhận thì là xl, sống được 30 năm cõi đời nhận ra được chân lý là không nên xl nhiều, xl nhiều có hại cho sức khoẻ, vậy nên mình nhất quyết không xl 😄
 
aNotHeRNo0b đã nói:
Java: 
class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Map<String, Boolean> hasSupplies = new HashMap<>();
        for (String supply : supplies) {
            hasSupplies.put(supply, true);
        }
        Map<String, List<String>> ingredientTree = buildIngredientTree(recipes, ingredients);

        List<String> canMake = new ArrayList<>();
        for (String recipe : recipes) {
            if (canCreateThis(recipe, ingredientTree, hasSupplies, new HashMap<>())) {
                canMake.add(recipe);
            }
        }

        return canMake;
    }

    public Map<String, List<String>> buildIngredientTree(String[] recipes, List<List<String>> ingredients) {
        Map<String, List<String>> ingredientTree = new HashMap<>();

        for (int i = 0; i < recipes.length; i++) {
            for (String ingredient : ingredients.get(i)) {
                List<String> require = ingredientTree.getOrDefault(recipes[i], new ArrayList<>());
                require.add(ingredient);
                ingredientTree.put(recipes[i], require);
            }
        }

        return ingredientTree;
    }

    public boolean canCreateThis(String recipe, Map<String, List<String>> ingredientTree, Map<String, Boolean> hasSupplies, Map<String, Boolean> isVisited) {
        if (hasSupplies.get(recipe) != null) {
            return hasSupplies.get(recipe);
        }

        if (null != isVisited.get(recipe)) {
            return false;
        }

        boolean canCreate = (ingredientTree.get(recipe) != null);
        for (String ingredient : ingredientTree.getOrDefault(recipe, new ArrayList<>())) {
            if (null == isVisited.get(ingredient)) {
                isVisited.put(ingredient, true);
                canCreate &= canCreateThis(ingredient, ingredientTree, hasSupplies, isVisited);
            }
        }

        hasSupplies.put(recipe, canCreate);
        return canCreate;
    }
}
Các bác debug giúp em với, em không rõ sai chỗ nào mà không pass được.
Nhấp để mở rộng...
Fen bày ra mà fen không dọn những thằng sau dfs tới nó thấy marked visited rồi nó ko tính nữa, sửa lại logic chỗ visited. Nên sửa lại đi tới đâu mark hẳn visited tới đó, check hết list ingredients thì hốt lại.
Java: 
public boolean canCreateThis(String recipe, Map<String, List<String>> ingredientTree,
                                Map<String, Boolean> hasSupplies, Map<String, Boolean> isVisited) {
        if (hasSupplies.get(recipe) != null) {
            return hasSupplies.get(recipe);
        }

        if (null != isVisited.get(recipe)) {
            return false;
        }

        [B]isVisited.put(recipe, true);[/B]

        boolean canCreate = (ingredientTree.get(recipe) != null);
        for (String ingredient : ingredientTree.getOrDefault(recipe, new ArrayList<>())) {
            [B]if (!canCreateThis(ingredient, ingredientTree, hasSupplies, isVisited)) {
                isVisited.remove(ingredient);
                return false;
            }[/B]
        }

        [B]isVisited.remove(recipe);[/B]

        hasSupplies.put(recipe, canCreate);
        return canCreate;
    }

Mà mấy cái visited dùng thẳng set luôn dùng hashmap true false rồi còn check null như kia hơi rườm rà :), chỗ build tree kia xem lại tiếp nha :shame: add thẳng cái cục ingredients luôn sao phải init, loops rồi add nhìn hơi mệt.
 
Sửa lần cuối:
cuối cùng cũng có công ty gọi em đi phỏng vấn sau 2 tháng thất nghiệp giải leetcode :too_sad:
C#: 
public class Solution {
    public void DFS (int u, int current, int[][] edges, List<HashSet<int>> tempResult)
    {
        for(int i = 0; i<edges.Length; i++)
        {
            if(edges[i][0] == current && !tempResult[edges[i][1]].Contains(u))
            {
                tempResult[edges[i][1]].Add(u);
                DFS(u, edges[i][1], edges, tempResult);
            }
        }
    }
    public IList<IList<int>> GetAncestors(int n, int[][] edges) {
        List<HashSet<int>> tempResult = new List<HashSet<int>>();
        List<IList<int>> result = new List<IList<int>>();
        for(int i = 0; i<n; i++)
        {
            tempResult.Add(new HashSet<int>());
        }
        for(int i = 0; i<n; i++)
        {
            DFS(i, i, edges, tempResult);
        }
        for(int i = 0; i<n; i++)
        {
            result.Add(tempResult[i].ToList());
        }
        return result;
    }
}
 
Mỹ Chu Lang đã nói:
cuối cùng cũng có công ty gọi em đi phỏng vấn sau 2 tháng thất nghiệp giải leetcode :too_sad:
C#: 
public class Solution {
    public void DFS (int u, int current, int[][] edges, List<HashSet<int>> tempResult)
    {
        for(int i = 0; i<edges.Length; i++)
        {
            if(edges[i][0] == current && !tempResult[edges[i][1]].Contains(u))
            {
                tempResult[edges[i][1]].Add(u);
                DFS(u, edges[i][1], edges, tempResult);
            }
        }
    }
    public IList<IList<int>> GetAncestors(int n, int[][] edges) {
        List<HashSet<int>> tempResult = new List<HashSet<int>>();
        List<IList<int>> result = new List<IList<int>>();
        for(int i = 0; i<n; i++)
        {
            tempResult.Add(new HashSet<int>());
        }
        for(int i = 0; i<n; i++)
        {
            DFS(i, i, edges, tempResult);
        }
        for(int i = 0; i<n; i++)
        {
            result.Add(tempResult[i].ToList());
        }
        return result;
    }
}
Nhấp để mở rộng...
Cố lên hội chưởng :D
Mà fen có tài năng code dài thiên bẩm nhỉ :shame:
 
Sửa lần cuối:
Python: 
class Solution:
    def getAncestors(self, n, edges):
        adjacency_list = [[] for _ in range(n)]
        ancestors = [[] for _ in range(n)]

        for edge in edges:
            from_node = edge[0]
            to_node = edge[1]
            adjacency_list[from_node].append(to_node)
        
        def dfs(last_ancestor, ancestor, children = set([])):
            if len(adjacency_list[ancestor]) == 0:
                return 
            for child in adjacency_list[ancestor]:
                if len(ancestors[child]) and ancestors[child][-1] == last_ancestor:
                    continue
                children.add(child)
                ancestors[child].append(i)
                dfs(last_ancestor, child, children)
    
        for i in range(n):
            children = set()
            dfs(i, i, children)

        return ancestors

Đọc mãi mới hiểu và code lại được:beat_brick: :beat_brick: :beat_brick: cách traverse xuôi, gà quá
 
billy_don đã nói:
Lâu rồi leetcode chưa ra linkedlist nhỉ, anh em làm cho đỡ bỡ ngỡ :D
Nhấp để mở rộng...

Có bài nào khó hơn không thím
Python: 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        if not head.next:
            return head
        
        odd_head, p_odd = head, head
        even_head, p_even = head.next, head.next
        p = head.next.next

        i = 0
        while p:
            if i & 1:
                p_even.next = p
                p_even = p
            else:
                p_odd.next = p
                p_odd = p

            p = p.next
            i += 1
        p_odd.next = even_head
        p_even.next = None
        return odd_head
 
Python: 
class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        # Approach 1 : Topological Sort O(N^2logN)
        graph = defaultdict(list)
        ans = [set() for _ in range(n)]
        counter = defaultdict(int)
        for f,t in edges:
            graph[f].append(t)
            ans[t].add(f)
            counter[t] += 1
       
        q = deque([ i for i in range(n) if not ans[i] ])
       
        while q:
            f = q.popleft()
            for t in graph[f]:
                counter[t] -= 1
                ans[t].update(ans[f])
                if counter[t] == 0:
                    q.append(t)
        return [sorted(list(a)) for a in ans]
        # Approach 2 : DFS O(N^2LogN)
        # graph = defaultdict(list)
        # ans = [set() for _ in range(n)]
        # for v1,v2 in edges:
        #     graph[v1].append(v2)
        # for i in range(n):
        #     q = deque([i])
        #     while q:
        #         node = q.popleft()
        #         for neighbor in graph[node]:
        #             if i not in ans[neighbor]:
        #                 ans[neighbor].add(i)
        #                 q.append(neighbor)
        # return [sorted(list(ancestors)) for ancestors in and]
 
billy_don đã nói:
Lâu rồi leetcode chưa ra linkedlist nhỉ, anh em làm cho đỡ bỡ ngỡ :D
Nhấp để mở rộng...
Mã: 
// Lists in F# are implemented as singly linked lists,
// which means that operations that access only
// the head of the list are O(1), and element access is O(n).
// https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/lists

let oddEvenList (list: int list) =
    list
    |> List.indexed
    |> List.partition (fun (i, _) -> i % 2 = 0)
    |> fun (oddList, evenList) ->
        let _, oddList = oddList |> List.unzip
        let _, evenList = evenList |> List.unzip
        oddList @ evenList

// Test with #time directive
[1..10000] |> oddEvenList
Real: 00:00:00.002, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it: int list =
  [1; 3; 5; 7; 9; 11; 13; 15; 17; 19; 21; 23; 25; 27; 29; 31; 33; 35; 37; 39;
   41; 43; 45; 47; 49; 51; 53; 55; 57; 59; 61; 63; 65; 67; 69; 71; 73; 75; 77;
   79; 81; 83; 85; 87; 89; 91; 93; 95; 97; 99; 101; 103; 105; 107; 109; 111;
   113; 115; 117; 119; 121; 123; 125; 127; 129; 131; 133; 135; 137; 139; 141;
   143; 145; 147; 149; 151; 153; 155; 157; 159; 161; 163; 165; 167; 169; 171;
   173; 175; 177; 179; 181; 183; 185; 187; 189; 191; 193; 195; 197; 199; ...]
 
Sửa lần cuối:
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
838
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.701

Chia sẻ trang này

Quay lại
Lên đầu trang