双指针

  • 定义：双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。最常见的双指针算法有两种：一种是，在一个序列里边，用两个指针维护一段区间；另一种是，在两个序列里边，一个指针指向其中一个序列，另外一个指针指向另外一个序列，来维护某种次序。

  • 模版：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for (int i = 0, j = 0; i < n; i ++ )  // j从某一位置开始，不一定是0
    {
        while (j < i && check(i, j)) j ++ ;

        // 具体问题的逻辑
    }
    //常见问题分类：
    //    (1) 对于一个序列，用两个指针维护一段区间，比如快排的划分过程
    //    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作


  • **核心思想：*优化，将时间复杂度为O(nn)优化为O(n)

  • **思路：**在利用双指针算法解题时,考虑原问题如何用暴力算法解出,观察是否可构成单调性,若可以,就可采用双指针算法对暴力算法进行优化.

二分

  • 模版

    1
    2
    3
    4
    5
    6
    7
    8
    //输出l相当于找最大值，输出r相当于找最小值
    int l = 0, r = n;
        while(r-l > 1) {
            int mid = (l+r)/2;
            if(a[mid] >= x) r = mid;
            else l = mid;
        }
        cout<<r<<" ";

深度优先搜索（DFS）

  • **简述：**一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

  • **核心思想：**为了求得问题的解，先选择某一种可能情况向前探索；在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索；如此反复进行，直至得到解或证明无解。

  • 操作步骤：

    1. 初始原点为v0，使用深度优先搜索，首先访问 v0 -> v1 -> v2 -> v5，到 v5 后面没有结点，则回溯到 v1 ，即最近的且连接有没访问结点的结点v1
    2. 此次从 v1 出发，访问 v1 -> v4 -> v6 -> v3，此时与v3相连的两个结点 v0 与 v6 都已经访问过，回溯到 v6 (v6 具有没访问过的结点)
    3. 此次从 v6 出发，访问 v6 -> v7，到 v7 后面没有结点，回溯
    4. 一直回溯到源点 v0 ，没有没访问过的结点，程序结束。

  • 模版

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    int a[510];   //存储每次选出来的数据
    int book[510];   //标记是否被访问
    int ans = 0; //记录符合条件的次数

    void DFS(int cur){
    	if(cur == k){ //k个数已经选完，可以进行输出等相关操作 
    		for(int i = 0; i < cur; i++){
    			printf("%d ", a[i]);
    		} 
    		ans++;
    		return ;
    	}
    	
    	for(int i = 0; i < n; i++){ //遍历 n个数，并从中选择k个数 
    		if(!book[i]){ //若没有被访问 
    			book[i] = 1; //标记已被访问 
    			a[cur] = i;  //选定本数，并加入数组 
    			DFS(cur + 1);  //递归，cur+1 
    			book[i] = 0;  //释放，标记为没被访问，方便下次引用 
    		}
    	}
    }

    滑动窗口

    • 滑动窗口是双指针算法的一种，基本思路为维护一个窗口，然后从前往后遍历元素进行运算。

    • 模版

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      int left = 0, right = 0;

      while (right < s.size()) {
          // 增大窗口
          window.add(s[right]);
          right++;
          
          while (window needs shrink) {
              // 缩小窗口
              window.remove(s[left]);
              left++;
          }
      }

哈希表

unordered_set

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
#include <iostream>
#include <string>
#include <unordered_set> // 必须包含这个头文件
using namespace std;
int main() {
    // 1. 定义：创建一个存储字符串的集合
    unordered_set<string> classroom;

    // 2. 插入（登记入场）：使用 insert()
    classroom.insert("张三");
    classroom.insert("李四");
    classroom.insert("王五");
    classroom.insert("张三"); // 再次插入张三，set会自动去重，教室里还是只有1个张三

    // 3. 查询（查找学生）：使用 count() 或 find()
    // count() 返回 1 表示在，0 表示不在
    if (classroom.count("张三")) {
        cout << "张三正在教室里学习。" << endl;
    }

    // 4. 删除（学生离开）：使用 erase()
    classroom.erase("李四");
    cout << "李四请假回家了。" << endl;

    // 再次检查李四
    if (classroom.count("李四") == 0) {
        cout << "确认：李四不在教室。" << endl;
    }

    // 5. 统计（当前人数）：使用 size()
    cout << "目前教室里共有 " << classroom.size() << " 个学生。" << endl;

    // 6. 遍历（查看所有在场名单）
    cout << "在场名单有：";
    for (const string& name : classroom) {
        cout << name << " ";
    }
    cout << endl;

    // 7. 清空（全员放学）：使用 clear()
    classroom.clear();

    // 8. 判空：使用 empty()
    if (classroom.empty()) {
        cout << "教室现在空无一人。" << endl;
    }

    return 0;
}

unordered_map

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
#include <iostream>
#include <string>
#include <unordered_map> // 必须包含这个头文件

using namespace std;

int main() {
    // 1. 定义：<键的类型, 值的类型>
    unordered_map<string, int> scores;

    // 2. 插入/修改：使用 [] 运算符，非常直观
    scores["张三"] = 95;
    scores["李四"] = 88;
    scores["王五"] = 72;
    
    // 如果键已存在，再次赋值会直接“覆盖”旧值
    scores["张三"] = 98; // 张三分数更新为 98

    // 3. 查询：使用 count() 判断是否存在某个 Key
    if (scores.count("张三")) {
        // 直接通过 [] 取出对应的 Value
        cout << "张三的分数是：" << scores["张三"] << endl;
    }

    // 4. 删除：使用 erase()，根据 Key 来删除整行记录
    scores.erase("王五");
    cout << "王五退学了，删除其成绩记录。" << endl;

    // 5. 统计：size() 返回的是“有多少对”键值对
    cout << "当前记录了 " << scores.size() << " 名学生的成绩。" << endl;

    // 6. 遍历：这是最特殊的地方
    // map 的每一项是一个 pair，包含 first (键) 和 second (值)
    cout << "全班成绩单：" << endl;
    for (auto const& pair : scores) {
        cout << "姓名：" << pair.first << " -> 分数：" << pair.second << endl;
    }

    // 7. 清空与判空
    scores.clear();
    if (scores.empty()) {
        cout << "账本已清空。" << endl;
    }

    return 0;
}