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

Cố Trường Ca đã nói:

Học @MasonMaoSuVuong à

code chay đi cho quen

Nhấp để mở rộng...

hiếu thứ tha đã nói:

ủa biwêekly contest mở lâu chưa các thím, thấy còn 1 tiếng

Nhấp để mở rộng...

freedom.9 đã nói:

Spoiler: Python 1 pass

Python:

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        maxSofar = -inf
        count = 0
        ans = 0
        for num in nums:
            if num > maxSofar:
                ans = 1
                maxSofar = num
                count = 1
            elif num == maxSofar:
                count += 1
                ans = max(ans, count)
            else:
                count = 0
        return ans

Mấy bài nay dễ quá, hôm nay tôi sẽ giới thiệu cho anh em 1 thuật toán là sweep line.
Bài toán là, có 1 cái nhà hàng và list của people, với mỗi ith people thì [start, end] là thời điểm mà người này vào nhà hàng hoặc rời nhà hàng, tính xem có tối đa bao nhiêu người ở trong 1 nhà hàng ở 1 đơn vị thời gian.
Làm xong 2 bài cơm thêm này sẽ học được thuật toán sweep line, thêm kiến thức mới vào đầu phá đảo interview

https://leetcode.com/problem-list/arl5aezd/

Nhấp để mở rộng...

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        int n = people.length;
        int[][] ordered_people = new int[n][3];
        for (int i = 0; i < n; i++) {
            ordered_people[i][0] = people[i];
            ordered_people[i][1] = i;
        }

        Arrays.sort(ordered_people, (a, b) -> {
            return a[0] - b[0];
        });
        PriorityQueue<Integer> start_bloom = new PriorityQueue<>();
        PriorityQueue<Integer> end_bloom = new PriorityQueue<>();

        for (int[] flower : flowers) {
            start_bloom.offer(flower[0]);
            end_bloom.offer(flower[1]);
        }

        int current_blooms = 0;
        int start = 0;
        int end = end_bloom.poll();
        int i = 0;
     
        while (i < n) {
            if (!start_bloom.isEmpty()) {
                start = start_bloom.poll();
                current_blooms++;
                while (i < n && ordered_people[i][0] < start  ) {
                    while (end < ordered_people[i][0]) {
                        current_blooms--;
                        end = end_bloom.poll();
                    }
                    ordered_people[i][2] = current_blooms - 1;
                    i++;
                }
                while (end < start) {
                    current_blooms--;
                    end = end_bloom.poll();
                }

            } else {
             
                if (!end_bloom.isEmpty()) {
                 
                    if (end < ordered_people[i][0]) {
                        current_blooms--;
                        end = end_bloom.poll();
                    } else {
                        ordered_people[i][2] = current_blooms;
                        i++;
                    }
                } else {
                    while (i<n && end >= ordered_people[i][0] ) {
                        ordered_people[i][2] = current_blooms;
                        i++;
                    }
                    while (i < n) {
                        ordered_people[i][2] = 0;
                        i++;
                    }
                }
            }
        }
        Arrays.sort(ordered_people, (a, b) -> {
            return a[1] - b[1];
        });
        int[] res = new int[n];
        for (int j = 0; j < n; j++) {
            res[j] = ordered_people[j][2];
        }
        return res;
    }
}

anoldvozer1710.v2 đã nói:

lâu lắm mới làm contest, chắc 3Q gang rồi, câu 4 nhìn đã đéo muốn làm

Nhấp để mở rộng...

Cố Trường Ca đã nói:

làm đi ko bên thread kia khinh đấy

@MasonMaoSuVuong đâu vào làm đi

Nhấp để mở rộng...

anoldvozer1710.v2 đã nói:

lâu lắm mới làm contest, chắc 3Q gang rồi, câu 4 nhìn đã đéo muốn làm

Nhấp để mở rộng...

Cố Trường Ca đã nói:

làm đi ko bên thread kia khinh đấy

@MasonMaoSuVuong đâu vào làm đi

Nhấp để mở rộng...

noobdev đã nói:

đù làm đc câu hard luôn, đỉnh vl, 2 câu hard mình nhìn accepted rate chán ko làm nữa, ngồi xem doto cho lành,

Nhấp để mở rộng...

Cố Trường Ca đã nói:

lại feed tiếp rồi

Nhấp để mở rộng...

anoldvozer1710.v2 đã nói:

ko làm đc hard thì cũng phải bú đc 2 câu chứ

Nhấp để mở rộng...

anoldvozer1710.v2 đã nói:

ko làm đc hard thì cũng phải bú đc 2 câu chứ

Nhấp để mở rộng...

noobdev đã nói:

câu 2 còn bị dính TLE 1 lần, chủ quan quá

Nhấp để mở rộng...

Cố Trường Ca đã nói:

dinh tle do dfs nên viết lại từ đầu bfs

Nhấp để mở rộng...

anoldvozer1710.v2 đã nói:

thấy ma trận mà còn đi viết dfs, mấy em nằm xuống bảnh cho 3 gậy sau nhớ

Nhấp để mở rộng...

Cố Trường Ca đã nói:

@freedom.9 chưa thấy gáy, chắc cũng feed rồi

Có vẻ như là đúng rồi

Nhấp để mở rộng...