双指针

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

  • 模版：

    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++;
          }
      }