Skip to main content

力扣算法编程技巧

1. 常用算法模板​

1.二分查找通用模板​

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int l = 1, r = n - 1; // 也就是 n-1，数值范围

        while (l < r) { // 【模版核心：不加等号】
            int mid = l + (r - l) / 2; // 先写标准的向下取整
            
            int cnt = 0;
            for (int x : nums) {
                if (x <= mid) cnt++;
            }

            // 【判定逻辑】
            if (cnt > mid) {
                // [1, mid] 太挤了，重复数就在这里面
                // mid 也有可能是答案，所以不能 -1，只能 r = mid
                r = mid; 
            } else {
                // [1, mid] 很空，重复数肯定在右边 [mid+1, n]
                // mid 肯定不是，扔掉，所以 l = mid + 1
                l = mid + 1;
            }
        }
        // 循环结束时 l == r，就是答案
        return l;
    }
};

​ 这里直接不加等号，结束时，l和r在一个位置，l就是要找的答案的坐标。

​ 然后考虑mid，如果mid可能是答案，则更新left或者right的时候可以保留，即让left或right=mid，否则，就扔掉。

​ 为什么写 mid=l + (r - l) / 2，而不是(l+r)/2，主要考虑到，l+r可能会导致int溢出。

2.快排通用模板​

void quick_sort(vector<int>& q,int l, int r)
{
    //1.递归终止条件
    if(l>=r) return;
    //2. 初始化:i,j往两侧外扩一格，pivot选中间
    //为什么要外扩，因为下面用的是 do-while，先右外向内跳一步
    int i=l-1,j=r+1;
    int pivot=q[(l+r) >> 1] //选中间作为基准，防止退化，尽量每次排序左右两边的数都是差不多的，>>是二进制右移操作，相当于除以2
       
    //核心分区
        while(i<j)
        {
            do i++;while(q[i]<pivot) // 找左边>=pivot的
            do j--;while(q[j]>pivot) // 找右边<=pivot的
            
            // 只有i<j才交换，防止交错后还在换
            if (i<j) swap(q[i],q[j]);
        }
   	//4. 递归
    //关键点，用j分界
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

明白了，你是希望每个工具的标题用 Markdown 的 ## 或 ### 直接在代码块外面显示，而不是在代码里加注释。我帮你改成这种格式，using namespace std; 保留，自定义降序也加上了。

3. SWAP - 交换两个变量​

#include <iostream>
#include <utility>  // swap

using namespace std;

int main() {
    int a = 5, b = 10;
    swap(a, b);
    cout << "a = " << a << ", b = " << b << "\n";
    return 0;
}

4. SORT - 排序数组或容器（升序/降序）​

#include <iostream>
#include <algorithm> // sort
#include <vector>

using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 3};

    // 升序排序
    sort(v.begin(), v.end());
    cout << "升序: ";
    for(int x : v) cout << x << " ";
    cout << "\n";

    // 自定义降序排序
    sort(v.begin(), v.end(), [](int a, int b){ return a > b; });
    cout << "降序: ";
    for(int x : v) cout << x << " ";
    cout << "\n";

    return 0;
}

5. REVERSE - 翻转数组或容器​

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    reverse(v.begin(), v.end());
    for(int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

6. MAX / MIN - 求最大值或最小值​

#include <iostream>
#include <algorithm> // max, min

using namespace std;

int main() {
    int a = 10, b = 20;
    cout << "max = " << max(a, b) << ", min = " << min(a, b) << "\n";
    return 0;
}

7. ACCUMULATE - 求和​

#include <iostream>
#include <numeric> // accumulate
#include <vector>

using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    int sum = accumulate(v.begin(), v.end(), 0); // 初始值 0
    cout << "sum = " << sum << "\n";
    return 0;
}

8. COUNT - 统计元素出现次数​

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v = {1, 2, 2, 3, 2, 4};
    int cnt = count(v.begin(), v.end(), 2);
    cout << "2 appears " << cnt << " times\n";
    return 0;
}

9. FIND - 查找元素​

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    auto it = find(v.begin(), v.end(), 3);
    if(it != v.end()) cout << "Found 3 at index " << (it - v.begin()) << "\n";
    else cout << "3 not found\n";
    return 0;
}

10. LOWER_BOUND / UPPER_BOUND - 二分查找范围​

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v = {1, 2, 2, 3, 4, 5};
    sort(v.begin(), v.end()); // 需要先排序
    auto lb = lower_bound(v.begin(), v.end(), 2); // 第一个 >= 2
    auto ub = upper_bound(v.begin(), v.end(), 2); // 第一个 > 2
    cout << "lower_bound = " << (lb - v.begin()) << ", upper_bound = " << (ub - v.begin()) << "\n";
    return 0;
}

11. INT_MIN / INT_MAX - 整型最小值与最大值​

#include <iostream>
#include <climits>  // INT_MIN, INT_MAX

using namespace std;

int main() {
    int minVal = INT_MIN;
    int maxVal = INT_MAX;

    cout << "INT_MIN = " << minVal << "\n";
    cout << "INT_MAX = " << maxVal << "\n";

    return 0;
}

2. 线性扫描艺术：滑动窗口技术（Sliding Window）​

2.1 理论基础：从暴力递归到线性扫描​

滑动窗口（Sliding Window）技术本质上是对暴力枚举法的极致优化。在处理数组或字符串的子序列问题时，暴力解法往往需要两层嵌套循环来遍历所有可能的子区间，导致时间复杂度高达 $O(N^2)$ 甚至 $O(N^3)$。滑动窗口通过维护一个动态的“视窗”，利用数据在时间序列上的连续性，将嵌套循环转化为单次遍历，从而将复杂度降维至 $O(N)$ 4。

其核心洞察在于“增量计算”：当窗口从位置 $[i, j]$ 滑动到 $[i+1, j+1]$ 时，中间的重叠部分 $[i+1, j]$ 的状态无需重新计算，只需扣除移出元素 $i$ 的影响并增加移入元素 $j+1$ 的贡献即可。这种思想不仅适用于求和，更广泛应用于计数、极值查找及哈希状态维护。

2.2 固定窗口模式（Fixed Window）​

固定窗口是滑动窗口的最基础形式，通常用于解决“寻找长度为 $k$ 的最佳子数组”类问题。

2.2.1 算法逻辑与C++模板​

在固定窗口中，窗口的大小 $k$ 是恒定的。我们首先初始化第一个长度为 $k$ 的窗口，随后同步移动左右边界。

通用C++模板：

C++

/* 
 * 固定窗口模板
 * 场景：求解长度为 k 的子数组的最大和/平均值/特定属性
 * 时间复杂度：O(N)
 * 空间复杂度：O(1)
 */
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>

using namespace std;

int fixedSlidingWindow(const vector<int>& nums, int k) {
    // 边界条件防御
    if (nums.size() < k) return -1; 

    // 1. 初始化阶段：计算第一个窗口的状态
    long long current_window_val = 0;
    for (int i = 0; i < k; ++i) {
        current_window_val += nums[i];
    }
    
    long long max_val = current_window_val;

    // 2. 滑动阶段：从第 k 个元素开始，每次右移一位
    // i 代表新进入窗口的元素索引 (right edge)
    // i - k 代表即将移出窗口的元素索引 (left edge)
    for (size_t i = k; i < nums.size(); ++i) {
        // 增量更新：减去左边离开的，加上右边进入的
        current_window_val += nums[i] - nums[i - k];
        
        // 维护最优解
        if (current_window_val > max_val) {
            max_val = current_window_val;
        }
    }

    return static_cast<int>(max_val);
}

2.2.2 案例解析：找到字符串中所有字母异位词​

问题背景：给定两个字符串 s 和 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

技术难点：需要在滑动过程中实时判断两个子串的字符频次是否一致。

深度实现：

C++

/*
 * LeetCode 438. Find All Anagrams in a String
 * 方法：固定窗口 + 数组哈希
 */
vector<int> findAnagrams(string s, string p) {
    int s_len = s.length(), p_len = p.length();
    if (s_len < p_len) return {};

    vector<int> result;
    // 使用大小为26的数组代替哈希表，利用C++数组的高效访问
    vector<int> p_count(26, 0);
    vector<int> window_count(26, 0);

    // 1. 预处理目标串 p 和第一个窗口
    for (int i = 0; i < p_len; ++i) {
        p_count[p[i] - 'a']++;
        window_count[s[i] - 'a']++;
    }

    // 检查第一个窗口
    if (p_count == window_count) {
        result.push_back(0);
    }

    // 2. 开始滑动
    for (int i = p_len; i < s_len; ++i) {
        // 移入右侧字符 s[i]
        window_count[s[i] - 'a']++;
        // 移出左侧字符 s[i - p_len]
        window_count[s[i - p_len] - 'a']--;

        // 比较两个频率数组（C++ vector 重载了 == 运算符，比较是 O(26) 即 O(1)）
        if (p_count == window_count) {
            result.push_back(i - p_len + 1);
        }
    }

    return result;
}

分析：此例展示了固定窗口与状态压缩（频率数组）的结合。由于字符集有限（26个字母），vector的比较操作被视为常数时间，整体复杂度严格保持在 $O(N)$。

2.3 可变窗口模式（Variable Window）​

可变窗口是更高级的形态，通常涉及两个指针 left 和 right。right 主动扩张以寻找可行解，left 被动收缩以寻找最优解（最短）或恢复合法性（最长） 5。

2.3.1 伸缩策略逻辑​

可变窗口通常遵循以下“虫取法”（Caterpillar Method）逻辑：

  1. 扩张（Expand）：增加 right 指针，将新元素纳入窗口，更新窗口状态。
  2. 判断（Check）：检查窗口状态是否满足特定条件（如无重复字符、总和大于Target等）。
  3. 收缩（Shrink）：
    • 若求最长子数组：当窗口不满足条件时，通过移动 left 收缩，直到恢复满足条件。
    • 若求最短子数组：当窗口满足条件时，尝试移动 left 收缩以寻找更短的可行解，直到不再满足条件。

通用C++模板：

C++

/*
 * 可变窗口通用模板
 * 适用于：最长/最短/计数类子数组问题
 */
int variableSlidingWindow(vector<int>& nums) {
    int n = nums.size();
    int left = 0, right = 0;
    int ans = 0; // 根据问题初始化（0或INT_MAX）
    
    // 定义维护窗口状态的数据结构（如Sum, Hash, Count）
    // long long current_sum = 0;

    while (right < n) {
        // A. 移入元素：更新状态
        int val_in = nums[right];
        // current_sum += val_in;

        // B. 收缩窗口逻辑
        // Case 1: 寻找最长合法子窗口 -> 当窗口非法时收缩
        // while (窗口状态非法) {
        //     int val_out = nums[left];
        //     current_sum -= val_out;
        //     left++;
        // }
        // ans = max(ans, right - left + 1);

        // Case 2: 寻找最短合法子窗口 -> 当窗口合法时尝试收缩
        // while (窗口状态合法) {
        //     ans = min(ans, right - left + 1);
        //     int val_out = nums[left];
        //     current_sum -= val_out;
        //     left++;
        // }

        right++; // 继续扩张
    }
    return ans;
}

2.3.2 案例解析：无重复字符的最长子串​

问题：LeetCode 3. Longest Substring Without Repeating Characters

策略：寻找最长合法窗口。当发现重复字符时，窗口非法，需收缩左边界直到重复字符被排除。

深度实现：

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 使用数组模拟哈希表优化性能（ASCII 128）
        // index 记录字符上一次出现的位置，避免逐步收缩，实现“跳跃式”收缩
        vector<int> last_seen(128, -1); 
        
        int n = s.length();
        int left = 0;
        int max_len = 0;
        
        for (int right = 0; right < n; ++right) {
            char current_char = s[right];
            
            // 如果当前字符之前出现过，并且出现在当前窗口内（>= left）
            if (last_seen[current_char] >= left) {
                // 直接将 left 跳到重复字符的下一位
                left = last_seen[current_char] + 1;
            }
            
            // 更新当前字符的最新位置
            last_seen[current_char] = right;
            
            // 更新结果
            max_len = max(max_len, right - left + 1);
        }
        
        return max_len;
    }
};

洞察：此实现展示了滑动窗口的一个高级优化——跳跃式窗口。标准模板中的 while 循环逐步收缩虽然也是 $O(N)$，但在特定场景下（如知道重复字符的具体索引），我们可以直接将 left 指针跳跃到重复位置的右侧，从而大幅减少指令数，提升常数级性能。

3. 指针的舞蹈：双指针策略（Two Pointers）​

3.1 双指针的多维形态​

双指针技术虽然简单，却是处理有序结构和链表问题的核心手段。它通过两个指针协同移动，将搜索空间从二维矩阵（所有可能的配对）压缩至一维路径 7。

主要形态包括：

  1. 对撞指针（Collision Pointers）：左右夹逼，常用于有序数组求和（2Sum, 3Sum）或反转操作。
  2. 快慢指针（Fast & Slow Pointers）：一快一慢，用于链表找环（Floyd判圈法）、寻找中点或数组原地去重。
  3. 分离双指针：处理两个独立序列，如归并排序的合并步骤。

3.2 对撞指针与K数之和​

对撞指针利用了序列的单调性。在有序数组中，如果 nums[left] + nums[right] > target，根据单调性，nums[right] 与任何 i > left 的数相加必然也大于 target，因此可以安全地丢弃 nums[right]（即 right--）。这种剪枝逻辑是双指针高效性的数学基础。

3.2.1 通用模板与去重技巧​

C++

/*
 * 对撞指针模板：有序数组两数之和
 * 包含去重逻辑（适用于 3Sum 等问题）
 */
vector<vector<int>> twoSumTarget(vector<int>& nums, int start, int target) {
    int left = start;
    int right = nums.size() - 1;
    vector<vector<int>> res;
    
    while (left < right) {
        int sum = nums[left] + nums[right];
        int left_val = nums[left];
        int right_val = nums[right];
        
        if (sum < target) {
            while (left < right && nums[left] == left_val) left++; // 加速跳过重复
        } else if (sum > target) {
            while (left < right && nums[right] == right_val) right--; // 加速跳过重复
        } else {
            res.push_back({left_val, right_val});
            // 找到一组解后，两边同时收缩并去重
            while (left < right && nums[left] == left_val) left++;
            while (left < right && nums[right] == right_val) right--;
        }
    }
    return res;
}

3.2.2 案例解析：盛最多水的容器​

问题：LeetCode 11. Container With Most Water

逻辑：给定高度数组，求两条线构成的容器最大容积。

核心证明：容积 $Area = (right - left) \times \min(height[left], height[right])$。如果 height[left] < height[right]，那么无论 right 如何左移，由于宽度减小且高度受限于 height[left]，新的容积不可能超过当前容积。因此，必须移动短板（left++）才有可能找到更大容积。

代码实现：

C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int max_area = 0;
        
        while (left < right) {
            int h_left = height[left];
            int h_right = height[right];
            int current_area = min(h_left, h_right) * (right - left);
            max_area = max(max_area, current_area);
            
            // 贪心策略：移动较短的那一边
            // 因为移动较长边，宽度减小，高度受限于较短边，面积必减小
            if (h_left < h_right) {
                left++;
            } else {
                right--;
            }
        }
        return max_area;
    }
};

3.3 快慢指针与链表操作​

快慢指针在链表操作中不仅是技巧，更是标准范式。

3.3.1 案例解析：环形链表检测​

问题：LeetCode 141. Linked List Cycle

原理：Floyd 判圈算法。快指针每次走两步，慢指针每次走一步。如果有环，快指针最终会追上慢指针；如果无环，快指针会到达末尾。

代码实现：

C++

/*
 * 链表节点定义
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head ||!head->next) return false;
        
        ListNode *slow = head;
        ListNode *fast = head;
        
        while (fast && fast->next) {
            slow = slow->next;       // 慢指针走一步
            fast = fast->next->next; // 快指针走两步
            
            if (slow == fast) {
                return true; // 相遇，说明有环
            }
        }
        
        return false; // 快指针到达终点，无环
    }
};

4. 栈的单调性：单调栈（Monotonic Stack）​

4.1 理论基础：寻找“下一个极值”​

单调栈是一种特殊的栈结构，其内部元素维持单调递增或递减的顺序。它专门用于解决一类特定问题：寻找数组中每个元素左边或右边第一个比它大或小的元素 8。

其核心原理是“及时止损”或“优胜劣汰”。例如，在寻找“下一个更大元素”时，如果当前元素 x 比栈顶元素 top 大，那么对于栈中更深处的元素来说，top 已经被 x “遮挡”了，top 不再可能是后续元素的“下一个更大值”，因此 top 可以被弹出。

4.2 四种变体模板总结​

单调栈主要有四种应用形态，通过调整遍历方向和比较符号来实现。

目标 (Target)栈的单调性 (Stack Property)遍历方向比较符号 (While Loop)典型应用
右边第一个更大 (Next Greater)单调递减 (Decreasing)左 -> 右nums[i] > st.top()每日温度, NGE I/II
右边第一个更小 (Next Smaller)单调递增 (Increasing)左 -> 右nums[i] < st.top()柱状图中最大矩形 (右边界)
左边第一个更大 (Prev Greater)单调递减 (Decreasing)右 -> 左nums[i] > st.top()股票跨度
左边第一个更小 (Prev Smaller)单调递增 (Increasing)右 -> 左nums[i] < st.top()柱状图中最大矩形 (左边界)

C++通用模板（Next Greater Element）：

C++

/*
 * 单调栈通用模板
 * 返回数组中每个元素右侧第一个更大元素的索引，不存在则为 -1
 */
vector<int> nextGreaterElementTemplate(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> st; // 存储索引
    
    for (int i = 0; i < n; ++i) {
        // 当当前元素破坏了栈的单调递减性时
        while (!st.empty() && nums[i] > nums[st.top()]) {
            int prev_index = st.top();
            st.pop();
            // nums[i] 就是 nums[prev_index] 的 Next Greater Element
            result[prev_index] = i; // 存储索引
            // 若需存储值：result[prev_index] = nums[i];
        }
        st.push(i);
    }
    return result;
}

4.3 经典案例深度解析​

4.3.1 每日温度 (Daily Temperatures)​

问题：LeetCode 739. Daily Temperatures

分析：这是典型的“右边第一个更大”问题。我们需要计算索引差值。

优化实现：

C++

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> answer(n, 0);
        stack<int> st; // 单调递减栈
        
        for (int i = 0; i < n; ++i) {
            // 当前温度比栈顶那天的温度高，说明 i 是栈顶那天的“升温日”
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int prev_day_index = st.top();
                st.pop();
                answer[prev_day_index] = i - prev_day_index; // 计算等待天数
            }
            st.push(i);
        }
        return answer;
    }
};

复杂度：每个元素进栈一次，出栈一次，时间复杂度严格为 $O(N)$。

4.3.2 柱状图中最大的矩形 (Largest Rectangle in Histogram)​

问题：LeetCode 84. Largest Rectangle in Histogram

挑战：这是一个Hard题目。要找到最大矩形，对于每个柱子 h，我们需要找到它左右两边第一个高度小于 h 的位置 L 和 R。那么以 h 为高度的最大矩形宽度就是 R - L - 1。

双次单调栈策略：

  1. 一次从左向右遍历，找每个柱子的 Next Smaller Element (确定右边界)。
  2. 一次从右向左遍历，找每个柱子的 Prev Smaller Element (确定左边界)。
  3. 或者更巧妙地，在一次遍历中同时确定左右边界。

一次遍历优化实现：

C++

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // 在数组尾部添加一个0，确保所有元素最后都能出栈
        heights.push_back(0); 
        int n = heights.size();
        int max_area = 0;
        stack<int> st; // 单调递增栈
        
        for (int i = 0; i < n; ++i) {
            // 当遇到一个较矮的柱子时，栈顶柱子的右边界就确定了（即当前 i）
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int h = heights[st.top()];
                st.pop();
                
                // 确定左边界：栈顶弹出后，新的栈顶就是左边第一个比它小的元素的索引
                // 如果栈为空，说明左边没有比它小的，左边界可视作 -1
                int left_bound = st.empty()? -1 : st.top();
                int width = i - left_bound - 1;
                
                max_area = max(max_area, h * width);
            }
            st.push(i);
        }
        return max_area;
    }
};

深度洞察：这里利用了哨兵技巧（Sentinel）。在末尾添加 0 强制弹栈，避免了循环结束后栈内仍有残留元素需单独处理的繁琐逻辑。这是工程化代码的常见优化手段。

5. 暴力搜索的智慧：回溯算法（Backtracking）​

5.1 状态空间树与剪枝​

回溯法（Backtracking）本质上是在一棵隐式的状态空间树（State Space Tree）上进行深度优先搜索（DFS）。它通过系统地构建候选解，并在确定某候选解无法通往有效解时“回溯”（Backtrack），即撤销上一步操作，退回到上一个状态尝试其他路径 10。

回溯法的三大要素：

  1. 路径（Path）：已经做出的选择。
  2. 选择列表（Choices）：当前状态下可以做的选择。
  3. 终止条件（Termination）：到达决策树底层，无法再做选择。

5.2 现代C++ Lambda递归模板​

传统C++回溯常需要定义辅助函数和成员变量。现代C++（C++11及以后）推荐在主函数内部定义 std::function 或利用 Lambda 表达式捕获上下文，使代码高度内聚且无需传递大量参数。

通用回溯模板：

C++

/*
 * 通用回溯模板
 * 解决全排列、组合、子集、棋盘问题
 */
void backtrackingTemplate(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> path;
    int n = nums.size();
    // 标记数组（视问题需要）
    vector<bool> used(n, false);

    // 定义递归 Lambda
    // function<void(int)> 用于兼容，C++23 可用 auto
    function<void(int)> backtrack = [&](int start_index) {
        // 1. 终止条件
        if (/* path 满足条件 */) {
            result.push_back(path);
            return; // 或继续搜索（视问题而定，如求子集则不需要return）
        }

        // 2. 遍历选择列表
        for (int i = start_index; i < n; ++i) {
            // 剪枝逻辑 (Pruning)
            if (used[i]) continue;
            // if (i > start_index && nums[i] == nums[i-1]) continue; // 排序去重剪枝

            // 3. 做选择
            path.push_back(nums[i]);
            used[i] = true;

            // 4. 进入下一层
            // 全排列传 0 (或不传start)，组合问题传 i + 1
            backtrack(i + 1); 

            // 5. 撤销选择 (回溯)
            used[i] = false;
            path.pop_back();
        }
    };

    backtrack(0);
}

5.3 经典案例：N皇后问题 (N-Queens)​

问题：LeetCode 51. N-Queens

描述：在 $N \times N$ 的棋盘上放置 $N$ 个皇后，使得它们互不攻击（不在同一行、同一列、同一斜线上）。

高效实现（位运算优化版）：

虽然可以用数组记录列、主对角线、副对角线的占用情况，但利用位运算（Bitmasking）可以将状态压缩，极大提升检查速度。

C++

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> solutions;
        vector<string> board(n, string(n, '.'));
        
        // cols, diag1 (左上-右下), diag2 (右上-左下) 使用位掩码
        // 1 表示被占用，0 表示空闲
        function<void(int, int, int, int)> backtrack = 
            [&](int row, int cols, int diag1, int diag2) {
            
            if (row == n) {
                solutions.push_back(board);
                return;
            }
            
            // 计算所有可选位置的位掩码
            // ~(cols | diag1 | diag2) 将所有被占用的位置变为0，空闲变为1
            // & ((1 << n) - 1) 截断超过 n 位的高位
            int availablePositions = ((1 << n) - 1) & ~(cols | diag1 | diag2);
            
            while (availablePositions!= 0) {
                // 取出最低位的 1 (即当前可选的一个位置)
                int position = availablePositions & -availablePositions;
                // 将该位置从可用列表中移除
                availablePositions = availablePositions & (availablePositions - 1);
                
                // 获取列索引（通过 log2 或内置函数 __builtin_ctz）
                int col = __builtin_ctz(position); 
                
                // 做选择
                board[row][col] = 'Q';
                
                // 递归
                // 下一行限制更新：
                // cols: 直接传递
                // diag1: 左移一位 (左下延伸)
                // diag2: 右移一位 (右下延伸)
                backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1);
                
                // 撤销选择
                board[row][col] = '.';
            }
        };
        
        backtrack(0, 0, 0, 0);
        return solutions;
    }
};

性能分析：此位运算优化的时间复杂度仍为 $O(N!)$，但在常数因子上远优于传统的数组检查。__builtin_ctz 是GCC/Clang内置函数，对应CPU指令，极快。

6. 图论基石：网格搜索与BFS/DFS​

6.1 网格（Grid）图的遍历哲学​

在算法竞赛中，二维网格是最常见的图结构。与邻接表表示的通用图不同，网格图的节点连接是隐式的（上下左右）。

方向数组（Direction Array）惯用法：

为了避免冗余的 if-else 判断，专业的C++实现通常使用方向数组 12。

C++

// 顺时针方向：上、右、下、左
const int dr = {-1, 0, 1, 0};
const int dc = {0, 1, 0, -1};

// 遍历邻居
for (int i = 0; i < 4; ++i) {
    int nr = r + dr[i];
    int nc = c + dc[i];
    // 边界检查 + 访问逻辑
}

6.2 广度优先搜索（BFS）与最短路径​

BFS 因其层序遍历特性，是寻找无权图中最短路径的标准算法 13。

6.2.1 腐烂的橘子（多源 BFS）​

问题：LeetCode 994. Rotting Oranges

场景：网格中有一些腐烂橘子，每分钟向四周传染。求所有橘子腐烂的最短时间。

策略：这是典型的多源 BFS。我们将所有初始腐烂的橘子同时加入队列，作为第0层，然后层层推进。

代码实现：

C++

#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid.size();
        queue<pair<int, int>> q;
        int fresh_count = 0;
        
        // 1. 初始化：找出所有腐烂橘子入队，并统计新鲜橘子
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(grid[i][j] == 2) {
                    q.push({i, j});
                } else if(grid[i][j] == 1) {
                    fresh_count++;
                }
            }
        }
        
        if(fresh_count == 0) return 0;
        
        int minutes = 0;
        const int dr = {-1, 1, 0, 0};
        const int dc = {0, 0, -1, 1};
        
        // 2. BFS 层序遍历
        while(!q.empty()) {
            int size = q.size();
            bool rotted_any = false;
            
            for(int i = 0; i < size; ++i) {
                auto [r, c] = q.front(); // C++17 结构化绑定
                q.pop();
                
                for(int k = 0; k < 4; ++k) {
                    int nr = r + dr[k];
                    int nc = c + dc[k];
                    
                    if(nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2; // 标记为腐烂 (Visited)
                        q.push({nr, nc});
                        fresh_count--;
                        rotted_any = true;
                    }
                }
            }
            if(rotted_any) minutes++;
        }
        
        return fresh_count == 0? minutes : -1;
    }
};

6.3 深度优先搜索（DFS）与连通性​

DFS 擅长探索图的连通分量、岛屿数量以及需要回溯的路径搜索 15。

6.3.1 岛屿数量 (Number of Islands)​

问题：LeetCode 200. Number of Islands

逻辑：遍历网格，每遇到一个 '1'，计数器加一，并启动 DFS 将与该 '1' 相连的所有陆地“淹没”（置为 '0'），以防止重复计数。

代码实现：

C++

class Solution {
private:
    void dfs(vector<vector<char>>& grid, int r, int c, int m, int n) {
        // 边界检查 + 非陆地检查
        if (r < 0 |

| c < 0 |
| r >= m |
| c >= n |
| grid[r][c] == '0') {
            return;
        }
        
        grid[r][c] = '0'; // 淹没岛屿
        
        // 递归四个方向
        dfs(grid, r + 1, c, m, n);
        dfs(grid, r - 1, c, m, n);
        dfs(grid, r, c + 1, m, n);
        dfs(grid, r, c - 1, m, n);
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int m = grid.size();
        int n = grid.size();
        int count = 0;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j, m, n);
                }
            }
        }
        return count;
    }
};

7. 集合管理的艺术：并查集（Union-Find）​

7.1 并查集的工程化实现​

并查集（Disjoint Set Union, DSU）是处理动态连通性问题的高效数据结构。它支持两个操作：union（合并）和 find（查找） 16。

为了达到接近常数 $O(1)$ 的时间复杂度，必须同时实现两大优化：

  1. 路径压缩（Path Compression）：在查找时，将路径上的所有节点直接挂在根节点下，扁平化树结构 17。
  2. 按秩/大小合并（Union by Rank/Size）：总是将小树合并到大树上，控制树的高度 18。

C++ DSU类模板：

C++

class DSU {
private:
    vector<int> parent;
    vector<int> size; // 用于按大小合并
    int count; // 连通分量数量

public:
    DSU(int n) : parent(n), size(n, 1), count(n) {
        // 初始化：每个节点的父节点是自己
        iota(parent.begin(), parent.end(), 0);
    }
    
    // 查找 (带路径压缩)
    int find(int x) {
        if (parent[x]!= x) {
            parent[x] = find(parent[x]); // 递归压缩
        }
        return parent[x];
    }
    
    // 合并 (按大小)
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX!= rootY) {
            // 将小树 (rootY) 合并到大树 (rootX)
            if (size[rootX] < size) {
                swap(rootX, rootY);
            }
            parent = rootX;
            size[rootX] += size;
            count--;
            return true; // 合并成功
        }
        return false; // 已连通
    }
    
    int getCount() const { return count; }
    int getSize(int x) { return size[find(x)]; }
};

7.2 复杂度分析：反阿克曼函数​

经过双重优化后，DSU 操作的时间复杂度为 $O(\alpha(N))$，其中 $\alpha$ 是反阿克曼函数。对于宇宙中任何可观测的粒子数量 $N$，$\alpha(N)$ 都不会超过 4。因此，在工程实践中，DSU 操作可被视为严格的 $O(1)$。

7.3 应用案例：冗余连接​

问题：LeetCode 684. Redundant Connection

逻辑：树是有 $N$ 个节点和 $N-1$ 条边的无环连通图。题目给出的图有 $N$ 条边，说明多了一条边构成了环。我们使用 DSU 遍历每一条边，如果边的两个端点已经在同一个集合中，说明这条边是导致环出现的“冗余边”。

代码实现：

C++

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        DSU dsu(n + 1); // 节点编号 1 到 n
        
        for (const auto& edge : edges) {
            if (!dsu.unite(edge, edge[1])) {
                // 如果 unite 返回 false，说明两点已连通，这条边是多余的
                return edge;
            }
        }
        return {};
    }
};

8. 优先级调度：堆（Heap）与优先队列​

8.1 C++ priority_queue 的定制​

C++ STL 的 std::priority_queue 是一个容器适配器，默认底层使用 vector 并表现为大顶堆（Max Heap）。

常用定制模式：

  1. 大顶堆（默认）：priority_queue<int> pq;
  2. 小顶堆：priority_queue<int, vector<int>, greater<int>> pq;
  3. 自定义结构体：重载 < 运算符或提供比较结构体 19。

8.2 案例解析：合并K个升序链表​

问题：LeetCode 23. Merge k Sorted Lists

策略：使用小顶堆维护 $k$ 个链表的当前头节点。每次弹出最小的节点接到结果链表后，并将该节点的下一个节点入堆。

代码实现：

C++

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

// 自定义比较器：小顶堆需要 "greater" 逻辑，即 val 大的优先级低
struct CompareNode {
    bool operator()(ListNode* const& p1, ListNode* const& p2) {
        return p1->val > p2->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, CompareNode> pq;
        
        // 初始化：将所有非空链表的头节点入堆
        for (auto l : lists) {
            if (l) pq.push(l);
        }
        
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        while (!pq.empty()) {
            ListNode* minNode = pq.top();
            pq.pop();
            
            tail->next = minNode;
            tail = tail->next;
            
            if (minNode->next) {
                pq.push(minNode->next);
            }
        }
        
        return dummy.next;
    }
};

复杂度：时间复杂度 $O(N \log k)$，其中 $N$ 是所有节点总数，$k$ 是链表条数。相比暴力合并的 $O(N k)$ 有显著提升。