最近在刷leetcode题目,积累了一些提醒以及用c++STL刷题经验,这里记录一下

题型

数组与字符串

在使用vector和string的方法以及stl包含的方法时,比如find,insert,erase,substr方法的参数类型与返回值类型. 有的支持迭代器,有的重载了索引类型等

双指针与数组/链表

在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。

删除链表倒数第n个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 延迟n步的节点
       // 双指针和哑节点
       // 哑节点
       ListNode* dummy = new ListNode(0,head);
        ListNode* first = head;
        ListNode* second = dummy;
        // 不首先遍历获得节点总数
        for(int i = 0;i<n;++i) {
        // 指向第n个节点
            first = first->next; // first和second之间有n-1个节点
        }
        while(first) {
            first = first->next;
            second = second->next; 
        }
        second->next = second->next->next;
        return dummy->next;
    }
};

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

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

class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 快慢指针
        if(head == nullptr) {
            return false;
        }
        ListNode* slowPtr = head,*fastPtr = head;
        while(fastPtr && fastPtr->next!=nullptr) {
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
            if(slowPtr == fastPtr) {
                return true;
            }
        }    
        return false;
    }
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 快慢指针
        if(head == nullptr) {
            return false;
        }
        ListNode* slowPtr = head,*fastPtr = head->next;
        while(fastPtr!=slowPtr) {
            if(fastPtr== nullptr || fastPtr->next == nullptr) {
                return false;
            }
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
           
        }    
        return true;
        
    }
};

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。

当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

每步操作需要同时更新指针 pA 和 pB。

如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。

如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。

当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。

回文链表

矩阵

螺旋矩阵

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        // i行移动到n-1-i列
        //  j列移动到j行
        // matrix_new[col][n−row−1]=matrix[row][col]
        int n = matrix.size();
        for(int i = 0;i<n/2;++i) {
            // 针对每一行
            for(int j = 0;j<(1+n)/2;j++) {
                int temp = matrix[i][j];
                // matrix_[i][j] = matrix[n-j-1][i]
                matrix[i][j] = matrix[n-j-1][i];
                matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
                matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
                matrix[j][n-i-1] = temp;
            }
        }
    }
};

搜索二维矩阵

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] > target) {
                --y;
            }
            else {
                ++x;
            }
        }
        return false;
    }
};

滑动窗口

无重复字符最长字串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
       unordered_map<char,int> char_map;
       int left = 0;
       int max_len{};
       for(int right = 0;right<s.size();right++) {
        char current_char  = s.at(right);
           if(char_map.count(current_char)&& char_map[current_char] >= left) {
            // 遇到了重复字符,获取它上一次出现的索引并进行更新
            left = char_map[current_char]+1;
           }
            // 更新当前字符的最新索引
            char_map[current_char] = right; // 更新最新的索引
            max_len = max(max_len,right-left+1);
       }
    return max_len;
    }
};

固定大小窗口

字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的 排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

前缀和

二分法

二分查找（Binary Search），也叫折半查找，是一种在有序数组中查找特定元素的算法。它的核心思想是每次都通过比较中间元素，将搜索范围缩小一半，从而达到极高的查找效率。其时间复杂度为 O(logN)，这使得它在处理大规模有序数据时表现卓越。

二分查找的精髓在于其迭代地缩小搜索范围。无论具体问题如何，万变不离其宗的是以下几个要素：

1. 明确搜索空间： 定义一个闭区间 [left, right]，表示当前可能包含目标解的范围。初始时，left 通常是数组的起始索引，right 是数组的结束索引。
2. 计算中间点： mid = left + (right - left) / 2。这种写法可以有效避免 (left + right) 可能导致的整数溢出，特别是在 left 和 right 都很大时。
3. 比较与决策： 将 nums[mid] 与目标值或某个条件进行比较。根据比较结果，有三种基本情况：
   • 找到了目标值（或满足条件）： 直接返回 mid 或进行其他处理。
   • nums[mid] 太小了： 说明目标值（或满足条件的解）在 mid 的右侧，更新 left = mid + 1。
   • nums[mid] 太大了： 说明目标值（或满足条件的解）在 mid 的左侧，更新 right = mid - 1 或 right = mid (取决于具体问题)。
4. 循环终止条件： 循环通常持续到 left <= right 或 left < right。循环结束后，left 和 right 的关系（例如 left == right 或 left == right + 1）将指示最终的搜索结果。

在实际应用中，二分查找的循环终止条件和边界更新方式会根据“寻找什么”而略有不同。最常见的两种模式是：

1. 查找特定值（或存在性）： 循环条件 while (left <= right)，当 left > right 时，表示整个搜索区间为空，未找到目标。
   • 如果 nums[mid] == target，返回 mid。
   • 如果 nums[mid] < target，left = mid + 1。
   • 如果 nums[mid] > target，right = mid - 1。
   • 特点： left 和 right 最终会越过彼此。
2. 查找边界（第一个/最后一个满足条件的元素）： 循环条件 while (left < right)，当 left == right 时，循环结束，left（或 right）就是所求的索引。
   • 如果 nums[mid] 满足条件：可能 mid 就是答案，也可能答案在 mid 的左侧。所以 right = mid。
   • 如果 nums[mid] 不满足条件：答案肯定在 mid 的右侧。所以 left = mid + 1。
   • 特点： left 和 right 最终会收敛到同一个点。这种模式在寻找“第一个满足XX条件”或“最后一个满足XX条件”的问题中非常常见。

单调栈

单调栈（Monotonic Stack）是一种特殊的栈数据结构，它在保持栈内元素严格单调递增或严格单调递减的同时，遍历处理输入序列。这种数据结构非常适合解决与“下一个更大/更小元素”相关的序列问题，因为它可以高效地找到每个元素左边或右边第一个比它大或小的元素，而无需进行嵌套循环。

核心知识：工作原理

单调栈的核心思想是“当一个元素入栈时，将所有不满足单调性的元素都弹出”。

以单调递增栈（栈底到栈顶递增）为例：

1. 遍历输入序列。
2. 当前元素 x 入栈：在 x 入栈之前，不断弹出栈顶元素 y，直到栈为空或 y < x。
3. 为什么这样做？
   • 对于每一个被弹出的元素 y，x 就是它右边第一个比它大的元素。
   • 通过这种方式，我们可以在一次遍历中，为每个元素找到它右边的第一个更大元素，时间复杂度仅为 O(n)。

LeetCode 经典题目

单调栈在 LeetCode 上有许多经典应用，这些题目通常能让你深入理解其工作原理。

1. 每日温度

问题描述：给定一个整数数组 temperatures，表示每天的温度。返回一个数组，其中 answer[i] 是指在第 i 天之后，至少需要等待多少天才能等到更暖和的温度。如果该天之后不存在更暖和的温度，则 answer[i] 为 0。

解题思路：

• 我们维护一个单调递减栈，栈中存储的是元素的索引。栈底到栈顶的索引对应的温度是递减的。
• 遍历温度数组：
  • 如果当前温度 temperatures[i] 大于栈顶索引 j 对应的温度 temperatures[j]，说明我们找到了 j 右边第一个比它大的元素。
  • 弹出栈顶索引 j，计算等待天数 i - j，并将其存入结果数组 answer[j]。
  • 重复此过程，直到栈顶元素不比当前温度小。
  • 最后，将当前索引 i 压入栈中。
• 栈中剩下的索引，意味着它们右边没有比它们更大的元素，对应的 answer 值为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// LeetCode 739. 每日温度
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> result(n, 0);
        stack<int> s;

        for (int i = 0; i < n; ++i) {
            while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
                int prev_index = s.top();
                s.pop();
                result[prev_index] = i - prev_index;
            }
            s.push(i);
        }
        return result;
    }
};

1. 柱状图中最大的矩形

问题描述：给定 n 个非负整数，表示一个柱状图，每个柱子的宽度为 1。找出这个柱状图中能形成的最大矩形面积。

解题思路：

• 要求最大矩形面积，可以转换为：对于每个柱子，找到以它为高的最大矩形。这个矩形的宽度由它左右两侧第一个比它低的柱子决定。
• 我们可以用两次单调栈遍历：
  1. 从左到右遍历，使用单调递增栈，找到每个柱子左边第一个比它低的柱子索引。
  2. 从右到左遍历，使用单调递增栈，找到每个柱子右边第一个比它低的柱子索引。
• 有了左右两边的索引，就可以计算以每个柱子为高的矩形面积，并找出最大值。

优化思路：

• 可以只用一次单调栈遍历来解决。
• 依然使用单调递增栈存储索引。当 heights[i] 小于栈顶 heights[top] 时，heights[top] 就是一个潜在的高度。
• 此时，heights[top] 的右边界是 i，左边界是新的栈顶（如果栈不为空）或 -1。计算面积并更新最大值。

1. 接雨水

问题描述：给定 n 个非负整数，表示一个柱状图，计算下雨后能接多少雨水。

解题思路：

• 可以用双指针或单调栈来解决。
• 使用单调递减栈存储索引。
• 遍历柱子数组：
  • 当 heights[i] 高于栈顶 heights[top] 时，说明 heights[top] 可能会形成一个凹槽。
  • 弹出 top，它就是凹槽的底部。
  • 新的栈顶 s.top() 是凹槽的左壁，i 是凹槽的右壁。
  • 计算凹槽的高度 min(heights[i], heights[s.top()]) - heights[top]，宽度 i - s.top() - 1，并累加雨水。

优先队列/堆

优先队列是一种抽象数据类型（ADT），它的核心特征是：

• 队列中的每个元素都有一个优先级。
• 队列总是按照优先级最高的元素进行出队（删除）操作。
• 元素的入队（插入）顺序不影响出队顺序，只与优先级有关。

你可以想象一个医院的急诊室：医生总是优先处理病情最严重的病人，而不是先到诊的病人。这就是一个优先队列的典型例子。

优先队列通常分为两种类型：

• 最大优先队列： 优先级最高的元素是最大的元素。
• 最小优先队列： 优先级最高的元素是最小的元素。

什么是堆？

堆是一种具体的数据结构，它通常是一个完全二叉树，并且满足特定的堆属性：

• 最大堆（Max Heap）： 任何一个父节点的值都大于或等于其子节点的值。因此，最大的元素总是在堆的根部。
• 最小堆（Min Heap）： 任何一个父节点的值都小于或等于其子节点的值。因此，最小的元素总是在堆的根部。

因为堆能够高效地找到最大或最小的元素，所以它成为了实现优先队列最常见、最有效的方式。在大多数编程语言中，当你使用“优先队列”时，底层往往就是一个堆。

堆可以通过完全二叉树实现堆排序.通过将数组构建成一个堆，然后不断地移除堆顶元素来完成排序。

堆排序主要分为两个步骤：

1. 建堆（Heapify）： 将一个无序数组构建成一个堆。我们通常会构建一个最大堆（Max Heap），这样数组中最大的元素就会被放在数组的第一个位置（即堆顶）。
2. 排序： 持续地从堆中移除最大的元素，并将其放到数组的正确位置上。

堆排序的关键在于一个名为 heapify 的操作。这个函数的作用是，确保以一个节点为根的子树满足堆的性质。以最大堆为例，heapify(arr, n, i) 函数会比较节点 i、它的左子节点和右子节点，找到这三个节点中最大的元素，并将其放在节点 i 的位置。如果发生了交换，就会对被交换的子树递归地调用 heapify，直到整个子树都满足最大堆的性质。

heapify 函数是堆排序的基础。它需要三个参数：数组 arr、堆的大小 n、以及要调整的子树的根节点索引 i。

heapSort 函数会调用 heapify 来完成建堆和排序两个步骤。

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

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

// 堆调整函数：将以 i 为根节点的子树调整为最大堆
// n 是堆的当前大小
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;       // 假设根节点是最大的
    int left = 2 * i + 1;  // 左子节点的索引
    int right = 2 * i + 2; // 右子节点的索引

    // 比较左子节点和根节点，更新 largest
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 比较右子节点和目前最大的节点，更新 largest
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大的不是根节点，则进行交换
    if (largest != i) {
        std::swap(arr[i], arr[largest]);

        // 递归地对被交换的子树进行堆调整
        heapify(arr, n, largest);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void heapSort(std::vector<int>& arr) {
    int n = arr.size();
// 步骤1：建堆
// 从最后一个非叶子节点开始（索引为 n/2 - 1），
// 依次向上对每个子树进行堆调整，直到整个数组成为一个最大堆。
for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
}

// 步骤2：排序
// 循环 n-1 次，每次从堆中移除一个最大元素并放到数组末尾
for (int i = n - 1; i > 0; i--) {
    // 将当前堆顶（最大值）与堆的最后一个元素交换
    // 此时，最大的元素已经位于数组的正确位置
    std::swap(arr[0], arr[i]);

    // 重新调整堆，忽略已经排序好的最后一个元素（i）
    heapify(arr, i, 0);
}
    }

贪心

动态规划

动态规划（Dynamic Programming，简称 DP）是一种通过将复杂问题分解成更小的重叠子问题来求解的算法思想。它的核心在于避免重复计算，通过存储子问题的解来提高效率。

掌握动态规划的关键，在于理解它解决的两大核心问题：

1. 最优子结构（Optimal Substructure）： 一个问题的最优解可以通过其子问题的最优解来构造。
2. 重叠子问题（Overlapping Subproblems）： 在求解问题的过程中，需要多次计算同一个子问题。

动态规划的解题步骤

解决一个动态规划问题，通常可以遵循以下四个步骤，这就像一个解题模板：

1. 确定 DP 状态（State）：
   • 状态是动态规划的核心。你需要定义一个数组或表格 dp，其中 dp[i] 或 dp[i][j] 代表了解决某个子问题的解。
   • 状态的定义必须能够唯一且完整地描述一个子问题。
   • 例如： 在“爬楼梯”问题中，dp[i] 可以定义为“爬到第 i 级台阶的方法总数”。
2. 确定状态转移方程（State Transition Equation）：
   • 状态转移方程是连接子问题与原问题的桥梁。它描述了如何从一个或多个子问题的解，计算出当前问题的解。
   • 例如： 在“爬楼梯”问题中，要爬到第 i 级台阶，可以从第 i-1 级爬一步，或者从第 i-2 级爬两步。所以状态转移方程是 dp[i] = dp[i-1] + dp[i-2]。
3. 确定 DP 数组的初始值和边界条件：
   • 动态规划的计算通常有一个起点。你需要为 DP 数组的最初几个元素（通常是 dp[0] 或 dp[0][0]）赋值。
   • 这些初始值是递归的终止条件，它们必须是已知的、能够推导出后续所有状态的值。
   • 例如： 在“爬楼梯”问题中，爬到第 0 级台阶只有 1 种方法（不动），dp[0] = 1。爬到第 1 级台阶也只有 1 种方法（爬一步），dp[1] = 1。
4. 确定遍历顺序：
   • 动态规划的计算是有依赖关系的。你需要按照一定的顺序（通常是从小到大或从左到右）遍历 DP 数组，确保在计算 dp[i] 时，所有它依赖的子问题的解（如 dp[i-1]、dp[i-2]）都已经计算完成。
   • 例如： 在“爬楼梯”问题中，我们需要从 i = 2 开始遍历，一直到 n，因为 dp[i] 依赖于 dp[i-1] 和 dp[i-2]。

动态规划的解题套路

掌握了上述四个步骤后，我们可以通过一个简单的套路来解决大部分动态规划问题：

1. 读题，识别动态规划问题： 如果问题可以分解为重叠子问题，并且需要求最优解（最大、最小、最多、最少），那么它很可能是动态规划。
2. 定义 DP 数组： 勇敢地写下 dp[i] 或 dp[i][j]，并用一句话描述它的含义。
3. 找递推关系（状态转移方程）： 思考如何从 dp[...小一些的索引...] 得到 dp[i]，这是最难的一步，通常需要举几个小例子来推导。
4. 初始化 DP 数组： 确定 dp[0]、dp[0][0] 等基本情况。
5. 编写循环： 按照正确的依赖顺序，编写 for 循环来填充 DP 数组。
6. 返回结果： 根据 DP 数组的定义，返回最终需要的答案。

最长递增字串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // dp[n] 表示以索引i结尾的数组的最长递增长度
        if(nums.empty()) {
            return 0;
        }
        int sz = nums.size();
        vector<int> dp(sz,1);
        int max_len{1};
        for(int i = 1;i<sz;++i) {
            for(int j = 0;j<i;j++) {
                if(nums.at(i)>nums.at(j)) {
                dp[i] = max(dp[i],dp[j]+1);
                }
            }
            max_len = max(max_len,dp[i]);
        }
        return max_len;
    }
};

最长公共字串

最长回文字串

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

一种方法是将原本字符串与逆序后的字符串求最长公共字串长度.

另外可以直接使用动态规划.

可以使用一个二维 DP 数组来解决这个问题。定义 dp[i][j] 为字符串 s 在索引 i 到 j 之间的子串中，最长回文子序列的长度

状态转移方程

要计算 dp[i][j]，我们需要考虑子串 s[i...j] 的两端字符 s[i] 和 s[j]：

• 如果 s[i] == s[j] 这意味着这两个字符可以作为回文子序列的一部分。此时，最长回文子序列的长度是在 s[i+1...j-1] 子串的最长回文子序列的基础上，加上这两个匹配的字符。 dp[i][j] = dp[i+1][j-1] + 2
• 如果 s[i] != s[j] 这两个字符不匹配，我们不能同时将它们都作为回文子序列的一部分。因此，我们需要在以下两种情况中取最大值：
  1. s[i...j-1] 子串中的最长回文子序列的长度 (dp[i][j-1])。
  2. s[i+1...j] 子串中的最长回文子序列的长度 (dp[i+1][j])。 dp[i][j] = max(dp[i][j-1], dp[i+1][j])

边界条件

需要初始化 DP 数组。当子串的长度为 1 时，它本身就是一个回文子序列，所以：

• dp[i][i] = 1

遍历顺序

观察状态转移方程，dp[i][j] 依赖于 dp[i+1][j-1]、dp[i][j-1] 和 dp[i+1][j]。这意味着在计算 dp[i][j] 时，我们需要先知道其左下角、左边和下边的值。

为了满足这个依赖关系，我们应该从小到大遍历子串的长度，然后从后往前遍历起始索引。

• 外层循环：子串长度 len 从 1 到 n。
• 内层循环：起始索引 i 从 n-1 到 0。
• 结束索引 j 总是 i + len - 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int sz = s.size();
        vector<vector<int>> dp(sz,vector<int>(sz));
        // 状态转移方程 i,j表示起始位置和截止位置 这个范围的最长回文字串长度
        // dp[i][j] = 1 ,i == j
        // dp[i][j] = 0 ,i > j
        // dp[i][j] = if s[i] == s[j] dp[i+1][j-1] + 2
        // s[i] != s[j]   dp[i][j]  = max(dp[i+1][j],dp[i][j-1])
        for(int i = sz-1;i>=0;i--) {
            dp[i][i] = 1;
            for(int j = i+1;j<sz;j++) {
                if(s.at(i) == s.at(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else{
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][sz-1];
    }
};

二叉树

用栈实现 DFS 的核心思想是：

1. 将根节点压入栈中。
2. 进入一个循环，只要栈不为空，就执行以下操作：
   • 弹出栈顶节点，并访问它。
   • 将该节点的右子节点压入栈中（如果存在）。
   • 将该节点的左子节点压入栈中（如果存在）。

为什么先压入右子节点，再压入左子节点？因为栈是后进先出（LIFO）的。这样做可以确保左子节点总是先于右子节点被弹出和访问，从而模拟了递归的深度优先探索顺序。

三种遍历方式的实现

使用栈实现 DFS 可以轻松模拟前序、中序和后序遍历。

1. 前序遍历（Pre-order Traversal）

前序遍历的顺序是：根 -> 左 -> 右。使用栈实现时，只需按照核心思想的步骤即可。

• 步骤：
  1. 将根节点入栈。
  2. 循环直到栈为空：
     • 弹出节点 node，访问它。
     • 将 node 的右子节点入栈（如果存在）。
     • 将 node 的左子节点入栈（如果存在）。

C++

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

#include <iostream>
#include <vector>
#include <stack>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

std::vector<int> preorderTraversal(TreeNode* root) {
    std::vector<int> result;
    if (root == nullptr) {
        return result;
    }

    std::stack<TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        result.push_back(node->val);

        if (node->right) {
            s.push(node->right);
        }
        if (node->left) {
            s.push(node->left);
        }
    }
    return result;
}

1. 中序遍历（In-order Traversal）

中序遍历的顺序是：左 -> 根 -> 右。这个实现稍复杂，因为我们需要在访问根节点之前，先遍历完它的所有左子节点。

• 步骤：
  1. 初始化一个 current 指针指向根节点。
  2. 循环直到 current 为空且栈为空：
     • 将所有左子节点依次入栈，直到 current 为空。
     • 弹出栈顶节点 node，访问它。
     • 让 current 指向 node 的右子节点，继续循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

std::vector<int> inorderTraversal(TreeNode* root) {
    std::vector<int> result;
    std::stack<TreeNode*> s;
    TreeNode* current = root;

    while (current != nullptr || !s.empty()) {
        while (current != nullptr) {
            s.push(current);
            current = current->left;
        }
        current = s.top();
        s.pop();
        result.push_back(current->val);
        current = current->right;
    }
    return result;
}

1. 后序遍历（Post-order Traversal）

后序遍历的顺序是：左 -> 右 -> 根。这是三种遍历中最复杂的。一种常见的技巧是：

• 先用类似前序遍历的方式，以根 -> 右 -> 左的顺序遍历。
• 将遍历结果存入一个临时数组。
• 最后将临时数组反转，即可得到后序遍历的结果。
• 步骤：
  1. 将根节点入栈。
  2. 循环直到栈为空：
     • 弹出节点 node，将它的值存入临时数组。
     • 将 node 的左子节点入栈（如果存在）。
     • 将 node 的右子节点入栈（如果存在）。
  3. 反转临时数组。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

std::vector<int> postorderTraversal(TreeNode* root) {
    std::vector<int> result;
    if (root == nullptr) {
        return result;
    }
    
    std::stack<TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        result.push_back(node->val);

        if (node->left) {
            s.push(node->left);
        }
        if (node->right) {
            s.push(node->right);
        }
    }
    std::reverse(result.begin(), result.end());
    return result;
}

图

图做深搜广搜的时候注意在哪里判断选择结束条件,实在做选择的时候还是在从堆栈中取出数据的时候

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int counts{};
while(!q.empty()) {
	int sz = q.size();
    while(sz--) {
        auto t = q.front();
        q.pop();
      //  if(t 满足终止条件) {
      //      
      //  }
        for(choice : choices) {
            //判断选择是否满足终止条件
        }
    }
    counts++;
}

Dijkstra

Dijkstra 算法用于在一个带权图中找到从一个起始节点到所有其他节点的最短路径。

Dijkstra 算法维护一个节点集合，这个集合中的节点已经确定了最短路径。它从起始节点开始，不断选择距离起始节点最近的未访问节点，并用这个节点来更新其所有邻接节点的距离。这个过程重复进行，直到所有节点都被访问。

算法步骤

1. 初始化：创建一个距离数组 dist，将起始节点的距离设为 0，其他所有节点的距离设为无穷大。
2. 优先队列：使用一个最小优先队列来存储 <距离, 节点> 对，初始时将 <0, 起始节点> 放入队列。
3. 循环：只要优先队列不为空，就执行以下操作：
   • 从队列中弹出距离最小的节点 u。
   • 如果 u 已经被访问过，则跳过。
   • 标记 u 为已访问。
   • 遍历 u 的所有邻接节点 v：
     • 计算通过 u 到 v 的新距离：new_dist = dist[u] + weight(u, v)。
     • 如果 new_dist < dist[v]，则更新 dist[v] = new_dist，并将 <new_dist, v> 放入优先队列。
4. 结果：当循环结束时，dist 数组中存储的就是起始节点到所有其他节点的最短距离。

适用场景

• 寻找最短路径，例如，导航系统计算两个地点之间的最短距离。
• 要求所有边权都为非负数。如果图中存在负权边，Dijkstra 算法会失效，此时需要使用 Bellman-Ford 或 SPFA 算法。

最小生成树（Minimum Spanning Tree, MST）是图论中的一个核心概念，它指的是一个加权连通图的特殊子图。

最小生成树的概念

• 图：一个由节点（顶点）和边组成的集合。
• 加权图：图中的每条边都有一个权重（或成本、距离）。
• 连通图：图中任意两个节点之间都存在一条路径。
• 生成树：是原图的一个子图，它连接了原图中的所有节点，但没有任何环，且包含了最少的边。一个包含 n 个节点的图，其生成树总是包含 n-1 条边。

而最小生成树，就是在所有可能的生成树中，所有边的权重之和最小的那一棵。

解决最小生成树问题的经典算法有两个：

• Prim 算法：从一个起始节点开始，逐步向外扩展，每次都选择连接已构建树和未加入树的权重最小的边。
• Kruskal 算法：将所有边按权重从小到大排序，然后依次选择边，只要这条边不会形成环，就将其加入到生成树中。

Prim

Prim 算法用于找到一个加权连通图的最小生成树（Minimum Spanning Tree, MST）。最小生成树是图的一个子图，它连接了所有节点，且所有边的权重之和最小。

Prim 算法从一个任意的起始节点开始，逐步添加边，以构建一棵树。在每一步中，它都选择连接当前已构建树与未加入树的节点的权重最小的边。这个过程重复进行，直到所有节点都被加入到树中。

算法步骤

1. 初始化：创建一个距离数组 dist，将起始节点的距离设为 0，其他节点的距离设为无穷大。这个距离表示节点与当前已构建树之间的最小边权。
2. 优先队列：使用一个最小优先队列来存储 <边权, 节点> 对，初始时将 <0, 起始节点> 放入队列。
3. 循环：只要优先队列不为空，就执行以下操作：
   • 从队列中弹出边权最小的节点 u。
   • 如果 u 已经被访问过，则跳过。
   • 标记 u 为已访问，并将边权 weight 加入到 MST 的总权重中。
   • 遍历 u 的所有邻接节点 v：
     • 如果 v 未被访问，并且边 (u, v) 的权重小于 v 当前的距离：
       • 更新 v 的距离：dist[v] = weight(u, v)。
       • 将 <weight(u, v), v> 放入优先队列。
4. 结果：当循环结束时，所有节点的 dist 值的总和（或者通过其他方式记录的边的权重之和）就是最小生成树的总权重。

适用场景

• 构建最小生成树，例如，设计一个网络连接所有城市，但要使总光缆长度最小。
• Prim 算法可以处理负权边，因为它只关心边本身的权重，而不是累积的路径权重。

区别总结

它的主要作用是计算一个有向图或无向图中任意两个节点之间的最短路径。这个算法可以处理带负权值的边，但不能处理负权环（如果图中存在负权环，算法会失效）。

Floyd 算法的核心思想

Floyd 算法的核心思想是动态规划。它通过逐步增加中间节点的数量来更新最短路径。

假设图中有 n 个节点，算法的执行过程是这样的：

1. 初始化：创建一个 ntimesn 的距离矩阵 dist。dist[i][j] 初始化为节点 i 到节点 j 的直接距离。如果两个节点之间没有直接连接，距离设为无穷大。
2. 迭代：算法会进行 n 次迭代，每次迭代都以一个节点 k 作为“中间节点”。
   • 在第 k 次迭代中，算法会遍历所有的节点对 (i,j)。
   • 它会检查，如果从 i 经过 k 到达 j 的路径比已知的最短路径更短，就更新 dist[i][j]。
   • 更新公式为：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。

通过这 n 次迭代，算法考虑了所有可能的中间节点，最终得到的 dist 矩阵就包含了任意两个节点之间的最短路径。

深搜广搜

连通分量

省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

要解决这个问题，我们可以将城市和它们之间的连接关系看作是一个图（Graph）。其中，每个城市都是图中的一个节点，如果两个城市相连，那么它们之间就有一条边。题目中定义的“省份”其实就是图中的连通分量（Connected Component）。

因此，问题的核心就变成了：给定一个图，找出其中的连通分量数量。

我们可以使用两种常见的图遍历算法来解决这个问题：深度优先搜索（DFS）或广度优先搜索（BFS）。

方法一：深度优先搜索（DFS）

DFS 的基本思想是从一个未访问过的城市开始，沿着它的连接路径一直走下去，直到所有与之相连的城市都被访问。当这条路径走完后，我们就找到了一个完整的省份。然后，我们从下一个未访问过的城市重新开始，重复这个过程，直到所有城市都被访问。

算法步骤：

1. 初始化一个计数器 count = 0，用于记录省份的数量。
2. 创建一个布尔数组 visited，大小为 n，用于标记城市是否已被访问。
3. 遍历所有城市，从 i = 0 到 n - 1。
4. 对于每个城市 i：
   • 如果 visited[i] 为 false，说明我们遇到了一个新省份。
   • 将 count 加 1。
   • 调用 DFS 函数，从城市 i 开始遍历，并标记所有与其相连的城市为已访问。
5. DFS 函数的实现：
   • 接收当前城市 i 作为参数。
   • 将 visited[i] 设置为 true。
   • 遍历所有城市 j，从 0 到 n - 1。
   • 如果城市 i 与城市 j 相连（isConnected[i][j] == 1），且城市 j 未被访问（!visited[j]），则递归调用 DFS 函数，从城市 j 继续遍历。

代码实现

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

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                // 找到一个新的省份
                count++;
                // 从当前城市开始，深度遍历所有相连的城市
                dfs(isConnected, visited, i);
            }
        }
        return count;
    }

    private void dfs(int[][] isConnected, boolean[] visited, int i) {
        // 标记当前城市为已访问
        visited[i] = true;
        // 遍历所有城市
        for (int j = 0; j < isConnected.length; j++) {
            // 如果城市i和城市j相连，且城市j未被访问过
            if (isConnected[i][j] == 1 && !visited[j]) {
                // 递归地继续遍历
                dfs(isConnected, visited, j);
            }
        }
    }
}

方法二：广度优先搜索（BFS）

BFS 的思想与 DFS 类似，只是遍历的方式不同。它不是沿着一条路径一直走，而是从一个城市开始，先访问所有与它直接相连的城市，然后是与这些城市直接相连的城市，以此类推。我们可以使用队列（Queue）来实现 BFS。

算法步骤：

1. 初始化 count = 0 和布尔数组 visited。
2. 遍历所有城市 i：
3. 如果 visited[i] 为 false，则 count++。
4. 创建一个队列，并将城市 i 加入队列。
5. 将 visited[i] 设置为 true。
6. 当队列不为空时：
   • 取出队列头部元素 currentCity。
   • 遍历所有城市 j：
   • 如果 currentCity 与城市 j 相连，且城市 j 未被访问，则将 j 加入队列，并将 visited[j] 设置为 true。

重新规划路线

除法求值

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
40
41
42
43
44
45
46
47
48
49
50
51
52

class Solution {

public:
    double dfs(const unordered_map<string,unordered_map<string,double>>& graph,string x,string z,set<string>& visited) {
            if(graph.find(x) == graph.end() || visited.count(x)) {
                return -1.0; // 没有找到
            }
            // 如果找到了终点，返回 1.0 (表示从自己到自己的权重)
            if (x == z) {
                return 1.0;
            }
            visited.insert(x);
            for(auto node:graph.at(x)) {
                double result = dfs(graph,node.first,z,visited);
                if(result != -1.0) {
                    return result*node.second; // 找到对应值
                }                 
            }
            return -1.0;
    }

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        //1. 构建已有的图
        unordered_map<string,unordered_map<string,double>> graph;
        for(int i = 0;i<equations.size();++i) {
            auto equation = equations.at(i);
            string x = equation[0];
            string y = equation[1];
            graph[x][y] = values[i];
            graph[y][x] = 1.0/values[i];
        }
        //2.dfs
        vector<double> result;
        for(auto query:queries) {
            string x = query[0];
            string y = query[1];
            if(graph.find(x) == graph.end() || graph.find(y) == graph.end()) {
                // 不存在该变量
                result.emplace_back(-1.0);
            }else if(x == y) {
                // 值相等
                result.emplace_back(1.0);
            }else {
                // 通过dfs查找值 
                set<string> visited;
                result.emplace_back(dfs(graph,x,y,visited));
            }
        }

        return result;
    }
};

回溯

回溯（Backtracking）是一种通过探索所有可能的候选解来找出所有解或最优解的算法策略。它通常用于解决组合问题、排列问题、子集问题等。

回溯算法的本质是深度优先搜索 (DFS) 的一种特殊应用。它像是在一个解空间树中进行遍历，每走一步就尝试一个选择，如果发现当前选择不能达到目标或偏离了最佳路径，就会“回溯”（撤销当前选择），退回到上一步，然后尝试另一个选择。

这个过程可以概括为：选择 → 探索 → 撤销。

掌握这三要素是编写回溯代码的关键：

路径 (Path): 记录已经做出的选择。这通常是一个 List 或 Vector，存储当前已选择的元素。

选择列表 (Choices): 当前可以做出的选择。这是从问题中抽象出来的，通常是某个集合或数组中剩余的元素。

结束条件 (Base Case / Termination Condition): 什么时候停止递归？通常是路径满足了特定条件（比如长度达到要求，找到了一个解）或者选择列表为空。

状态修改

参数传递： 通常，path 应该作为引用（或指针）传递，因为它在递归过程中需要被修改和回溯。其他参数根据是否需要在递归调用中改变而定。

状态的“做选择”和“撤销选择”： 确保每做一步选择后，都将其添加到 path 中；在递归调用结束后，务必撤销这个选择，恢复到递归前的状态，以便尝试其他分支。这是回溯算法的核心。

剪枝是回溯算法的灵魂，能极大提高效率。

• 定义： 在搜索过程中，一旦发现当前路径不可能得到有效解或最优解时，就立即停止对该路径的后续搜索。

• 常见剪枝点：

  • 边界条件检查： 例如，如果路径长度已经超过了目标长度。
  • 不合法条件： 例如，组合问题中，如果当前选择导致和已经超过了目标值。
  • 排序： 对输入数据进行排序，可以帮助你在遍历选择时，当发现某个分支不可能生成有效解时，跳过后续相似的选择。例如，在有重复元素的组合问题中，排序后可以跳过重复的元素。

  当输入数组中包含重复元素，但要求结果中不允许有重复的组合/排列时，去重是一个常见的难点。

  • 排序 + if (i > start && nums[i] == nums[i-1]) continue;：这是最经典的去重技巧。
    • 首先，对输入数组进行排序。
    • 在 for 循环遍历 Choices 时，检查当前元素是否与前一个元素相同。如果相同，并且前一个元素已经被跳过（而不是本次递归中被选择后移除的），则跳过当前元素，以避免生成重复的路径。
    • 这个判断通常应用于同一层递归中的去重，防止在同一位置做出相同的选择。

  遍历方式的选择

  是否允许重复选择元素：

  • 允许（例如组合问题，[1,1,2] 选两个，可以是 [1,1]）： 递归时，下一个选择的起始索引可以从当前选择的索引开始 (i 或 startIndex)。

  • 不允许（例如排列问题，每个元素只能用一次）： 递归时，需要通过 visited 数组或移除元素的方式，确保元素不被重复选择。

​ 是否要求组合/排列：

• 组合 (Combinations)： 结果不考虑元素顺序（[1,2] 和 [2,1] 视为同一种）。通常通过在递归时传递一个 startIndex 参数来确保选择的元素索引是递增的，避免生成重复的组合。
• 排列 (Permutations)： 结果考虑元素顺序（[1,2] 和 [2,1] 视为不同种）。通常需要一个 visited 数组或类似机制来标记已使用的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Java 示例
void backtrack(参数, ... Path, Choices) {
    // 1. 结束条件：满足某个条件时，将Path加入结果集，并返回
    if (满足结束条件) {
        result.add(new ArrayList<>(Path)); // 注意：这里通常需要拷贝Path，因为Path后续还会被修改
        return;
    }

    // 2. 遍历所有选择
    for (选择 in Choices) {
        // 做选择：将当前选择加入Path
        Path.add(选择);
        
        // 剪枝（可选）：如果当前选择明显不符合条件，提前终止分支
        // if (...) continue; 或 return;

        // 递归：进入下一个决策层
        backtrack(参数, ... Path, newChoices); // newChoices通常是基于当前选择更新后的
        
        // 撤销选择：从Path中移除当前选择，回到上一个状态
        Path.remove(Path.size() - 1); 
    }
}

常见回溯问题类型

• 子集问题： 找出所有可能的子集（Subsets）。
• 组合问题： 找出所有和为目标值的组合，或固定长度的组合（Combinations Sum, Combinations）。
• 排列问题： 找出所有可能的排列（Permutations）。
• 迷宫问题/路径查找： 在网格或图中寻找路径（Word Search, N-Queens）。
• 数独求解： 填字游戏。

搜索与排序

排序

快速排序

核心思想：分治,快速排序主要分为三个步骤：

1. 选择基准（Pick a Pivot）： 从数组中选择一个元素作为基准。基准的选择有很多策略（第一个、最后一个、中间的、随机的），不同的选择会影响算法的性能。
2. 分区（Partition）： 重新排列数组，将所有小于基准的元素移到基准的左边，所有大于基准的元素移到基准的右边。等于基准的元素可以放在任意一边。分区结束后，基准元素就处于其最终的有序位置。
3. 递归（Recursion）： 递归地对基准左边的子数组和基准右边的子数组进行快速排序。

分区操作是快速排序的核心。目标是将数组 arr[low...high] 以 pivot 为基准进行分区。

Lomuto 分区方案：

1. 选择 arr[high] 作为基准（或其他位置，然后交换到 high）。
2. 维护一个索引 i，指向“小于基准”区域的最后一个元素。
3. 遍历 j 从 low 到 high-1：
   • 如果 arr[j] <= pivot，则将 arr[j] 交换到 arr[i+1] 的位置，并增加 i。
4. 最后，将基准元素（arr[high]）交换到 arr[i+1] 的位置。
5. 返回 i+1，即基准最终的索引。

• 优点： 简单易懂。
• 缺点： 对有大量重复元素的数组性能较差

Hoare 分区方案：

1. 选择 arr[low] 作为基准（或其他位置）。
2. 维护两个指针 i（从 low-1 开始向右移动）和 j（从 high+1 开始向左移动）。
3. while (true) 循环：
   • do i++ 直到 arr[i] >= pivot。
   • do j-- 直到 arr[j] <= pivot。
   • 如果 i < j，交换 arr[i] 和 arr[j]。
   • 否则，跳出循环。
4. 返回 j（或 i，取决于实现）。

• 优点： 对有大量重复元素的数组性能更好，通常比 Lomuto 更高效。
• 缺点： 边界条件和指针移动相对复杂，容易出错。

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

void quickSort( vector<int>& nums,int l,int r) {
    if(l>=r) {
        return;
    }
    int pivotIndex = partition(nums,l,r);
    // quickSort(nums,l,pivotIndex-1);
    quickSort(nums,l,pivotIndex-1);
    quickSort(nums,pivotIndex+1,r);
}
int partition(vector<int>& nums,int l , int r) {
    int pivotIndex = l;
    int pivot = nums.at(pivotIndex);
    if(l>=r) {
        return l;
    }
    // hore分区 
    while(l<r) {
        while(l<r && nums.at(l)<=pivot) {
            l++;
        }
        while(l<r && nums.at(r)>=pivot) {
            r--;
        }
        swap(nums.at(l),nums.at(r));
    }
    l = nums.at(l)>pivot?l-1:l;    
    swap(nums.at(pivotIndex),nums.at(l));
    return l;
}

归并排序

归并排序（Merge Sort）是一种高效的、基于分治（Divide and Conquer）思想的排序算法。它的核心思想是将一个大问题分解成若干个小问题，直到小问题足够简单可以直接解决，然后将这些小问题的解合并起来，从而解决原先的大问题。

归并排序主要分为两个核心步骤：

1. 分解（Divide）： 不断地将待排序的数组从中间一分为二，直到每个子数组只包含一个元素（一个元素自然是有序的）。
2. 合并（Conquer）： 将相邻的两个有序子数组合并成一个更大的有序数组。这个合并过程会重复进行，直到所有子数组都被合并成一个完整的有序数组。

前缀树

相关知识

前缀树（Trie），又称“字典树”，是一种用于高效存储和查找字符串集合的树形数据结构。它的核心思想是利用字符串的公共前缀来减少查询时间。

前缀树的核心知识

1. 结构

一个前缀树由一系列节点组成，每个节点通常包含以下信息：

• 子节点数组（或哈希表）：用于存储指向子节点的指针。数组的大小取决于字符集，例如，如果只包含小写字母 ‘a’ 到 ‘z’，数组大小就是 26。
• 结束标记（布尔值）：标记当前节点是否代表一个完整的单词的结尾。

1. 工作原理

前缀树的查找和插入操作都非常直观：

• 插入：从根节点开始，遍历字符串的每个字符。如果当前字符对应的子节点不存在，就创建一个新节点；然后移动到那个子节点，继续下一个字符。当所有字符都遍历完后，将最后一个节点的结束标记设为 true。
• 查找：从根节点开始，遍历字符串的每个字符。如果某个字符对应的子节点不存在，说明字符串不在树中。如果遍历完整个字符串，并且最后一个节点的结束标记为 true，则说明找到了该单词。

1. 性能优势

• 时间复杂度：
  • 插入和查找的时间复杂度都非常高效，通常是 O(L)，其中 L 是字符串的长度。与哈希表相比，它的性能不依赖于哈希函数的质量，而且没有哈希冲突的问题。
• 空间复杂度：
  • 空间消耗取决于存储的字符串数量和它们的公共前缀。在许多情况下，多个字符串共享前缀可以节省空间，但如果字符串都很长且没有公共前缀，空间消耗可能会大于哈希表。

考点

如何实现前缀树(包括插入,查找，前缀查找)并利用前缀树进行单词查找.

LeetCode 题目实践

掌握了前缀树的原理后，我们可以用它来解决一些 LeetCode 上的经典问题。

1. 实现前缀树 (Trie)

这是最基础的题目，要求你实现 Trie 类，包含 insert、search 和 startsWith 三个方法。通过这道题可以巩固对前缀树结构的理解。

• insert(word)：将单词 word 插入前缀树。
• search(word)：判断 word 是否在前缀树中。
• startsWith(prefix)：判断是否有以 prefix 为前缀的单词

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

class TrieNode {
    public:
        vector<TrieNode*> chars{26,nullptr};
        bool isEndOfWord{};

};

class Trie {
    public:
        TrieNode* trieRoot;
    
public:
    Trie():trieRoot(new TrieNode) {
        
    }
    void insert(string word) {
        if(word.empty()) {
            return;
        }
        auto node = trieRoot;
        for(auto ch:word) {
             auto n = node->chars[ch-'a'];
             if(n == nullptr) {
                n = new TrieNode;
                node->chars[ch-'a'] = n;
             }
             node = n;
        }
        node->isEndOfWord = true;
    }
    
    bool search(string word) {
        if(word.empty()) {
            return false;
        }
        auto node = trieRoot;
        for(auto ch:word) {
            auto n = node->chars[ch-'a'];
            if(n == nullptr) {
                return false;
            }
            node = n;
        }
        return node->isEndOfWord;
    }
    
    bool startsWith(string prefix) {
        if(prefix.empty()) {
            return false;
        }
        auto node = trieRoot;
       for(auto ch:prefix) {
            auto n = node->chars[ch-'a'];
            if(n == nullptr) {
                return false;
            }
            node = n;
       }
       return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

1. 单词搜索 II

这道题需要你在一个网格中找出所有符合条件的单词。如果对每个单词都进行独立的搜索，效率会很低。使用前缀树可以大大优化。

• 思路：
  1. 将所有待查找的单词构建成一棵前缀树。
  2. 遍历网格中的每个单元格，从该单元格开始进行深度优先搜索（DFS）。
  3. DFS 的过程中，每访问一个新单元格，就检查它对应的字符是否存在于前缀树中。
  4. 如果当前路径构成的字符串是前缀树中的一个单词，就将其加入结果集。
  5. 利用前缀树，一旦某个字符在当前路径中不匹配任何前缀，就可以剪枝，避免不必要的搜索。

1. 键值映射

这道题要求你实现一个字典，支持插入键值对和计算具有某个前缀的所有键对应值的总和。

• 思路：
  1. 构建一个前缀树，每个节点除了子节点指针外，还要存储一个累加值。
  2. insert(key, val)：在插入时，从根节点开始遍历 key 的每个字符。每经过一个节点，都将该节点的累加值更新为 val。
  3. sum(prefix)：遍历 prefix 对应的路径，返回最后一个节点的累加值。

前缀树在处理与字符串前缀相关的查找、插入、计数等问题时，是一种非常高效且优雅的解决方案。

区间集合

c++刷题

c++的STL相比于java集合的使用没有那么简单,迭代器以及一些容器类的使用更加晦涩.

这里介绍一些常用类,常用方法以及注意事项,还有一些没那么常见的类也要看一看注意一下.

使用c++STL需要注意的点是容器本身的方法和std下提供的算法的不同,比如参数是size_type还是iter_pos,以及返回值是迭代器还是size_type.

std::find以及string.find,map.find等差别.erase返回值的差别

vector的常用操作

很常用容器,支持随机访问以及尾部增删

注意它没有find方法,因为可以使用遍历方便查找,或者使用std::find.

std::vector 是 C++ STL 中最常用的容器之一，因为它兼具动态数组的灵活性和 C 风格数组的性能优势。但在 LeetCode 刷题或实际开发中，如果不注意一些细节，它也可能带来性能问题或难以排查的 bug。

std::vector 常用方法注意事项

1. 索引访问：[] vs. .at()

• vec[index] (下标运算符)：
  • 优点：速度最快，因为它不执行边界检查。
  • 缺点：如果 index 超出 [0, vec.size() - 1] 范围，会导致未定义行为 (Undefined Behavior)。这可能表现为程序崩溃、数据损坏或看似随机的错误。
  • 注意事项：仅在你100%确定索引有效时使用。在 LeetCode 这种注重性能的场景，如果你的逻辑能保证索引有效，它很常见。
• vec.at(index) (成员函数)：
  • 优点：执行边界检查。如果 index 超出范围，会抛出 std::out_of_range 异常，这使得调试更容易。
  • 缺点：由于额外的检查，其性能略低于 []。
  • 注意事项：在你不确定索引是否总是有效时，或者在需要严格错误处理的生产代码中，更推荐使用 .at()。

2. push_back() 的性能与 reserve()

• vec.push_back(value)：
  • 优点：方便地在末尾添加元素。
  • 注意事项：当 vector 的当前容量不足以容纳新元素时，它会进行重新分配 (reallocation)。
    • 重新分配会涉及：
      1. 分配一块更大的新内存（通常是当前容量的 1.5 倍或 2 倍）。
      2. 将所有现有元素复制（或移动）到新内存。
      3. 释放旧内存。
    • 这是一个相对昂贵的操作，特别是当 vector 很大时。频繁的重新分配会严重影响性能。
• vec.reserve(new_cap)：
  • 功能：预留 new_cap 大小的内存空间，但不改变 vector 的实际大小 (size())。
  • 优点：如果你知道 vector 大致会增长到多大，或者需要添加大量元素，预先调用 reserve() 可以避免多次重新分配，显著提升性能。
  • 注意事项：reserve() 只能增加容量，不能减少。

3. 迭代器失效 (Iterator Invalidation)

• 当 vector 发生重新分配时：所有指向其内部元素的迭代器、指针和引用都会失效。这意味着它们可能指向错误的内存地址，或者指向已经被释放的内存。

• 常见的引起重新分配的操作：

  • push_back() (当容量不足时)
  • insert()
  • resize()
  • erase() (虽然 erase 返回下一个有效迭代器，但它也会使被删除元素及之后的所有迭代器失效)

• 注意事项：

  • 在循环中进行 erase() 操作时，如果使用传统的 for 循环，必须小心处理返回的迭代器：it = vec.erase(it);
  • 在进行可能引起重新分配的操作后，务必重新获取迭代器。

  erase 的重载版本都会使从被删除元素（或范围）开始到 vector 末尾的所有迭代器、指针和引用失效。因此，在使用 erase 后，你通常需要重新获取迭代器。 erase主要是删除指定迭代器或者迭代器范围,参数没有size_type指定索引的类型.

  std::remove 和 erase-remove 惯用法

  在需要删除满足特定条件的所有元素时，通常不直接在循环中使用 erase，而是使用 std::remove (或 std::remove_if) 结合 vector::erase 的惯用法。这种方法通常更高效，因为它只进行一次数据移动。

  • std::remove (或 std::remove_if)：这是一个算法（在 <algorithm> 中），它将所有要“删除”的元素移动到范围的末尾，并返回一个指向新逻辑末尾的迭代器。它不实际删除元素，也不改变容器的大小。
  • vector::erase：然后使用 vector::erase 来删除从 std::remove 返回的迭代器到 vector.end() 之间的元素，从而真正改变 vector 的大小并释放内存。

4.pop_back() 与 front()/back() 的使用

• vec.pop_back() 和 vec.front() / vec.back()：

  • 注意事项：在使用这些方法前，必须确保 vector 非空（即 !vec.empty()）。如果 vector 为空时调用它们，会导致未定义行为。

  vec.front()

  • 功能： 返回 vector 中第一个元素的引用。
  • 返回值： 对第一个元素的引用 (T&)。
  • 注意事项： vector 不能为空。调用空 vector 的 front() 会导致未定义行为。
  • 例子： int first = myVector.front();

  vec.back()

  • 功能： 返回 vector 中最后一个元素的引用。
  • 返回值： 对最后一个元素的引用 (T&)。
  • 注意事项： vector 不能为空。调用空 vector 的 back() 会导致未定义行为。
  • 例子： int last = myVector.back();

  vec.data() (C++11)

  • 功能： 返回指向 vector 内部存储数据的首个元素的指针。这允许你将 vector 的数据作为 C 风格数组传递给 C 语言 API。
  • 返回值： T* (非 const 版本) 或 const T* ( const 版本)。
  • 注意事项： 返回的指针在 vector 重新分配内存后会失效。
  • 例子： int* rawArray = myVector.data();

5. clear() vs. shrink_to_fit()

• vec.clear():

  • 功能：删除 vector 中的所有元素，使其 size() 变为 0。
  • 注意事项：它不一定会释放 vector 内部已分配的内存，capacity() 可能保持不变。

• vec.shrink_to_fit() (C++11):

  • 功能：请求 vector 将其容量调整到刚好足以容纳当前元素（即 capacity() 变为 size()）。这是一个提示，不保证一定会减少容量。

  • 注意事项：如果 vector 之前有过大量元素，然后清空或删除了大部分，但你希望立即释放多余内存以节省资源，可以使用它。但频繁调用也可能导致不必要的开销。

6.插入与删除元素

vec.insert(const_iterator position, const T& value) / vec.insert(const_iterator position, T&& value)

• 功能： 在 position 迭代器指向的位置之前插入一个 value。
• 返回值： 指向新插入元素的迭代器。
• 注意事项： 插入操作会使 position 及其之后所有迭代器失效。如果容量不足，会触发重新分配。时间复杂度为 O(N)，因为需要移动 position 之后的所有元素。
• 例子： auto it = myVector.insert(myVector.begin() + 1, 99);

ec.insert(const_iterator position, size_type count, const T& value)

• 功能： 在 position 迭代器指向的位置之前插入 count 个 value。
• 返回值： 指向第一个新插入元素的迭代器。
• 注意事项： 同单元素 insert。

vec.insert(const_iterator position, InputIt first, InputIt last)

• 功能： 在 position 迭代器指向的位置之前插入 [first, last) 范围内的元素。
• 返回值： 指向第一个新插入元素的迭代器。
• 注意事项： 同单元素 insert。

vec.emplace(const_iterator position, Args&&... args) (C++11)

• 功能： 在 position 迭代器指向的位置就地构造一个元素。
• 返回值： 指向新构造元素的迭代器。
• 注意事项： 同 insert。

vec.erase(const_iterator position)

• 功能： 删除 position 迭代器指向的单个元素。
• 返回值： 指向被删除元素之后第一个有效元素的迭代器。如果删除的是最后一个元素，则返回 vec.end()。
• 注意事项： 删除操作会使 position 及其之后的所有迭代器失效。时间复杂度为 O(N)。
• 例子： auto it_next = myVector.erase(myVector.begin() + 1);

vec.erase(const_iterator first, const_iterator last)

• 功能： 删除 [first, last) 范围内的元素。
• 返回值： 指向被删除范围之后第一个有效元素的迭代器。如果删除的范围包含 vector 的所有元素直到末尾，则返回 vec.end()。
• 注意事项： 删除操作会使 first 及其之后的所有迭代器失效。时间复杂度为 O(N)。
• 例子： auto it_next = myVector.erase(myVector.begin() + 1, myVector.begin() + 3);

vec.swap(std::vector& other)

• 功能： 高效地交换两个 vector 的内容。这是一种常数时间操作，因为它只交换了内部的指针和大小信息。
• 返回值： void。
• 注意事项： 交换后，迭代器和引用仍然指向它们原来的元素，只是这些元素现在属于另一个 vector 对象了。

7.构造函数与 resize() 的区别

• 构造函数 std::vector<T> vec(count);：创建 count 个元素，并对它们进行默认初始化。
• vec.resize(count);：如果 count 大于当前 size()，会添加新的元素并进行默认初始化。
• vec.clear(); 之后再 vec.resize(count);：会清空现有元素，然后创建 count 个新元素并默认初始化。

string的常用操作

主要是insert,erase的返回值,vector的insert,erase操作只能是迭代器并返回操作成功指向的迭代器(insert返回指向的插入成功的迭代器,erase返回指向删除后的下一个迭代器)

而string的insert和erase的重载方法中有参数是索引,返回值是指向字符串自身的引用,也就是说可以链式调用.

std::string& insert(size_type index, const std::string& str); 等重载

• 返回值： 字符串自身的引用（*this）。
• 注意事项： 在指定位置 index 插入内容。index 不能超过 size()，否则抛出 std::out_of_range。插入操作可能涉及大量字符移动，性能开销较大。

std::string& erase(size_type index = 0, size_type count = npos); 等重载

• 返回值： 字符串自身的引用（*this）。
• 注意事项： 从 index 位置开始删除 count 个字符。index 不能超过 size()，否则抛出 std::out_of_range。删除操作可能涉及大量字符移动。

并且注意,erase的第一个参数是offset,第二个参数是删除个数,默认一直删到末尾.

类似的参数还有substr,第一个参数是offset,第二个参数是limit.

std::string substr(size_type pos = 0, size_type len = npos) const;

• 返回值： 从 pos 位置开始，长度为 len 的新字符串。
• 注意事项： 返回一个副本，而不是引用。pos 不能超过 size()，否则抛出 std::out_of_range。len 超过实际可用长度时会被截断。

此外erase,insert也有对应参数为迭代器的重载

1
2
3
4
5
6
7

iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);

iterator insert(const_iterator pos, CharT c);
iterator insert(const_iterator pos, size_type count, CharT c);
template<class InputIt>
iterator insert(const_iterator pos, InputIt first, InputIt last);

迭代器失效： 大多数 insert 操作都可能导致字符串重新分配内存，这会使所有之前获得的指向该字符串内部的迭代器和指针失效。这意味着你不能在 insert 操作之后依赖旧的迭代器继续操作。如果你需要继续迭代，应该使用 insert 的返回值（新的迭代器）。

性能开销： 在字符串的中间或开头进行插入操作，通常需要移动大量现有字符，这会带来较大的性能开销。如果性能是关键考虑因素，并且需要频繁在中间插入，你可能需要重新评估数据结构或算法。

字符串查找可以使用find,返回值是索引

作用： 在字符串中查找子串或字符。

• size_type find(const std::string& str, size_type pos = 0) const; / find(CharT c, size_type pos = 0) const; 等重载
  • 返回值： 如果找到，返回第一次出现的起始位置索引；如果未找到，返回 std::string::npos。
  • 注意事项： pos 指定从哪个位置开始查找。npos 是 size_type 的一个特殊静态成员常量，通常是 size_type 的最大值，表示“找不到”。
• size_type rfind(const std::string& str, size_type pos = npos) const; 等重载
  • 返回值： 如果找到，返回最后一次出现的起始位置索引；如果未找到，返回 std::string::npos。
  • 注意事项： rfind 从字符串末尾开始向前查找（但返回的索引是从字符串开头算的）。
• size_type find_first_of(const std::string& str, size_type pos = 0) const; 等重载
  • 返回值： 查找 str 中任意一个字符在当前字符串中第一次出现的索引。
  • 注意事项： 如果 str 是 "aeiou"，它会查找 a 或 e 或 i 或 o 或 u 中任意一个字符的第一次出现。
• size_type find_last_of(const std::string& str, size_type pos = npos) const; 等重载
  • 返回值： 查找 str 中任意一个字符在当前字符串中最后一次出现的索引。
• size_type find_first_not_of(const std::string& str, size_type pos = 0) const; 等重载
  • 返回值： 查找不在 str 中的字符在当前字符串中第一次出现的索引。
• size_type find_last_not_of(const std::string& str, size_type pos = npos) const; 等重载
  • 返回值： 查找不在 str 中的字符在当前字符串中最后一次出现的索引。

还有个replace方法可能容易忽略,能替换字符串

std::string& replace(size_type pos, size_type len, const std::string& str); 等重载

• 返回值： 字符串自身的引用（*this）。
• 注意事项： 将 pos 位置开始、长度为 len 的子串替换为 str。

一般注意事项：

• 内存管理： std::string 会自动管理内存，你无需手动 new 或 delete。当字符串内容变化且当前容量不足时，它会自动重新分配内存（通常会以指数级增长，如 1.5 倍或 2 倍）。
• 异常安全： std::string 的大多数操作都提供异常安全保证。
• 性能考量： 频繁的字符串拼接、插入、删除操作（尤其是字符串头部或中部）可能导致多次内存重新分配和数据拷贝，影响性能。在这种情况下，考虑使用 reserve() 预分配内存，或者考虑使用其他数据结构（如 std::vector<char> 或字符数组）在底层操作，再转换为 std::string。
• std::string::npos： 这是一个静态成员常量，表示“未找到”或“到字符串末尾”。
• 空字符串： 大多数操作都能正确处理空字符串，但访问 front()、back()、operator[] 或 erase() 等可能需要非空字符串的操作时，要特别注意空字符串的情况，避免未定义行为。

list与deque的常用操作

list是双向链表,在链表两端增删数据效率O(1),但查询需要遍历,而deque支持随机访问.

std::list 是一个双向链表实现，这意味着它的元素在内存中不一定是连续存储的。每个元素都包含指向前一个和后一个元素的指针。

快速插入/删除： 在列表的任何位置进行插入和删除操作都是常数时间复杂度 O(1)，因为只需要修改少量指针。

不支持随机访问： 无法通过索引 [] 或 at() 直接访问元素，访问元素需要线性时间 O(n) 遍历。

迭代器稳定性： 插入和删除操作不会使其他迭代器失效（除了被删除的元素对应的迭代器）。

内存开销： 每个元素除了存储数据本身，还需要额外的内存来存储前后指针，因此比 std::vector 和 std::deque 有更高的内存开销。

iterator erase(const_iterator pos);

• 返回值： 指向被删除元素之后的元素的迭代器。
• 注意事项： 删除 pos 处元素。O(1) 复杂度。pos 必须有效且不能是 end()。

iterator erase(const_iterator first, const_iterator last);

• 返回值： 指向被删除范围之后的元素的迭代器。
• 注意事项： 删除范围 [first, last) 的元素

std::list 作为双向链表，其核心优势在于高效的非尾部插入和删除以及迭代器稳定性。因此，它拥有一系列专门针对链表特性的方法：

1. splice() 系列方法
   • 作用： 这是 std::list 最独特且功能强大的方法之一。它能以 O(1) 的复杂度（不包括查找插入位置和移动元素的迭代器）将一个 list 的元素移动到另一个 list 中，或者移动一个 list 中的部分元素。元素不是复制，而是直接修改它们的链表指针，效率极高。
   • 重载示例：
     • void splice(const_iterator pos, std::list& other);：将 other 整个列表的所有元素移动到当前列表的 pos 之前。other 列表会变空。
     • void splice(const_iterator pos, std::list& other, const_iterator it);：将 other 列表中 it 指向的单个元素移动到当前列表的 pos 之前。
     • void splice(const_iterator pos, std::list& other, const_iterator first, const_iterator last);：将 other 列表中 [first, last) 范围内的元素移动到当前列表的 pos 之前。
   • vector 对比： std::vector 没有 splice 方法，因为其底层是连续内存，任何元素的“移动”实际上都是复制和删除，需要 O(n) 复杂度。
2. remove() 和 remove_if()
   • 作用： 删除列表中所有等于特定值（remove）或满足特定条件（remove_if）的元素。
   • 重载示例：
     • void remove(const T& value);
     • template<class Predicate> void remove_if(Predicate pred);
   • vector 对比： std::vector 通常通过“移除-擦除 (erase-remove idiom)”来实现类似功能：vec.erase(std::remove(vec.begin(), vec.end(), value), vec.end());。这在 std::vector 中是 O(n) 操作，并且会移动元素，而 std::list 的 remove 操作是真正的 O(n) 遍历和 O(1) 删除每个元素。
3. unique()
   • 作用： 删除列表中连续的重复元素。
   • 重载示例：
     • void unique();
     • template<class BinaryPredicate> void unique(BinaryPredicate binary_pred);
   • vector 对比： std::vector 使用 std::unique 算法（同样需要配合 erase），它也只删除连续重复的元素。但 list 的 unique 是成员函数，是针对链表优化的。
4. merge()
   • 作用： 将另一个已排序的列表的元素合并到当前列表，使当前列表保持排序。另一个列表会被清空。
   • 重载示例：
     • void merge(std::list& other);
     • template<class Compare> void merge(std::list& other, Compare comp);
   • vector 对比： std::vector 通常使用 std::merge 算法，它会创建一个新容器来存放合并结果，而不是直接在原地合并并清空源容器。list 的 merge 操作是基于链表指针的 O(n) 高效合并。
5. sort()
   • 作用： 对列表进行排序。
   • 重载示例：
     • void sort();
     • template<class Compare> void sort(Compare comp);
   • vector 对比： std::vector 使用全局函数 std::sort，它要求随机访问迭代器。由于 std::list 不支持随机访问，它不能使用 std::sort，因此它提供了自己的成员 sort() 方法，通常是基于归并排序（merge sort）的变种，以适应链表结构。
6. reverse()
   • 作用： 反转列表中元素的顺序。
   • 重载示例：
     • void reverse();
   • vector 对比： std::vector 可以使用 std::reverse 算法。list 的 reverse 是成员函数，针对链表结构优化。

std::deque (double-ended queue) 是一个双端队列容器，它支持在两端（头部和尾部）快速插入和删除元素。它在内部通常实现为分段的动态数组，这意味着其元素在内存中不一定是连续的，但可以通过一个“映射”结构来快速访问。

std::deque 的设计目标是支持两端的高效插入/删除，同时保留随机访问的能力。虽然它的特殊方法不如 std::list 那么多，但其头部操作是其显著优势

头部/尾部快速插入/删除： push_front(), pop_front(), push_back(), pop_back() 都是常数时间复杂度 O(1)。

随机访问： 支持通过索引 [] 和 at() 进行随机访问，平均是常数时间复杂度 O(1) (因为它通过映射表快速找到对应内存段)。

中部插入/删除： 在中部插入和删除元素是线性时间复杂度 O(n)，因为可能需要移动元素。

迭代器稳定性：

• 在头部或尾部插入/删除不会使现有迭代器失效（除了指向被删除元素的迭代器）。
• 在中部插入或删除会使所有迭代器失效。

内存使用： 比 std::vector 更灵活，因为它不要求连续内存，但可能比 std::vector 有略高的间接访问开销。

iterator insert(const_iterator pos, const T& value); / insert(const_iterator pos, T&& value); 等重载

• 返回值： 指向新插入元素的迭代器。
• 注意事项： 在 pos 迭代器指向的位置之前插入元素。中部插入是 O(n) 复杂度。pos 可以是 end()。所有迭代器可能失效。

iterator insert(const_iterator pos, size_type count, const T& value);

• 返回值： 指向新插入序列第一个元素的迭代器。

template<class InputIt> iterator insert(const_iterator pos, InputIt first, InputIt last);

• 返回值： 指向新插入序列第一个元素的迭代器。

iterator erase(const_iterator pos);

• 返回值： 指向被删除元素之后的元素的迭代器。
• 注意事项： 删除 pos 处元素。中部删除是 O(n) 复杂度。pos 必须有效且不能是 end()。所有迭代器可能失效。

iterator erase(const_iterator first, const_iterator last);

• 返回值： 指向被删除范围之后的元素的迭代器。
• 注意事项： 删除范围 [first, last) 的元素。

void clear();

• 返回值： void。
• 注意事项： 删除所有元素，双端队列变为空。

void resize(size_type count); / void resize(size_type count, const T& value);

• 返回值： void。
• 注意事项： 改变双端队列大小。

void swap(std::deque& other);

• 返回值： void。
• 注意事项： 交换两个双端队列的内容，O(1) 复杂度

push_front()

• 作用： 在双端队列的头部添加一个元素。
• 重载示例：
  • void push_front(const T& value);
  • void push_front(T&& value);
• vector 对比： std::vector 没有 push_front() 方法。在 vector 的头部插入元素需要将所有现有元素后移，复杂度为 O(n)，效率极低。deque 的 push_front() 是常数时间复杂度 O(1) (均摊)。

pop_front()

• 作用： 删除双端队列的头部元素。
• 重载示例：
  • void pop_front();
• vector 对比： std::vector 没有 pop_front() 方法。在 vector 的头部删除元素同样需要将所有后续元素前移，复杂度为 O(n)。deque 的 pop_front() 是常数时间复杂度 O(1) (均摊)。

std::vector 专注于连续内存和快速随机访问，以及尾部操作。它的优势在于缓存局部性好，适合作为动态数组。

std::list 则专注于高效的任意位置插入和删除，其 splice()、remove()、merge() 和成员 sort() 等方法都是其链表特性的体现，是 vector 所不具备的。

std::deque 则是介于两者之间，它提供了 vector 的大部分功能（包括随机访问），同时具备 list 在两端操作上的 O(1) 优势，即 push_front() 和 pop_front() 是其独有且高效的操作。

stack与queue

std::stack 和 std::queue 是 C++ 标准库（STL）中两种非常重要的容器适配器（Container Adapters）。它们不是独立的底层数据结构，而是将现有的序列容器（如 std::deque、std::list 或 std::vector）封装起来，提供特定的访问接口，从而模拟栈（LIFO，后进先出）和队列（FIFO，先进先出）的行为。

构造函数 (Constructors)

• std::stack<T> s;
  • 功能： 创建一个空的栈。默认底层容器是 std::deque<T>。
  • 返回值： 无。
  • 例子： std::stack<int> myStack;
• std::stack<T, Container> s(container_obj);
  • 功能： 使用指定的底层容器类型 Container 创建栈，并用一个现有容器对象初始化。
  • 返回值： 无。
  • 例子： std::list<int> myList = {1, 2, 3}; std::stack<int, std::list<int>> myStackFromList(myList);

s.push(const T& value)

• 功能： 在栈顶插入一个元素。
• 返回值： 无。
• 例子： myStack.push(10);

s.pop()

• 功能： 移除栈顶元素。
• 返回值： 无。
• 注意事项： 不返回被移除的元素。 在调用前必须确保栈不为空，否则会导致未定义行为。
• 例子： myStack.pop();

s.top()

• 功能： 返回栈顶元素的引用。
• 返回值： T& (对栈顶元素的引用)。
• 注意事项： 不移除元素。 在调用前必须确保栈不为空，否则会导致未定义行为。
• 例子： int topElement = myStack.top();

std::queue<T> q;

• 功能： 创建一个空的队列。默认底层容器是 std::deque<T>。
• 返回值： 无。
• 例子： std::queue<std::string> myQueue;

std::queue<T, Container> q(container_obj);

• 功能： 使用指定的底层容器类型 Container 创建队列，并用一个现有容器对象初始化。
• 返回值： 无。
• 例子： std::vector<std::string> myVec = {"A", "B"}; std::queue<std::string, std::vector<std::string>> myQueueFromVec(myVec); （注意：vector 不支持 pop_front，所以不能作为 queue 的底层容器。这里写错，正确的应该是 std::list 或 std::deque）
• 更正例子： std::deque<std::string> myDeque = {"A", "B"}; std::queue<std::string, std::deque<std::string>> myQueueFromDeque(myDeque);

q.push(const T& value)

• 功能： 在队尾插入一个元素。
• 返回值： 无。
• 例子： myQueue.push("Task 1");

q.pop()

• 功能： 移除队头元素。
• 返回值： 无。
• 注意事项： 不返回被移除的元素。 在调用前必须确保队列不为空，否则会导致未定义行为。
• 例子： myQueue.pop();

q.front()

• 功能： 返回队头元素的引用。
• 返回值： T& (对队头元素的引用)。
• 注意事项： 不移除元素。 在调用前必须确保队列不为空，否则会导致未定义行为。
• 例子： std::string currentTask = myQueue.front();

q.back()

• 功能： 返回队尾元素的引用。
• 返回值： T& (对队尾元素的引用)。
• 注意事项： 不移除元素。 在调用前必须确保队列不为空，否则会导致未定义行为。
• 例子： std::string lastAddedTask = myQueue.back();

注意队列有q.back获得队尾元素,而栈只能访问一端,也就是栈顶.

map/unordered_map

std::map 是 C++ 标准库中的一个有序关联容器，它存储键值对 (key-value pairs)。它的主要特点是：

• 键是唯一的：std::map 中不允许有重复的键。
• 元素是排序的：std::map 中的所有元素都会根据它们的键自动进行升序排序。默认情况下，它使用键类型的 operator< 进行排序。
• 底层实现是平衡二叉搜索树：通常是红黑树。这确保了大部分操作的对数时间复杂度。

std::map<Key, Value> m;

• 功能： 创建一个空的 map。
• 返回值： 无。
• 示例： std::map<std::string, int> wordCounts;

std::map<Key, Value> m = {{k1, v1}, {k2, v2}};

• 功能： 使用初始化列表创建 map。
• 返回值： 无。
• 示例： std::map<int, char> grades = {{1, 'A'}, {2, 'B'}};

std::map<Key, Value> m(first, last);

• 功能： 从另一个范围 [first, last) 初始化 map，范围内的元素必须是键值对类型（如 std::pair<Key, Value>）。
• 返回值： 无。

m.insert({key, value}) / m.insert(std::make_pair(key, value))

• 功能： 插入一个键值对。如果 key 已存在，则插入失败，map 不会被修改。
• 返回值： std::pair<iterator, bool>。
  • iterator 指向新插入的元素或已存在的具有相同键的元素。
  • bool 为 true 表示成功插入新元素，false 表示元素已存在。

m.emplace(Args&&... args) (C++11)

• 功能： 在 map 中就地构造一个键值对。通常比 insert 接受 std::pair 更高效。
• 返回值： 同 insert。

m.erase(const Key& key)

• 功能： 删除 map 中匹配 key 的键值对。
• 返回值： size_type，表示被删除元素的数量（对于 map 而言，总是 0 或 1，因为键是唯一的）。

m.erase(iterator pos)

• 功能： 删除 pos 迭代器指向的单个元素。
• 返回值： 指向被删除元素之后第一个有效元素的迭代器。如果删除的是最后一个元素，则返回 m.end()。

m.erase(iterator first, iterator last)

• 功能： 删除 [first, last) 范围内的元素。
• 返回值： 指向被删除范围之后第一个有效元素的迭代器。

m.count(const Key& key)

• 功能： 返回 map 中匹配 key 的元素数量。
• 返回值： size_type (对于 map 而言，总是 0 或 1)。

m.find(const Key& key)

• 功能： 查找 map 中匹配 key 的元素。
• 返回值： 如果找到，返回指向该元素的迭代器；否则，返回 m.end() 迭代器。

m.lower_bound(const Key& key)

• 功能： 返回指向第一个键不小于 key 的元素的迭代器。
• 返回值： iterator。

m.upper_bound(const Key& key)

• 功能： 返回指向第一个键大于 key 的元素的迭代器。
• 返回值： iterator

std::unordered_map 是一种无序的关联容器，它通过哈希表（Hash Table）实现。它也存储键值对，但元素没有特定的排序，而是根据键的哈希值来组织。

um.insert({key, value}) / um.insert(std::make_pair(key, value))

• 功能： 插入一个键值对。如果 key 已存在，则插入失败。
• 返回值： std::pair<iterator, bool>。同 std::map。

um.emplace(Args&&... args) (C++11)

• 功能： 就地构造一个键值对。
• 返回值： 同 insert。

um.erase(const Key& key)

• 功能： 删除 unordered_map 中匹配 key 的键值对。
• 返回值： size_type，表示被删除元素的数量（对于 unordered_map 而言，总是 0 或 1，因为键是唯一的）。

um.erase(iterator pos)

• 功能： 删除 pos 迭代器指向的单个元素。
• 返回值： 指向被删除元素之后下一个可能有效（但无序）的元素的迭代器。

um.erase(iterator first, iterator last)

• 功能： 删除 [first, last) 范围内的元素。
• 返回值： 指向被删除范围之后下一个可能有效（但无序）的元素的迭代器。

um.count(const Key& key)

• 功能： 返回 unordered_map 中匹配 key 的元素数量。
• 返回值： size_type (总是 0 或 1)。

um.find(const Key& key)

• 功能： 查找 unordered_map 中匹配 key 的元素。
• 返回值： 如果找到，返回指向该元素的迭代器；否则，返回 um.end() 迭代器。

set/unordered_set

std::set 是一种有序的关联容器，它存储唯一的元素，并且所有元素都根据其值的严格弱序（strict weak ordering）\进行排序。其底层通常实现为*红黑树（Red-Black Tree）*。

std::set<T> s;

• 功能： 创建一个空的 set。
• 返回值： 无。
• 示例： std::set<int> mySet;

std::set<T> s = {e1, e2, ...};

• 功能： 使用初始化列表创建 set。
• 返回值： 无。
• 示例： std::set<std::string> uniqueWords = {"apple", "banana", "apple"}; (实际只存储 “apple”, “banana”)

std::set<T> s(first, last);

• 功能： 从另一个范围 [first, last) 初始化 set。
• 返回值： 无。

s.insert(const T& value) / s.insert(T&& value)

• 功能： 插入一个元素。如果 value 已存在，则插入失败，set 不会被修改。
• 返回值： std::pair<iterator, bool>。
  • iterator 指向新插入的元素或已存在的相同元素。
  • bool 为 true 表示成功插入新元素，false 表示元素已存在。

s.emplace(Args&&... args) (C++11)

• 功能： 在 set 中就地构造一个元素。
• 返回值： 同 insert。

s.erase(const T& value)

• 功能： 删除 set 中匹配 value 的元素。
• 返回值： size_type，表示被删除元素的数量（对于 set 而言，总是 0 或 1，因为元素是唯一的）。

s.erase(iterator pos)

• 功能： 删除 pos 迭代器指向的单个元素。
• 返回值： 指向被删除元素之后第一个有效元素的迭代器。如果删除的是最后一个元素，则返回 s.end()。

s.erase(iterator first, iterator last)

• 功能： 删除 [first, last) 范围内的元素。
• 返回值： 指向被删除范围之后第一个有效元素的迭代器。

s.count(const T& value)

• 功能： 返回 set 中匹配 value 的元素数量。
• 返回值： size_type (对于 set 而言，总是 0 或 1)。

s.find(const T& value)

• 功能： 查找 set 中匹配 value 的元素。
• 返回值： 如果找到，返回指向该元素的迭代器；否则，返回 s.end() 迭代器。

s.lower_bound(const T& value)

• 功能： 返回指向第一个不小于 value 的元素的迭代器。
• 返回值： iterator。

s.upper_bound(const T& value)

• 功能： 返回指向第一个大于 value 的元素的迭代器。
• 返回值： iterator。

std::set 的元素类型 (T) 必须是可比较的。这意味着它必须能够通过 operator< 进行排序，或者你需要提供一个自定义的比较函数。

std::unordered_set 是一种无序的关联容器，它存储唯一的元素。其底层通过哈希表（Hash Table）实现。

us.insert(const T& value) / us.insert(T&& value)

• 功能： 插入一个元素。如果 value 已存在，则插入失败。
• 返回值： std::pair<iterator, bool>。同 std::set。

us.emplace(Args&&... args) (C++11)

• 功能： 就地构造一个元素。
• 返回值： 同 insert。

us.erase(const T& value)

• 功能： 删除 unordered_set 中匹配 value 的元素。
• 返回值： size_type，表示被删除元素的数量（对于 unordered_set 而言，总是 0 或 1）。

us.erase(iterator pos)

• 功能： 删除 pos 迭代器指向的单个元素。
• 返回值： 指向被删除元素之后下一个可能有效（但无序）的元素的迭代器。

us.erase(iterator first, iterator last)

• 功能： 删除 [first, last) 范围内的元素。
• 返回值： 指向被删除范围之后下一个可能有效（但无序）的元素的迭代器。

us.count(const T& value)

• 功能： 返回 unordered_set 中匹配 value 的元素数量。
• 返回值： size_type (总是 0 或 1)。

us.find(const T& value)

• 功能： 查找 unordered_set 中匹配 value 的元素。
• 返回值： 如果找到，返回指向该元素的迭代器；否则，返回 us.end() 迭代器。

erase与find的参数与对应返回值

在map/set以及unordered_map/unordered_set中,erase成员方法参数如果是size_type,返回值是删除个数,如果是迭代器或者迭代器范围,返回值指向下一个元素迭代器. 而find通过值返回迭代器.

而在string中,erase参数是offset与len,返回指向新字符串的引用,find参数是字符或字符串返回size_type索引.

而在vector,list中,erase参数是迭代器或者迭代器范围,返回删除成功后指向的下一个元素迭代器,而没有find成员方法.

priority_queue

std::priority_queue 是 C++ 标准库 (STL) 中的一个容器适配器 (Container Adapter)，它提供了一个类似队列的接口，但其内部元素总是按照特定优先级排序。默认情况下，它是一个最大堆（Max-Heap），意味着队头元素总是当前所有元素中最大的

std::priority_queue<T> pq;

• 功能： 创建一个空的优先级队列。默认底层容器是 std::vector<T>，默认比较器是 std::less<T> (用于实现最大堆)。
• 返回值： 无。
• 示例： std::priority_queue<int> max_heap;

std::priority_queue<T, Container, Compare> pq(comp);

• 功能： 使用指定的底层容器类型 Container 和自定义比较器 Compare 创建优先级队列。comp 是比较器的实例。

• 返回值： 无。

• 示例 (最小堆 - Min-Heap)：

  1	std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

  这里，std::greater<int> 使得“大”的元素优先级“低”（因为 a > b 为 true，a 就排在 b 后面），从而实现最小堆。

pq.push(const T& value)

• 功能： 插入一个元素到优先级队列中。它会根据优先级自动将其放置到正确的位置，并维护堆的属性。
• 返回值： 无。
• 例子： max_heap.push(10);

pq.pop()

• 功能： 移除优先级最高的元素（即堆顶元素）。
• 返回值： 无。
• 注意事项： 不返回被移除的元素。 在调用前必须确保队列不为空，否则会导致未定义行为。
• 例子： max_heap.pop();

pq.top()

• 功能： 返回优先级最高的元素（即堆顶元素）的常量引用。
• 返回值： const T& (对堆顶元素的常量引用)。
• 注意事项： 不移除元素。 在调用前必须确保队列不为空，否则会导致未定义行为。
• 例子： int highest_priority_element = max_heap.top();

pq.empty()

• 功能： 检查优先级队列是否为空。
• 返回值： bool (true 表示空，false 表示非空)。
• 例子： if (max_heap.empty()) { /* 队列为空 */ }

pq.size()

• 功能： 返回优先级队列中元素的数量。
• 返回值： size_type (无符号整数类型)。
• 例子： std::cout << max_heap.size();

vector 可以作为 map 的键但不能直接作为 unordered_map 的键

set同理.

std::map 是一个有序关联容器，它的底层通常实现为红黑树（一种自平衡二叉搜索树）。std::map 存储元素时，需要能够对键进行排序。这意味着 std::map 的键类型必须是可比较的 (Comparable)，具体来说，它需要支持小于运算符 operator<。

而 std::vector 恰好默认提供了 operator< 的重载。

std::vector的operator<` 是如何工作的？

std::vector 的 operator< 执行的是字典序 (lexicographical comparison) 比较。这意味着它会逐个元素地比较两个 vector：

1. 从第一个元素开始比较。
2. 如果两个 vector 在某个位置上的元素不相等，那么拥有较小元素的那个 vector 被认为是“更小”的。
3. 如果一个 vector 是另一个 vector 的前缀（即较短的那个 vector 的所有元素都与较长的 vector 的对应前缀元素相同），那么较短的那个 vector 被认为是“更小”的。

关键在于它们底层的实现机制不同：

• std::map (基于红黑树)：

  • 需要键是可比较的（通过 operator<）。
  • std::vector 默认提供了字典序的 operator<，所以它满足这个要求。
  • 操作的平均时间复杂度是 O(logN)。

• std::unordered_map (基于哈希表)：

  • 需要键是可哈希的（通过 std::hash 特化）和可相等比较的（通过 operator==）。

  • std::vector 默认没有提供 std::hash 特化，所以它不满足这个要求，除非你自定义哈希函数。

  • 操作的平均时间复杂度是 O(1)。

    std::unordered_set 是一种无序集合容器，它存储唯一元素的集合。它的底层也是基于哈希表实现的。因此，它对所存储的元素类型有同样的要求：

    1. 可哈希 (Hashable)：必须存在 std::hash<T> 的特化，能够为元素类型 T 计算哈希值。
    2. 可相等比较 (EqualityComparable)：元素类型 T 必须支持 operator==，用于在哈希冲突时判断元素是否真正相等。

如果vector,string等作为map的key,然后对这个key进行了操作会怎样.

如果 std::map 的 key 是 std::vector，然后你对这个 作为 key 的 std::vector 对象本身 进行了修改（比如 push_back 元素或 clear），那会发生非常严重的问题，通常会导致未定义行为

std::map 依靠键的顺序来组织其内部的红黑树结构。当你插入一个 std::vector 作为键时，map 会使用 std::vector 的 operator< 来确定这个键在树中的位置。

如果你修改了这个 vector 键（例如 push_back），它的内容就变了，这意味着它的字典序比较结果也可能改变。

此时，红黑树的内部结构就会变得不一致 (corrupted)。树的节点仍然按照旧的键值进行组织，但实际的键值已经改变，导致查找、插入、删除等操作都会出错，因为它们会根据错误的顺序进行导航。最终结果就是未定义行为，程序可能崩溃，也可能产生错误的结果。

其他一些类

multimap/unordered_multimap

multiset/unordered_multiset

tuple

std::tuple 是一个固定大小的异构（heterogeneous）容器，可以存储不同类型的固定数量的对象。你可以把它想象成一个“增强版”的 std::pair，因为 pair 只能存储两个不同类型的元素，而 tuple 可以存储任意数量的不同类型元素。

核心特点

• 异构性: 存储的元素类型可以不同。
• 固定大小: tuple 的大小在编译时就确定了，不能动态改变。
• 零开销抽象: 通常，tuple 的性能可以媲美直接使用多个独立变量，编译器可以进行很好的优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <tuple>
#include <string>

std::tuple<int, double, std::string> t1(10, 3.14, "hello");
// 或使用 C++11 后的列表初始化（需要显式指定类型）
std::tuple<int, double, std::string> t2 = {20, 2.71, "world"};
auto t3 = std::make_tuple(30, 1.618, "C++"); // t3 类型为 std::tuple<int, double, const char*>
int i = std::get<0>(t1);         // 获取第一个元素 (10)
double d = std::get<1>(t1);      // 获取第二个元素 (3.14)
std::string s = std::get<2>(t1); // 获取第三个元素 ("hello")
constexpr size_t size = std::tuple_size<decltype(t1)>::value; // size = 3
auto person = std::make_tuple("Alice", 30, "New York");
auto [name, age, city] = person; // 相当于声明了 name, age, city 三个变量并赋值
std::cout << name << ", " << age << ", " << city << std::endl;

array

std::array 是一个固定大小的同构序列容器，它封装了 C 风格的静态数组。它提供了像 std::vector 一样的 STL 容器接口（如迭代器、size()、at() 等），但它的大小在编译时就确定，且不能改变。它的数据是直接存储在栈上（如果大小允许且不是全局/静态），而不是堆上，避免了动态内存分配的开销。

核心特点

• 固定大小: 大小在编译时已知且不可变。
• 同构性: 存储的元素类型必须相同。
• 栈分配: 数据通常直接存储在栈上（除非太大或声明为全局/静态），性能优势明显。
• C 风格数组的替代: 提供了 C 风格数组的性能，同时拥有 STL 容器的安全性（如边界检查 at()) 和易用性。

1
2
3
4

#include <array>

std::array<int, 5> arr1; // 声明一个包含 5 个 int 的 array，元素默认初始化 (int 为 0)
std::array<double, 3> arr2 = {1.1, 2.2, 3.3}; // 使用初始化列表

std下STL方法

遇到的错误

1. runtime error: addition of unsigned offset to 0x7fb499600340 overflowed to 0x7fb49960033f (basic_string.h)

这是一个非常典型的 Undefined Behavior (UB) 警告/错误，通常由 Clang/LLVM 编译器（或其衍生的 sanitizers，如 AddressSanitizer/ASan）在运行时检测到。

为什么会发生这种错误？

1. 无效的索引或指针算术：

   • 你可能在使用一个指针或迭代器，并对其添加了一个负数或一个非常大的无符号数，导致指针指向了它不应该指向的内存区域，甚至“绕回”到内存地址空间的低端。
   • 一个常见的场景是，你有一个指向数组末尾的指针，然后尝试对其进行 ptr + offset 操作，而 offset 是一个非常大的无符号数，或者实际上应该是一个负数但被误用为无符号数。

   例如：

   1 2 3

   char* p = some_array + size; // p 指向数组末尾之后一个位置 unsigned int offset = some_large_unsigned_value; char* invalid_p = p + offset; // 此时如果 offset 足够大，可能会导致地址回绕

   或者更直接的：

   1 2 3

   char* p = some_array; size_t invalid_idx = -1; // 这是一个非常大的无符号数 char element = p[invalid_idx]; // 等同于 p + invalid_idx，可能溢出

2. 减法错误导致无符号数溢出：

   • 如果你有一个无符号整型变量 u_var，并且执行 u_var - another_unsigned_var，如果 u_var < another_unsigned_var，结果将是一个非常大的正数（无符号数下溢）。
   • 然后你用这个非常大的结果作为内存偏移量。

   例如：

   1 2 3 4 5

   std::vector<int> v = {1, 2, 3}; size_t index = 0; // 假设某种逻辑错误导致 index 变成了 0，然后你尝试 index - 1 size_t prev_index = index - 1; // prev_index 会变成 size_t 的最大值 int val = v[prev_index]; // 访问越界，很可能导致地址回绕

3. 内存越界访问：

   • 虽然错误信息明确是“addition of unsigned offset … overflowed”，但最根本的原因常常是试图访问一个不在合法范围内的内存地址。
   • 尤其是在使用 size_t 或 unsigned int 作为索引或偏移量时，如果计算结果错误地变成了非常大的正数，就可能导致这种所谓的“溢出”。

4. Line 1122: Char 9: runtime error: reference binding to null pointer of type ‘int’ (stl_vector.h)

遇到的这个 runtime error: reference binding to null pointer of type 'int' (stl_vector.h) 错误，是一个非常经典的 C++ 未定义行为 (Undefined Behavior, UB) 错误，而且它通常是由 AddressSanitizer (ASan) 或其他内存安全工具在运行时检测到的。错误信息清晰地指出：你正在尝试将一个引用绑定到一个空指针上，而这是 C++ 标准不允许的。

虽然错误信息指向 stl_vector.h，但这通常意味着你的代码在尝试访问 std::vector 的某个元素时，使用了无效的索引，导致 std::vector 内部的指针（指向其元素存储的内存）被非法地用于引用绑定。

错误的根本原因

这个错误最常见的根本原因就是：你试图通过 [] 运算符或 at() 方法访问一个 std::vector 中不存在的元素。

具体来说，当 std::vector 为空或者你提供的索引超出了其有效范围时，会发生以下情况：

1. std::vector 为空：
   • 当 std::vector 的 size() 为 0 时，它可能不分配任何内存，或者其内部的 data() 指针就是 nullptr。
   • 此时，如果你尝试 myVector[0]，编译器并不知道 myVector 是空的，它会直接计算 data() + 0，如果 data() 是 nullptr，结果仍然是 nullptr。
   • 然后，对 *nullptr 进行解引用并尝试将其绑定到引用时，就会触发这个错误。
2. 索引越界 (Out-of-bounds access)：
   • 你尝试访问的索引 i 大于或等于 myVector.size()。
   • myVector[i] 的操作在内部通常被转换为 *(myVector.data() + i)。如果 i 足够大，超出了已分配内存的范围，甚至可能导致指针算术溢出（回到内存地址空间低端，接近 nullptr）或者直接尝试访问未映射的内存区域。
   • 如果恰好 myVector.data() + i 的结果接近或就是 nullptr，就会触发这个特定的错误