Common Algo

1. 贪心算法 (Greedy Algorithm)

核心思想: 每一步都做出局部最优选择，希望最终得到全局最优解。

适用场景: 具有「最优子结构」和「贪心选择性质」的问题。

示例：活动选择问题

#include <vector>
#include <algorithm>

struct Activity {
    int start, end;
};

// 按结束时间排序
int maxActivities(std::vector<Activity>& acts) {
    std::sort(acts.begin(), acts.end(), 
        [](const Activity& a, const Activity& b) {
            return a.end < b.end;
        });
    
    int count = 1;
    int last_end = acts[0].end;
    
    for (size_t i = 1; i < acts.size(); i++) {
        if (acts[i].start >= last_end) {
            count++;
            last_end = acts[i].end;
        }
    }
    return count;
}

示例：区间调度问题（最少会议室）

#include <vector>
#include <queue>
#include <algorithm>

int minMeetingRooms(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return 0;
    
    std::sort(intervals.begin(), intervals.end());
    
    // 最小堆，存储每个会议室的结束时间
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    pq.push(intervals[0][1]);
    
    for (size_t i = 1; i < intervals.size(); i++) {
        // 最早结束的会议已经结束
        if (intervals[i][0] >= pq.top()) {
            pq.pop();
        }
        pq.push(intervals[i][1]);
    }
    return pq.size();
}

---

2. 动态规划 (Dynamic Programming)

核心思想: 将复杂问题分解为子问题，存储子问题的解以避免重复计算。

关键要素: 状态定义、状态转移方程、初始状态、边界条件。

示例：斐波那契数列（记忆化搜索）

#include <vector>

// 自顶向下：记忆化搜索
int fibMemo(int n, std::vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

int fib(int n) {
    std::vector<int> memo(n + 1, -1);
    return fibMemo(n, memo);
}

示例：0/1 背包问题

#include <vector>
#include <algorithm>

// dp[i][w] = 前i个物品，容量为w时的最大价值
int knapsack01(const std::vector<int>& weight,
               const std::vector<int>& value, 
               int capacity) {
    int n = weight.size();
    std::vector<std::vector<int>> dp(n + 1, 
        std::vector<int>(capacity + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (weight[i-1] <= w) {
                dp[i][w] = std::max(
                    dp[i-1][w],                          // 不选
                    dp[i-1][w - weight[i-1]] + value[i-1]  // 选
                );
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][capacity];
}

// 空间优化版本
int knapsack01Opt(const std::vector<int>& weight,
                  const std::vector<int>& value, 
                  int capacity) {
    std::vector<int> dp(capacity + 1, 0);
    
    for (size_t i = 0; i < weight.size(); i++) {
        // 倒序遍历，避免重复计算
        for (int w = capacity; w >= weight[i]; w--) {
            dp[w] = std::max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[capacity];
}

示例：最长公共子序列 (LCS)

#include <string>
#include <vector>

int longestCommonSubsequence(const std::string& text1, 
                              const std::string& text2) {
    int m = text1.size(), n = text2.size();
    std::vector<std::vector<int>> dp(m + 1, 
        std::vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

示例：最长递增子序列 (LIS)

#include <vector>
#include <algorithm>

// O(n^2) 解法
int lengthOfLIS_n2(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> dp(n, 1);
    int maxLen = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
        maxLen = std::max(maxLen, dp[i]);
    }
    return maxLen;
}

// O(n log n) 解法：二分优化
int lengthOfLIS(const std::vector<int>& nums) {
    std::vector<int> tails;
    
    for (int num : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

---

3. 分治算法 (Divide and Conquer)

核心思想: 将问题分解为若干子问题，递归解决后合并结果。

示例：归并排序

#include <vector>

void merge(std::vector<int>& nums, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];
    
    for (int p = 0; p < k; p++) {
        nums[left + p] = temp[p];
    }
}

void mergeSort(std::vector<int>& nums, int left, int right) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}

示例：快速排序

#include <vector>
#include <algorithm>

int partition(std::vector<int>& nums, int low, int high) {
    int pivot = nums[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (nums[j] <= pivot) {
            i++;
            std::swap(nums[i], nums[j]);
        }
    }
    std::swap(nums[i + 1], nums[high]);
    return i + 1;
}

void quickSort(std::vector<int>& nums, int low, int high) {
    if (low < high) {
        int pi = partition(nums, low, high);
        quickSort(nums, low, pi - 1);
        quickSort(nums, pi + 1, high);
    }
}

示例：计算逆序对数量

#include <vector>

long long mergeCount(std::vector<int>& nums, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    long long invCount = 0;
    
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
            invCount += (mid - i + 1);  // 左边剩余元素都大于nums[j]
        }
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];
    
    for (int p = 0; p < k; p++) {
        nums[left + p] = temp[p];
    }
    return invCount;
}

long long countInversions(std::vector<int>& nums, int left, int right) {
    if (left >= right) return 0;
    
    int mid = left + (right - left) / 2;
    long long count = 0;
    count += countInversions(nums, left, mid);
    count += countInversions(nums, mid + 1, right);
    count += mergeCount(nums, left, mid, right);
    return count;
}

---

4. 回溯算法 (Backtracking)

核心思想: 通过尝试所有可能的候选解来找出所有解，并在发现候选解不满足条件时回退。

示例：全排列

#include <vector>

void backtrack(std::vector<int>& nums, int start,
               std::vector<std::vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    
    for (int i = start; i < nums.size(); i++) {
        std::swap(nums[start], nums[i]);
        backtrack(nums, start + 1, result);
        std::swap(nums[start], nums[i]);  // 回溯
    }
}

std::vector<std::vector<int>> permute(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    backtrack(nums, 0, result);
    return result;
}

示例：N 皇后问题

#include <vector>
#include <string>

class Solution {
    std::vector<std::vector<std::string>> result;
    
    bool isValid(std::vector<std::string>& board, 
                 int row, int col) {
        int n = board.size();
        // 检查列
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // 检查左上对角线
        for (int i = row - 1, j = col - 1; 
             i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // 检查右上对角线
        for (int i = row - 1, j = col + 1; 
             i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
    
    void backtrack(std::vector<std::string>& board, int row) {
        if (row == board.size()) {
            result.push_back(board);
            return;
        }
        
        int n = board[row].size();
        for (int col = 0; col < n; col++) {
            if (!isValid(board, row, col)) continue;
            
            board[row][col] = 'Q';
            backtrack(board, row + 1);
            board[row][col] = '.';  // 撤销选择
        }
    }
    
public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        std::vector<std::string> board(n, std::string(n, '.'));
        backtrack(board, 0);
        return result;
    }
};

示例：子集生成

#include <vector>

void backtrack(const std::vector<int>& nums, int start,
               std::vector<int>& path,
               std::vector<std::vector<int>>& result) {
    result.push_back(path);  // 每个节点都是一个子集
    
    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, result);
        path.pop_back();  // 回溯
    }
}

std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    std::vector<int> path;
    backtrack(nums, 0, path, result);
    return result;
}

---

5. 二分查找 (Binary Search)

核心思想: 在有序数组中，每次将搜索区间减半。

时间复杂度: O(log n)

示例：基础二分查找

#include <vector>

int binarySearch(const std::vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;  // 未找到
}

示例：查找左边界

#include <vector>

int findLeftBound(const std::vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // 检查边界
    if (left >= nums.size() || nums[left] != target) {
        return -1;
    }
    return left;
}

示例：查找右边界

#include <vector>

int findRightBound(const std::vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // 检查边界
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return right;
}

示例：二分答案（寻找平方根）

#include <algorithm>

int mySqrt(int x) {
    if (x < 2) return x;
    
    int left = 1, right = x / 2;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        long long square = (long long)mid * mid;
        
        if (square == x) {
            return mid;
        } else if (square < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;  // right 是最后一个满足 mid^2 <= x 的值
}

---

6. 双指针技术

示例：快慢指针（检测链表环）

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode *head) {
    if (!head || !head->next) return false;
    
    ListNode *slow = head;
    ListNode *fast = head->next;
    
    while (fast && fast->next) {
        if (slow == fast) return true;
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}

示例：滑动窗口（最小覆盖子串）

#include <string>
#include <unordered_map>
#include <climits>

std::string minWindow(std::string s, std::string t) {
    std::unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0;
    int start = 0, len = INT_MAX;
    
    while (right < s.size()) {
        char c = s[right++];
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }
        
        while (valid == need.size()) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            char d = s[left++];
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    return len == INT_MAX ? "" : s.substr(start, len);
}

---

算法选择指南

问题类型	推荐算法	典型示例
最优子结构 + 贪心选择	贪心	活动选择、Huffman编码
重叠子问题	动态规划	背包问题、LCS、LIS
可分解子问题	分治	归并排序、快速排序
搜索所有可能解	回溯	全排列、N皇后、子集
有序数组查找	二分查找	查找元素、查找边界
数组/字符串处理	双指针	链表环、滑动窗口

复杂度对比

算法	时间复杂度	空间复杂度	特点
贪心	因问题而异	O(1) ~ O(n)	快但不保证全局最优
动态规划	因问题而异	O(n) ~ O(n²)	保证最优，但空间开销大
分治	O(n log n)	O(log n) ~ O(n)	递归实现简洁
回溯	指数级	O(n)	枚举所有可能
二分查找	O(log n)	O(1)	要求有序