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

_Gia_Cat_Luong_

_Gia_Cat_Luong_

Senior Member
Tự dưng dạo này lại có hứng thú lướt voz làm LC. Nay không có nhiều tgian như trước nên mỗi ngày làm một bài daily của LC thôi. Ae cùng tham gia vào chém gió hằng ngày.

Leetcode Daily là gì ?
Đơn giản là mỗi ngày trên LC sẽ random ra một bài đặt lên đầu trang, cả thế giới đều thấy, đc xem như một challenge nho nhỏ của ngày hôm đấy. Topic này sẽ thảo luận về cách giải của bài đấy. Ví dụ hôm nay (20/06/2022):

Screen Shot 2022-06-20 at 09.34.33.png



Luyện Leetcode như thế nào

thảo luận - Leetcode mỗi ngày (https://voz.vn/t/leetcode-moi-ngay.568742/post-18474170)

Update:
Vì thớt này bàn về thuật toán nên sẽ show code khá nhiều khiến việc lội trang của ae bất tiện. Nên anh em chú ý phần nào có code thì cần để vào SPOILER.

p/s: Trước mình toàn đăng bài trong topic thuật toán bên kia nhưng h nó nhiều trang quá rồi, lội mệt. Với bên đó nhiều chủ đề quá đăng cái này vào sợ loãng.
 
Last edited:
_Gia_Cat_Luong_ said:
Tự dưng dạo này lại có hứng thú lưới voz làm LC. Nay không có nhiều tgian như trước nên mỗi ngày làm một bài daily của LC thôi. Ae cùng tham gia vào chém gió hằng ngày.

Leetcode Daily là gì ?
Đơn giản là mỗi ngày trên LC sẽ random ra một bài đặt lên đầu trang, cả thế giới đều thấy, đc xem như một challenge nho nhỏ của ngày hôm đấy. Topic này sẽ thảo luận về cách giải của bài đấy. Ví dụ hôm nay (20/06/2022):

View attachment 1220198

Bài hôm nay ?
https://leetcode.com/problems/short-encoding-of-words/
View attachment 1220208
View attachment 1220209

Phân tích chút chút:
  • Constraint này chắc là O(n^2)
  • Bài này có vẻ là bài search string thôi, nếu không có vấn đề gì đặc biệt thì sẽ khá đễ vì search string bth = O(n), lặp qua hết thì O(n^2) vừa đủ pass.
  • Nhưng nó có nhiều dislike nên có khi có nhiều testcase khốn nạn, cần verify kĩ trước khi submit
Thế thôi, mình chưa làm đc nên chưa có solution để post, anh em vào thảo luận nào.

p/s: Trước mình toàn đăng bài trong topic thuật toán bên kia nhưng h nó nhiều trang quá rồi, lội mệt. Với bên đó nhiều chủ đề quá đăng cái nào vào sợ loãng.
Click to expand...
thớt tiềm năng,đặt mặt tiền
 
Last edited:
Với 1 dev trình bình thường, chưa luyện thuật toán bao giờ nên đi thẳng vào leetcode giải bài rồi học dần hay là kiếm sách học trước nhỉ các my fen?
 
bài dạng prefix suffix kiểu này có thể xoay bỉm để sử dụng trie, độ phức tạp chắc bằng tổng số ký tự thôi
 
ngx3009 said:
Thuật toán hơi đuối, thì vào study-plan học data structure rồi algorithm được k bác

Gửi từ Xiaomi 220333QAG bằng vozFApp
Click to expand...
Được fen, link trên của mình chỉ focus vào DS thôi, không có Algorithm gì nhiều. Cứ chăm chỉ thôi fen, mỗi ngày 1 bài 1 năm 365 bài = auto giỏi.
 
Solution đơn giản nhất có thể nghĩ ra :)
C#: 
public class Solution {
    public int MinimumLengthEncoding(string[] words) {
        Array.Sort(words, (x, y) => x.Length.CompareTo(y.Length));
        var dup = new List<string>();
        int removed = 0, total = 0;
        for(int i=0; i < words.Length - 1; i++){
            total += (words[i].Length + 1);

            for(int j = i+1; j< words.Length; j++){
                if(words[j].EndsWith(words[i])){
                    removed += (words[i].Length + 1);
                    break;
                }
            }
        }
        return total - removed + words[words.Length -1].Length + 1;
    }
}

1655697443843.png


Mới đầu quên break sau khi loại trừ substring nên fail lần đầu
 
_Gia_Cat_Luong_ said:
Bước tiếp theo chính là chia sẻ cho mọi người đó fen, fen done bài hnay rồi à. Share solution lên ae cùng thẩm nào :D
Click to expand...

Lời khuyên cho các thím là cứ làm nhiều vào, sẽ ngộ ra nhiều thuật toán hay ho để sử dụng được cho nhiều tình huống.

Còn bài sáng nay thì dùng HashSet là pass thôi, không cần dùng đến trie

  • Sort array dảm dần theo độ dài
  • Với mỗi word trong words
    • Nếu đã tồn tại trong HashSet thì bỏ qua.
    • Nếu chưa thì thêm word này vào danh sách result, và thêm tất cả substring của word này vào hashset.
  • Join danh sách result lại là ra kết quả.

Code: 
public class Solution {
    public int MinimumLengthEncoding(string[] words) {
        Array.Sort(words, (a,b) => b.Length - a.Length);
        HashSet<string> found = new ();
       
        List<string> ret = new ();
        foreach (var word in words)
        {
            if (found.Contains(word))
                continue;
           
            ret.Add(word);
            for (var i = 0; i < word.Length; i++)
                found.Add(word.Substring(i));
        }
       
        var r = string.Join('#', ret);
        Console.WriteLine(r);
        return r.Length + 1;
    }
}
[/CODE}

[/SPOILER]
 
_Gia_Cat_Luong_ said:
Tự dưng dạo này lại có hứng thú lướt voz làm LC. Nay không có nhiều tgian như trước nên mỗi ngày làm một bài daily của LC thôi. Ae cùng tham gia vào chém gió hằng ngày.

Leetcode Daily là gì ?
Đơn giản là mỗi ngày trên LC sẽ random ra một bài đặt lên đầu trang, cả thế giới đều thấy, đc xem như một challenge nho nhỏ của ngày hôm đấy. Topic này sẽ thảo luận về cách giải của bài đấy. Ví dụ hôm nay (20/06/2022):

View attachment 1220198

Bài hôm nay ?
https://leetcode.com/problems/short-encoding-of-words/

View attachment 1220208
View attachment 1220209

Phân tích chút chút:
  • Constraint này chắc là O(n^2)
  • Bài này có vẻ là bài search string thôi, nếu không có vấn đề gì đặc biệt thì sẽ khá đễ vì search string bth = O(n), lặp qua hết thì O(n^2) vừa đủ pass.
  • Nhưng nó có nhiều dislike nên có khi có nhiều testcase khốn nạn, cần verify kĩ trước khi submit
Thế thôi, mình chưa làm đc nên chưa có solution để post, anh em vào thảo luận nào.

p/s: Trước mình toàn đăng bài trong topic thuật toán bên kia nhưng h nó nhiều trang quá rồi, lội mệt. Với bên đó nhiều chủ đề quá đăng cái này vào sợ loãng.
Click to expand...
chia sẻ mình kinh nghiệm luyện leetcode được k thím :adore:
 
Bài này hôm nay thì thông thường sẽ dùng trie để search theo suffix. Nhưng cách này code dài với mấy nay toàn bài về trie nên t cố làm theo cách khác.
Ý tưởng là lật ngược từng word rồi sort, sau đó count, word nào có prefix trùng với prefix của word phía sau thì ignore.
C++: 
class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        for (auto &word : words) reverse(word.begin(), word.end());
        sort(words.begin(), words.end());
        
        int ret = 0;
        for (int i = 0; i < words.size(); ++i){
            if (i == words.size() - 1
                || words[i].size() > words[i+1].size()
                || words[i+1].substr(0, words[i].size()) != words[i]) {
                ret += words[i].size() + 1;
            }
        }
        return ret;
    }
};

TC là O(NlogN). :big_smile:
 
thuyduong2007 said:
Bài này hôm nay thì thông thường sẽ dùng trie để search theo suffix. Nhưng cách này code dài với mấy nay toàn bài về trie nên t cố làm theo cách khác.
Ý tưởng là lật ngược từng word rồi sort, sau đó count, word nào có prefix trùng với prefix của word phía sau thì ignore.
C++: 
class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        for (auto &word : words) reverse(word.begin(), word.end());
        sort(words.begin(), words.end());
      
        int ret = 0;
        for (int i = 0; i < words.size(); ++i){
            if (i == words.size() - 1
                || words[i].size() > words[i+1].size()
                || words[i+1].substr(0, words[i].size()) != words[i]) {
                ret += words[i].size() + 1;
            }
        }
        return ret;
    }
};

TC là O(NlogN). :big_smile:
Click to expand...
Cái này chắc gần optimal rồi, mình góp ý chút xíu:
  • words.size() > words[i+1].size(): Đoạn này không cần vì đã sort rồi
  • i == words.size() - 1: đoạn này hơi thừa, vì cái str cuối cùng chắc chắn sẽ đc cộng vào nên mình khởi tạo luôn từ đầu ret = words.back().size() + 1 và chạy đến words.size() - 1 thôi.


Chỉ là mấy cái chút chút, về cơ bản vẫn là O(nlogn). Best as always bro :love:
 
_Gia_Cat_Luong_ said:
Cái này chắc gần optimal rồi, mình góp ý chút xíu:
  • words.size() > words[i+1].size(): Đoạn này không cần vì đã sort rồi
  • i == words.size() - 1: đoạn này hơi thừa, vì cái str cuối cùng chắc chắn sẽ đc cộng vào nên mình khởi tạo luôn từ đầu ret = words.back().size() + 1 và chạy đến words.size() - 1 thôi.


Chỉ là mấy cái chút chút, về cơ bản vẫn là O(nlogn). Best as always bro :love:
Click to expand...
Đồng ý với fen cái số 2, còn cái số 1 là bắt buộc mà. Nó mới sort theo lexicographical thôi mà, :big_smile:
giả sử 2 words là b, abcd thì sau khi sort sẽ là abcd, b. Nên bắt buộc phải check cái size trước. :big_smile:
 

Similar threads

4 More Years
Nhiều người mất sạch bài đăng trên Facebook
Replies
0
Views
198
4 More Years
4 More Years
4 More Years
Elon Musk có kế hoạch tính phí người dùng X mới để cho phép đăng bài
2 3
Replies
48
Views
3K
bimatcuasoi5
bimatcuasoi5
Lenh Ho Dai Ca
Giám đốc Nhã Nam xin lỗi
2 3 4
Replies
68
Views
8K
clonebymeeeee
clonebymeeeee
buiduchanh1995
thắc mắc Cách thiết kế database cho hệ thống lớn
2
Replies
37
Views
3K
khonganhit19
khonganhit19
meekoo
thắc mắc [Hỏi AI] Cách làm sao để train AI hiểu một task nào đấy?
Replies
9
Views
1K
weed_bông
weed_bông

Share this page

Back
Top