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.
cũng dính quả TLE như bác này mô tả24/6/2022:
-> 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
- 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
- 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/
View attachment 1227544
- độ 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
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 %
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 nha24/6/2022:
-> 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
- 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
- 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/
View attachment 1227544
- độ 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
lâu rồi cũng không làm tại thời gian k phù hợpSáng mai có thím nào máu chiến Weekly contest không
Sent from Samsung SM-A528B using vozFApp
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
nums[i] < nums[i-1] thì cần check 2 trường hợp:nums[i] sao cho nums[i-1] <= nums[i] <= nums[i+1]nums[i-1] sao cho nums[i-2] <= nums[i-1] <= nums[i]
Vì bài này dễ bị chủ quan ấy mà. Mình cũng submit sai một lầm rồi mới pass, lolbài hôm nay nhẹ nhàng mà tỉ lệ accept thấp thế 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] if(nums[i+1] >= max){
nums[i] = nums[i+1];
}
else {
nums[i+1] = nums[i];
}
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.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
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.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
via theNEXTvoz for iPhone
