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

aNotHeRNo0b said:
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.
Click to expand...
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.
 
Last edited:
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 said:
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;
    }
}
Click to expand...
Cố lên hội chưởng :D
Mà fen có tài năng code dài thiên bẩm nhỉ :shame:
 
Last edited:
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 said:
Lâu rồi leetcode chưa ra linkedlist nhỉ, anh em làm cho đỡ bỡ ngỡ :D
Click to expand...

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 said:
Lâu rồi leetcode chưa ra linkedlist nhỉ, anh em làm cho đỡ bỡ ngỡ :D
Click to expand...
Code: 
// 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; ...]
 
Last edited:
C-like: 
use std::collections::*;

#[derive(Debug)]
pub struct UnionFind {
    parents: Vec<usize>,
    ranks: Vec<usize>,
    set_count: usize,
    set_sizes: Vec<usize>
}

impl UnionFind {
    pub fn new(size: usize) -> Self {
        let mut parents = vec![0; size];

        for i in 0..size {
            parents[i] = i;
        }

        let ranks = vec![0; size];
        let set_sizes = vec![1; size];

        Self {
            parents: parents,
            ranks: ranks,
            set_count: size,
            set_sizes: set_sizes
        }
    }

    pub fn find_set(&mut self, i: usize) -> usize {
        if self.parents[i] == i {
            i
        } else {
            self.parents[i] = self.find_set(self.parents[i]);

            self.parents[i]
        }
    }

    pub fn same_set(&mut self, i: usize, j: usize) -> bool {
        self.find_set(i) == self.find_set(j)
    }

    pub fn union(&mut self, i: usize, j: usize) {
        if self.same_set(i, j) {
            return;
        }

        let mut set_i = self.find_set(i);
        let mut set_j = self.find_set(j);

        if self.ranks[set_i] > self.ranks[set_j] {
            (set_i, set_j) = (set_j, set_i);
        }

        if self.ranks[set_i] == self.ranks[set_j] {
            self.ranks[set_j] += 1;
        }

        self.set_sizes[set_j] += self.set_sizes[set_i];

        self.parents[set_i] = set_j;
        self.set_count -= 1;
    }

    pub fn set_count(&self) -> usize {
        self.set_count
    }

    pub fn set_size(&mut self, i: usize) -> usize {
        let set_i = self.find_set(i);

        self.set_sizes[set_i]
    }
}

impl Solution {
    pub fn max_num_edges_to_remove(n: i32, edges: Vec<Vec<i32>>) -> i32 {
        let un = n as usize;
        let mut auf = UnionFind::new(un);
        let mut buf = UnionFind::new(un);
        let total_edge_count = edges.len();
        let mut used_edge_count = 0;

        for edge in edges.iter().filter(|&edge| edge[0] == 3) {
            let u = edge[1] as usize - 1;
            let v = edge[2] as usize - 1;

            if !auf.same_set(u, v) && !buf.same_set(u, v) {
                auf.union(u, v);
                buf.union(u, v);
                used_edge_count += 1;
            }
        }

        for edge in edges.iter().filter(|&edge| edge[0] == 1) {
            let u = edge[1] as usize - 1;
            let v = edge[2] as usize - 1;

            if !auf.same_set(u, v) {
                auf.union(u, v);
                used_edge_count += 1;
            }
        }

        for edge in edges.iter().filter(|&edge| edge[0] == 2) {
            let u = edge[1] as usize - 1;
            let v = edge[2] as usize - 1;

            if !buf.same_set(u, v) {
                buf.union(u, v);
                used_edge_count += 1;
            }
        }

        if auf.set_count != 1 || buf.set_count != 1 {
            -1
        } else {
            (total_edge_count - used_edge_count) as i32
        }
    }
}


C-like: 
impl Solution {
    pub fn odd_even_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut odd_head = Some(Box::new(ListNode::new(1)));
        let mut odd_tail = odd_head.as_mut();
        let mut even_head = Some(Box::new(ListNode::new(0)));
        let mut even_tail = even_head.as_mut();
        let mut i = 0;

        while let Some(mut node) = head {
            head = node.next.take();

            if i % 2 == 0 {
                even_tail =
                    even_tail.and_then(|mut tail| {
                        tail.next = Some(node);
                        tail.next.as_mut()
                    });
            } else {
                odd_tail =
                    odd_tail.and_then(|mut tail| {
                        tail.next = Some(node);
                        tail.next.as_mut()
                    });
            }

            i += 1;
        }

        even_tail.zip(odd_head).map(|(tail, head)| tail.next = head.next);

        even_head.and_then(|mut head| head.next.take())
    }
}
 
bài hôm nay có phần gần giống với việc dùng thuật toán Kruskal tìm minimum spanning tree, nhưng làm việc trên unweighted graph nên không cần phải sort theo edge weight nữa

hiểu đại khái vậy nhưng vẫn chưa rõ lắm tại sao cách dùng type 3 edge trước rồi add edge có type khác vào sao lại là optimal, có cao nhân nào chỉ giáo không
 
Theo mình nghĩ thì có 3 bước để giải, mà phức tạp quá
B1: trong các cạnh type 3, tạo nên các miền liên thông, trong mỗi miền liên thông, tạo cây khung => tính ra các cạnh type 3 dư
B2: dựa trên kết quả của B1, tạo cây khung của Alice. Ko tạo đc thì return -1. Tạo ra đc cây khung thì tính các cạnh type 1 bị dư.
B3 thì tương tự bước 2.
 
billy_don said:
Bài hay cho anh em luyện graph:
Click to expand...
Bữa giờ gặp topo sort hoài mà ko biết nên rảnh ngồi đọc làm thử
JavaScript: 
var findAllRecipes = function(recipes, ingredients, supplies) {
    const recipes_set = new Set(recipes);

    // Prepare graph
    const graph = {};
    const inDegree = {};
    for (let i = 0; i < recipes.length; i++) {
        if (recipes[i] in inDegree === false) inDegree[recipes[i]] = 0;
        for (const ing of ingredients[i]) {
            if (ing in graph === false) graph[ing] = [];
            graph[ing].push(recipes[i]);
            inDegree[recipes[i]]++;
        }
    }

    //console.log(graph, inDegree);

    // Topo sort
    // Init topo queue from supplies as it all has zero degree.
    const queue = [...supplies];
    const ans = [];
    
    while (queue.length) {
        let ingred = queue.shift();
        // Only add item which is recipe
        if (recipes_set.has(ingred)) {
            ans.push(ingred);
        }

        if (ingred in graph === false) continue;

        for (const recipe of graph[ingred]) {
            inDegree[recipe]--;
            if (inDegree[recipe] == 0) {
                queue.push(recipe);
            }
        }
    }

    return ans;
};
 
HIL said:
Code: 
// 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; ...]
Click to expand...
Cách cài đặt này không thỏa mãn ràng buộc O(1) space, ngoài ra còn quá phức tạp (sử dụng fancy functions không cần thiết).

Bài này thì tư tưởng tail recursion quá rõ ràng nên một cách khác đơn giản hơn như sau:
Code: 
let oddEvenList xs =
    let rec pick (os, es) xs p =
        match xs, p with
        | x :: xs', true -> pick (x :: os, es) xs' false
        | x :: xs', false -> pick (os, x :: es) xs' true
        | _ -> es @ os |> List.rev

    pick ([], []) xs true
Chỉ cần thêm memory space cho đúng một biến bool (là p), nên SC = O(1). Cách cài đặt trên có thể chuyển thành single-line function bằng cách dùng List.fold, như sau:
Code: 
let oddEventList<'t> =
    List.fold (fun (os, es, p) x ->
        if p then (x :: os, es, not p)
        else (os, x :: es, not p)) ([], [], true)
    >> (fun (a, b, _) -> b @ a |> List.rev)
 
Last edited:
Konstante said:
Cách cài đặt này không thỏa mãn ràng buộc O(1) space, ngoài ra còn quá phức tạp (sử dụng fancy functions không cần thiết).

Bài này thì tư tưởng tail recursion quá rõ ràng nên một cách khác đơn giản hơn như sau:
Code: 
let oddEvenList xs =
    let rec pick (os, es) xs p =
        match xs, p with
        | x :: xs', true -> pick (x :: os, es) xs' false
        | x :: xs', false -> pick (os, x :: es) xs' true
        | _ -> es @ os |> List.rev

    pick ([], []) xs true
Chỉ cần thêm memory space cho đúng một biến bool (là b), nên SC = O(1). Cách cài đặt trên có thể chuyển thành single-line function bằng cách dùng List.fold.
Click to expand...
Hay thế, mình ko nghĩ được recursion luôn
 

Similar threads

nhbin
kiến thức Kèo Watch to earn 5p mỗi ngày $EVERY gọi vốn $60M từ A16Z, Coinbase, DragonFly
Replies
0
Views
98
nhbin
nhbin
Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
637
heocon0123
heocon0123
MasterchiefsReborn
Sinh viên than kiến tập mà làm việc không kịp ăn
2 3
Replies
47
Views
3K
OneThing
OneThing
domino123
kiến thức PixelTap by Pixelverse
Replies
0
Views
162
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
17
Views
445
truonggiang!
T

Share this page

Back
Top