算法模块

STL和基础数据结构

1. 士兵队列训练问题（双向链表List）
2. 产生冠军(集合 set)
3. 约瑟夫问题（vector 数组）

搜索技术

1. 递归与排列

2. 子集生成与组合

3. DFS:深度优先搜索：从某个状态开始，不断地转移状态直到无法转移，然后回退到前一步的状态，继续转移到其他状态如此不断重复，最终得到解。

   ​ 1.经典部分和问题：给定整数a1、a2、…、an,判断是否可以从中选出若干数，使他们恰好为k

   限制条件：
   	1<=n<=20
   	-10^8<=ai<=10^8
   	-10^8<=k<=10^8

   输入：n=4 a={1,2,4,7} k=13        输出：yes

   输入：n=4 a={1,2,4,7} k=15        输出：no

   #include<iostream>
   using namespace std;
   int n,k;
   int a[100];
   bool dfs(int i,int sum){//对i项之后的进行分支
   	if(i==n) return sum==k;//如果前n项都计算过了，则返回sun是否与k相等
   	if(dfs(i+1,sum)) return true;//不加上a[i]的情况
   	if(dfs(i+1,sum+a[i])) return true;
   	return false; 	
   }
   int main(){
   	cin>>n;
   	for(int i=0;i<n;i++) cin>>a[i];
   	cin>>k;
   	if(dfs(0,0)) printf("yes\n");
   	else printf("no\n");
   }

   ​ 2.水洼问题(八连通)dfs：有一个大小为 NM 的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼？（八连通指的是下图中相对 W 的的部分）

   输入：
   10 12
   W........WW.
   .WWW.....WWW
   ....WW...WW.
   .........WW.
   .........W..
   ..W......W..
   .W.W.....WW.
   W.W.W.....W.
   .W.W......W.
   ..W.......W.
   
   输出：
   3

   代码：

   #include <iostream>
   using namespace std;
   char a[105][105];
   int M,N;
   void dfs(int i ,int j)
   {
    a[i][j] = '.';//将遍历后的地方设为空地(无水洼)
    int nx,ny;//声明遍历一次后的坐标
    for(int x = -1;x<=1;x++)
       for(int y = -1;y<=1;y++)
       {
           nx = i+x;
           ny = j+y;
           if(nx>=0&&nx<N&&ny>=0&&ny<M&&a[nx][ny]=='W')  dfs(nx,ny);/*满足条件(nx,ny是否在院子里，以及是否有积水)一直dfs直到与开始'w'邻接的'w'都被替换完*/
       }
   }
   int main()
   {
    int count = 0;
    cin>>N>>M;
    for(int i = 0;i<N;i++)
       for(int j = 0;j<M;j++)
          cin>>a[i][j];
    for(int i = 0;i<N;i++)
       for(int j = 0;j<M;j++)
           if(a[i][j]=='W')
           {
                dfs(i,j);
                count++;
        }
    cout<<count;
    return 0; 
   }

    /*
           岛屿问题
           L200. 岛屿数量 （Easy）----见本次
           463. 岛屿的周长 （Easy）
           695. 岛屿的最大面积 （Medium）
           827. 最大人工岛 （Hard）
           DFS 的基本结构
           网格结构要比二叉树结构稍微复杂一些，它其实是一种简化版的图结构。
           要写好网格上的 DFS 遍历，我们首先要理解二叉树上的 DFS 遍历方法，再类比写出网格结构上的 DFS 遍历。
           我们写的二叉树 DFS 遍历一般是这样的：
           */
           /* //java
           void traverse(TreeNode root) {
               // 判断 base case
               if (root == null) {
                   return;
               }
               // 访问两个相邻结点：左子结点、右子结点
               traverse(root.left);
               traverse(root.right);
               可以看到，二叉树的 DFS 有两个要素：「访问相邻结点」和「判断 base case」。
               第一个要素是访问相邻结点。二叉树的相邻结点非常简单，只有左子结点和右子结点两个。二叉树本身就是一个递归定义的结构：一棵二叉树，它的左子树和右子树也是一棵二叉树。那么我们的 DFS 遍历只需要递归调用左子树和右子树即可。
               第二个要素是 判断 base case。一般来说，二叉树遍历的 base case 是 root == null。这样一个条件判断其实有两个含义：一方面，这表示 root 指向的子树为空，不需要再往下遍历了。另一方面，在 root == null 的时候及时返回，可以让后面的 root.left 和 root.right 操作不会出现空指针异常。
               对于网格上的 DFS，我们完全可以参考二叉树的 DFS，写出网格 DFS 的两个要素：
               首先，网格结构中的格子有多少相邻结点？答案是上下左右四个。对于格子 (r, c) 来说（r 和 c 分别代表行坐标和列坐标），四个相邻的格子分别是 (r-1, c)、(r+1, c)、(r, c-1)、(r, c+1)。换句话说，网格结构是「四叉」的。
               其次，网格 DFS 中的 base case 是什么？从二叉树的 base case 对应过来，应该是网格中不需要继续遍历、grid[r][c] 会出现数组下标越界异常的格子，也就是那些超出网格范围的格子。
               这一点稍微有些反直觉，坐标竟然可以临时超出网格的范围？这种方法我称为「先污染后治理」—— 甭管当前是在哪个格子，先往四个方向走一步再说，如果发现走出了网格范围再赶紧返回。这跟二叉树的遍历方法是一样的，先递归调用，发现 root == null 再返回。
               这样，我们得到了网格 DFS 遍历的框架代码：
               void dfs(int[][] grid, int r, int c) {
               // 判断 base case
               // 如果坐标 (r, c) 超出了网格范围，直接返回
               if (!inArea(grid, r, c)) {
                   return;
               }
               // 访问上、下、左、右四个相邻结点
               dfs(grid, r - 1, c);
               dfs(grid, r + 1, c);
               dfs(grid, r, c - 1);
               dfs(grid, r, c + 1);
           }
           // 判断坐标 (r, c) 是否在网格中
           boolean inArea(int[][] grid, int r, int c) {
               return 0 <= r && r < grid.length&& 0 <= c && c < grid[0].length;
           }
       }
       网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于，遍历中可能遇到遍历过的结点。这是因为，网格结构本质上是一个「图」，我们可以把每个格子看成图中的结点，每个结点有向上下左右的四条边。在图中遍历时，自然可能遇到重复遍历结点。
       这时候，DFS 可能会不停地「兜圈子」，永远停不下来
       如何避免这样的重复遍历呢？答案是标记已经遍历过的格子。以岛屿问题为例，我们需要在所有值为 1 的陆地格子上做 DFS 遍历。每走过一个陆地格子，就把格子的值改为 2，这样当我们遇到 2 的时候，就知道这是遍历过的格子了。也就是说，每个格子可能取三个值：
       void dfs(int[][] grid, int r, int c) {
       // 判断 base case
       if (!inArea(grid, r, c)) {
           return;
       }
       // 如果这个格子不是岛屿，直接返回
       if (grid[r][c] != 1) {
           return;
       }
       grid[r][c] = 2; // 将格子标记为「已遍历过」
   
       // 访问上、下、左、右四个相邻结点
       dfs(grid, r - 1, c);
       dfs(grid, r + 1, c);
       dfs(grid, r, c - 1);
       dfs(grid, r, c + 1);
   }
   
   // 判断坐标 (r, c) 是否在网格中
   boolean inArea(int[][] grid, int r, int c) {
       return 0 <= r && r < grid.length
               && 0 <= c && c < grid[0].length;
   }*/
   
           var numIslands = function (grid) {
               let res = 0;
               const dfs = (grid, row, col) => {
                   if (row >= grid.length || col >= grid[0].length || row < 0 || col < 0) {
                       return;
                   }
   
                   if (grid[row][col] != '1') {
                       return;
                   }
   
                   grid[row][col] = '2';
                   dfs(grid, row - 1, col);
                   dfs(grid, row + 1, col);
                   dfs(grid, row, col - 1);
                   dfs(grid, row, col + 1);
               }
               for (let i = 0; i < grid.length; i++) {
                   for (let j = 0; j < grid[0].length; j++) {
                       if (grid[i][j] == '1') {
                           dfs(grid, i, j);
                           res++;
                       }
                   }
               }
               return res;
           };

4. BFS

   ​ 经典BFS问题迷宫最短路径 给定一个大小为 N * M 的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数

   pair类型定义在#include 头文件中 pair将一对值(T1和T2)组合成一个值 first 与 second取值
   pair<T1, T2> p1;创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
   pair类型的使用相当的繁琐，如果定义多个相同的pair类型对象，可以使用typedef简化声明：

   输入两个数字 N 和 M，分别表示迷宫的长和宽，用空格隔开
   输入代表迷宫的字符串，N 行 M 列，由 '#'，'.'，'S'，'G' 组成，分别表示墙壁，通道，起点，终点 
   输入：
   10 10
   #S######.#
   ......#..#
   .#.##.##.#
   .#........
   ##.##.####
   ....#....#
   .#######.#
   ....#.....
   .####.###.
   ....#...G#
   输出：22

   代码：

   #include<iostream>
   #include<queue>
   using namespace std; 
   
   const int INF=100000000;//定义未到达初始状态 
   const int MAX_N=100+5,MAX_M=100+5;
   typedef pair<int,int> P;
   
   char maze[MAX_N][MAX_M];//定义迷宫 
   int N,M;
   int sx,sy;//定义起点 
   int gx,gy; //定义终点
   
   int d[MAX_N][MAX_M];//记录到达各个位置的最短路径 
   
   int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};//四个方向移动的向量 右、上、左、下
   
   int bfs() {
   	queue<P> que;
   	//初始化距离数组
   	for(int i=0;i<N;i++)
   		for(int j=0;j<M;j++) 
   		d[i][j] = INF;
   		que.push(P(sx,sy));//将起点加入队列
   		d[sx][sy] = 0;
   		while(que.size()){
   			//从队首取出元素
   			P p = que.front(); que.pop();
   			 //判断取出的是否是终点
   			 if(p.first==gx&&p.second==gy) break;
   			 
   			 //从取出点的四个方向循环 nx ny为移动后的坐标 
   			 for(int i=0;i<4;i++){
   			 	int nx = p.first+dx[i];
   				int ny = p.second+dy[i];
   				//判断是否可以移动以及是否已经访问过
   				if(0<=nx && nx<N && 0<=ny && ny<M && maze[nx][ny]!='#' && d[nx][ny]==INF){
   					//满足条件则入队
   					que.push(P(nx,ny));
   					d[nx][ny] = d[p.first][p.second] + 1; 
   				} 
   			 }  
   		} 
   		return d[gx][gy];
   } 
   int main() {
   	cin>>N>>M;
   	for(int i=0;i<N;i++)
   	cin>>maze[i];
   	for(int i=0;i<N;i++){
   			for(int j=0;j<M;j++){
   		if(maze[i][j]=='S'){
   			sx=i;
   			sy=j;
   		}
   		if(maze[i][j]=='G'){
   			gx=i;
   			gy=j;
   		}
   		} 
   	}
   
   	int res = bfs();
   	cout<<res;
   }

• 红黑砖问题

  八叔码问题和状态图搜索（快速判重—康托展开Cantor() O(n^2)—–>把一个集合产生的全排列按字典序排序，第X个排列的计算公式： X=a[n](n-1)!+a[n-1](n-2)!+……+a[2]1!+a[1]0!）找到并用数组置1处理

• bfs与A*算法(bfs+贪心)

  评估函数

赏

Thanks

支付宝

微信