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

C++ không có trò return về 2 biến nên đành dùng mảng 2 phần tử :(
Có mà, C++ giờ code như python :p
C++:
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        auto [a,b] = make_tuple(0,0);
        for (auto x : cost) {
            tie(a,b) = make_tuple(b,x + min(a,b));
        }
        return min(a,b);
    }
};
 

...Batman...

Senior Member
có bác nào đang làm contest hôm nay không? Có thanh niên VN này rank 5 kinh vđ
https://leetcode.com/contest/weekly-contest-301/ranking/
contest rating > 3k, codeforces 2k6
codeforces thì hơn leetcode nhiều ko nhỉ, em thấy nhiều nơi tuyển ưu tiên rank cao codeforces, topcoder
Có std::min với std::max mà thím.

C++ không có trò return về 2 biến nên đành dùng mảng 2 phần tử :(
C++:
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if (cost.size() == 2){
            return min(cost[0],cost[1]);
        }
        vector<int> recentCost{0,0};
        for (auto i = 2;i<=cost.size();i++){
            recentCost[i%2] = min(
                recentCost[i%2] + cost[i-2],
                recentCost[(i+1)%2] + cost[i-1]
            );
        }
       
        return recentCost[cost.size()%2];
    }
};

Có nhé min(x, y) = y ^ ((x ^ y) & -(x < y))

Ưu điểm: không cần rẽ nhánh nên sẽ nhanh hơn if else trong trường hợp tổng quát.

Sent from Xiaomi M2007J20CG using vozFApp
Code của em một cách thô thiển nhất. Cũng thử dùng deque mà ko có nhanh hơn :shame:
C++:
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        unsigned int c1=cost[0], c2=cost[1], c=0;
        for (size_t i=2; i < cost.size(); i++){
            c = (c1 < c2)? c1 : c2;
            c1 = c2;
            c2 = c + cost[i];
        }
        return (c1 < c2? c1 : c2);
    }
};
 
Có nhé min(x, y) = y ^ ((x ^ y) & -(x < y))

Ưu điểm: không cần rẽ nhánh nên sẽ nhanh hơn if else trong trường hợp tổng quát.

Sent from Xiaomi M2007J20CG using vozFApp
T nhớ trước có ai post cái link về việc dùng các toán tử bit thay thế cho rẽ nhánh trong các hàm cơ bản.

AE nào muốn hiểu rõ tại sao cái này lại nhanh hơn rẽ nhánh thì có thể tìm hiểu cái pipeline và branch prediction.
Giải thích đơn giản là phần cứng khi thực hiện tính toán 1 câu lệnh thì nó sẽ tiến hành load câu lệnh tiếp theo luôn. Do đó khi có rẽ nhánh thì nó sẽ không biết phải load trước câu lệnh tiếp theo từ nhánh nào, vì cái đó phụ thuộc vào kết quả của câu lệnh hiện tại.
Nó có nhiều kỹ thuật để xử lý hoặc predict cái branch bằng phần cứng hoặc phần mềm. Tuy nhiên vẫn có khả năng nó predict sai dẫn đến hao tổn tài nguyên.
Cách bên trên thì nó không có rẽ nhánh => không cần predict nữa => k predict sai, :big_smile:
 

bribnt

Đã tốn tiền
Nó có nhiều kỹ thuật để xử lý hoặc predict cái branch bằng phần cứng hoặc phần mềm. Tuy nhiên vẫn có khả năng nó predict sai dẫn đến hao tổn tài nguyên.:big_smile:

Nói thêm về cái vụ predict này. Nếu kết quả các lệnh rẽ nhánh mà đi theo một pattern đơn giản thì nó sẽ hoạt động rất tốt. Ngược lại nếu random thì tài thánh cũng không đoán được, tỉ lệ 50/50.

Ví du với lệnh if else tìm min. Nếu kết quả có dạng này: x x x y x x x y x x x y ... (cứ 3 x lại có 1 y) thì sau vài bước bộ predict sẽ được train để nhận dạng pattern đó, những lần sau nó sẽ đoán đúng với tỉ lệ rất cao.

Một ví dụ cơ bản là điều kiện vòng lặp for (int i = 0; i < n; ++i), với vòng lặp lớn thì (i < n) sẽ đúng hết trừ lần cuối nên predict sẽ dễ dàng đoán đúng trong hầu hết trường hợp.
 

...Batman...

Senior Member
T nhớ trước có ai post cái link về việc dùng các toán tử bit thay thế cho rẽ nhánh trong các hàm cơ bản.

AE nào muốn hiểu rõ tại sao cái này lại nhanh hơn rẽ nhánh thì có thể tìm hiểu cái pipeline và branch prediction.
Giải thích đơn giản là phần cứng khi thực hiện tính toán 1 câu lệnh thì nó sẽ tiến hành load câu lệnh tiếp theo luôn. Do đó khi có rẽ nhánh thì nó sẽ không biết phải load trước câu lệnh tiếp theo từ nhánh nào, vì cái đó phụ thuộc vào kết quả của câu lệnh hiện tại.
Nó có nhiều kỹ thuật để xử lý hoặc predict cái branch bằng phần cứng hoặc phần mềm. Tuy nhiên vẫn có khả năng nó predict sai dẫn đến hao tổn tài nguyên.
Cách bên trên thì nó không có rẽ nhánh => không cần predict nữa => k predict sai, :big_smile:
ko rẽ nhánh thì rõ ràng là dễ hơn rồi mà :D
Khi máy gặp 1 lệnh rẽ nhánh, chương trình mã máy sẽ nhảy đến đoạn địa chỉ của nhánh đó, sau đó thực hiện xong lại nhảy ngược lại về đoạn cũ.
Còn ko phải rẽ nhánh thì cứ thế mà nó đi thôi nên nhanh hơn nhiều.
 

God Emperor Leto

Senior Member
Có mà, C++ giờ code như python :p
C++:
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        auto [a,b] = make_tuple(0,0);
        for (auto x : cost) {
            tie(a,b) = make_tuple(b,x + min(a,b));
        }
        return min(a,b);
    }
};
nếu cần gán a=b, b=x hay như python là a, b = b, x thì có thể xài a = std::exchange(b, x), ko cần làm cái tuple làm gì đâu
JEWoIdl.png
 
ko rẽ nhánh thì rõ ràng là dễ hơn rồi mà :D
Khi máy gặp 1 lệnh rẽ nhánh, chương trình mã máy sẽ nhảy đến đoạn địa chỉ của nhánh đó, sau đó thực hiện xong lại nhảy ngược lại về đoạn cũ.
Còn ko phải rẽ nhánh thì cứ thế mà nó đi thôi nên nhanh hơn nhiều.
Uhm, cũng đúng. Ví dụ đoạn code rẽ nhánh cần jump đến ở quá xa, nằm ngoài instruction cache thì nó sẽ bị miss cache.
 
nếu cần gán a=b, b=x hay như python là a, b = b, x thì có thể xài a = std::exchange(b, x), ko cần làm cái tuple làm gì đâu
JEWoIdl.png
Do thím kia kêu C++ không có trò return về 2 biến được nên t mới show cho ông ấy cách return về tuple, viết kiểu nhìn giống python, :big_smile: . btw, cảm ơn Kân team vì đã add thêm cách dùng exchange.
 

bribnt

Đã tốn tiền
ko rẽ nhánh thì rõ ràng là dễ hơn rồi mà :D
Khi máy gặp 1 lệnh rẽ nhánh, chương trình mã máy sẽ nhảy đến đoạn địa chỉ của nhánh đó, sau đó thực hiện xong lại nhảy ngược lại về đoạn cũ.
Còn ko phải rẽ nhánh thì cứ thế mà nó đi thôi nên nhanh hơn nhiều.

Đoạn này không đúng lắm.
  • CPU, cụ thể là Branch Predictor Unit (BPU) sẽ chọn 1 trong 2 (hoặc nhiều) nhánh để thực thi tiếp.
  • Đến lúc có đủ thông tin thì sẽ tính toán check điều kiện rẽ nhánh. Nếu đã đoán đúng thì không cần làm gì nữa, nếu đoán sai thì phải rollback lại từ đầu.

Nên trong trường hợp BPU hoạt động tốt thì thì rẽ nhánh nhanh hơn vì logic code để không rẽ nhánh thường phức tạp.

Còn vụ nhảy các kiểu cũng không phải cái gì to tát lắm, miễn là lệnh vẫn còn đang ở trong cache thì không ảnh hưởng gì.
 

kyo_pyro

Senior Member
Có mà, C++ giờ code như python :p
C++:
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        auto [a,b] = make_tuple(0,0);
        for (auto x : cost) {
            tie(a,b) = make_tuple(b,x + min(a,b));
        }
        return min(a,b);
    }
};
Nhìn ma giáo quá thôi bỏ qua lul. Dùng mấy cái này ko biết thực chất nó làm gì bên dưới nên không ưng lắm.
 

Arik97

Senior Member

God Emperor Leto

Senior Member
Nhìn ma giáo quá thôi bỏ qua lul. Dùng mấy cái này ko biết thực chất nó làm gì bên dưới nên không ưng lắm.
https://en.cppreference.com/w/cpp/language/structured_binding
đọc doc 1 tí là biết thoy mà
cgE9MkI.gif

make_tuple(0,0); tạo ra 1 unname struct object có 2 biến int nằm trên stack là _i1 = 0, _i2 = 0
auto [a, b] = make_tuple(0, 0); thì a, b là _i1 và _i2
tie(a, b) = make_tuple(t1, t2) thì vế phải tạo t1 và t2 trên stack, vế trái tạo int& _a = a và int& _b = b, rồi gán _a = t1, _b = t2. Compiler nó optimize đi cái references _a _b hết thì ko khác gì viết 4 dòng t1 = ...; t2 = ...; a = t1; b = t2;

cái tuple ko khác gì 1 struct, chỉ có điều là compiler nó tự đặt tên cho struct đó, dev ko cần biết đến cái tên struct đó nên gọi nó là unnamed struct - struct ko tên, ko có ma giáo nào cả. Implement nó thì hình như có magic thặc nhưng ko có ma giáo gì hết
JiZo9zf.png


C++ từ trước tới giờ muốn return bao nhiêu biến cũng được cả. Lúc trước có thể phải tạo cái struct chứa các biến cần trả về, phải đặt tên cho cái struct đó. Bây giờ C++ hại điện thì xài tuple khỏi cần đặt tên
JiZo9zf.png
trade off duy nhất là compiling time cho tuple lâu hơn cái struct tự tạo
X0OgXK6.png


nếu trả về 2 biến thì có thể xài pair thay thế cho tuple. make_pair thế make_tuple. Compile lẹ hơn tuple mà xài tương tự auto [a, b] = make_pair(0, 0), tie(a, b) = make_pair(t1, t2)
 
Last edited:

dynamic programming

Senior Member
google thử tên thanh niên Trần Xuân Bách thì ra cái này. https://vnexpress.net/viet-nam-gianh-ba-huy-chuong-vang-olympic-tin-hoc-chau-a-4470874.html
Contest tuần này khó gấp đôi tuần trc :(

Sent from Samsung SM-G986U1 using vozFApp

Vl cu này mới học lớp 11 thôi à.
Contest hôm nay có Q1 với Q4 là khó hơn mọi khi chứ 2 câu medium thì đơn giản.
Mẹ nó cho cái câu đầu easy nhìn choáng vc, mất tận 10p để giải câu này :(

Sent from Samsung SM-J730G using vozFApp
 

Venjsen

Senior Member
Vl cu này mới học lớp 11 thôi à.
Contest hôm nay có Q1 với Q4 là khó hơn mọi khi chứ 2 câu medium thì đơn giản.
Mẹ nó cho cái câu đầu easy nhìn choáng vc, mất tận 10p để giải câu này :(

Sent from Samsung SM-J730G using vozFApp
đấy là thanh niên top 7, thanh niên top 5 khả năng cao là người Mỹ hoặc chuyển sang Mỹ lâu lắm rồi, teammate của nó 100% là người Mỹ, kể cả nhiều năm trước, mà đỏ cf VN có mấy người thôi, teamup để train liên tục mà thanh niên ấy không dính tí VN nào luôn, profile codechef hắn để location Mỹ. Thanh niên top 7 tính ra đang rank top 1 codeforces location VN.
codeforces thì hơn leetcode nhiều ko nhỉ, em thấy nhiều nơi tuyển ưu tiên rank cao codeforces, topcoder
cf là chỗ để thi đấu, lc là chỗ luyện phỏng vấn, học dsa. Problem bên codeforces thuộc thể loại ad-hoc, nhiều toán, tổ hợp, chỉnh hợp, xác suất, số học,... Bên lc thì không cần nhiều, thể loại căn bản, cổ điển, nhưng lại cần khá đa dạng thuật toán và ctdl. Bên cf thì không cần (mức căn bản chứ mức nâng cao thì không đếm nổi thuật), như chúng nó hay troll lên tím cf chỉ cần học binary search là đủ. Bên cf là chỗ thi đấu nên chỉ cần xanh là được, bên cf luyện phỏng vấn nên cần tối ưu đpt. So sánh độ khó câu hỏi thì hard bên leetcode như chúng nó review thì dao động từ 1k5-1k9 rate bên cf (tầm trên basic 1 tí, chưa nâng cao lắm). Vấn đề bên cf thì đa dạng gấp nhiều lần, vì ra đề mỗi lần mỗi team khác nhau ra đề (trừ div3 div 4 và edu round có đội ngũ ra đề riêng), vì yêu cầu đề phải mới mẻ, tư tưởng khác lạ nên cf chi tiền cho team nào bỏ chất xám sáng tạo vấn đề đủ để tổ chức contest (div 2 300$, div 1 600$, div1+2 900$). Nói tóm lại lc là chỗ để mấy khứa khá giỏi chưa lên mức pro bên cf sang speedforces hành gà, có khứa top 1 lc rank 34 (khá pro) bên cf. Còn lại chưa thấy ai rank <100. Như khứa top 5 contest kia bên cf rank 319.
 

...Batman...

Senior Member
đấy là thanh niên top 7, thanh niên top 5 khả năng cao là người Mỹ hoặc chuyển sang Mỹ lâu lắm rồi, teammate của nó 100% là người Mỹ, kể cả nhiều năm trước, mà đỏ cf VN có mấy người thôi, teamup để train liên tục mà thanh niên ấy không dính tí VN nào luôn, profile codechef hắn để location Mỹ. Thanh niên top 7 tính ra đang rank top 1 codeforces location VN.

cf là chỗ để thi đấu, lc là chỗ luyện phỏng vấn, học dsa. Problem bên codeforces thuộc thể loại ad-hoc, nhiều toán, tổ hợp, chỉnh hợp, xác suất, số học,... Bên lc thì không cần nhiều, thể loại căn bản, cổ điển, nhưng lại cần khá đa dạng thuật toán và ctdl. Bên cf thì không cần (mức căn bản chứ mức nâng cao thì không đếm nổi thuật), như chúng nó hay troll lên tím cf chỉ cần học binary search là đủ. Bên cf là chỗ thi đấu nên chỉ cần xanh là được, bên cf luyện phỏng vấn nên cần tối ưu đpt. So sánh độ khó câu hỏi thì hard bên leetcode như chúng nó review thì dao động từ 1k5-1k9 rate bên cf (tầm trên basic 1 tí, chưa nâng cao lắm). Vấn đề bên cf thì đa dạng gấp nhiều lần, vì ra đề mỗi lần mỗi team khác nhau ra đề (trừ div3 div 4 và edu round có đội ngũ ra đề riêng), vì yêu cầu đề phải mới mẻ, tư tưởng khác lạ nên cf chi tiền cho team nào bỏ chất xám sáng tạo vấn đề đủ để tổ chức contest (div 2 300$, div 1 600$, div1+2 900$). Nói tóm lại lc là chỗ để mấy khứa khá giỏi chưa lên mức pro bên cf sang speedforces hành gà, có khứa top 1 lc rank 34 (khá pro) bên cf. Còn lại chưa thấy ai rank <100. Như khứa top 5 contest kia bên cf rank 319.
Em đang xem một số vị trí thì với CV của em chưa đủ mạnh, nên cần rank tốt tốt chút trên Codeforces, Topcoder.
Chắc em nên tìm cách khác :shame: cạnh tranh thế thì lấy đâu ra rank cao được đây
 

dynamic programming

Senior Member
đấy là thanh niên top 7, thanh niên top 5 khả năng cao là người Mỹ hoặc chuyển sang Mỹ lâu lắm rồi, teammate của nó 100% là người Mỹ, kể cả nhiều năm trước, mà đỏ cf VN có mấy người thôi, teamup để train liên tục mà thanh niên ấy không dính tí VN nào luôn, profile codechef hắn để location Mỹ. Thanh niên top 7 tính ra đang rank top 1 codeforces location VN.
Thanh niên VN top 7 đấy, tại lúc em post thì đang diễn ra contest nên BXH về sau thay đổi
 

tdat00

Đã tốn tiền
Hôm thứ 6 lười làm bài Hard nên mất streak 70 ngày nên lười hẳn các thím ạ, cuối tuần toàn đi chơi chả muốn làm task giờ mới vào guồng trở lại :angry:

Bài sáng nay thì tôi dùng queue cho đơn giản

https://leetcode.com/submissions/detail/743808725/
C#:
public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        List<int> ret = new ();

        if (root == null)
            return ret;
        
        Queue<TreeNode> q = new();
        TreeNode current = null;
        q.Enqueue(root);
        
        while (q.Count > 0)
        {
            int count = q.Count;
            for (var i = 0; i < count; i++)
            {
                current = q.Dequeue();
                
                if (current.left != null) q.Enqueue(current.left);
                if (current.right != null) q.Enqueue(current.right);
            }
            
            ret.Add(current.val);
        }
        
        return ret;
    }
}
 

Blue Amethyst

Senior Member
Hôm thứ 6 lười làm bài Hard nên mất streak 70 ngày nên lười hẳn các thím ạ, cuối tuần toàn đi chơi chả muốn làm task giờ mới vào guồng trở lại :angry:

Bài sáng nay thì tôi dùng queue cho đơn giản

https://leetcode.com/submissions/detail/743808725/
C#:
public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        List<int> ret = new ();

        if (root == null)
            return ret;
       
        Queue<TreeNode> q = new();
        TreeNode current = null;
        q.Enqueue(root);
       
        while (q.Count > 0)
        {
            int count = q.Count;
            for (var i = 0; i < count; i++)
            {
                current = q.Dequeue();
               
                if (current.left != null) q.Enqueue(current.left);
                if (current.right != null) q.Enqueue(current.right);
            }
           
            ret.Add(current.val);
        }
       
        return ret;
    }
}
tưởng thím bỏ, đi ngắm gái luôn rồi chứ :beauty:

Btw, bài hôm nay em cũng dùng đệ quy :big_smile:

Java:
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null)
            return res;
        traverse(root, res, 1);
        return res;
    }
    
    private void traverse(TreeNode root, List<Integer> res, int level)
    {
        if (root == null)
            return;
        if (res.size() < level)
            res.add(root.val);
        traverse(root.right, res, level + 1);
        traverse(root.left, res, level + 1);
    }
}
 
Top