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

ngoctan_95

Senior Member
LC hôm nay (23/06/2022):
#630. (Hard) Link
chưa có thời gian làm nhưng đưa link lên cho các thím bàn luận đã
Bài này khó vãi nồi :( 5 lần submit error, lần 6 thì Time Exceed, lần 8 mới pass =((
Screen Shot 2022-06-23 at 18.19.55.png
Ý tưởng là chỉ chạy kiểm tra từ đầu tới cuối, kiểm tra thời gian và lần đếm theo thứ tự:
A[x, y]
B[z, f, g]
  • Kiểm tra tổng A[x][0] với thời gian, lưu vào số lần đếm
  • Kiểm tra giá trị lớn nhất từ 0 đến số lần đếm, lưu delta chênh lệch giữa các course[x, k]
  • Kiểm tra giá trị course[max, c] và course[index, c], lưu lại chênh lệch thời gian vào thời gian tổng và giá trị course[max, c]
 
Last edited:

_Gia_Cat_Luong_

Senior Member

23/06/2022​

#630. (Hard) https://leetcode.com/problems/course-schedule-iii/

Phân tích bài toán:

  • Trước tiên, dễ thấy bài toán là học (sắp xếp) các khóa học theo một thứ tự nào đó sao cho tối ưu nhất, nghĩa là học được nhiều khóa học nhất
  • Vậy thứ tự nào là tối ưu ? Ta chưa biết nhưng có 2 hướng có thể nghĩ đến ngay:
    • Ưu tiên học những khóa học có cost ngắn trước, vì đơn giản là chọn khóa càng ngắn thì càng ít tốn thời gian ⇒ Học được nhiều khóa hơn
    • Ưu tiên học những khóa có deadline sớm trước, vì deadline sớm không lo học để đến lúc trễ rồi là phải bỏ khóa
  • Cả 2 hướng trên đều có điểm hợp lý, nhưng nếu nghĩ sâu hơn thì ta nên theo cách số 2, vì:
    • Deadline là cố định, nếu quá deadline thì ta không thể học được khóa học nữa
    • Cost thì sắp xếp được, suy cho cùng ta học khóa học ở thời điểm nào cũng sẽ tốn một lượng thời gian như nhau, miễn là trước deadline của nó
  • Ví dụ, ta 2 có khóa học A với chi phí và deadline là (50, 1000) và B là (300, 310)
    • Khóa học A sẽ linh động hơn khóa học B nhiều, ta có thể học A ở bất kì thời điểm nào từ [0-950]. Trong khi B chỉ có thể học được từ [0-10].
    • Vì thế, ta cần ưu tiên học B trước cho xong, còn A có thể sắp xếp học sau, tùy hoàn cảnh sao cho tối ưu
⇒ Vậy trước tiên ta sort mảng input theo thứ tự tăng dần của deadline, để ta có thể ưu tiên học các khóa học có deadline sớm trước

Solution:

  • Sau khi sắp xếp, bài toán trở thành ta sẽ chọn khóa học nào và không chọn khóa học nào sao cho kết quả tối ưu nhất
  • Xét một giải pháp đơn giản, với mỗi khóa học, ta cố gắng đăng ký khóa học này nếu có thể:
    • Nếu thời gian bắt đầu học + chi phí vẫn còn trong deadline cho phép ⇒ Đăng ký học
    • Nếu thời gian bắt đầu học + chi phí vượt quá deadline ⇒ không đăng ký được
  • Trong trường hợp không đăng ký được, ta lại cân nhắc:
    • Bỏ qua khóa học này
    • Hoặc bỏ qua một khóa học khác thay thế nếu như nó có lợi hơn
  • Để bỏ qua được khóa học khác sao cho có lợi hơn, khóa học khác này sẽ cần:
    • Có chi phí cao hơn khóa học hiện tại, nếu không thì không có lợi hơn
    • Phải được học trước khóa học hiện tại, nếu học sau thì đâu có giúp đăng ký được khóa hiện tại
    • ⇒ Mà để có lợi nhất, ta sẽ chọn khóa học có chi phí lớn nhất đã học trước đó, vì khi đó ta sẽ tiết kiệm được thời gian nhiều nhất
  • Vậy làm sao để tìm được khóa học có chi phí cao nhất trong khác khóa học đã qua ? Đơn giản ta sẽ lưu chi phí của chúng vào một max heap và luôn lấy được phần tử lớn nhất với chi phí O(logn)
Mã giả:

Code:
scheduleCourse(courses) {
    courses.sort(<by deadline>) // sắp xếp lại các khóa học theo thứ tự deadline tăng dần

    t = 0 // khởi tạo thời gian tổng các khóa đã học = 0
    h = new <max heap> // khởi tạp max heap để lưu chi phí của các khóa học đã qua

    for each (c in courses) {
        if (t + [c0] <= c[1]) { // đăng kí khóa học c vẫn còn khả thi
            t += c[0] // tăng thời gian tổng lên tương ứng với chi phí của c
            h.push(c[0]) // đưa chi phí của c vào heap
        }
        else {
            if (<chi phí của khóa học cao nhất trong h lớn hơn chi phí của c>) {
                // không học khóa này nữa
                maxC = h.pop() // lấy khóa học này ra khỏi heap
                t -= maxC // giảm lượng thời gian tương ứng khỏi tổng thời gian đã học

                // thay vào đó, học khóa c
                t += c[0] // tăng thời gian tổng lên tương ứng với chi phí của c
                h.push(c[0]) // đưa chi phí của c vào heapp>
            }
        }
    }

    return h.size // các khóa học còn trong heap chính là các khóa ta sẽ học
}

Nhận xét:
  • Solution này có độ phức tạp O(nlogn) cho các thao tác trên heap và sort
  • Đây là một giải pháp greedy
 

23/06/2022​

#630. (Hard) https://leetcode.com/problems/course-schedule-iii/

Phân tích bài toán:

  • Trước tiên, dễ thấy bài toán là học (sắp xếp) các khóa học theo một thứ tự nào đó sao cho tối ưu nhất, nghĩa là học được nhiều khóa học nhất
  • Vậy thứ tự nào là tối ưu ? Ta chưa biết nhưng có 2 hướng có thể nghĩ đến ngay:
    • Ưu tiên học những khóa học có cost ngắn trước, vì đơn giản là chọn khóa càng ngắn thì càng ít tốn thời gian ⇒ Học được nhiều khóa hơn
    • Ưu tiên học những khóa có deadline sớm trước, vì deadline sớm không lo học để đến lúc trễ rồi là phải bỏ khóa
  • Cả 2 hướng trên đều có điểm hợp lý, nhưng nếu nghĩ sâu hơn thì ta nên theo cách số 2, vì:
    • Deadline là cố định, nếu quá deadline thì ta không thể học được khóa học nữa
    • Cost thì sắp xếp được, suy cho cùng ta học khóa học ở thời điểm nào cũng sẽ tốn một lượng thời gian như nhau, miễn là trước deadline của nó
  • Ví dụ, ta 2 có khóa học A với chi phí và deadline là (50, 1000) và B là (300, 310)
    • Khóa học A sẽ linh động hơn khóa học B nhiều, ta có thể học A ở bất kì thời điểm nào từ [0-950]. Trong khi B chỉ có thể học được từ [0-10].
    • Vì thế, ta cần ưu tiên học B trước cho xong, còn A có thể sắp xếp học sau, tùy hoàn cảnh sao cho tối ưu
⇒ Vậy trước tiên ta sort mảng input theo thứ tự tăng dần của deadline, để ta có thể ưu tiên học các khóa học có deadline sớm trước

Solution:

  • Sau khi sắp xếp, bài toán trở thành ta sẽ chọn khóa học nào và không chọn khóa học nào sao cho kết quả tối ưu nhất
  • Xét một giải pháp đơn giản, với mỗi khóa học, ta cố gắng đăng ký khóa học này nếu có thể:
    • Nếu thời gian bắt đầu học + chi phí vẫn còn trong deadline cho phép ⇒ Đăng ký học
    • Nếu thời gian bắt đầu học + chi phí vượt quá deadline ⇒ không đăng ký được
  • Trong trường hợp không đăng ký được, ta lại cân nhắc:
    • Bỏ qua khóa học này
    • Hoặc bỏ qua một khóa học khác thay thế nếu như nó có lợi hơn
  • Để bỏ qua được khóa học khác sao cho có lợi hơn, khóa học khác này sẽ cần:
    • Có chi phí cao hơn khóa học hiện tại, nếu không thì không có lợi hơn
    • Phải được học trước khóa học hiện tại, nếu học sau thì đâu có giúp đăng ký được khóa hiện tại
    • ⇒ Mà để có lợi nhất, ta sẽ chọn khóa học có chi phí lớn nhất đã học trước đó, vì khi đó ta sẽ tiết kiệm được thời gian nhiều nhất
  • Vậy làm sao để tìm được khóa học có chi phí cao nhất trong khác khóa học đã qua ? Đơn giản ta sẽ lưu chi phí của chúng vào một max heap và luôn lấy được phần tử lớn nhất với chi phí O(logn)
Mã giả:

Code:
scheduleCourse(courses) {
    courses.sort(<by deadline>) // sắp xếp lại các khóa học theo thứ tự deadline tăng dần

    t = 0 // khởi tạo thời gian tổng các khóa đã học = 0
    h = new <max heap> // khởi tạp max heap để lưu chi phí của các khóa học đã qua

    for each (c in courses) {
        if (t + [c0] <= c[1]) { // đăng kí khóa học c vẫn còn khả thi
            t += c[0] // tăng thời gian tổng lên tương ứng với chi phí của c
            h.push(c[0]) // đưa chi phí của c vào heap
        }
        else {
            if (<chi phí của khóa học cao nhất trong h lớn hơn chi phí của c>) {
                // không học khóa này nữa
                maxC = h.pop() // lấy khóa học này ra khỏi heap
                t -= maxC // giảm lượng thời gian tương ứng khỏi tổng thời gian đã học

                // thay vào đó, học khóa c
                t += c[0] // tăng thời gian tổng lên tương ứng với chi phí của c
                h.push(c[0]) // đưa chi phí của c vào heapp>
            }
        }
    }

    return h.size // các khóa học còn trong heap chính là các khóa ta sẽ học
}

Nhận xét:
  • Solution này có độ phức tạp O(nlogn) cho các thao tác trên heap và sort
  • Đây là một giải pháp greedy
Thím ơi có cách nào học leetcode nhanh mà dễ không thím
 

ngx3009

Junior Member
Mình đi làm bận quá, tối về còn chơi game nên cũng ít có thời gian :D

Có cách nào nhanh thím bày mình với
chắc không có đâu bác, vì thuật toán khó, giờ chỉ còn cách mưa dầm thấm lâu thôi
bây giờ có ít thời gian thì bác cố gắng bỏ chơi game đi
 

_Gia_Cat_Luong_

Senior Member
Mình đi làm bận quá, tối về còn chơi game nên cũng ít có thời gian :D

Có cách nào nhanh thím bày mình với
Quy tắc 10000 giờ thôi thím. Thím tự suy phân tích mình có cái gì trong những cái sau đây thì cố tận dụng cái đó:

1. Thông minh. Người giỏi học gì cũng nhanh. Nay làm easy mai làm medium mốt chơi hard luôn.
2. Nhiều thời gian rảnh: Mỗi ngày làm nhiều hơn người khác, ng ta 1 2 bài thì mình 7 8 bài
3. Không có deadline gấp rút: Mỗi ngày làm một chút vài năm sau mới giỏi
4. Giàu: Winner mẹ rồi khỏi LC làm qq gì nữa

Thế nha
 

ngx3009

Junior Member
Nhưng mà hiện tại bài dễ leetcode cũng k làm đc thì có cải thiện để làm medium ko bác nhỉ?

Hay cần tố chất nữa
em cũng gà lắm, em đang follow theo lộ trình bác Gia Cát Lượng chỉ
bác mới làm LC thì đầu tiên cứ như em này, code trâu cũng được, qua hết test case nhưng quá time limit cũng được, rồi cố gắng optimize, không được thì đọc giải ở discuss :D
 

tu_tay_bop_dai

Senior Member
Sắp tới FJP có dự định tổ chức một cuộc đua xe đạp. Tuy nhiên có một vấn đề là các con đường ở thành phố nơi tổ chức có quá nhiều con dốc liên tiếp nhau. Do đó, ban tổ chức đang lo ngại về mức độ nguy hiểm khi tổ chức cuộc đua. Biết độ nguy hiểm được định nghĩa là mức chênh lệnh lớn nhất giữa hai con dốc liên tiếp và ban tổ chức có thể thay đổi độ cao của nhiều nhất k ngọn dốc thành độ cao bất kỳ. Bạn hãy giúp ban tổ chức tìm cách tốt nhất để thay đổi độ cao của các con dốc sao cho độ nguy hiểm là nhỏ nhất. Ví dụ Với n = 4, k = 1, arr = [1, 5, 2, 4] thì kết quả là FJPRace(n, k, arr) = 2. Giải thích: ban đầu chênh lệch giữa hai con dốc liên tiếp lần lượt là [4,3,2] ,do đó độ nguy hiểm là 4, nhưng bạn có thể biến đổi độ cao của các con dốc thành [1, 1, 2, 4] hoặc [1, 2, 2, 4], ... để đạt được độ nguy hiểm nhỏ nhất là 2.. Với n = 6, k = 4, arr = [6, 2, 9, 11, 6, 5] thì kết quả là FJPRace(n, k, arr) = 0. Giải thích: bạn có thể biến đổi độ cao của tất cả con dốc về 6. Đầu vào/Đầu ra [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript. [Đầu vào] int n - số con dốc tại thành phố 1 ≤ n ≤ 10000 [Đầu vào] int k - số con dốc có thể thay đổi độ cao 1 ≤ k ≤ 100 [Đầu vào] Array of integers a - mảng thể hiện độ cao của các con dốc 1 ≤ ai ≤ 1000000000 [Đầu ra] Integer - độ nguy hiểm nhỏ nhất có thể đạt được
Bài này dùng thuật toán gì để giải thế mấy bro
 

_Gia_Cat_Luong_

Senior Member
em cũng gà lắm, em đang follow theo lộ trình bác Gia Cát Lượng chỉ
bác mới làm LC thì đầu tiên cứ như em này, code trâu cũng được, qua hết test case nhưng quá time limit cũng được, rồi cố gắng optimize, không được thì đọc giải ở discuss :D
Nếu nói về strategy nhỏ để luyện LC, thì mình share chút tips.
1. Đặt target về thời gian làm bài. Vd: Easy = 30p, Medium = 1 tiếng, Hard = 3 tiếng

2. Bước đầu tiên là cố gắng giải được, ra đáp án đúng là đc TLE tính sau

3. Luôn cố gắng phân tích độ phức tạp của giải pháp mình định làm trước khi làm

4. Nếu bài có hint thì chia ra các mốc thời gian, nếu đến lúc đó vẫn không làm đc thì xem hint. Hạn chế xem hint. Một hint lớn luôn có đó là Related Topics của câu hỏi, nhấn vào xem vd topic là Binary Search thì mình có định hướng sẵn để nghĩ đáp án. Luôn xem cái này là hint đầu tiên trước các hint khác.

5. Chạy được rồi thì cố gắng nghĩ edge cases chứ đừng chờ đến khi submit báo lỗi, bước này quan trọng

6. Optimize nếu bị TLE, cố gắng submit được là được, không cần beats bn % cả

7. Hết giờ mà chưa làm được, hoặc submit thành công nhưng chỉ beat dưới 20% thì vào discuss hoặc search youtube xem cách người ta làm
  • Phải hiểu được solution của ng ta khác của mình như thế nào, và đúng ra mình nên tiếp cận ntn để đi đến được solution giống người ta
  • Nhận diện được pattern của bài toán này là gì
  • Độ phức tạp sau khi được cải thiện là gì, vì sao nó cải thiện được độ phức tạp, người ta dùng cái gì để cải thiện
  • Vì sao người ta nghĩ ra dùng cái này để cải thiện độ phức tạp ?
8. Không copy code mà tự implement lại bằng code của mình. Tốt nhất nên coi solution bằng một ngôn ngữ và implement lại bằng một ngôn ngữ khác để tránh copy

9. Quan trọng: Làm như tui đang làm, viết giải thích về solution của mình (và đăng lên đây). Có sự khác biệt lớn giữa code đượcgiải thích được. Một khi giải thích được bằng lời thì sẽ rất khó quên.
 
em cũng gà lắm, em đang follow theo lộ trình bác Gia Cát Lượng chỉ
bác mới làm LC thì đầu tiên cứ như em này, code trâu cũng được, qua hết test case nhưng quá time limit cũng được, rồi cố gắng optimize, không được thì đọc giải ở discuss :D
Mình easy làm kiểu trâu bò thì đc :( nhưng mà có chỗ for lồng for rồi if lồng if
 

NudeDuck

Junior Member
Bài hôm nay hay ở nhiều khía cạnh: đầu tiên phải nhìn ra tổng thời gian của các việc đã làm phải bé hơn lastDay, với cái thứ hai là vụ swap
 

bribnt

Đã tốn tiền
9. Quan trọng: Làm như tui đang làm, viết giải thích về solution của mình (và đăng lên đây). Có sự khác biệt lớn giữa code đượcgiải thích được. Một khi giải thích được bằng lời thì sẽ rất khó quên.

Thực ra cái bác đang làm chỉ mới là giải thích về mặt ý tưởng. Chứ vẫn chưa chứng minh vì sao cách làm là đúng về mặt toán học. Cho nên có thể có những thắc mắc như:
  • tại sao ở mệnh đề else lại không thể tăng số khóa học lên? Liệu có thể xóa 1 khóa học trong heap và thêm khóa hiện tại cộng thêm một khóa khác đã bị bỏ qua không?
  • trong trường hợp không tăng được số khóa học thì việc swap 1 - 1 đã tối ưu chưa? Lỡ như có cách swap 2 - 2 để totalTime nhỏ hơn nữa thì sao?

Để chứng minh tính đúng đắn của thuật toán thì có một công cụ gọi là loop invariant. Đặt trước một điều kiện và chứng minh nó đúng với mọi bước lặp, thường là bằng quy nạp. Từ đó kết luận thuật toán đúng. Trong bài này thì có thể dùng invariant sau:
  • sau khi duyệt xong khóa học thứ ci (đã sort) thì phương án đang có trong heap là tối ưu với đầu vào là các khóa c0 c1... ci
  • totalTime cũng là nhỏ nhất trong số các phương án khác có cùng số khóa học.

Sent from HUAWEI DBY-W09 using vozFApp
 

_Gia_Cat_Luong_

Senior Member
Thực ra cái bác đang làm chỉ mới là giải thích về mặt ý tưởng. Chứ vẫn chưa chứng minh vì sao cách làm là đúng về mặt toán học. Cho nên có thể có những thắc mắc như:
  • tại sao ở mệnh đề else lại không thể tăng số khóa học lên? Liệu có thể xóa 1 khóa học trong heap và thêm khóa hiện tại cộng thêm một khóa khác đã bị bỏ qua không?
  • trong trường hợp không tăng được số khóa học thì việc swap 1 - 1 đã tối ưu chưa? Lỡ như có cách swap 2 - 2 để totalTime nhỏ hơn nữa thì sao?

Để chứng minh tính đúng đắn của thuật toán thì có một công cụ gọi là loop invariant. Đặt trước một điều kiện và chứng minh nó đúng với mọi bước lặp, thường là bằng quy nạp. Từ đó kết luận thuật toán đúng. Trong bài này thì có thể dùng invariant sau:
  • sau khi duyệt xong khóa học thứ ci (đã sort) thì phương án đang có trong heap là tối ưu với đầu vào là các khóa c0 c1... ci
  • totalTime cũng là nhỏ nhất trong số các phương án khác có cùng số khóa học.

Sent from HUAWEI DBY-W09 using vozFApp
Cũng không cần sâu xa thế, mục tiêu giải thích chỉ là để mình hiểu rõ hơn và lâu hơn thôi. Làm ở mức độ nào bản thân thấy ổn là được rồi :D.
 

phuocrose

Senior Member
k có pro như các bác, đang tập làm các bài easy hết rồi lên medium luôn nhỉ ? bọn này k support dart, java thì lâu r nhớ. toàn phải tự viết chỗ khác tự test luôn
 
Top