Notes

tags: Learning English,读书笔记 source: Joseph Devlin. How to Speak and Write Correctly, 2007. http://archive.org/details/how_to_speak_and_write_correctly_librivox. I found this book in my Kindle on the subway to work this morning. And remembered that I downloaded it free from the Kindle store years ago. For some reasons, maybe my English was not good enough to read it, I haven’t read it yet. After read a little, I think it’s prefect for me for now. The reasons is: ...

tags: Data Structures,Tree WHAT is a heap? Tree-based data structure which is essentially an almost complete tree that statifies the heap property. Max heap For any given node C, if P is a parent node of C, then the key(the value) of P is greater than or equal to the key of C. Min heap The P is less than or equal to the key C. When to use a heap? Priority queue. Heapsort.

tags: Algorithm

tags: Hash Table,LeetCode101,Sorting,Two Pointers Intuition with HashMap class Solution { public: int numRescueBoats(vector<int>& people, int limit) { unordered_map<int, int> cntOfWeights; for (auto iter = people.begin(); iter != people.end(); ++iter) { cntOfWeights[*iter]++; } int r = 0; for (int i = 0; i < people.size(); i++) { if (cntOfWeights[people[i]] == 0) { continue; } cntOfWeights[people[i]]--; for (int j = (limit - people[i]); j > 0; --j) { if (cntOfWeights.find(j) != cntOfWeights.end() && cntOfWeights[j] > 0) { cntOfWeights[j]--; break; } } r++; } return r; } }; Sorting and Two Pointers class Solution { public: int numRescueBoats(vector<int>& people, int limit) { int i = 0; int j = people.size() - 1; // heaviest go first sort(people.rbegin(), people.rend()); for (; i <= j; i++) { if (people[i] + people[j] <= limit) j--; } return i; } };