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.
small-lambda đã nói:
cái này mình nghĩ vẫn chưa trực tiếp chứng minh được là cái thuật toán như post trên này ra kết quả đúng, khi chứng minh thì phải nhìn vào phần thân của algo và chỉ ra được là sau mỗi lần loop là nó giữ một cái invariant gì đó dẫn đến kết quả đúng, kể cả khi graph A hoặc B disconnected, nhưng cảm ơn bạn đã dành thời gian

mà nghĩ kĩ, tốn thời gian đi chứng minh làm gì, vì luyện leetcode đâu phải để giỏi CS 😔
Nhấp để mở rộng...
Nếu mà đồ thị không liên thông thì sẽ trả ra kết quả -1 luôn.
Bạn nói đúng đấy. Theo đúng quy trình thì phải chứng minh như thế.
Việc chứng minh tính đúng đắn của thuật toán rất quan trọng đó bạn, làm như thế thì mới nhanh tiến bộ.
 
Konstante đã nói:
mình trình bày một cài đặt sử dụng kỹ thuật continuation rất hay gặp trong functional programming:
Mã: 
let oddEventList xs =
    let rec pickcps xs k =
        match xs with
        | x :: x' :: xs'' -> pickcps xs'' (fun (os, es) -> k (x :: os, x' :: es))
        | x :: _ -> pickcps [] (fun (os, es) -> k (x :: os, es))
        | _ -> ([], []) |> k |> (fun (a, b) -> a @ b)

    pickcps xs id
Nhấp để mở rộng...
Cảm ơn bạn. Qua đây, mình biết thêm về CPS, mà đúng như bạn nói, hay gặp trong compiler của các functional language hơn. Và từ đó, cũng hiểu sâu thêm cơ chế hoạt động của computation expression trong F#.

Konstante đã nói:
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:
Mã: 
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).
Nhấp để mở rộng...
Bạn nào muốn tìm hiểu thêm về accumulator & tail recursion, dùng ví dụ bằng F#

Tail Recurse

Tips on refactoring recursive functions to tail-recursive functions.
blog.ploeh.dk blog.ploeh.dk
và với sự góp mặt của compiler
learn.microsoft.com

Tail calls in F#

learn.microsoft.com

Konstante đã nói:
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:
Mã: 
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)
Nhấp để mở rộng...
Mình cho rằng one-liner với List.fold như vậy có phần khiên cưỡng, tuy cho kết quả đúng nhưng giảm đi tính readability. Vầy có lẽ trong sáng hơn

Mã: 
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

hoặc

Mã: 
let oddEventList<'t> list =
    list
    |> 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

Tuy nhiên, trong trường hợp này, dùng pattern matching như ban đầu có vẻ dễ đọc nhất.

Konstante đã nói:
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).
Nhấp để mở rộng...
Đồng ý với nhận xét trên trong context của LeetCode với ràng buộc optimization.
 
Sửa lần cuối:
Python: 
class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        auf = UF(n)
        buf = UF(n)
        needed_edges = 0
        for t, v1, v2 in edges:
            if t == 3:
                needed_edges +=  auf.union(v1, v2) | buf.union(v1, v2)
        for t, v1, v2 in edges:
            if t == 1:
                needed_edges += auf.union(v1, v2)
            elif t == 2:
                needed_edges += buf.union(v1, v2)
     
        if auf.is_completed() and buf.is_completed():
            return len(edges) - needed_edges
        return -1
class UF:
    def __init__(self, size):
        self.rep = [i for i in range(size + 1)]
        self.rank = [ 1 for _ in range(size + 1)]
        self.total_edges = size - 1
 
    def is_completed(self):
        return self.total_edges == 0
    def find(self, node):
        if node != self.rep[node]:
            self.rep[node] = self.find(self.rep[node])
     
        return self.rep[node]
 
    def union(self, node1, node2):
        rep1 = self.find(node1)
        rep2 = self.find(node2)
        if rep1 != rep2:
            if self.rank[rep1] < self.rank[rep2]:
                self.rep[rep1] = rep2
            elif self.rank[rep1] > self.rank[rep2]:
                self.rep[rep2] = rep1
            else:
                self.rep[rep2] = rep1
                self.rank[rep1] += 1
            self.total_edges -= 1
            return 1
        else:
            return 0
 
PHP: 
class Solution {

    /**
     * @param Integer[] $arr
     * @return Boolean
     */
    function threeConsecutiveOdds($arr) {
        for ($i=0; $i<=count($arr)-3; $i++) {
            if ($arr[$i] % 2 == 0) continue;
            if ($arr[$i+1] % 2 == 0) continue;
            if ($arr[$i+2] % 2 == 0) continue;

            return true;
        }

        return false;
    }
}
 
Python: 
    def threeConsecutiveOdds(self, arr: List[int]) -> bool:
        for i in range(len(arr) - 2):
            if arr[i] % 2 + arr[i + 1] % 2 + arr[i + 2] %2 ==3 :
                return True
        return False

Note : Bài nay dễ chắc anh em bỏ qua hết rồi :gach:
 
Bài dễ nhưng mấy solution bên trên đều dính lỗi kiểm tra parity của một phần tử nhiều lần.

C-like: 
impl Solution {
    pub fn three_consecutive_odds(arr: Vec<i32>) -> bool {
        let is_odd = |i: usize| { arr[i] & 1 == 1 };
      
        let mut i = 2;
        while i < arr.len() {
            if !is_odd(i) {
                i += 3;
                continue;
            }
            if !is_odd(i - 1) {
                i += 2;
                continue;
            }
            if !is_odd(i - 2) {
                i += 1;
                continue;
            }
            return true;
        }
        return false;
    }
}
 
Sửa lần cuối:
Bài Weekly Premium hôm nay là phiên bản dễ hơn của bài Daily hôm qua. Nếu anh em không có Premium mà muốn làm thì đây là đề bài.

1719800634583.png
 
Swift: 
class Solution {
    func threeConsecutiveOdds(_ arr: [Int]) -> Bool {
        var countOdds = 0
        for num in arr {
            if num%2==0 {
                countOdds = 0
            } else {
                if countOdds == 2 {
                    return true
                }
                countOdds += 1
            }
        }
        return false
    }
}
 
C-like: 
impl Solution {
    pub fn three_consecutive_odds(arr: Vec<i32>) -> bool {
        let mut odd_count = 0;

        for num in arr {
            if num % 2 == 1 {
                odd_count += 1;
            } else {
                odd_count = 0;
            }

            if odd_count >= 3 {
                return true;
            }
        }

        false
    }
}

C-like: 
use std::collections::*;

impl Solution {
    pub fn find_all_recipes(recipes: Vec<String>, ingredients: Vec<Vec<String>>, supplies: Vec<String>) -> Vec<String> {
        let mut stack = vec![];
        let supply_set =
            supplies.into_iter().
                fold(HashSet::new(), |mut set, supply| {
                    set.insert(supply);
                    set
                });

        let recipe_indices =
            recipes.iter().enumerate().
                fold(HashMap::new(), |mut map, (i, recipe)| {
                    map.insert(recipe.clone(), i);
                    map
                });

        let n = recipes.len();
        let mut graph = vec![vec![]; n];
        let mut in_degrees = vec![0; n];
        for (i, recipe) in recipes.iter().enumerate() {
            for ingredient in &ingredients[i] {
                if let Some(&recipe_index) = recipe_indices.get(ingredient) {
                    graph[recipe_index].push(i);
                    in_degrees[i] += 1;
                }
            }
        }

        'outer: for (i, &in_degree) in in_degrees.iter().enumerate() {
            if in_degree != 0 {
                continue;
            }

            for ingredient in &ingredients[i] {
                if !supply_set.contains(ingredient) {
                    continue 'outer;
                }
            }

            stack.push(i);
        }

        let mut result = vec![];
        while let Some(i) = stack.pop() {
            result.push(recipes[i].clone());

            'outer: for &neighbour in &graph[i] {
                if in_degrees[neighbour] == 0 {
                    continue;
                }

                in_degrees[neighbour] -= 1;

                if in_degrees[neighbour] > 0 {
                    continue;
                }

                for ingredient in &ingredients[neighbour] {
                    if recipe_indices.get(ingredient).is_none() && !supply_set.contains(ingredient) {
                        continue 'outer;
                    }
                }

                stack.push(neighbour);
            }
        }

        result
    }
}

C-like: 
use std::collections::*;

impl Solution {
    pub fn find_order(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> Vec<i32> {
        let n = num_courses as usize;
        let mut graph = vec![vec![]; n];
        let mut in_degrees = vec![0; n];

        for edge in prerequisites {
            let (u, v) = (edge[0] as usize, edge[1] as usize);
            graph[v].push(u);
            in_degrees[u] += 1;
        }

        let mut stack = vec![];
        for (vertex, &in_degree) in in_degrees.iter().enumerate() {
            if in_degree == 0 {
                stack.push(vertex);
            }
        }

        let mut vertices = vec![];
        while let Some(vertex) = stack.pop() {
            vertices.push(vertex as i32);

            for &neighbour in &graph[vertex] {
                if in_degrees[neighbour] == 0 {
                    continue;
                }

                in_degrees[neighbour] -= 1;

                if in_degrees[neighbour] == 0 {
                    stack.push(neighbour);
                }
            }
        }

        if vertices.len() == n {
            vertices
        } else {
            vec![]
        }
    }
}
 
Sửa lần cuối:
Cuối tuần đi chơi mất luôn badge tháng, mịa
Thầy ông cố nội đã nói:
JavaScript: 
var maximumImportance = function(n, roads) {
    const connected = new Array(n).fill(0);
    for (const [a, b] of roads) {
        connected[a]++;
        connected[b]++;
    }

    connected.sort((a, b) => b - a);

    let res = 0;
    let i = n;
    for (const c of connected) {
        res += c * i--;
    }

    return res;
};

@danghieu1709 đâu rồi chưa up nữa
Nhấp để mở rộng...
 
C-like: 
impl Solution {
    pub fn intersect(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> Vec<i32> {
        let (m, n) = (nums1.len(), nums2.len());

        if m == 0 || n == 0 {
            return vec![];
        }

        nums1.sort_unstable();
        nums2.sort_unstable();

        let (mut left, mut right) = (0, 0);

        let mut result = vec![];
        while left < m && right < n {
            if nums1[left] == nums2[right] {
                result.push(nums1[left]);
                (left, right) = (left + 1, right + 1);
                continue;
            }

            if nums1[left] < nums2[right] {
                left += 1;
                continue;
            }

            right += 1;
        }

        result
    }
}

C-like: 
use std::collections::HashMap;

impl Solution {
    pub fn intersect(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> Vec<i32> {
        let (m, n) = (nums1.len(), nums2.len());

        if m == 0 || n == 0 {
            return vec![];
        }

        let (freq_source, search_targets) =
            if m < n {
                (&nums1, &nums2)
            } else {
                (&nums2, &nums1)
            };

        let mut freqs =
            freq_source.iter().fold(HashMap::new(), |mut map, &num| {
                map.entry(num).and_modify(|freq| *freq += 1).or_insert(1);
                map
            });

        let mut result = vec![];
        for num in search_targets {
            match freqs.get_mut(num) {
                Some(freq) => {
                    if *freq == 0 {
                        continue;
                    }

                    result.push(*num);
                    *freq -= 1;
                },
                None => continue
            }
        }

        result
    }
}
 
Sửa lần cuối:
HashMap đơn giản
JavaScript: 
function intersect(nums1: number[], nums2: number[]): number[] {
    const map = new Map(), res: number[] = [];
    for (const num of nums1) {
        map.set(num, (map.get(num) || 0) + 1);
    }
    for (const num of nums2) {
        if (map.get(num)) {
            res.push(num);
            map.set(num, map.get(num) - 1)
        }
    }
    return res;
};
 
Resubmit
zCP5WuR.gif

Java: 
public int[] intersect(int[] A, int[] B) {
    Arrays.sort(A);
    Arrays.sort(B);
    List<Integer> result = new ArrayList<>();
    int i = 0, j = 0;
    while (i < A.length && j < B.length) {
        if (A[i] == B[j]) {
            result.add(A[i]);
            i++;
            j++;
        } else if (A[i] < B[j]) {
            i++;
        } else {
            j++;
        }
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
}
 
JavaScript: 
var intersect = function(nums1, nums2) {
    const c1 = Array(1001).fill(0);
    const c2 = Array(1001).fill(0);

    for (const n of nums1) {
        c1[n]++;
    }

    for (const n of nums2) {
        c2[n]++;
    }

    const res = [];

    for (let i = 0; i <= 1000; i++) {
        if (c1[i] && c2[i]) {
            const count = Math.min(c1[i], c2[i]);
            for (let j = 0; j < count; j++) {
                res.push(i);
            }
        }
    }
    
    return res;
};
 
Mã: 
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        mp = {}
        res = []
        for num in nums1:mp[num] = mp.get(num , 0) + 1
        for num in nums2:
            if num in mp and mp[num] > 0:
                res.append(num)
                mp[num] -= 1
        
        return res
Nhẹ nhàng
zFNuZTA.png
 
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.708

Chia sẻ trang này

Quay lại
Lên đầu trang