thảo luận [Học Tập] Topic thuật toán
- Thread starter unknowpc90
- Start date
Fzen
Đã tốn tiền
Bạn bí chỗ nào thì hỏi chứ không lẽ bí hết, nhìn vào ít nhất bạn phải làm được ý 3
Lập Trình Viên Số Khổ
Senior Member
bài này nhìn dễ mà, cứ tính lần lượt là ra thui
Hiếu Lã
Senior Member
Em thấy nó bí việc quản lý bộ nhớ đấy bác, số nó tăng theo cấp số nhân kìa. loại nào lưu cho đủBạn bí chỗ nào thì hỏi chứ không lẽ bí hết, nhìn vào ít nhất bạn phải làm được ý 3
Last edited:
dogamer02
Senior Member
Tự code lại BigInt, dùng mảng số hoặc là string cũng được mà fen
Hiếu Lã
Senior Member
Tự code lại BigInt, dùng mảng số hoặc là string cũng được mà fen
Em đang tìm xem có cái nào kiểu kiểu như modulo để áp dụng vào trường hợp này k. Chứ em k muốn tính cả 100 số ra bác ạ.
Gửi từ Samsung SM-A730F bằng vozFApp
clonemasteruwu
Senior Member
Đề yêu cầu tất cả các bước hay chỉ bước cuối? Nếu phải đủ tất cả các bước thì cứ đúng thế mà làm, còn chỉ yêu cầu tìm cái cuối thì b phải nói rõ là cần giải thuật chứ
Hiếu Lã
Senior Member
Đề yêu cầu tất cả các bước hay chỉ bước cuối? Nếu phải đủ tất cả các bước thì cứ đúng thế mà làm, còn chỉ yêu cầu tìm cái cuối thì b phải nói rõ là cần giải thuật chứ
Trước mắt là tìm giải thuật để tính được trung bình cộng của 100 số kia đã rồi mới làm được tiếp chứ bác
Gửi từ Samsung SM-A730F bằng vozFApp
clonemasteruwu
Senior Member
Bác k hiểu ý mình r, ví dụ đề bài chỉ yêu cầu tìm k, thì sẽ (có thể) có cách tìm k mà không cần biết mean (algorithm = do less work), còn nếu bắt làm đủ từng đó bước thì cứ thế mà làmTrước mắt là tìm giải thuật để tính được trung bình cộng của 100 số kia đã rồi mới làm được tiếp chứ bác
Gửi từ Samsung SM-A730F bằng vozFApp
Hiếu Lã
Senior Member
À. Ý em là trước mắt xử lý vụ tràn số lúc tính trung bình cộng của cả mảng bác ạ.
Gửi từ Samsung SM-A730F bằng vozFApp
_Gia_Cat_Luong_
Senior Member
Chuyên mục mỗi ngày 1 bài leetcode!!
Tình hình là tháng vừa rồi dịch, thất nghiệp ở nhà chán quá nên mình nảy ra ý tưởng luyện leetcode. Vừa coi như có cái để làm với luyện tay nghề sau này phỏng vấn.
Mỗi ngày mình làm 2-5 bài leetcode (tùy độ khó), cũng kéo dài hơn 2 tuần rồi. Nay thấy làm một mình chán quá nên vác lên đây chém gió với anh em cho xôm.
Một chút về bản thân thì mình hiện tại dev cỏ, đang thất nghiệp và tính chờ hết dịch sẽ apply vào một công ty nào đó ở EU hoặc US.
Cách làm leet code của mình đơn giản là làm theo thứ tự chứ k filter gì. Hard hay easy gì cũng phang tuốt. Cứ làm xong 1 bài thì làm đến bài tiếp theo. Dĩ nhiên là trừ mấy bài premium ra vì k có tiền T_T. Hiện tại mình làm đến #352 rồi. Ngôn ngữ mình dùng chính là python.
Mỗi ngày mình sẽ chọn ra 1 bài thấy hay trong ngày hôm đó và chia sẻ với mọi người. Các bài còn lại mình sẽ để link nếu bác nào thích thì thảo luận.
Tình hình là tháng vừa rồi dịch, thất nghiệp ở nhà chán quá nên mình nảy ra ý tưởng luyện leetcode. Vừa coi như có cái để làm với luyện tay nghề sau này phỏng vấn.
Mỗi ngày mình làm 2-5 bài leetcode (tùy độ khó), cũng kéo dài hơn 2 tuần rồi. Nay thấy làm một mình chán quá nên vác lên đây chém gió với anh em cho xôm.
Một chút về bản thân thì mình hiện tại dev cỏ, đang thất nghiệp và tính chờ hết dịch sẽ apply vào một công ty nào đó ở EU hoặc US.
Cách làm leet code của mình đơn giản là làm theo thứ tự chứ k filter gì. Hard hay easy gì cũng phang tuốt. Cứ làm xong 1 bài thì làm đến bài tiếp theo. Dĩ nhiên là trừ mấy bài premium ra vì k có tiền T_T. Hiện tại mình làm đến #352 rồi. Ngôn ngữ mình dùng chính là python.
Mỗi ngày mình sẽ chọn ra 1 bài thấy hay trong ngày hôm đó và chia sẻ với mọi người. Các bài còn lại mình sẽ để link nếu bác nào thích thì thảo luận.
_Gia_Cat_Luong_
Senior Member
Giới thiệu xong xuôi. Đây là 3 bài mình làm ngày hôm nay:
#345. https://leetcode.com/problems/reverse-vowels-of-a-string
#347. https://leetcode.com/problems/top-k-frequent-elements
#352. https://leetcode.com/problems/data-stream-as-disjoint-intervals
Mình sẽ share về bài Top K Frequent Elements:
Bài medium nhưng khá đơn giản.
Ý tưởng của mình là đếm số lần xuất hiện của mỗi phần tử trong mảng. Sau đó sort theo số lần xuất hiện giảm dần. Cuối cùng trả về k phần tử đầu tiên.
Độ phức tạp tgian là O(nlogn) cho thao tác sort. Space là O(n).
Follow up: Trong bài có follow up là mình thử thực hiện với độ phức tạp thấp hơn O(nlogn). Mình lười nên k làm nhưng theo mình có 2 hướng:
p/s:
- Bài này sẽ khá hack não nếu k có cái constraint: It is guaranteed that the answer is unique. => Thế nên trước khi giải bất kì bài nào thì đều cần đọc kĩ constraint.
#345. https://leetcode.com/problems/reverse-vowels-of-a-string
#347. https://leetcode.com/problems/top-k-frequent-elements
#352. https://leetcode.com/problems/data-stream-as-disjoint-intervals
Mình sẽ share về bài Top K Frequent Elements:
Python:
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = defaultdict(int)
for n in nums:
count[n] += 1
count = [(c, n) for n, c in count.items()]
count.sort(reverse=True)
return [n for c, n in count[:k]]Bài medium nhưng khá đơn giản.
Ý tưởng của mình là đếm số lần xuất hiện của mỗi phần tử trong mảng. Sau đó sort theo số lần xuất hiện giảm dần. Cuối cùng trả về k phần tử đầu tiên.
Độ phức tạp tgian là O(nlogn) cho thao tác sort. Space là O(n).
Follow up: Trong bài có follow up là mình thử thực hiện với độ phức tạp thấp hơn O(nlogn). Mình lười nên k làm nhưng theo mình có 2 hướng:
- Dùng Quickselect => độ phức tạp là O(k logn). Đúng với follow up là better than O(n logn)
- Có thể đơn giản thay hàm sort mặc định bằng radix sort thì độ phức tạp sẽ về O(n).
p/s:
- Bài này sẽ khá hack não nếu k có cái constraint: It is guaranteed that the answer is unique. => Thế nên trước khi giải bất kì bài nào thì đều cần đọc kĩ constraint.
uytuhgdfr
Member
Vãi thế mà ông kia làm 400 bài từ bài 1 tới bài 400 luôn mới sợ.mình làm có mấy bài easy với medium, làm 1 hồi xong quay lại bài cũ éo nhớ giải kiểu gì luôn. Giờ mình chuyển qua luyện theo pattern. Đang tập làm sliding window
vietdt89
Junior Member
ai k quen giải thuật toán lúc đầu khó lắm, mần mãi mới xong 1 bài. Nhưng luyện dần dần đến lúc bon tay rồi thì nhanh không, nó có pattern cả đấy, phải nhìn ra pattern thì mới nhanh được.
_Gia_Cat_Luong_
Senior Member
Fen nói chính xác, cái này làm nhiều quen tay thôi chứ cũng chả phải thần thánh gì.
Làm theo từng chủ đề cũng đc, nó giúp mình dễ quen hơn. Nhưng làm mãi 1 cái thì nhanh chán :v.
Cũng chả hiểu sao bọn EU US nó có văn hóa pv là phải test cái này. Thấy vô nghĩa vkl. Mình làm thấy giống giải câu đố vậy thôi, giải được thì hay ho chứ chả có bn tác dụng thực tế.
uytuhgdfr
Member
Thấy test thuật toán toàn công ty lớn. Chắc phải cần đến thuật toán thì người ta mới tuyển. Công ty nhỏ thì ai làm visa mời bác sang được.
_Gia_Cat_Luong_
Senior Member
Vẫn nhiều cty có visa sponsor mà. Đợt trước mình có pv vài cty bên đó (k phải FAANG), tụ nào cũng có ít nhất 2 vòng thuật toán. Cơ mà fail sạch :v.
vietdt89
Junior Member
k pv cái này thì biết pv cái gì bác, nó phản ánh tư duy của ng lập trình. Còn ngôn ngữ nó bao la lắm. 1 cty có tỷ cái project, mỗi project 1 loại ngôn ngữ nền tảng. Tuyển thằng thuật toán tốt tức là tư duy nó tốt, dễ thích ứng với cty
Coffe_Bên_Lề
Junior Member
Em ưng ý kiến của bác này, tiếc là không thể thả tim, em chuẩn bị sang năm 3 rồi, mà thuật toán còn yếu quá, mấy bài từ mức dễ còn giải được lên mức trung bình là phân tích không nổi nữa
không biết cải thiện được trình độ giải thuật không nữa chứ cứ mấy bài ngang mức trung bình nhiều lúc loay hoay gần 1 tiếng mà chưa giải đượcSimilar threads
