thảo luận Leetcode contest, đường tới Guardian

ti_say_hi · 13/4/24

honda stone đã nói:
Em lưu 1 cái stack giảm dần, kèm số lượng, thêm 1 số rất lớn ở cuối dãy để chặn.

Mỗi lần nhét 1 số vào stack thì loại những thằng nhỏ hơn nó ra, mỗi lần loại như thế thì cập nhật kết quả.

Em có dùng thêm 1 cách ạ, em dùng 1 cái mảng left đếm số phần tử phía trước i trong range[0, i-1] có giá trị bằng nums nhưng ở giữa ko có thằng nào lớn hơn nums hết.

Java:

int[] left = new int[n]; for (int i = 0; i < n; i++) { left[i] = 1; int j = i-1; while (j >= 0 && nums[j] <= nums[i]) { if (nums[j] == nums[i]) { left[i] += left[j]; break; } j--; } }

LmaoSuVuong · 13/4/24

ti_say_hi đã nói:
Em có dùng thêm 1 cách ạ, em dùng 1 cái mảng left đếm số phần tử phía trước i trong range[0, i-1] có giá trị bằng nums nhưng ở giữa ko có thằng nào lớn hơn nums hết.

Java:

int[] left = new int[n]; for (int i = 0; i < n; i++) { left[i] = 1; int j = i-1; while (j >= 0 && nums[j] <= nums[i]) { if (nums[j] == nums[i]) { left[i] += left[j]; break; } j--; } }

à ừ nhỉ đếm ngược từ cuối dãy gặp lớn hơn thì ngưng, e đếm xuôi từ 0 ăn tle

Java:

for(int j=0;j<=top;j++){
if(stack[j]==stack[top])count++;
}

thành

Java:

for(int j=top;j>=0;j--){
if(stack[j]==stack[top]) count++;
else break;
 }

là pass r

seastar · 13/4/24

Sau khi xem sol của top1 thì mới thấy mình bị thiếu cái gì. :beat_brick:

C++:

            if (dist[u] != d){  // Sự khác biệt ở đây
                continue;
            }

Thêm đk này vào beat 100% luôn, :beat_brick:

C++:

class Solution {
public:
    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        vector <vector <pair <int, int>>> adj(n);
        for (auto &edge: edges){
            auto u = edge[0], v = edge[1], w = edge[2];
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
        }

        const int inf = 1e9 + 7;
        vector <int> dist = disappear;
        priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;

        auto transition = [&](int d, int u){
            if (dist[u] > d){
                dist[u] = d;
                pq.emplace(d, u);
            }
        };

        transition(0, 0);
        while (not pq.empty()){
            auto [d, u] = pq.top(); pq.pop();
            if (dist[u] != d){
                continue;
            }
            for (auto &[v, w]: adj[u]){
                transition(d + w, v);
            }
        }

        for (auto u = 0; u < n; u++){
            if (dist[u] == disappear[u]){
                dist[u] = -1;
            }
        }
        return dist;
    }
};

freedom.9 · 13/4/24

Thì ra solution q4 của mình đúng mà bị dupplicated, chỉ cần tìm next greaters rồi bisearch thôi huhu
Suy nghĩ phức tạp quá tìm cả previous greaters =((

JustAnOtherClone · 13/4/24

2 lần tham gia contest đều được 3/4 câu, câu cuối cứ cảm giác no hope kiểu éo gì ấy.

LmaoSuVuong · 13/4/24

thôi hẹn mấy bác sáng mai chiến tiếp

LmaoSuVuong · 13/4/24

JustAnOtherClone đã nói:
2 lần tham gia contest đều được 3/4 câu, câu cuối cứ cảm giác no hope kiểu éo gì ấy.

câu cuối hôm nay nếu fen làm daily cả tuần nay r thì thấy quen vl

seastar · 13/4/24

Bài 4 dùng mono stack giảm dần thôi. T thấy bài đó dễ mà. Cả tuần nay làm dạng này chán rồi. Bữa ở leetcode daily có nói anh em ôn kỹ cái này rồi mà, :ah:

C++:

class Solution {
public:
    long long numberOfSubarrays(vector<int>& nums) {
        vector<pair<int,int>> stack;
        long long ret = 0;
        for (int i = 0; i < nums.size(); ++i) {
            while( !stack.empty() && nums[i] > stack.back().first) {
                stack.pop_back();
            }
            if (!stack.empty() && stack.back().first == nums[i]) {
                ret += stack.back().second;
                stack.back().second += 1;
            } else stack.emplace_back(nums[i], 1);
        }
        return ret + nums.size();
    }
};

JustAnOtherClone · 13/4/24

LmaoSuVuong đã nói:
câu cuối hôm nay nếu fen làm daily cả tuần nay r thì thấy quen vl

tuần này trên công ty nhiều task quá, ko ăn cắp thời gian cày leetcode được.

freedom.9 · 13/4/24

Bài 4 nghĩ phức tạp quá làm ko ra trời ơi :ah:

nghĩ đơn giản là lượm tiền rồi huhuhu

Python:

class Solution:
    def numberOfSubarrays(self, nums: List[int]) -> int:
        def binarySearch(leftBoundary, rightBoundary, items):
            left = 0
            right = len(items) - 1
            leftIndex = -1
            while left <= right:
                mid = (left + right) // 2
                if items[mid] >= leftBoundary:
                    leftIndex = mid
                    right = mid - 1
                else:
                    left = mid + 1
                    
            rightIndex = -1
            
            left = 0
            right = len(items) - 1
            while left <= right:
                mid = (left + right) // 2
                if items[mid] <= rightBoundary:
                    rightIndex = mid
                    left = mid + 1
                else:
                    right = mid - 1
            return rightIndex - leftIndex + 1
        
        n = len(nums)
        nextGreater = [n]*n
        stack = []
        indexes = defaultdict(list)
        for i in range(n):
            indexes[nums[i]].append(i)
            while stack and nums[stack[-1]] < nums[i]:
                nextGreater[stack.pop()] = i
            stack.append(i)

        ans = 0
        for i in range(n):
            rightBoundary = nextGreater[i] - 1
            count = binarySearch(i, rightBoundary, indexes[nums[i]])
            
            ans += count
            
        return ans

LmaoSuVuong · 13/4/24

Java:

class Solution {
    public long numberOfSubarrays(int[] nums) {
        long ans = 0;
        int[] stack = new int[100001];
        int top = -1;
        HashMap<Integer, Integer> freq = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if (top < 0) {//stack empty
                top++;
                stack[top] = nums[i];
            } else {
                if (nums[i] > stack[0]) {
                    top = -1;
                    freq = new HashMap();
                } else {
                    while (top >= 0 && nums[i] > stack[top]) {
                        freq.put(stack[top],freq.get(stack[top])-1);
                        top--;
                    }
                }

                top++;
                stack[top] = nums[i];
            }
      
            freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
            ans += freq.get(nums[i]);
        }
        return ans;
    }
}

NahSama · 14/4/24

câu 3 dùng dijsktra mà éo ra khó chịu thế nhỉ, cày lc để làm OA th chứ contest xin thua :burn_joss_stick:

freedom.9 · 14/4/24

NahSama đã nói:
câu 3 dùng dijsktra mà éo ra khó chịu thế nhỉ, cày lc để làm OA th chứ contest xin thua

Câu 3 dijktra phải early continue nếu visitedAt != inf thì mới pass, ăn 2 cái TLE.
Làm 2 bài 7ph hí hửng tưởng ngon trym rồi ai ngờ làm xong bài 3 vẫn rank 4k hơn ko được + điểm nào, chua vl =((

ti_say_hi · 14/4/24

freedom.9 đã nói:
Câu 3 dijktra phải early continue nếu visitedAt != inf thì mới pass, ăn 2 cái TLE.
Làm 2 bài 7ph hí hửng tưởng ngon trym rồi ai ngờ làm xong bài 3 vẫn rank 4k hơn ko được + điểm nào, chua vl

Sáng nay em vừa làm lại Q3, hôm qua em đọc đề thì cứ tưởng là node disappear tại thời gian T thì sau đó T+1 sẽ appear lại, nhưng thật ra là nó disappear mãi mãi từ thời gian T

LmaoSuVuong · 14/4/24

nay 2 câu hard lận à

freedom.9 · 14/4/24

vỡ mồm con chồn

JustAnOtherClone · 14/4/24

làm 2 câu rồi nghỉ thôi, câu 3 k <= 2 * 10^9 lận, méo biết tối ưu kiểu gì

honda stone · 14/4/24

em làm xong q3 không biết q4 làm kiểu gì, thấy lú vcl

freedom.9 · 14/4/24

honda stone đã nói:
em làm xong q3 không biết q4 làm kiểu gì, thấy lú vcl

q3 hint tí đi mai fence :ah:

JustAnOtherClone · 14/4/24

freedom.9 đã nói:
q3 hint tí đi mai fence

solution thì đợi xong contest mới hỏi chứ fen, gian lận thế chơi bời gì

thảo luận Leetcode contest, đường tới Guardian

Junior Member

Senior Member

Member

Senior Member

Senior Member

Tệp đính kèm

Senior Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này