thảo luận [Học Tập] Topic thuật toán
- Người tạo chủ đề unknowpc90
- Ngày bắt đầu
vite551314
Junior Member
không biết có bác nào có thuật tính tổng ước của 1 số nhanh nhanh không
thuyduong2007
Member
Không thím ơi. Map hay set nó dùng red-back tree, dạng gần giống như cây tự cân bằng ấy. Nên sau khi build xong cái map, mình duyệt từ đầu đến cuối thì nó sẽ theo thứ tự, mặc định nó sẽ là tăng dần.
Còn dict trong python nó dùng hash table. Bên C++ có unordered_map tương tự, cũng dùng hash_table.
Bài trên nếu muốn dùng hash table cũng được, khi đó thì phải sort cái dãy input, build hash table. Sau đó duyệt theo dãy input đã được sort + search trong hash table. Độ phức tạp cũng giống cách t. Nhưng trên C++ có thể cách này sẽ chạy nhanh hơn. Do việc duyệt trên 1 dãy liên tục sẽ it bị miss cache hơn là duyệt trong cái map.
vexliva
Member
Ờ bài trên python mình nhìn thì thấy dùng hash table. Làm ra thì cũng NlogN do cái sortKhông thím ơi. Map hay set nó dùng red-back tree, dạng gần giống như cây tự cân bằng ấy. Nên sau khi build xong cái map, mình duyệt từ đầu đến cuối thì nó sẽ theo thứ tự, mặc định nó sẽ là tăng dần.
Còn dict trong python nó dùng hash table. Bên C++ có unordered_map tương tự, cũng dùng hash_table.
Bài trên nếu muốn dùng hash table cũng được, khi đó thì phải sort cái dãy input, build hash table. Sau đó duyệt theo dãy input đã được sort + search trong hash table. Độ phức tạp cũng giống cách t. Nhưng trên C++ có thể cách này sẽ chạy nhanh hơn. Do việc duyệt trên 1 dãy liên tục sẽ it bị miss cache hơn là duyệt trong cái map.
Fireknight
Member
Có cái sàng eratos ấy thím, xài giống eratos bình thường sau đó lấy ra tính tổng thím
nashwade
Senior Member
Tổng ước thì cứ for hết ước rồi cộng lại thôi chứ sàng cũng có nhanh hơn đâu nhỉ
Fireknight
Member
Sàng nó nhanh hơn có thể tính được n<= 10^6 và ai<=10^6 thím ạTổng ước thì cứ for hết ước rồi cộng lại thôi chứ sàng cũng có nhanh hơn đâu nhỉ
nashwade
Senior Member
Câu ban đầu thím kia hỏi là 1 số mà thím? Nếu 1 số thì sàng luôn luôn chậm hơn là duyệt qua các ước chứ.
.gears
Senior Member
sàng thì để tính tất cả ước trong khoảng 1 lần xong truy vấn nhanh thôi.
preprocess O(nlog(n)), O(1) với mỗi truy vấn.
còn nếu chỉ cần truy vấn 1 lần từ O(sqrt(n)) tính trực tiếp nhanh hơn.
KimSoHyunGoddness
Member
Leetcode mới có phần study plan nè mấy thím. Vào học thuật toán.
Tiện thể em khoe bản thành tích trên leetcode luôn
KimSoHyunGoddness
Member
Vậy là hôm nay hoàn thành được 3 bài này. Khá cơ bản mấy bác ạ
Xem tệp đính kèm 721763
Khoe. Cơ mà bỏ lâu rồi ko luyện lại
. Thấy từ Medium lên Hard là cả 1 khoảng cách , giải dc có 19 bài hard
giải dc là ghê rồi, nhiều bài hard khó lắm
uytuhgdfr
Member
Vãi. Giải được bài Hard là qua Google làm được rồi.
uytuhgdfr
Member
Giải được Hard thì qua nước ngoài làm thôi bạn.Xem tệp đính kèm 721763
Khoe. Cơ mà bỏ lâu rồi ko luyện lại. Thấy từ Medium lên Hard là cả 1 khoảng cách , giải dc có 19 bài hard
vexliva
Member
Bài này check case chắc mệt mỏi luôn
Sửa lần cuối:
thuyduong2007
Member
Bên leetcode mình mới làm gần đây nên mới được nhiu đây thôi. Trước cày bên hackerrank cũng tầm hơn trăm bài.
uytuhgdfr
Member
VN mình nhiều người giỏi vãi. Mà sao không vượt biên được nhỉ. Toàn trình Hard thế này.
Yêu em Thu Nga CN12 ptit
Senior Member
Nghỉ leetcode để làm bài của trường mấy ngày rồi, spam bài easy nên cũng được nhiều phết
Chủ đề tương tự
