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

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
Thực ra đối với bài LC hôm nay đúng là cần phải chứng minh tính đúng đắn của solution về mặt toán học. Vì đa số ae đều dùng greedy để giải, mà greedy k đảm bảo sẽ tìm được best solution. Nên đúng là cần thêm bước đó. Tuy nhiên ở đây chủ yếu là nơi để ae thảo luận, chia sẻ thôi, cũng k cần phải căng thẳng quá. Ae nào rảnh rỗi thì có thể ngồi chứng minh rồi post lên đây. :big_smile:
 

Violet_7

Senior Member
24/6/2022:
  • 1 câu hard leetcode
  • nhìn nhận đề bài, nếu nghĩ theo kiểu straight forward đề bài biến dãy nguyên số 1 thành cái target thì rất khó, độ phức tạp sẽ là 2 ^ n nếu làm kiểu này
  • n max là 5 * 10^4 nên time < O(n^ 2) -> phải có trick
  • sau 1 hồi suy nghĩ, trick ở đây là: giả sử lúc đầu dãy là nguyên số 1, số thêm vào là tổng của dãy trước đó -> số thêm vào chính là số lớn nhất của dãy lúc sau. VD target = {9, 5, 3} -> số lớn nhất là 9, tổng dãy trước khi thành dãy này phải == 9 mà số thay thế là 9 nên giải sử dãy trước có dạng {a, 5, 3} -> a + 5 + 3 == 9 -> a = 1 -> dãy trước đó là {1, 5, 3}
  • lúc đầu sort dãy target theo chiều từ lớn đến bé nhưng gặp phải vấn đề VD số 9 trong dãy target lại trở thành số lớn nhất trong tương lai thì sao. VD {9, 3, 1} -> dãy trước là {5, 4, 1} -> 5 lại là số lớn nhất
-> dùng heap, cứ mỗi lần sẽ lấy số lớn nhất ra rồi add vào số của dãy trước đó, Như vd {9, 3, 1} -> {5, 4, 1} , pop số 9 ra rồi add số 5 vào
- Nhưng lại bị tle -> VD [1, 1000000] nếu làm theo kiểu này thì mấy 1000000 lần pop và add -> số cần add = số lớn nhất(là số đã pop) % tổng còn lại
-> ra đáp án
CODE: https://leetcode.com/submissions/detail/729724835/
  • độ phức tạp time: mỗi lần pop and add, tổng sẽ giảm 1 nửa -> log(sum target ) * log(n) + nlog(n) cho cái heap
  • mất 30p để giải xong bài này :beauty::beauty:
1656034183783.png
 

Attachments

  • 1656034386653.png
    1656034386653.png
    26.5 KB · Views: 29
Last edited:

tdat00

Đã tốn tiền
4 lần submit mới qua được. Bài hôm nay không khó nhưng mấy cái test case khốn nạn quá. Các thím cần chú ý vụ tràn số mới được.
Screen Shot 2022-06-24 at 08.57.24.png



Cái test khốn nạn
M7EYXjT.png


Screen Shot 2022-06-24 at 08.43.43.png
 
Last edited:

Sunday_Sunday

Senior Member
24/6/2022:
  • 1 câu hard leetcode
  • nhìn nhận đề bài, nếu nghĩ theo kiểu straight forward đề bài biến dãy nguyên số 1 thành cái target thì rất khó, độ phức tạp sẽ là 2 ^ n nếu làm kiểu này
  • n max là 5 * 10^4 nên time < O(n^ 2) -> phải có trick
  • sau 1 hồi suy nghĩ, trick ở đây là: giả sử lúc đầu dãy là nguyên số 1, số thêm vào là tổng của dãy trước đó -> số thêm vào chính là số lớn nhất của dãy lúc sau. VD target = {9, 5, 3} -> số lớn nhất là 9, tổng dãy trước khi thành dãy này phải == 9 mà số thay thế là 9 nên giải sử dãy trước có dạng {a, 5, 3} -> a + 5 + 3 == 9 -> a = 1 -> dãy trước đó là {1, 5, 3}
  • lúc đầu sort dãy target theo chiều từ lớn đến bé nhưng gặp phải vấn đề VD số 9 trong dãy target lại trở thành số lớn nhất trong tương lai thì sao. VD {9, 3, 1} -> dãy trước là {5, 4, 1} -> 5 lại là số lớn nhất
-> dùng heap, cứ mỗi lần sẽ lấy số lớn nhất ra rồi add vào số của dãy trước đó, Như vd {9, 3, 1} -> {5, 4, 1} , pop số 9 ra rồi add số 5 vào
- Nhưng lại bị tle -> VD [1, 1000000] nếu làm theo kiểu này thì mấy 1000000 lần pop và add -> số cần add = số lớn nhất(là số đã pop) % tổng còn lại
-> ra đáp án
CODE: https://leetcode.com/submissions/detail/729724835/
  • độ phức tạp time: mỗi lần pop and add, tổng sẽ giảm 1 nửa -> log(sum target ) * log(n) + nlog(n) cho cái heap
  • mất 30p để giải xong bài này :beauty::beauty:
View attachment 1227544
cũng dính quả TLE như bác này mô tả :ah::ah::ah:
 

tu_tay_bop_dai

Senior Member
Pain :cry:
1656057279321.png


Code: https://leetcode.com/submissions/detail/729960682/
Bài này mình dùng đệ quy để giải.

Mấy cái TLE là do ban đầu mình chỉ khai báo biến int còn mấy chỗ sai là thiếu điều kiện thoát đệ quy sau mình sửa từng cái một :byebye: Cách giải thì cũng giống của mấy bác trên đó là tính ngược mảng trước bằng số lớn nhất của mảng hiện tại và dùng %
 

_Gia_Cat_Luong_

Senior Member
24/6/2022:
  • 1 câu hard leetcode
  • nhìn nhận đề bài, nếu nghĩ theo kiểu straight forward đề bài biến dãy nguyên số 1 thành cái target thì rất khó, độ phức tạp sẽ là 2 ^ n nếu làm kiểu này
  • n max là 5 * 10^4 nên time < O(n^ 2) -> phải có trick
  • sau 1 hồi suy nghĩ, trick ở đây là: giả sử lúc đầu dãy là nguyên số 1, số thêm vào là tổng của dãy trước đó -> số thêm vào chính là số lớn nhất của dãy lúc sau. VD target = {9, 5, 3} -> số lớn nhất là 9, tổng dãy trước khi thành dãy này phải == 9 mà số thay thế là 9 nên giải sử dãy trước có dạng {a, 5, 3} -> a + 5 + 3 == 9 -> a = 1 -> dãy trước đó là {1, 5, 3}
  • lúc đầu sort dãy target theo chiều từ lớn đến bé nhưng gặp phải vấn đề VD số 9 trong dãy target lại trở thành số lớn nhất trong tương lai thì sao. VD {9, 3, 1} -> dãy trước là {5, 4, 1} -> 5 lại là số lớn nhất
-> dùng heap, cứ mỗi lần sẽ lấy số lớn nhất ra rồi add vào số của dãy trước đó, Như vd {9, 3, 1} -> {5, 4, 1} , pop số 9 ra rồi add số 5 vào
- Nhưng lại bị tle -> VD [1, 1000000] nếu làm theo kiểu này thì mấy 1000000 lần pop và add -> số cần add = số lớn nhất(là số đã pop) % tổng còn lại
-> ra đáp án
CODE: https://leetcode.com/submissions/detail/729724835/
  • độ phức tạp time: mỗi lần pop and add, tổng sẽ giảm 1 nửa -> log(sum target ) * log(n) + nlog(n) cho cái heap
  • mất 30p để giải xong bài này :beauty::beauty:
View attachment 1227544
Bác giải thích khá chi tiết nên xin phép lấy bài của bác pin lên trang đầu luôn nha
 

tdat00

Đã tốn tiền
Sáng mai có thím nào máu chiến Weekly contest không :p

Sent from Samsung SM-A528B using vozFApp
 

tdat00

Đã tốn tiền
lâu rồi cũng không làm tại thời gian k phù hợp
cũng chưa bao giờ làm hết 4 câu =((=((=((

Tôi cũng thỉnh thoảng rảnh lắm mới làm contest thôi. Cảm giác làm 4 bài trong 2h nó phê lắm :p:love:

Sent from Samsung SM-A528B using vozFApp
 

Violet_7

Senior Member
25/6/2022:
  • Đánh giá 1 câu medium khá nhẹ nhàng
  • Nhìn nhận đề bài, cho 1 dãy số và chỉ đc quyền thay đổi 1 số duy nhất để dãy trở thành dãy ko giảm, lưu ý chỉ 1 số
  • Như vậy trong dãy đó ko thể tồn tại 2 số có index i sao cho nums của i> nums của i + 1, hay là 2 lần giảm, vì như thế sẽ cần phải sửa 2 số
-> chỉ có duy nhất 1 lần giảm của dãy hoặc ko có lần nào
  • Nếu ko có lần nào giảm thì return true
  • Nếu có 1 lần giảm, giả sử lần đó là nums của i > nums của i + 1 -> phải chọn 1 số trong 2 số nums i và nums i + 1 để sửa
  • VD {a, 7, 1, b} -> phải chọn số 7 hoặc 1 để sửa
  • -> vì dãy có đúng 1 lần giảm nên có tính chất a <= 7 và 1 <= b
-> nếu a <= 1 thì ta có thể sửa số 7 thành số 1
-> nếu 7 <= b thì ta có thể sửa số 1 thành 7
-> còn ko có 2 TH trên thì ko thể sửa được VD {5, 7, 1, 2}
-> ra đáp án
- Time complexity: O(n)
Code: https://leetcode.com/submissions/detail/730475998/
- mất mười mấy phút để giải :beauty::beauty:
 
Last edited:

tdat00

Đã tốn tiền
Bài hôm nay dễ quá nên chắc bà con chủ quan nhiều, không xử lý edge case nên tỉ lệ accept thấp.

Giải pháp không có gì đặc biệt, duyệt từng item trong mảng, nếu thấy nums[i] < nums[i-1] thì cần check 2 trường hợp:
  • Thay thế nums[i] sao cho nums[i-1] <= nums[i] <= nums[i+1]
  • Thay thế nums[i-1] sao cho nums[i-2] <= nums[i-1] <= nums[i]


Vì mấy cái i-1, i-2... này nên các thím cần check điều kiện kỹ để khỏi bị index out of range.
 

tu_tay_bop_dai

Senior Member
Mình check nếu mảng chỉ có 1 hoặc 2 phần tử thì trả về true luôn. Từ 3 phần tử trở lên thì mới duyệt.
Phương pháp thì như các bác trên là so sánh nums[i] > nums[i+1] rồi chỉnh sửa. Còn việc sửa số nào thì mình dùng 1 biến max = num[i-1]
C#:
if(nums[i+1] >= max){
    nums[i] = nums[i+1];
}
 else {
    nums[i+1] = nums[i];
}
Sau khi sửa xong thì check xem nếu đã sửa quá 1 lần thì trả về false, còn không thì trả về true
https://leetcode.com/submissions/detail/730564022/
 

ctw_god

Senior Member
Làm embedded thì luyện LC có giúp ích gì nhiều ko anh em?
Công việc low code lâu ngày quên hết cách code rồi. Hic :too_sad:

via theNEXTvoz for iPhone
 

_Gia_Cat_Luong_

Senior Member
Làm embedded thì luyện LC có giúp ích gì nhiều ko anh em?
Công việc low code lâu ngày quên hết cách code rồi. Hic :too_sad:

via theNEXTvoz for iPhone
Mình k làm embedded nên không dám chắc. Nhưng theo kn mình thì luyện LC ít khi nào giúp được gì trong công việc. Vì phỏng vấn / sở thích là chính thôi.
 

tulanhvip

Senior Member
Làm embedded thì luyện LC có giúp ích gì nhiều ko anh em?
Công việc low code lâu ngày quên hết cách code rồi. Hic :too_sad:

via theNEXTvoz for iPhone
Câu hỏi của thím thì em không rõ, nhưng chiều ngược lại code embedded xong có mấy cái trick áp dụng cho code application thông thường khá hay. 1 trong những cái em khác tâm đắc là dùng bitwise để check config, role, cực kì tiết kiệm bộ nhớ mà lại rất clearly.
 

Violet_7

Senior Member
26/6/2022:
  • 1 câu medium nhẹ nhàng
  • nhìn ngay vào đề bài ta thấy ngay đc là tìm tổng prefix + suffix có size = k lớn nhất
-> build 2 mảng prefix và suffix của dãy ban đầu, rồi tìm prefix của i + suffic của k - i lớn nhất
-> ra đáp án
  • Time : O(k)
  • Space: O(k)
1 câu khá dễ, nghĩ có 30 giây là ra, code mất 10 phút vì sáng dạy hơi ngáo
CODE: https://leetcode.com/submissions/detail/731292328/

- Sau khi đọc discuss thì có solution space O(1), thì lại nghĩ tiếp
-> solution space O(1) cx chả có j, chỉ là tối ưu cái solution ban đầu,

- Đầu tiên tạo biến prefixSum là tổng k số ban đầu, rồi tạo biến sufixSum, maxScore
- Khi prefixSum giảm 1 số thì suffixSum sẽ tăng lên 1 số cuối
- maxScore = max(maxScore, prefixSum + suffixSum)
Code: https://leetcode.com/submissions/detail/731295371/
 
Last edited:
Top