thảo luận [Học Tập] Topic thuật toán

thuyduong2007 · 12/9/21

Fireknight đã nói:
ủa thằng multimap này nó tự sắp xếp giảm dần luôn hả thím

map/set/multimap/multiset đều sắp xếp có thứ tự dựa vào key nhé. mặc định thì là tăng dần. Có thể thay đổi thứ tự sắp xếp bằng cách truyền compare object vào constructor nhé.
https://en.cppreference.com/w/cpp/container/multimap/multimap

Đối với multimap/multiset do nó cho phép chứa các key trùng nhau. Trong trường hợp này thì từ C++11 nó sẽ dựa vào thứ tự insert. Còn trước C++11 thì k có standard tùy vào implement của mỗi compiler thôi. Thím kia có xài auto nên => ít nhất là C++11 rồi.

Còn bài bên trên thì thím kia dùng cái multimap với compare obj là default nên thứ tự tăng dần mới đúng. Lúc đầu thím ấy đã sort cái a theo thứ tự giảm dần. Sau đó add vào cái multimap thì sẽ ra được key tăng dần, trùng key thì giảm dần. Ngược lại hoàn toàn so với yêu cầu. Sau đó reverse lại để ra đúng kết quả.

@Yêu em Thu Nga CN12 ptit : Thay vì duyệt từ đầu đến cuối cái multimap rồi reverse thì thím chỉ cần duyệt ngược cái multimap là được.

. Tuy nhiên cách hiện tại t thấy chưa ổn lắm. Thấy hơi rườm rà.

thuyduong2007 · 12/9/21

@Yêu em Thu Nga CN12 ptit
Đây là solution của t.

C++:

void sortByFreq(vector<int> &nums) {
    unordered_map<int,int> freq(nums.size());
    for (auto x : nums) freq[x]++;

    sort(nums.begin(), nums.end(),
                    [&freq](int a, int b)
                        {
                            auto freq_a = freq[a];
                            auto freq_b = freq[b];
                            return freq_a == freq_b ? a < b : freq_a > freq_b;
                        });
}

Fireknight · 12/9/21

thuyduong2007 đã nói:
map/set/multimap/multiset đều sắp xếp có thứ tự dựa vào key nhé. mặc định thì là tăng dần. Có thể thay đổi thứ tự sắp xếp bằng cách truyền compare object vào constructor nhé.
https://en.cppreference.com/w/cpp/container/multimap/multimap

Đối với multimap/multiset do nó cho phép chứa các key trùng nhau. Trong trường hợp này thì từ C++11 nó sẽ dựa vào thứ tự insert. Còn trước C++11 thì k có standard tùy vào implement của mỗi compiler thôi. Thím kia có xài auto nên => ít nhất là C++11 rồi.

Còn bài bên trên thì thím kia dùng cái multimap với compare obj là default nên thứ tự tăng dần mới đúng. Lúc đầu thím ấy đã sort cái a theo thứ tự giảm dần. Sau đó add vào cái multimap thì sẽ ra được key tăng dần, trùng key thì giảm dần. Ngược lại hoàn toàn so với yêu cầu. Sau đó reverse lại để ra đúng kết quả.

@Yêu em Thu Nga CN12 ptit : Thay vì duyệt từ đầu đến cuối cái multimap rồi reverse thì thím chỉ cần duyệt ngược cái multimap là được. . Tuy nhiên cách hiện tại t thấy chưa ổn lắm. Thấy hơi rườm rà.

Cảm ơn thím :love:

snake_case · 13/9/21

Mọi người cho em hỏi là sau khi hashing rồi đẩy vào hash table theo cách separate chaining thì làm sao để từ key dò trực tiếp ra value ạ? Ví dụ ["test"]=1, em băm "test" ra rồi nhưng trong cái list tại một phần tử của bucket nó lại nhiều phần tử cùng hashed key thì chọn chọn chính xác kiểu gì qua key? :too_sad:

thuyduong2007 · 13/9/21

snake_case đã nói:
Mọi người cho em hỏi là sau khi hashing rồi đẩy vào hash table theo cách separate chaining thì làm sao để từ key dò trực tiếp ra value ạ? Ví dụ ["test"]=1, em băm "test" ra rồi nhưng trong cái list tại một phần tử của bucket nó lại nhiều phần tử cùng hashed key thì chọn chọn chính xác kiểu gì qua key?

mỗi bucket sẽ trỏ đến 1 cái list, mỗi phần từ trong list gồm {key, value}. duyệt hết cái list, compare key, lấy ra phần tử có chứa key cần tìm.

_Gia_Cat_Luong_ · 13/9/21

snake_case đã nói:
Mọi người cho em hỏi là sau khi hashing rồi đẩy vào hash table theo cách separate chaining thì làm sao để từ key dò trực tiếp ra value ạ? Ví dụ ["test"]=1, em băm "test" ra rồi nhưng trong cái list tại một phần tử của bucket nó lại nhiều phần tử cùng hashed key thì chọn chọn chính xác kiểu gì qua key?

Duyệt qua từng cái, kiểm tra equal thôi fen

snake_case · 13/9/21

thuyduong2007 đã nói:
mỗi bucket sẽ trỏ đến 1 cái list, mỗi phần từ trong list gồm {key, value}. duyệt hết cái list, compare key, lấy ra phần tử có chứa key cần tìm.

_Gia_Cat_Luong_ đã nói:
Duyệt qua từng cái, kiểm tra equal thôi fen

Trường hợp mình chỉ có key thôi ý bác mà em search mãi google không ra :beat_brick:

cuc gach · 13/9/21

snake_case đã nói:
Trường hợp mình chỉ có key thôi ý bác mà em search mãi google không ra

Bác hash key ra để tìm bucket. Cái bucket đó trỏ đến linked list rồi so sánh key cần tìm lần lượt với các node trong list, nếu trùng thì trả về value.

snake_case · 13/9/21

cuc gach đã nói:
Bác hash key ra để tìm bucket. Cái bucket đó trỏ đến linked list rồi so sánh key cần tìm lần lượt với các node trong list, nếu trùng thì trả về value.

Ý mình là có cách nào để node chỉ chứa dữ liệu thôi mà từ key vẫn tìm được ra không? Mình mới dấn thân vào nên hỏi hơi ngu ngốc :cry:

_Gia_Cat_Luong_ · 13/9/21

snake_case đã nói:
Ý mình là có cách nào để node chỉ chứa dữ liệu thôi mà từ key vẫn tìm được ra không? Mình mới dấn thân vào nên hỏi hơi ngu ngốc

Vẫn k hiểu câu hỏi fen ơi, hay fen cho vd đc k ?

snake_case · 13/9/21

_Gia_Cat_Luong_ đã nói:
Vẫn k hiểu câu hỏi fen ơi, hay fen cho vd đc k ?

Mình có bộ key-value như sau ("abc", "85") mình muốn đưa duy nhất value vào trong hash table dùng separate chaining. Có cách nào sau khi hash thằng abc mà tìm thẳng được giá trị 85 mà không cần duyệt cái list ở vị trí số [1] kia không?

thuyduong2007 · 13/9/21

snake_case đã nói:
Mình có bộ key-value như sau ("abc", "85") mình muốn đưa duy nhất value vào trong hash table dùng separate chaining. Có cách nào sau khi hash thằng abc mà tìm thẳng được giá trị 85 mà không cần duyệt cái list ở vị trí số [1] kia không?Xem tệp đính kèm 763699

không nhé bạn, kiểu gì cũng phải lưu lại cả key và value rồi duyệt và so sánh

onib18 · 13/9/21

snake_case đã nói:
Mình có bộ key-value như sau ("abc", "85") mình muốn đưa duy nhất value vào trong hash table dùng separate chaining. Có cách nào sau khi hash thằng abc mà tìm thẳng được giá trị 85 mà không cần duyệt cái list ở vị trí số [1] kia không?Xem tệp đính kèm 763699

Về cơ bản nếu bạn dùng separate chaining thì nó đã là kỹ thuật dùng một danh sách tại một index để giải quyết collision rồi, nên mong muốn của bạn không được nếu áp dụng separate chaining.

Khi dùng hash table thì hash value của key dùng để đánh dấu index, cái bảng lưu index của bạn có kích thước giới hạn và nhỏ hơn số lượng các "biến thể" key có thể có nên sẽ xảy ra tình trạng collision.

Giả sự key chỉ là tập các ký tự a..z và đội dài 7 thì đã có 8 tỷ giá trị key khác nhau, bạn không muốn làm một bảng index có 8 tỷ phần tử thì sẽ chấp nhận việc có một số key có cùng hash value -> khi đó xảy ra collision thì sẽ tiếp tục lấy giá trị của key so sánh tiếp để tìm ra value mong muốn -> cần duyệt list hoặc bucket

Nếu bạn không muốn duyệt như vậy có thể tìm hiểu một số phương pháp như hash nhiều lần, tăng kích thước bảng index lên để lưu để khử collision... nhưng chi phí khi đó có thể còn tốn kém hơn phương pháp separate chaining

thuyduong2007 · 14/9/21

onib18 đã nói:
Về cơ bản nếu bạn dùng separate chaining thì nó đã là kỹ thuật dùng một danh sách tại một index để giải quyết collision rồi, nên mong muốn của bạn không được nếu áp dụng separate chaining.

Khi dùng hash table thì hash value của key dùng để đánh dấu index, cái bảng lưu index của bạn có kích thước giới hạn và nhỏ hơn số lượng các "biến thể" key có thể có nên sẽ xảy ra tình trạng collision.

Giả sự key chỉ là tập các ký tự a..z và đội dài 7 thì đã có 8 tỷ giá trị key khác nhau, bạn không muốn làm một bảng index có 8 tỷ phần tử thì sẽ chấp nhận việc có một số key có cùng hash value -> khi đó xảy ra collision thì sẽ tiếp tục lấy giá trị của key so sánh tiếp để tìm ra value mong muốn -> cần duyệt list hoặc bucket

Nếu bạn không muốn duyệt như vậy có thể tìm hiểu một số phương pháp như hash nhiều lần, tăng kích thước bảng index lên để lưu để khử collision... nhưng chi phí khi đó có thể còn tốn kém hơn phương pháp separate chaining

Về lý thuyết thì hàm hash là quy một tập trong không gian vô hạn về 1 tập trong không gian hữu hạn nên không thể tạo ra một hàm hash tổng quát mà k có collision.
Còn những cách trên bạn nói để khử collision chỉ áp dụng được khi input bị giới hạn.

longvatrong111 · 18/9/21

Các thím cho em hỏi chút, có ai bị tình trạng làm 1 bài xong gặp lại thì quên cách giải không?

Nay em vừa thi leetcode, bài 3 giống hệt 1 bài đã xuất hiện trên trang này, mà không tài nào nhớ nổi cách giải.
Mở lại solution của chính mình cũng không hiểu code, đành phải copy paste, may mà độ tương đồng là 99%, không ngờ bọn nó ra đề cũng tệ.

Coffe_Bên_Lề · 18/9/21

longvatrong111 đã nói:
Các thím cho em hỏi chút, có ai bị tình trạng làm 1 bài xong gặp lại thì quên cách giải không?

Nay em vừa thi leetcode, bài 3 giống hệt 1 bài đã xuất hiện trên trang này, mà không tài nào nhớ nổi cách giải.
Mở lại solution của chính mình cũng không hiểu code, đành phải copy paste, may mà độ tương đồng là 99%, không ngờ bọn nó ra đề cũng tệ.

Chung quy đều dựa trên cách giải hết thím, chỉ khác là cái mệnh đề thôi :LOL:

và hướng đặt vấn đề thôi, nếu muốn thím thử nhảy qua sân bọn codeforces ấy, bên đó khắc nghiệt hơn nhiều

nashwade · 19/9/21

longvatrong111 đã nói:
Các thím cho em hỏi chút, có ai bị tình trạng làm 1 bài xong gặp lại thì quên cách giải không?

Nay em vừa thi leetcode, bài 3 giống hệt 1 bài đã xuất hiện trên trang này, mà không tài nào nhớ nổi cách giải.
Mở lại solution của chính mình cũng không hiểu code, đành phải copy paste, may mà độ tương đồng là 99%, không ngờ bọn nó ra đề cũng tệ.

Bình thường thím ơi. Luyện khả năng suy nghĩ và tư duy chứ không phải luyện khả năng ghi nhớ bài

thuyduong2007 · 19/9/21

longvatrong111 đã nói:
Các thím cho em hỏi chút, có ai bị tình trạng làm 1 bài xong gặp lại thì quên cách giải không?

Nay em vừa thi leetcode, bài 3 giống hệt 1 bài đã xuất hiện trên trang này, mà không tài nào nhớ nổi cách giải.
Mở lại solution của chính mình cũng không hiểu code, đành phải copy paste, may mà độ tương đồng là 99%, không ngờ bọn nó ra đề cũng tệ.

Cái này bt mà. Chủ yếu là luyện về cách tiếp cận, giải quyết bài toán thôi. Chứ đâu ai luyện để nhớ đề làm gì.

.
Mà chuyện đọc lại code của mình không hiểu cũng là điều bình thường. Nhiều khi còn nghĩ sao ngày xưa mình code gà vậy, :beat_brick:

. Nhưng việc thấy code lúc trước của mình cùi bắp cũng là một dấu hiệu tốt, chứng tỏ mình đã tiến bộ.

longvatrong111 · 19/9/21

thuyduong2007 đã nói:
Cái này bt mà. Chủ yếu là luyện về cách tiếp cận, giải quyết bài toán thôi. Chứ đâu ai luyện để nhớ đề làm gì. .
Mà chuyện đọc lại code của mình không hiểu cũng là điều bình thường. Nhiều khi còn nghĩ sao ngày xưa mình code gà vậy, . Nhưng việc thấy code lúc trước của mình cùi bắp cũng là một dấu hiệu tốt, chứng tỏ mình đã tiến bộ.

Gặp bài mới giống 99%, đọc lại code cũ mới 3 tuần mà ko hiểu + không nghĩ ra solution :beat_shot:

Copy paste sửa 1 chút thì ok.
2 bài đây thím:
https://leetcode.com/problems/maximum-profit-in-job-scheduling/
https://leetcode.com/problems/maximum-earnings-from-taxi/
Bài sau là đề thi biweekly hôm qua, giống 99% bài cũ.
Nên em hoang mang sợ cách cày kiểu làm hết bài này đến bài khác không hiệu quả.

Fireknight · 19/9/21

longvatrong111 đã nói:
Gặp bài mới giống 99%, đọc lại code cũ mới 3 tuần mà ko hiểu + không nghĩ ra solution
Copy paste sửa 1 chút thì ok.
2 bài đây thím:
https://leetcode.com/problems/maximum-profit-in-job-scheduling/
https://leetcode.com/problems/maximum-earnings-from-taxi/
Bài sau là đề thi biweekly hôm qua, giống 99% bài cũ.
Nên em hoang mang sợ cách cày kiểu làm hết bài này đến bài khác không hiệu quả.

Thím thử suy nghĩ lâu hơn trước khi xem lời giải sẽ dễ nhớ hơn

thảo luận [Học Tập] Topic thuật toán

Member

Member

Member

Senior Member

Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này