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
View attachment 1227544