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

nhethanh2 · 26/8/23

JavaScript:

function findLongestChain(pairs: number[][]): number {
 const sortedPairs = sortPairsByRightNumber(pairs);
 let result = 1;
 let currentPair = sortedPairs[0];
 sortedPairs.forEach(pair=>{
    if (pair[0]>currentPair[1]) {
        result++;
        currentPair=pair;
        }
    })
    return result
};

function sortPairsByRightNumber (pairs:number[][]): number[][]{
    const sortedPairs = pairs.sort((p1,p2)=>p1[1]-p2[1])
    return sortedPairs;
}

Bleach & Sarcasm · 26/8/23

nếu sort [ai, bi] tăng dần theo bi thì có thể xài "tham lam" giải trong ~~O(n)~~ được

edit: sort mất O(nlogn) nên giải trong O(nlogn) mới đúng

giả sử cho dãy N đoạn, tạo được dãy có độ dài L kết thúc tại x, giờ cho thêm đoạn [a, b], sẽ tạo được dãy mới độ dài L+1 kết thúc tại b nếu a > x.

Giờ phải xét thứ tự append [a,b] vào thế nào thì đúng:
cho 3 đoạn [a,b], [c,d], [e,f]

TH0: nhận 3 đoạn hay 3 đoạn ko cắt nhau thì dễ dàng nhận thấy sắp xếp theo p[0] hay p[1] cũng được

TH1: chỉ nhận 2 đoạn: gọi 2 đoạn nhận là [a,b] và [c,d], b < c, 2 đoạn này ko đụng nhau. Ta chỉ cần xét [a,b] đụng [e,f] là đủ, vì nếu [e,f] chỉ đụng [c,d] mà ko đụng [a,b] thì ta chọn đoạn [e,f] hay [c,d] gì cũng thu được 2 đoạn.
TH1a: a < e: Ko xét TH f <= b hay [e,f] nằm trong [a,b] vì TH này chọn [a,b] hay [e,f] cũng đúng. Xét [a-----|e--b]--[c----f|---d]: nhìn hình này thì nếu sắp xếp tăng theo p[0] thì sẽ có thứ tự [a,b], [e,f] vì a < e, vậy là loại được [e,f] vì [e,f] cắt [a,b] đã nhận trươc đó. Sắp xếp tăng theo p[1] cũng đúng vì ở đây ko xét f <= b nghĩa là f > b vậy [a,b] cũng tới trước [e,f]
TH1b: e >= a: Nếu e đứng trước a như |e[a-------b]--[c-----f|---d] thì sắp xếp theo p[0] tăng dần sẽ được [e,f] [a,b] có thể chỉ nhận 1 đoạn [e,f] nếu f >= c, ko phải là nhận 2 đoạn, vậy ko thể sx tăng dần theo p[0] được. Sx tăng dần theo p[1] thì vẫn đúng, vì 2 đoạn [a,b] [c,d] ko đụng nhau, mặc định [a,b] đứng trước [c,d] nên b < c, vậy nếu f > c nghĩa là f > b, vậy sx theo p[1] thì [a,b] sẽ tới trước [e,f].

TH2: chỉ nhận 1 đoạn: [a,b], [c,d], [e,f] đụng nhau. Ví dụ |e-[a---|c--------b]-d|--f|, thì nhận thấy tham lam lấy đoạn có p[1] bé nhất để đoạn liền sau [a', b'] phải so sánh a' > p[1] này, thì p[1] càng bé càng dễ nhận a' hơn, ví dụ p[1] = 3 hoặc 6 hoặc 8, đoạn liền sau là [7,9] thì lấy p[1] = 3 hoặc 6 đều được, lấy 3 vẫn đúng, nếu đoạn liều sau là [2, 11] thì p[1] = 3 ko nhận được đoạn này thì p[1] = 6 hay 8 cũng ko nhận được. Vậy sx theo p[1] tăng dần sẽ lấy p[1] nhỏ nhất trong 3 đoạn này, vẫn đúng trong TH2 này.

chỉ có 3 TH cho 3 đoạn, mà xét 3 đoạn cũng mở rộng ra cho n đoạn được nên sx p[1] tăng dần rồi lướt 1 vòng for append các đoạn đã sx theo p[1] vào là được

C++:

struct Solution {
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(begin(pairs), end(pairs), [](auto& p, auto& q){ return p[1] < q[1]; });
        return accumulate(begin(pairs) + 1, end(pairs), 1,
                          [rightMostVal = pairs[0][1]](int res, auto& p) mutable {
                              if (p[0] > rightMostVal) ++res, rightMostVal = p[1];
                              return res;
                          });
    }
};

edit: xài count_if đún hơn là xài accumulate

C++:

struct Solution {
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(begin(pairs), end(pairs), [](auto& p, auto& q){ return p[1] < q[1]; });
        return 1 + count_if(begin(pairs) + 1, end(pairs),
                            [rightMostVal = pairs[0][1]](auto& p) mutable {
                                return p[0] > rightMostVal ? rightMostVal = p[1], true : false;
                            });
    }
};

hoặc

C++:

struct Solution {
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(begin(pairs), end(pairs), [](auto& p, auto& q){ return p[1] < q[1]; });
        return count_if(begin(pairs), end(pairs), [rightMostVal = pairs[0][0] - 1](auto& p) mutable {
            return p[0] > rightMostVal ? rightMostVal = p[1], true : false;
        });
    }
};

freedom.9 · 26/8/23

Biết là greedy được mà cứ đi sort theo start date, ngu vãi.
Xài DP thì ra rồi cơ mà ko nhanh lắm. Có thêm tí kinh nghiệm :ah:

Hi_guys · 26/8/23

C++:

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [] (auto& a, auto& b) {return a[1] < b[1];});
        int tail = pairs[0][1];
        int cnt = 1;
        for (int i = 1; i < pairs.size(); i++)
            if (pairs[i][0] > tail) {
                cnt++;
                tail = pairs[i][1];
            }
        return cnt;
    }
};

nchhnchh · 26/8/23

dp O(n2)

Python:

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        n = len(pairs)
        dp = [1] * n

        pairs = sorted(pairs, key= lambda x:x[0]+x[1] )
        for i in range(1, n):
            u, _ = pairs[i]
            for j in range(0, i):
                _, v = pairs[j]
                if v < u and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1

        return max(dp)

Hover · 26/8/23

freedom.9 đã nói:
https://leetcode.com/problems/bus-routes/
1 bài pv của Uber, giải chơi ae. Bài này tụi nó hay xài để pv vì vừa có thể ktra được nhiều alogrithm khác nhau.
Dạo này giải leetcode ko phải đi pv nữa mà vì nghiện vl. Làm mấy bài graph này hay vãi.

Câu này hôm bữa xem 1 clip thấy rồi, nhưng câu này với mình thì dễ, đọc đề nghĩ ra luôn sol. :beauty:

Hover · 26/8/23

Bleach & Sarcasm đã nói:
nếu sort [ai, bi] tăng dần theo bi thì có thể xài "tham lam" giải trong ~~O(n)~~ được

edit: sort mất O(nlogn) nên giải trong O(nlogn) mới đúng

giả sử cho dãy N đoạn, tạo được dãy có độ dài L kết thúc tại x, giờ cho thêm đoạn [a, b], sẽ tạo được dãy mới độ dài L+1 kết thúc tại b nếu a > x.

Giờ phải xét thứ tự append [a,b] vào thế nào thì đúng:
cho 3 đoạn [a,b], [c,d], [e,f]

TH0: nhận 3 đoạn hay 3 đoạn ko cắt nhau thì dễ dàng nhận thấy sắp xếp theo p[0] hay p[1] cũng được

TH1: chỉ nhận 2 đoạn: gọi 2 đoạn nhận là [a,b] và [c,d], b < c, 2 đoạn này ko đụng nhau. Ta chỉ cần xét [a,b] đụng [e,f] là đủ, vì nếu [e,f] chỉ đụng [c,d] mà ko đụng [a,b] thì ta chọn đoạn [e,f] hay [c,d] gì cũng thu được 2 đoạn.
TH1a: a < e: Ko xét TH f <= b hay [e,f] nằm trong [a,b] vì TH này chọn [a,b] hay [e,f] cũng đúng. Xét [a-----|e--b]--[c----f|---d]: nhìn hình này thì nếu sắp xếp tăng theo p[0] thì sẽ có thứ tự [a,b], [e,f] vì a < e, vậy là loại được [e,f] vì [e,f] cắt [a,b] đã nhận trươc đó. Sắp xếp tăng theo p[1] cũng đúng vì ở đây ko xét f <= b nghĩa là f > b vậy [a,b] cũng tới trước [e,f]
TH1b: e >= a: Nếu e đứng trước a như |e[a-------b]--[c-----f|---d] thì sắp xếp theo p[0] tăng dần sẽ được [e,f] [a,b] có thể chỉ nhận 1 đoạn [e,f] nếu f >= c, ko phải là nhận 2 đoạn, vậy ko thể sx tăng dần theo p[0] được. Sx tăng dần theo p[1] thì vẫn đúng, vì 2 đoạn [a,b] [c,d] ko đụng nhau, mặc định [a,b] đứng trước [c,d] nên b < c, vậy nếu f > c nghĩa là f > b, vậy sx theo p[1] thì [a,b] sẽ tới trước [e,f].

TH2: chỉ nhận 1 đoạn: [a,b], [c,d], [e,f] đụng nhau. Ví dụ |e-[a---|c--------b]-d|--f|, thì nhận thấy tham lam lấy đoạn có p[1] bé nhất để đoạn liền sau [a', b'] phải so sánh a' > p[1] này, thì p[1] càng bé càng dễ nhận a' hơn, ví dụ p[1] = 3 hoặc 6 hoặc 8, đoạn liền sau là [7,9] thì lấy p[1] = 3 hoặc 6 đều được, lấy 3 vẫn đúng, nếu đoạn liều sau là [2, 11] thì p[1] = 3 ko nhận được đoạn này thì p[1] = 6 hay 8 cũng ko nhận được. Vậy sx theo p[1] tăng dần sẽ lấy p[1] nhỏ nhất trong 3 đoạn này, vẫn đúng trong TH2 này.

chỉ có 3 TH cho 3 đoạn, mà xét 3 đoạn cũng mở rộng ra cho n đoạn được nên sx p[1] tăng dần rồi lướt 1 vòng for append các đoạn đã sx theo p[1] vào là được

C++:

struct Solution { int findLongestChain(vector<vector<int>>& pairs) { sort(begin(pairs), end(pairs), [](auto& p, auto& q){ return p[1] < q[1]; }); return accumulate(begin(pairs) + 1, end(pairs), 1, [rightMostVal = pairs[0][1]](int res, auto& p) mutable { if (p[0] > rightMostVal) ++res, rightMostVal = p[1]; return res; }); } };

Nói chung tư tưởng là lấy được 1 item kết thúc trước sẽ không bao giờ tệ hơn lấy 1 item kết thúc sau. Còn nếu sắp xếp theo p[0] thì duyệt ngược lại. :smile:

Bleach & Sarcasm · 26/8/23

Hover đã nói:
Nói chung tư tưởng là lấy được 1 item kết thúc trước sẽ không bao giờ tệ hơn lấy 1 item kết thúc sau. Còn nếu sắp xếp theo p[0] thì duyệt ngược lại.

ờm ngủ dậy xong thấy tư tưởng đơn giản thặc, trưa ngồi vẽ lên cho thấy khó

Hover · 26/8/23

Bleach & Sarcasm đã nói:
ờm ngủ dậy xong thấy tư tưởng đơn giản thặc, trưa ngồi vẽ lên cho thấy khó

Code của phen nhiều đoạn làm ngắn mình đọc chưa thấm được, tại dốt C++ nữa :burn_joss_stick:

freedom.9 · 27/8/23

https://leetcode.com/problems/reverse-linked-list-ii
https://leetcode.com/problems/reverse-nodes-in-k-group
Làm xong 2 bài này là master linked list này ae, đọc editorial đỉnh vãi :ah:

Bleach & Sarcasm · 27/8/23

Hover đã nói:
Code của phen nhiều đoạn làm ngắn mình đọc chưa thấm được, tại dốt C++ nữa

toy codegolf nửa mùa thoy, code giải được lần đầu tiên cũng dài lắm, sau đó mới nhìn lại hàm for nào xài hàm trong thư viện chuẩn được thì rút gọn 5-10 lần rồi xiaolol "1" dòng này nọ

hungmessi2 · 27/8/23

freedom.9 đã nói:
https://leetcode.com/problems/reverse-linked-list-ii
https://leetcode.com/problems/reverse-nodes-in-k-group
Làm xong 2 bài này là master linked list này ae, đọc editorial đỉnh vãi

Confirm

realhaidinh · 27/8/23

freedom.9 đã nói:
https://leetcode.com/problems/reverse-linked-list-ii
https://leetcode.com/problems/reverse-nodes-in-k-group
Làm xong 2 bài này là master linked list này ae, đọc editorial đỉnh vãi

hôm trước vừa đọc cái trick pointer to pointer của lão linus nên áp dụng vào bài 1 luôn :beauty:

C++:

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* nodeRight = head;
        ListNode** ppl = &head;
        ListNode** ppr;
        int idx = 1;
        for(ListNode* curr = head; curr != nullptr; curr = curr->next){
            if(idx < left){
                ppl = &((*ppl)->next);
                nodeRight = nodeRight->next;
            }
            else if(idx == left){
                ppr = &nodeRight;
            }
            else if(idx > left && idx <= right){
                (*ppr)->next = curr->next;
                curr->next = *ppl;
                *ppl = curr;
                curr = *ppr;
            }
            idx++;
        }
        return head;
    }
};

freedom.9 · 27/8/23

Cái bài 2 fence nào cho mình xem code với, sao mà sai cay thế nhỉ :too_sad:

via theNEXTvoz for iPhone

nchhnchh · 27/8/23

freedom.9 đã nói:
Cái bài 2 fence nào cho mình xem code với, sao mà sai cay thế nhỉ

via theNEXTvoz for iPhone

contest hôm nay à

Python:

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        result = set()
        i = 1
        while len(result) < n:
            if i not in result and (target - i) not in result:
                result.add(i)
            i += 1
        return sum(result)

freedom.9 · 27/8/23

nchhnchh đã nói:

contest hôm nay à

Python:

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        result = set()
        i = 1
        while len(result) < n:
            if i not in result and (target - i) not in result:
                result.add(i)
            i += 1
        return sum(result)

Sao phải check i not in set nhỉ, i luôn tăng mà.

via theNEXTvoz for iPhone

freedom.9 · 27/8/23

nchhnchh đã nói:

contest hôm nay à

Python:

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        result = set()
        i = 1
        while len(result) < n:
            if i not in result and (target - i) not in result:
                result.add(i)
            i += 1
        return sum(result)

À mình biết sao sai rồi, code của mình để var ans = 0 nó tự cast qua int hèn gì ko pass all test cases.
Phải để ý kiểu dữ liệu mới được

thanbaiks · 27/8/23

JavaScript:

var canCross = function(stones) {
    if (stones[1] !== 1) {
        return false;
    }
    const memo = [];
    const go = (i, j) => memo[i * 2005 + j] ??= (() => {
        if (i === stones.length-1) {
            return true;
        }
        for (let k = i+1; k < stones.length; k++) {
            if (Math.abs(j - (stones[k] - stones[i])) <= 1) {
                if (go(k, stones[k] - stones[i])) {
                    return true;
                }
            } else if (stones[k] - stones[i] > j + 1) {
                return false;
            }
        }
    })();
    return go(1, 1);
};

Violet_7 · 27/8/23

Contest hôm nay bọn quant ra đề khó quá :too_sad:

.đc 2 câu, câu 3 sau contest 30p mới xong. Câu 4 chưa có ý tưởng gì

trinity · 27/8/23

Violet_7 đã nói:
Contest hôm nay bọn quant ra đề khó quá .đc 2 câu, câu 3 sau contest 30p mới xong. Câu 4 chưa có ý tưởng gì

Khó vậy mà để medium, đúng lừa

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

Junior Member

Senior Member

Senior Member

Junior Member

Senior Member

Member

Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này