Hướng dẫn cho Gộp dãy toàn số 1
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
- Cách trâu: Độ phức tạp \(O(n^2)\): Đếm số lượng số 1 trong dãy. Giả sử là \(x\). Ta cần tìm dãy con có độ dài \(x\) với số lượng số 1 nhiều nhất. Như vậy, số lượng phép tráo đổi cần thiết sẽ là số lượng số 0 trong dãy vừa tìm có độ dài \(x\) ở trên.
- Cách 2. Độ phức tạp \(O(n)\). Cải tiến từ cách trâu ở trên, sử dụng kĩ thuật dịch cửa sổ (sliding window). Ta gọi preCount là mảng lưu số lượng phần từ 1 trong mỗi dãy con - tính bằng kĩ thuật cộng dồn. Tiếp tục sử dụng kĩ thuật sliding window tìm đoạn con kích thước x có số lượng 1 nhiều nhất.
Bình luận