Common Algorithm Patterns
Common Algorithm Patterns Each pattern has only two parts: Explanation + Code Framework. 1) Framework Thinking (Traversal First) Explanation Most problems are traversal problems in disguise: arrays, linked lists, trees, graphs. Identify the data structure first, then pick traversal order, then fill business logic into the skeleton. Code Framework 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include <vector> using namespace std; struct ListNode { int val; ListNode* next; }; struct TreeNode { int val; TreeNode* left; TreeNode* right; }; void processValue(int x) { // TODO: business logic (void)x; } void traverseArray(const vector<int>& nums) { for (int i = 0; i < (int)nums.size(); ++i) { processValue(nums[i]); } } void traverseList(ListNode* head) { for (ListNode* p = head; p != nullptr; p = p->next) { processValue(p->val); } } void traverseTree(TreeNode* root) { if (root == nullptr) return; // Pre-order processValue(root->val); traverseTree(root->left); traverseTree(root->right); // Post-order } 2) Binary Search (Shrink Search Space) Explanation Use binary search when monotonicity exists. The key is consistency: interval definition + boundary update rules. ...