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

Đuôi Chuột Ngoáy Lọ Mỡ · 5/7/24

C++:

vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        vector<int> ans(2, int(1e6));
        vector<int> tmp;
        ListNode *prev;
        ListNode *cur;
        ListNode *next;
        prev = head;
        cur = prev->next;
        next = cur->next;
        int i = 2;
        if (cur->next == nullptr) return {-1, -1};
        while(next != nullptr) {
            if ((cur->val > prev->val && cur->val > next->val) || (cur->val < prev->val && cur->val < next->val)) {
                tmp.push_back(i);
            }
            prev = prev->next;
            cur = cur->next;
            next = next->next;
            ++i;
        }
        int n = tmp.size();
        if(n < 2) return {-1, -1};
        if(n == 2) return {tmp[1] - tmp[0], tmp[1] - tmp[0]};
        ans[1] = tmp[n-1] - tmp[0];
        for(int i = 1; i < n; i++) {
            ans[0] = min(ans[0], tmp[i] - tmp[i - 1]);
        }
        return ans;
    }

chạy chậm quá, hóng cao nhân chỉ thêm ạ

Ung Thư Gan · 5/7/24

Đuôi Chuột Ngoáy Lọ Mỡ đã nói:
C++:

vector<int> nodesBetweenCriticalPoints(ListNode* head) { vector<int> ans(2, int(1e6)); vector<int> tmp; ListNode *prev; ListNode *cur; ListNode *next; prev = head; cur = prev->next; next = cur->next; int i = 2; if (cur->next == nullptr) return {-1, -1}; while(next != nullptr) { if ((cur->val > prev->val && cur->val > next->val) || (cur->val < prev->val && cur->val < next->val)) { tmp.push_back(i); } prev = prev->next; cur = cur->next; next = next->next; ++i; } int n = tmp.size(); if(n < 2) return {-1, -1}; if(n == 2) return {tmp[1] - tmp[0], tmp[1] - tmp[0]}; ans[1] = tmp[n-1] - tmp[0]; for(int i = 1; i < n; i++) { ans[0] = min(ans[0], tmp[i] - tmp[i - 1]); } return ans; }

chạy chậm quá, hóng cao nhân chỉ thêm ạ

Em nghĩ bác xử lý không cần temp sẽ nhanh hơn, làm như bác vừa tăng TC vừa tăng SC
, code của bác chạy 2 pass lận

Ung Thư Gan · 5/7/24

askri79 đã nói:

Swift:

class Solution {
    func nodesBetweenCriticalPoints(_ head: ListNode?) -> [Int] {
        guard let head else { return [-1, -1] }

        var minDistance = -1
        var maxDistance = -1

        var firstPos = 0
        var prePos = 0
        var currPos = 1

        func dfs(node1: ListNode?, node2: ListNode?, node3: ListNode?) {
            guard let node1, let node2, let node3 else { return }
            currPos += 1
            let isDistinct = (node2.val > node1.val && node2.val > node3.val) ||
                            (node2.val < node1.val && node2.val < node3.val)
            if isDistinct {
                if firstPos != 0 {
                    minDistance = minDistance != -1 ? min(minDistance, currPos - prePos) : currPos - prePos
                    maxDistance = max(maxDistance, currPos - firstPos)
                    prePos = currPos
                } else {
                    firstPos = currPos
                    prePos = currPos
                }
            }

            dfs(node1: node2, node2: node3, node3: node3.next)
        }

        dfs(node1: head, node2: head.next, node3: head.next?.next)

        return [minDistance, maxDistance]
    }
}

Bác này giỏi quá, vậy mà cũng nghĩ ra được

linhdz2709 · 5/7/24

Đuôi Chuột Ngoáy Lọ Mỡ đã nói:
C++:

vector<int> nodesBetweenCriticalPoints(ListNode* head) { vector<int> ans(2, int(1e6)); vector<int> tmp; ListNode *prev; ListNode *cur; ListNode *next; prev = head; cur = prev->next; next = cur->next; int i = 2; if (cur->next == nullptr) return {-1, -1}; while(next != nullptr) { if ((cur->val > prev->val && cur->val > next->val) || (cur->val < prev->val && cur->val < next->val)) { tmp.push_back(i); } prev = prev->next; cur = cur->next; next = next->next; ++i; } int n = tmp.size(); if(n < 2) return {-1, -1}; if(n == 2) return {tmp[1] - tmp[0], tmp[1] - tmp[0]}; ans[1] = tmp[n-1] - tmp[0]; for(int i = 1; i < n; i++) { ans[0] = min(ans[0], tmp[i] - tmp[i - 1]); } return ans; }

chạy chậm quá, hóng cao nhân chỉ thêm ạ

bỏ hết mấy cái biến này đi bác. mình có dùng lại thằng head nữa đâu
ListNode *prev;
ListNode *cur;
ListNode *next;
head = head->next thôi

Đuôi Chuột Ngoáy Lọ Mỡ · 5/7/24

Ung Thư Gan đã nói:
Em nghĩ bác xử lý không cần temp sẽ nhanh hơn, làm như bác vừa tăng TC vừa tăng SC
, code của bác chạy 2 pass lận

linhdz2709 đã nói:
bỏ hết mấy cái biến này đi bác. mình có dùng lại thằng head nữa đâu
ListNode *prev;
ListNode *cur;
ListNode *next;
head = head->next thôi

Người quan sát cô đơn · 5/7/24

linhdz2709 đã nói:
bỏ hết mấy cái biến này đi bác. mình có dùng lại thằng head nữa đâu
ListNode *prev;
ListNode *cur;
ListNode *next;
head = head->next thôi

bỏ đống đó đi thì lấy gì để so sánh

Đuôi Chuột Ngoáy Lọ Mỡ · 5/7/24

Người quan sát cô đơn đã nói:
bỏ đống đó đi thì lấy gì để so sánh

như vầy là được rồi

chiyeuemthoi · 5/7/24

Mã:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        prev = head.val
        head = head.next
        cnt = 2
        res = []
        ans = [float("inf") , -1]
        while head.next:
            if head.val > head.next.val and head.val > prev:res.append(cnt)
            if head.val < head.next.val and head.val < prev:res.append(cnt)
            cnt += 1
            prev = head.val
            head = head.next

        if len(res) < 2: return [-1 , -1]
        
        ans[1] = res[-1] - res[0]
        for i in range(1 , len(res)):
            ans[0] = min(ans[0] , res[i] - res[i - 1])
        return ans

Người quan sát cô đơn · 5/7/24

Đuôi Chuột Ngoáy Lọ Mỡ đã nói:
như vầy là được rồi

head->next = null thì head->next->next lỗi nhé

Đuôi Chuột Ngoáy Lọ Mỡ · 5/7/24

Người quan sát cô đơn đã nói:
head->next = null thì head->next->next lỗi nhé

đề cho ít nhất 2 phần tử mà, khum lỗi đâu

Người quan sát cô đơn · 5/7/24

Đuôi Chuột Ngoáy Lọ Mỡ đã nói:
đề cho ít nhất 2 phần tử mà, khum lỗi đâu

chạy đến cái node n-1 là lỗi r còn gì.

Đuôi Chuột Ngoáy Lọ Mỡ · 5/7/24

Người quan sát cô đơn đã nói:
chạy đến cái node n-1 là lỗi r còn gì.

while(head->next->next != null) mà

Konstante · 5/7/24

Đuôi Chuột Ngoáy Lọ Mỡ đã nói:
C++:

vector<int> nodesBetweenCriticalPoints(ListNode* head) { vector<int> ans(2, int(1e6)); vector<int> tmp; ListNode *prev; ListNode *cur; ListNode *next; prev = head; cur = prev->next; next = cur->next; int i = 2; if (cur->next == nullptr) return {-1, -1}; while(next != nullptr) { if ((cur->val > prev->val && cur->val > next->val) || (cur->val < prev->val && cur->val < next->val)) { tmp.push_back(i); } prev = prev->next; cur = cur->next; next = next->next; ++i; } int n = tmp.size(); if(n < 2) return {-1, -1}; if(n == 2) return {tmp[1] - tmp[0], tmp[1] - tmp[0]}; ans[1] = tmp[n-1] - tmp[0]; for(int i = 1; i < n; i++) { ans[0] = min(ans[0], tmp[i] - tmp[i - 1]); } return ans; }

chạy chậm quá, hóng cao nhân chỉ thêm ạ

Bác thử thay ans và tmp bằng các variables kiểu int bình thường thôi (mỗi cái thay bằng hai variables), để đỡ phải truy cập bộ nhớ và các thao tác push tốn tài nguyên. Thay bằng biến kiểu int thì compiler sẽ có thể optimize dùng registers.

Đuôi Chuột Ngoáy Lọ Mỡ · 5/7/24

Konstante đã nói:
Bác thử thay ans và tmp bằng các variables kiểu int bình thường thôi (mỗi cái thay bằng hai variables), để đỡ phải truy cập bộ nhớ và các thao tác push tốn tài nguyên. Thay bằng biến kiểu int thì compiler sẽ có thể optimize dùng registers.

trư cũng nghĩ là dùng 3 biến được nhưng chưa biết làm kiểu gì

small-lambda · 5/7/24

tại sao các bạn không đấm nhau

Người quan sát cô đơn · 5/7/24

Đuôi Chuột Ngoáy Lọ Mỡ đã nói:
trư cũng nghĩ là dùng 3 biến được nhưng chưa biết làm kiểu gì

loop từng node, nếu tim đc local maxima hay local minima thì so sanh với min rồi cập nhật min thôi.

Konstante · 5/7/24

Đuôi Chuột Ngoáy Lọ Mỡ đã nói:
trư cũng nghĩ là dùng 3 biến được nhưng chưa biết làm kiểu gì

Cái tmp hình như bác để lưu các critical points, thực ra không cần lưu hết, chỉ cần lưu cái đầu tiên và một cái hiện tại (để tính max distance), còn min distance thì bác cứ tính dần dần ngay trong vòng lặp while (về sau vòng lặp for không cần nữa).

small-lambda · 5/7/24

Người quan sát cô đơn đã nói:
loop từng node, nếu tim đc local maxima hay local minima thì so sanh với min rồi update cập nhật min thôi.

làm luôn đi cho thiên hạ thấy võ công :love:

Người quan sát cô đơn · 5/7/24

small-lambda đã nói:
làm luôn đi cho thiên hạ thấy võ công

làm ở trên r mà mai fen

small-lambda · 5/7/24

Người quan sát cô đơn đã nói:
làm ở trên r mà mai fen

dùng 3 biến thôi anh tài

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

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này