Notes

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; } };

tags: Math,backtracking,LeetCode101 Backtracking and stack overflow Intuition: We can abstract all the operations to a Tree, then apply DFS on it. For example: startValue=2, target=3, the tree looks like: /* 2 /\ / \ / \ 1(-1) 4(x2) /\ /\--+ / \ / \ 0(-1) 2(x2) 3(-1) 8(x2) */ class Solution { public: int brokenCalc(int startValue, int target) { unordered_set<int> visited; return backtracking(0, startValue, target, visited); } int backtracking(int count, int val, int target, unordered_set<int> & visited) { if (val == target) { return count; } if (visited.find(val) != visited.end()) { return -1; } int left = -1, right = -1; count++; visited.insert(val); if (val > 0) { left = backtracking(count, val - 1, target, visited); } if (val <= target * 2) { right = backtracking(count, val * 2, target, visited); } visited.erase(val); if (left != -1 && right != -1) { return min(left, right); } else if (left != -1) { return left; } return right; } }; Change target to startValue class Solution { public: int brokenCalc(int startValue, int target) { int r = 0; while (target > startValue) { target = target % 2 > 0 ? target + 1 : target / 2; r++; } return r + startValue - target; } };

tags: String,LeetCode101,Tricky Initialize a string that fills 'a' in it. Then we turn it to the expected string from end to start. The maximal value of each position in the string is 26. If we start from all elements is 'a' in the string. Then the represent value of the string is n. If it’s not equal to k. Then we need turn the last character of string to r = k - n. Two cases must be handled: ...

tags: Math,Hash Table,LeetCode101 class Solution { public: string intToRoman(int num) { vector<string> roman {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; vector<int> integers {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }; string r; int times = 0; for (int i = 0; i < integers.size(); ++i) { if (num >= integers[i]) { times = num / integers[i]; num -= times * integers[i]; for (int j = times; j > 0; --j) { r.append(roman[i]); } } } return r; } };