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

âu dương chấn thương said:
LC Premium là có thêm 1 bài mỗi tuần hả bác
Click to expand...
Đúng rồi người anh em.
1719805133369.png
 
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![]
        }
    }
}
 
Last edited:
Cuối tuần đi chơi mất luôn badge tháng, mịa
Thầy ông cố nội said:
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
Click to expand...
 
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
    }
}
 
Last edited:
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;
};
 
Code: 
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
 
Java: 
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        int len = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                nums1[len] = nums1[i];
                len++;
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        int[] res = new int[len];
        for (int index = 0; index < len; index++) {
            res[index] = nums1[index];
        }
        return res;
    }
}
 
Last edited:
LmaoSuVuong said:
Java: 
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i  =0;
        int j =0 ;
        int len=0;
        while(i<nums1.length && j<nums2.length){
            if(nums1[i]==nums2[j]){
                nums1[len] = nums1[i];
                len++;
                i++;j++;
            }
            else if(nums1[i]<nums2[j]){
               i++;
            }
            else{
               j++;
            }
        }
        int[] res = new int[len];
        for(int index =0 ; index < len ; index++){
            res[index]=nums1[index];
        }
        return res;
    }
}
Click to expand...
góc trên bên phải có nút format đó fen, sao ko format lại nhìn cho nó gọn.
 
PHP: 
class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Integer[]
     */
    function intersect($nums1, $nums2) {
        $dictNums2 = [];
        foreach ($nums2 as $n) {
            if (!isset($dictNums2[$n])) $dictNums2[$n] = 0;
            $dictNums2[$n]++;
        }

        $intersecion = [];
        foreach ($nums1 as $n) {
            if (!isset($dictNums2[$n]) || $dictNums2[$n] < 1) continue;

            $intersecion[] = $n;
            $dictNums2[$n]--;
        }

        return $intersecion;
    }
}
 
Last edited:
Java: 
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i1 = 0, i2 = 0;
        List<Integer> intersectNums = new ArrayList<>();
        while (i1 != nums1.length && i2 != nums2.length) {
            if (nums1[i1] > nums2[i2]) {
                i2++;
            } else if (nums1[i1] < nums2[i2]) {
                i1++;
            } else {
                intersectNums.add(nums1[i1]);
                i1++;
                i2++;
            }
        }

        int[] answer = new int[intersectNums.size()];
        for (int i = 0; i < intersectNums.size(); i++) {
            answer[i] = intersectNums.get(i);
        }

        return answer;
    }
}

Follow up không đổi :v chỉ là giảm từ độ phức tạp từ O(nlogn) xuống O(n) và SC giảm từ O(log) xuống O(1). Không phụ thuộc và value range của nums1 và nums2
 
Java: 
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        
        if(nums1.length > nums2.length){
            return intersect(nums2, nums1);
        }

         HashMap<Integer, Integer> m = new HashMap<>();
        for (int n: nums1){
            m.put(n, m.getOrDefault(n,0) +1);
        }
        int k = 0;
        for (int n: nums2){
            int cnt = m.getOrDefault(n, 0);
            if (cnt > 0 ){
                nums1[k++] = n;
                m.put(n, cnt -1);
            }
        }
        return Arrays.copyOfRange(nums1, 0, k);
}
}
1719899619089.png
 
C-like: 
impl Solution {
    pub fn intersect(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        #[inline]
        fn opt_get_mut<'t, T>(v: &'t mut [T], i: i32) -> &'t mut T {
            unsafe { v.get_unchecked_mut(i as usize) }
        }
        #[inline]
        fn opt_get<'t, T>(v: &'t mut [T], i: i32) -> &'t T {
            unsafe { v.get_unchecked(i as usize) }
        }
        let (mut e1, mut e2) = (vec![0; 1001], vec![0; 1001]);
        
        nums1.into_iter().for_each(|i| {
            let ei = opt_get_mut(&mut e1, i);
            *ei = *ei + 1;
            
        });
        nums2.into_iter().for_each(|i| {
            let ei = opt_get_mut(&mut e2, i);
            *ei = *ei + 1;
        });
        return (0..1001).map(|i| {
            let (&ei1, &ei2) = (opt_get(&mut e1, i), opt_get(&mut e2, i));
            let min = if ei1 < ei2 { ei1 } else { ei2 };
            vec![i; min]
        }).collect::<Vec<_>>().concat();
    }
}
 
Last edited:
bài dễ quá thì phải làm khó lên các bạn à, thay vì copy vài integer thì lấy reference ra, thay vì lấy reference ra trực tiếp thì phải bỏ vào hàm, lúc duyệt qua frequency map cho hai array thì thay vì viết loop để thêm element vào kết quả thì alloc thêm array tạm rồi lấy element từ array tạm nhét vào trong kết quả 💪

phải làm vầy để cho thế giới biết mình não to chứ 🧠
 
small-lambda said:
bài dễ quá thì phải làm khó lên các bạn à, thay vì copy vài integer thì lấy reference ra, thay vì lấy reference ra trực tiếp thì phải bỏ vào hàm, lúc duyệt qua frequency map cho hai array thì thay vì viết loop để thêm element vào kết quả thì alloc thêm array tạm rồi lấy element từ array tạm nhét vào trong kết quả 💪

phải làm vầy để cho thế giới biết mình não to chứ 🧠
Click to expand...
thay vì dài dòng ntn thì t viết 1 dòng được k? :doubt:

Python: 
return (Counter(nums1) & Counter(nums2)).elements()
 

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
104
nhbin
nhbin
Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
641
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
164
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
17
Views
446
truonggiang!
T

Share this page

Back
Top