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

[seastar]

Tính trước kết quả ở compile time. Khi run chỉ cần access array để lấy kết quả.

class Solution {
public:
    int tribonacci(int n) {
        return arr_[n];
    }
private:
    static constexpr array<int, 38> arr_ = [] {
        array<int, 38> arr{};
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 1;
        for (int i = 3; i< arr.size(); ++i) {
            arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
        }
        return arr;
    }();
};

Chỉ có ngôn ngữ thượng đẳng mới làm đc ntn,

 

[thanbaiks]

Tính trước kết quả ở compile time. Khi run chỉ cần access array để lấy kết quả.

class Solution {
public:
    int tribonacci(int n) {
        return arr_[n];
    }
private:
    static constexpr array<int, 38> arr_ = [] {
        array<int, 38> arr{};
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 1;
        for (int i = 3; i< arr.size(); ++i) {
            arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
        }
        return arr;
    }();
};

Chỉ có ngôn ngữ thượng đẳng mới làm đc ntn,

Spoiler: JavaScript hạ đẳng

/**
 * @param {number} n
 * @return {number}
 */
var tribonacci = function(n) {
    return [
        0,
        1,
        1,
        2,
        4,
        7,
        13,
        24,
        44,
        81,
        149,
        274,
        504,
        927,
        1705,
        3136,
        5768,
        10609,
        19513,
        35890,
        66012,
        121415,
        223317,
        410744,
        755476,
        1389537,
        2555757,
        4700770,
        8646064,
        15902591,
        29249425,
        53798080,
        98950096,
        181997601,
        334745777,
        615693474,
        1132436852,
        2082876103
    ][n]
};

 

[anoldvozer1710.v2]

Spoiler: JavaScript hạ đẳng

/**
 * @param {number} n
 * @return {number}
 */
var tribonacci = function(n) {
    return [
        0,
        1,
        1,
        2,
        4,
        7,
        13,
        24,
        44,
        81,
        149,
        274,
        504,
        927,
        1705,
        3136,
        5768,
        10609,
        19513,
        35890,
        66012,
        121415,
        223317,
        410744,
        755476,
        1389537,
        2555757,
        4700770,
        8646064,
        15902591,
        29249425,
        53798080,
        98950096,
        181997601,
        334745777,
        615693474,
        1132436852,
        2082876103
    ][n]
};

lại nhớ hôm trước có thằng làm weekly contest lol

via theNEXTvoz for iPhone

 

[seastar]

Spoiler: JavaScript hạ đẳng

/**
 * @param {number} n
 * @return {number}
 */
var tribonacci = function(n) {
    return [
        0,
        1,
        1,
        2,
        4,
        7,
        13,
        24,
        44,
        81,
        149,
        274,
        504,
        927,
        1705,
        3136,
        5768,
        10609,
        19513,
        35890,
        66012,
        121415,
        223317,
        410744,
        755476,
        1389537,
        2555757,
        4700770,
        8646064,
        15902591,
        29249425,
        53798080,
        98950096,
        181997601,
        334745777,
        615693474,
        1132436852,
        2082876103
    ][n]
};

hard coding thì hạ đẳng là đúng rồi,

 

[thanbaiks]

lại nhớ hôm trước có thằng làm weekly contest lol

via theNEXTvoz for iPhone

Chưa làm contest bao giờ. Nhưng trong contest thì nó ko nên show hidden tests lên

 

[afatnan]

Spoiler: 31/1

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size(), res = 0;
        vector<int> idx(n);
        iota(begin(idx), end(idx), 0);
        sort(begin(idx), end(idx), [&scores, &ages](const int &i1, const int &i2){
            return (ages[i1] < ages[i2]) || (ages[i1] == ages[i2] && scores[i1] < scores[i2]);
        });
        vector<int> dp = scores;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < i; ++j)
                if(scores[idx[i]] >= scores[idx[j]])
                    dp[idx[i]] = max(dp[idx[i]], dp[idx[j]] + scores[idx[i]]);
            res = max(res, dp[idx[i]]);
        }
        
        return res;
    }
};

 

[bribnt]

Segment tree - O(n log M + n log n) (M = max age)

Spoiler: 230131 - 1626. Best Team With No Conflicts

class Solution {
    vector<int> st;
    int n;
    void init(int n) {
        st.assign((this->n = n) * 2, 0);
    }
    void update(int age, int mx) {
        for (st[age += n] = mx; age; age >>= 1)
            st[age >> 1] = max(st[age], st[age^1]);
    }
    int get(int min_age, int max_age) {
        int res = 0;
        for (int l = min_age + n, r = max_age + n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, st[l++]);
            if (r & 1) res = max(res, st[--r]);
        }
        return res;
    }
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size(), res = 0, max_age = 0;
        vector<pair<int, int>> sa(n);
        init(1001);
        for (int i = 0; i < n; ++i)
            sa[i] = make_pair(scores[i], ages[i]);
        sort(begin(sa), end(sa), greater{});
        for (auto [score, age] : sa) {
            max_age = max(max_age, age);
            int curr = get(age, max_age + 1) + score;
            update(age, curr);
            res = max(curr, res);
        }
        return res;
    }
};

 

[thanbaiks]

Spoiler: JavaScript

/**
 * @param {number[]} scores
 * @param {number[]} ages
 * @return {number}
 */
var bestTeamScore = function(scores, ages) {
    const players = _.zip(ages, scores).sort((u, v) => (u[0]+u[1]*1000) - (v[0]+v[1]*1000));
    const maxOfAge = [];
    let ans = -Infinity;
    for (const [a, s] of players) {
        let tmp = 0;
        for (let i = 1; i <= a; i++) {
            tmp = Math.max(tmp, (maxOfAge[i] ?? 0) + s);
        }
        maxOfAge[a] = tmp;
        ans = Math.max(ans, tmp);
    }

    return ans;
};

 

[anoldvozer1710.v2]

Đúng như dự đoán, hôm nay lại thêm 1 bài DP nữa

Spoiler: Ý tưởng

• Để tránh việc phải luôn so sánh giữa age và score khi loop -> store cặp age-score vào 1 mảng khác và sort by age sau đó là score với thứ tự tăng dần.
• Bài toán bây giờ là ở mỗi 1 giá trị i, do tuổi trong khoảng từ 0 đến i-1 chắc chắn sẽ nhỏ hơn hoặc bằng i -> cần phải tìm xem ở trong khoảng từ 0-> i-1 có candidate nào có score nhỏ hơn hoặc bằng giá trị tại i -> so sánh giữa các giá trị max -> bài toán con -> DP.

Spoiler: TypeScript 31/1

function bestTeamScore(scores: number[], ages: number[]): number {
    let candidates: number[][] = [];
    const n = scores.length;
    // store pairs of ages and scores
    for (let i = 0; i < n; i++) {
        candidates.push([ages[i], scores[i]]);
    }
    // sort by ages first, then sort by score
    candidates = candidates.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);

    // using dp to store the maximum score

    let dp: number[] = Array(n).fill(0);
    dp[0] = candidates[0][1];
    let max = dp[0];
    for (let i = 0; i < n; i++) {
        let currentScore = candidates[i][1];
        dp[i] = currentScore;
        for (let j = 0; j < i; j++) {
            // Only compare if the score at j is smaller than currentScore
            if (candidates[j][1] <= candidates[i][1]) {
                dp[i] = Math.max(dp[i], dp[j] + currentScore);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
};

 

[bdbc voz]

năm nay kín là đẹp

 

[anoldvozer1710.v2]

năm nay kín là đẹp
View attachment 1635808

cày ác dữ vậy thím

 

[lefeno]

Ko biết có cần phải xuất sắc lắm mới giỏi được thuật toán như mấy bác trên ko? Em mới join leetcode thấy bài khó vãi.
Làm sao mà nhìn mà nghĩ ra được lời giải. Trong leetcode nó ít nhất có gợi ý O(N) O(N+M) chứ ở ngoài làm sao nghĩ tới đó được. Nếu tập nhiều thì quen ko ạ? Em chỉ mới làm lại data structure và interview study 15 ngày mà em ngu ngơ quá .

 

[RiDoGanhTeam]

năm nay kín là đẹp
View attachment 1635808

dây là của em năm ngoái.. Kiểu không còn là ôn luyện nữa mà là thói quen r ồi ngày vào check 1 bài giải vận động não bộ thội.

 

[RiDoGanhTeam]

Ko biết có cần phải xuất sắc lắm mới giỏi được thuật toán như mấy bác trên ko? Em mới join leetcode thấy bài khó vãi.
Làm sao mà nhìn mà nghĩ ra được lời giải. Trong leetcode nó ít nhất có gợi ý O(N) O(N+M) chứ ở ngoài làm sao nghĩ tới đó được. Nếu tập nhiều thì quen ko ạ? Em chỉ mới làm lại data structure và interview study 15 ngày mà em ngu ngơ quá .

Làm quen là được bác, nó như giải toán vậy, làm chặp sẽ nhớ nhiều dạng rồi giải nhanh với dễ hơn... Cái này làm vận động não bộ thôi chứ mình vẫn khuyến khích luyện thêm về computer science với hiểu sâu bản chất của những thứ mình làm sẽ giúp ích cho công việc hằng ngày hơn...

 

[lefeno]

Làm quen là được bác, nó như giải toán vậy, làm chặp sẽ nhớ nhiều dạng rồi giải nhanh với dễ hơn... Cái này làm vận động não bộ thôi chứ mình vẫn khuyến khích luyện thêm về computer science với hiểu sâu bản chất của những thứ mình làm sẽ giúp ích cho công việc hằng ngày hơn...

Cảm ơn bác. Luyện thêm về computer science là luyện gì v bác? Tại em thấy mấy công ty tuyển dụng giờ toàn yêu cầu giỏi thuật toán bla bla các kiểu nên em thấy rén, không tự tin gì hết.

 

[somalis]

Mấy bác cho hỏi leetcode này mình phải mua đúng không, thấy có phí thì phải

 

[anoldvozer1710.v2]

Mấy bác cho hỏi leetcode này mình phải mua đúng không, thấy có phí thì phải

subscribe mấy cái premium thôi thím, code bình thường ko cần

 

[chiyeuemthoi]

dây là của em năm ngoái.. Kiểu không còn là ôn luyện nữa mà là thói quen r ồi ngày vào check 1 bài giải vận động não bộ thội.View attachment 1636464

vãi lắm vậy , bác tổng giải dc bn bài rồi vậy

 

[RiDoGanhTeam]

Cảm ơn bác. Luyện thêm về computer science là luyện gì v bác? Tại em thấy mấy công ty tuyển dụng giờ toàn yêu cầu giỏi thuật toán bla bla các kiểu nên em thấy rén, không tự tin gì hết.

Kiểu design system đồ, hoặc là hiểu sâu về máy tính á, hiểu rõ bản chất mọi cái... Mình thấy cái đó có ich hơn nhiều vì nó thực tiễn và giúp mình giải quyết vấn đề nhiều hơn...

 

[RiDoGanhTeam]

vãi lắm vậy , bác tổng giải dc bn bài rồi vậy

tầm 1k1 bài thôi bác.. mình làm chơi chơi thôi chứ ko ham hố cày leetcode cho lắm... kiểu có ngày lên đồng nhìn vào làm được là cứ thế mà gõ thôi, còn bí thì thôi dẹp qua bên từ từ làm tiếp, kiểu vậy.. làm dần nó lên được chừng đó