• Shopee đêm nay có mã cho ngày 5/5

thảo luận [Học Tập] Topic thuật toán

Thạch Sanh_4.0 said:
Mình hiện tại đang rất tuyệt vọng với môn Thuật toán này, không hiểu tại sao mình đã học nó gần cả năm nay mà thấy vẫn không có gì tiến bộ, gặp một tình uống thực sự mình rất bí ý tưởng, mà khi có ý tưởng rồi thì lại rất khó biến ý tưởng thành code. Mình khó khăn nhất là với các bài toán về Quy hoạch động, thật sự là mình chả làm được bài nào nếu không xem hướng dẫn trên Hackerrank. Hôm qua tính làm vài bài để luyện trình mà làm cả buổi sáng cũng không nổi 1 bài, mình rất buồn vì bản thân,
Mình cần lời khuyên của mọi người, chỉ cho mình con đường đi với, mình vẫn cố gắng luyện tập nó hằng ngày mà sao vẫn không khá hơn ???
Click to expand...
Về phần động lực, mình thấy bạn cần nghĩ đến là bạn học thuật toán làm gì ?
Bạn có thể tham khảo post này của mình: https://voz.vn/t/hoc-tap-topic-thuat-toan.182659/post-11115169
Maybe chỉ là ý kiến cá nhân của mình thôi, nhưng từ đó bạn có thêm góc nhìn và hiểu được tại sao bạn muốn học thuật toán. Nếu không có mục đích rõ ràng thì việc học sẽ mông lung và rất nhanh nản.

Tuy nhiên điều mình thấy quan ngại là việc bạn không thể biến ý tưởng của mình thành code ? Cái này khiến mình cảm giác phần coding basic của bạn chưa đủ vững. Có thể bạn cần cải thiện thêm về các kỹ năng lập trình cơ bản trước khi nhảy vào mảng thuật toán này ? Vì khả năng chuyển ý tưởng thành code là kỹ năng bắt buộc để luyện LC rồi.

Một trong những cách mình suggest là:
1. Đọc solution của những bài mình không giải được bằng một ngôn ngữ khác trong phần discuss (vd hay làm python thì chọn C++ hoặc java để đọc).
2. Cố gắng hiểu ý tưởng đằng sau.
3. Chạy thử vài whiteboard examples.
4. Sau đó implement lại bằng ngôn ngữ mình thường dùng mà không check với solution mẫu.

Nếu bạn struggle với DP thì cứ filter các bài DP mà làm, chọn bài easy trước rồi tăng dần độ khó.
 
thuyduong2007 said:
cách này có 1 vấn đề là nếu string quá lớn thì cái sum có thể bị tràn nhé.
Bài này có nhiều biến thể, cách làm tốt nhất là dùng xor. Vừa không bị tràn lại chạy nhanh hơn do phép xor tốn ít CPU cycle hơn.

Giải thích: Do phép xor có tính chất sau: x^x=0. Nên khi xor toàn bộ các chữ cái của s và t cho nhau thì những chữ đi theo cặp giống sẽ tạo ra kết quả 0 và cuối cùng chỉ còn lại t.

C++: 
class Solution {
public:
    char findTheDifference(string s, string t) {
        char l = 0;
        for (auto& x : s) l ^= x;
        for (auto& x : t) l ^= x;
        return l;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Find the Difference.
Click to expand...

Bài này giới hạn length 1000 nên không tràn nổi đâu.
Bài này khá giống bài Cho 1 mảng và tìm phần tử chỉ xuất hiện duy nhất 1 lần, số lần xuất hiện của các phần tử khác đều là số chẵn.
Còn 1 bài nâng cao hơn khá nhiều là Cho 1 mảng và tìm phần tử chỉ xuất hiện duy nhất 1 lần, số lần xuất hiện của các phần tử khác là 3.
 
Last edited:
_Gia_Cat_Luong_ said:
Về phần động lực, mình thấy bạn cần nghĩ đến là bạn học thuật toán làm gì ?
Bạn có thể tham khảo post này của mình: https://voz.vn/t/hoc-tap-topic-thuat-toan.182659/post-11115169
Maybe chỉ là ý kiến cá nhân của mình thôi, nhưng từ đó bạn có thêm góc nhìn và hiểu được tại sao bạn muốn học thuật toán. Nếu không có mục đích rõ ràng thì việc học sẽ mông lung và rất nhanh nản.

Tuy nhiên điều mình thấy quan ngại là việc bạn không thể biến ý tưởng của mình thành code ? Cái này khiến mình cảm giác phần coding basic của bạn chưa đủ vững. Có thể bạn cần cải thiện thêm về các kỹ năng lập trình cơ bản trước khi nhảy vào mảng thuật toán này ? Vì khả năng chuyển ý tưởng thành code là kỹ năng bắt buộc để luyện LC rồi.

Một trong những cách mình suggest là:
1. Đọc solution của những bài mình không giải được bằng một ngôn ngữ khác trong phần discuss (vd hay làm python thì chọn C++ hoặc java để đọc).
2. Cố gắng hiểu ý tưởng đằng sau.
3. Chạy thử vài whiteboard examples.
4. Sau đó implement lại bằng ngôn ngữ mình thường dùng mà không check với solution mẫu.

Nếu bạn struggle với DP thì cứ filter các bài DP mà làm, chọn bài easy trước rồi tăng dần độ khó.
Click to expand...
cảm ơn bạn rất nhiều
 
1627885672971.png

Em mới làm đc bài này. Hehe
 

Attachments

  • 1627885665581.png
    1627885665581.png
    410.1 KB · Views: 51
haylachoi said:
Bài này giới hạn length 1000 nên không tràn nổi đâu.
Bài này khá giống bài Cho 1 mảng và tìm phần tử chỉ xuất hiện duy nhất 1 lần, số lần xuất hiện của các phần tử khác đều là số chẵn.
Còn 1 bài nâng cao hơn khá nhiều là Cho 1 mảng và tìm phần tử chỉ xuất hiện duy nhất 1 lần, số lần xuất hiện của các phần tử khác là 3.
Click to expand...
Uhm, bài này thì k tràn được do testcase đã bị giới hạn. Tuy nhiên giải pháp dùng sum thì vẫn tồn tại vấn đề tràn số học. Trong khi dùng xor vừa không lo bị tràn, lại chạy nhanh hơn. Thì rõ ràng dùng xor là giải pháp tốt hơn mà. Như bạn đã nói thì có rất nhiều biến thể của bài này và hầu như đều dùng xor để giải quyết.
 
thuyduong2007 said:
Uhm, bài này thì k tràn được do testcase đã bị giới hạn. Tuy nhiên giải pháp dùng sum thì vẫn tồn tại vấn đề tràn số học. Trong khi dùng xor vừa không lo bị tràn, lại chạy nhanh hơn. Thì rõ ràng dùng xor là giải pháp tốt hơn mà. Như bạn đã nói thì có rất nhiều biến thể của bài này và hầu như đều dùng xor để giải quyết.
Click to expand...
Đương nhiên là bitwise sẽ nhanh hơn nhiều. Cơ mà dùng sum vẫn ok mà. Với mảng max length int32 thì dùng index để duyệt thì có thể vừa cộng ở 1 mảng và trừ ở 1 mảng, lưu sum ở int64 thì sẽ ko bị tràn đâu.
 
Xài Sum ổn nhưng mà nó không phải giải pháp tốt nhất.
Cách bạn xử lý để không bị tràn thì nó chỉ có thể áp dụng trong bài này và một số bài đơn giản thôi. Nó không phải giải pháp tổng quát để xử lý những vấn đề tương tự như thế này. Chưa kể cách xử lý này dễ dẫn đến sai sót nữa. Khi bạn cộng trừ số int32 sau đó lưu lại vào int64, nếu không cast cẩn thận thì sẽ rất dễ bị sai.
 
@_Gia_Cat_Luong_
Mình bổ sung thêm cách viết bằng C++ với giải thuật đệ qui cho bài
https://leetcode.com/problems/decode-string
C++: 
class Solution {
public:
    string decodeString(string s) {
        string result;
        decodeStringRecursive(s,result);
        return result;
    }
    
     int decodeStringRecursive(const string &s, string &result, int idx = 0){
         int numDup = 0;
         while (idx < s.size()) {
             if (s[idx] == '['){
                string inSquare;
                idx = decodeStringRecursive(s, inSquare , idx+1);
                result += mulStr(inSquare, numDup);
                numDup = 0;
             } else if (s[idx] >= '0' && s[idx] <= '9'){
                numDup = numDup*10 + (s[idx] - '0');
            } else if (s[idx] == ']'){
                return idx;
            } else {
                result.push_back(s[idx]);
            }
            idx++;
        }
        return idx;
     }
    
    string mulStr(string s, int n){
        string result;
        result.reserve(n*s.size());
        while (n > 0){
            result += s;
            n--;
        }
        return result;
    }
    
};


Runtime: 0 ms, faster than 100.00% of C++ online submissions for Decode String.
Memory Usage: 6.4 MB, less than 89.59% of C++ online submissions for Decode String.
 
Cho các thím làm thử bài này, đề thi hsg quốc gia ngày xưa nè:

Tìm chuỗi con liên tục tăng dài nhất, với điều kiện, các số trong chuỗi phải là các số thuộc dãy sau:

u1 = 1, uk = uk-1 + k

ví dụ dãy: 8 8 2000 1 6 6 15 399

Thì đáp án là 3, vì dãy 6 6 15 là chuỗi tăng dài nhất, thỏa mãn là các số thuộc dãy trên: (u1 = 1, u2 = 3, u3 = 6, u 4 = 10, u5 = 15)
// note: u(k) tức là phần tử thứ k trong dãy.

(giá mà ngày xưa mình thi tin thay toán thì ngon cmnr...)
 
Last edited:
thuyduong2007 said:
@_Gia_Cat_Luong_
Mình bổ sung thêm cách viết bằng C++ với giải thuật đệ qui cho bài
https://leetcode.com/problems/decode-string
C++: 
class Solution {
public:
    string decodeString(string s) {
        string result;
        decodeStringRecursive(s,result);
        return result;
    }
   
     int decodeStringRecursive(const string &s, string &result, int idx = 0){
         int numDup = 0;
         while (idx < s.size()) {
             if (s[idx] == '['){
                string inSquare;
                idx = decodeStringRecursive(s, inSquare , idx+1);
                result += mulStr(inSquare, numDup);
                numDup = 0;
             } else if (s[idx] >= '0' && s[idx] <= '9'){
                numDup = numDup*10 + (s[idx] - '0');
            } else if (s[idx] == ']'){
                return idx;
            } else {
                result.push_back(s[idx]);
            }
            idx++;
        }
        return idx;
     }
   
    string mulStr(string s, int n){
        string result;
        result.reserve(n*s.size());
        while (n > 0){
            result += s;
            n--;
        }
        return result;
    }
   
};


Runtime: 0 ms, faster than 100.00% of C++ online submissions for Decode String.
Memory Usage: 6.4 MB, less than 89.59% of C++ online submissions for Decode String.
Click to expand...
Yêu ghê, thím giống mình thường thích giải mấy bài parser bằng đệ quy. Bài trên là bài hiếm hoi mà mình làm bằng stack :D.
 
_Gia_Cat_Luong_ said:
Yêu ghê, thím giống mình thường thích giải mấy bài parser bằng đệ quy. Bài trên là bài hiếm hoi mà mình làm bằng stack :D.
Click to expand...
Theo như quan sát của mình thì hầu như bài nào giải được bằng stack thì đều giải được bằng đệ quy và ngược lại. Do chương trình quản lý function, local variable,... bằng stack. Cái này không biết có nghiên cứu nào so sánh 2 giải thuật này chưa nhỉ?
 
thuyduong2007 said:
Theo như quan sát của mình thì hầu như bài nào giải được bằng stack thì đều giải được bằng đệ quy và ngược lại. Do chương trình quản lý function, local variable,... bằng stack. Cái này không biết có nghiên cứu nào so sánh 2 giải thuật này chưa nhỉ?
Click to expand...
Về lý thuyết thì tất cả đệ quy đều có thể khử được bằng stack. Còn điều ngược lại mình không chắc lắm.
 
Fire Of Heart said:
Cho các thím làm thử bài này, đề thi hsg quốc gia ngày xưa nè:

Tìm chuỗi con liên tục tăng dài nhất, với điều kiện, các số trong chuỗi phải là các số thuộc dãy sau:

u1 = 1, uk = uk-1 + k

ví dụ dãy: 8 8 2000 1 6 6 15 399

Thì đáp án là 3, vì dãy 6 6 15 là chuỗi tăng dài nhất, thỏa mãn là các số thuộc dãy trên: (u1 = 1, u2 = 3, u3 = 6, u 4 = 10, u5 = 15)
// note: u(k) tức là phần tử thứ k trong dãy.

(giá mà ngày xưa mình thi tin thay toán thì ngon cmnr...)
Click to expand...
8-)8-) trong nóng ngoài lạnh thôi, có những thứ sacrifice như bọn vđv tập olympic kể ra lại làm thế hệ đi sau nhùn
Bài kia validate số thuộc dãy trong O(1), lis trong n logn :rolleyes: mà đề mỗi năm một khoai mà, làm thử đề voi xem có ngắm đc cái giải nhì k :misdoubt::misdoubt:
 
Tiếp tục chuyên mục mỗi ngày một leetcode. Các bài mình làm ngày hôm nay:

#396. (Medium) https://leetcode.com/problems/rotate-function
#397. (Medium) https://leetcode.com/problems/integer-replacement
#398. (Medium) https://leetcode.com/problems/random-pick-index

Mình sẽ share về bài Integer Replacement:
#397. (Medium) https://leetcode.com/problems/integer-replacement

Phân tích bài toán:
  • 1 <= n <= 2^31 - 1: Với constraint này thì chỉ có O(logn) và O(1) là work
  • Nhận thấy nếu n là số chẵn thì đáp án sẽ là 1 + integerReplacement(n / 2)
  • Nếu n là số lẻ thì sẽ là 1 + min(integerReplacement(n + 1), integerReplacement(n - 1)).
  • Vì n là số lẻ => n + 1 và n - 1 sẽ là số chẵn => Tiếp theo sẽ được chia 2.
  • Nếu theo flow bình thường thì độ phức sẽ là O(logn). Vì số n sau mỗi lần đệ quy sẽ giảm đi một nửa. => Works

Solution:
Python: 
class Solution:
    def integerReplacement(self, n: int) -> int:
        if n == 1:
            return 0
     
        if n % 2 == 0:
            return 1 + self.integerReplacement(n // 2)

        return 1 + min(self.integerReplacement(n + 1), self.integerReplacement(n - 1))


Optimization:
  • Solution trên chưa tối ưu nếu ta để ý kĩ trong trường hợp n lẻ, ta cần đệ quy cho 2 trường hợp
  • Các bạn cần để ý là thông thường việc đệ quy nó sẽ tăng theo cấp số nhân. Đệ quy cho 2 trường hợp thì sẽ dễ dẫn đến độ phức tạp 2^n
  • Thử tưởng tượng nếu n lẻ, sau đó (n + 1) / 2 và (n - 1) / 2 cũng là số lẻ. Lúc đó ta sẽ phải tính cho 4 trường hợp.
  • Suy rộng ra nếu cứ mỗi bước đệ quy ta phải tính 2 trường hợp thì sau logn bước, ta cần phải tính cho 2^logn = O(n) cho trường hợp xấu nhất
  • Vậy làm sao để tránh vấn đề này ? Ý tưởng là sử dụng quy hoạch động để tránh giải lại các bài toán con gối nhau.
  • Trong bài trên thì memoization là giải pháp đơn giản mà k làm thay đổi cấu trúc Solution. Với python thì thêm cái decoration @cache vào là đc. What an easy method.
Python: 
class Solution:
    @cache
    def integerReplacement(self, n: int) -> int:
        if n == 1:
            return 0
     
        if n % 2 == 0:
            return 1 + self.integerReplacement(n // 2)

        return 1 + min(self.integerReplacement(n + 1), self.integerReplacement(n - 1))
 
Last edited:
Fire Of Heart said:
Cho các thím làm thử bài này, đề thi hsg quốc gia ngày xưa nè:

Tìm chuỗi con liên tục tăng dài nhất, với điều kiện, các số trong chuỗi phải là các số thuộc dãy sau:

u1 = 1, uk = uk-1 + k

ví dụ dãy: 8 8 2000 1 6 6 15 399

Thì đáp án là 3, vì dãy 6 6 15 là chuỗi tăng dài nhất, thỏa mãn là các số thuộc dãy trên: (u1 = 1, u2 = 3, u3 = 6, u 4 = 10, u5 = 15)
// note: u(k) tức là phần tử thứ k trong dãy.

(giá mà ngày xưa mình thi tin thay toán thì ngon cmnr...)
Click to expand...
Bài này thì mình thấy tương tự như bài LIS thôi nhỉ. Chỉ thay đổi cái điều kiện increase bằng phải thuộc dãy số trong bài. Vì thấy công thức của dãy số cũng k quá phức tạp (gần giống như cấp số cộng) nên thiết nghĩ có thể tìm ra công thức để check điều này.
 
clonemasteruwu said:
8-)8-) trong nóng ngoài lạnh thôi, có những thứ sacrifice như bọn vđv tập olympic kể ra lại làm thế hệ đi sau nhùn
Bài kia validate số thuộc dãy trong O(1), lis trong n logn :rolleyes: mà đề mỗi năm một khoai mà, làm thử đề voi xem có ngắm đc cái giải nhì k :misdoubt::misdoubt:
Click to expand...

giải nhì hơi căng đấy :LOL:)
muốn nhì thì phải ôn đủ kiểu anh ơi, tầm giải nhì là coi như tạm đủ tầm thi IMO cmnr :D
 
_Gia_Cat_Luong_ said:
Bài này thì mình thấy tương tự như bài LIS thôi nhỉ. Chỉ thay đổi cái điều kiện increase bằng phải thuộc dãy số trong bài. Vì thấy công thức của dãy số cũng k quá phức tạp (gần giống như cấp số cộng) nên thiết nghĩ có thể tìm ra công thức để check điều này.
Click to expand...

công thức dãy tăng này chứng minh quy nạp ra ngay :D
 
Chết rồi mấy bác, em gặp bài toán khó quá, ko giải được.
Bài toán có liên quan tới kiểu lồng vào nhau tới vô hạn luôn(có thể có). Ko biết giải sao
 
KimSoHyunGoddness said:
Chết rồi mấy bác, em gặp bài toán khó quá, ko giải được.
Bài toán có liên quan tới kiểu lồng vào nhau tới vô hạn luôn(có thể có). Ko biết giải sao
Click to expand...
Share đề lên đây thử bạn ơi ?

Hoặc bạn có thể áp dụng thuật toán này, mình thấy nó hữu dụng với tất cả các bài LC:
1627906545117.png
 
_Gia_Cat_Luong_ said:
Share đề lên đây thử bạn ơi ?

Hoặc bạn có thể áp dụng thuật toán này, mình thấy nó hữu dụng với tất cả các bài LC:
View attachment 689181
Click to expand...
Đây là bài cá nhân bác ạ. Đề là như này nè.
1627906883379.png

Em có danh sách cấp độ như thế này. GIờ yêu cầu là chuyển nó về dạng bảng như thế này
1627906941201.png

Hiện tại là được giới hạn ở level 10. Nhưng trong tương lai là có thể sẽ hơn nữa.
 

Similar threads

Miền Tây
Cận cảnh đường ống ngầm khổng lồ, thu gom toàn bộ nước thải làm sống lại sông Tô Lịch
7 8 9
Replies
170
Views
16K
HanamichiFFX
HanamichiFFX
L
thảo luận Một vài chia sẻ có thể hữu ích cho các bạn trẻ trong sự nghiệp ngành IT
2 3 4
Replies
70
Views
5K
i need her k19
i need her k19
Uoc_mo_Tay_Tang
Bắt đầu thảm nhựa tuyến tránh thành phố Long Xuyên
Replies
0
Views
124
Uoc_mo_Tay_Tang
Uoc_mo_Tay_Tang
manoao
Tiêu thụ điện miền Bắc tăng hơn 13 triệu kWh/ngày, thủy điện giữ nước chờ nắng nóng
Replies
4
Views
295
seotopgoole
S
Masterchiefs
Thu nhập của người dân Hà Nội, TP.HCM tăng ra sao trong hơn 10 năm qua
2
Replies
21
Views
980
LamNguyenV2
LamNguyenV2

Share this page

Back
Top