Search thấy cho chọn comparer mà.Cái PriorityQueue của C# nó hơi ngu là Dequeue số nhỏ ra trước nên mình xài trick tí
https://docs.microsoft.com/en-us/do...r(system-collections-generic-icomparer((-1)))
Search thấy cho chọn comparer mà.Cái PriorityQueue của C# nó hơi ngu là Dequeue số nhỏ ra trước nên mình xài trick tí
Search thấy cho chọn comparer mà.
https://docs.microsoft.com/en-us/do...r(system-collections-generic-icomparer((-1)))
cùng idea với thímHơi rườm rà thím, chuyển cái priority value về negative là được rồi
Sent from Samsung SM-A528B using vozFApp
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 passLC 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 đã
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
}
Thím ơi có cách nào học leetcode nhanh mà dễ không thím23/06/2022
#630. (Hard) https://leetcode.com/problems/course-schedule-iii/
Phân tích bài toán:
⇒ 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
- 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
Solution:
Mã giả:
- 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)
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
Không thímThím ơi có cách nào học leetcode nhanh mà dễ không thím
Mình đi làm bận quá, tối về còn chơi game nên cũng ít có thời gianKhông thím
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ôiMình đi làm bận quá, tối về còn chơi game nên cũng ít có thời gian
Có cách nào nhanh thím bày mình với
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ỉ?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
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 đó: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
Có cách nào nhanh thím bày mình với
em cũng gà lắm, em đang follow theo lộ trình bác Gia Cát Lượng chỉ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
Bài này dùng thuật toán gì để giải thế mấy broSắ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
Nếu nói về strategy nhỏ để luyện LC, thì mình share chút tips.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
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 ifem 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
Bài này có vẻ là kth element thôi. Lấy gap, sort lại giảm dần rồi trả về phần tử thứ k. Chưa suy nghĩ sâu xa, maybe có trick.Bài này dùng thuật toán gì để giải thế mấy bro
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 được và giải thích được. Một khi giải thích được bằng lời thì sẽ rất khó quên.
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 .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