算法 搜索

深度优先搜索

广度优先搜索

深搜与广搜的区别

深搜 dfs——回溯——“不撞南墙不回头”

思路

总的来说是不撞南墙不回头，相当于一个人严格按照固定的行为模式。

例如走方格，依次走上下左右，每次走到一个新格子记录自己已经走过的方向，当到达终点或是所有方向走完之后，会重新回到上一格，代表上一格此方向【之前按照哪个方向到达此格的方向】的遍历完成。

形成效果

一个dfs其实是对一个问题的结果集的所有解题情况的遍历【不管这个解题情况是否复合题意】。

dfs 搜索树与回溯

一个dfs其实是对一个问题的结果集的所有解题情况的遍历，在遍历过程中，前面解题情况的选择会影响到后面的解题情况。

例如走迷宫，解题情况其实就是主人公走到哪个格子，他会影响到之后走过的路径。

所以我们其实可以将解题情况进行串联，将前面的选择作为一个图的前驱节点，而后面的结果作为后继节点，那么所有的解题情况的遍历便可以组成一个树，我们叫做搜索树。树上的根节点到 某个叶节点的一条路径就是一条解题过程。

那迷宫来进行距离，我们把主人公当前正在走的点当作前驱，而之后依照行为模式工作后所走到的下一个点作为后继。那么所有所走过的路径的集合便可构成一个树。

在dfs遍历解题结果的过程中，会存储并改变一些解题的状态，由于我们是会对所有情况依次进行遍历，当一种情况遍历完成后，dfs应该回到上一个节点进行行为模式的继续遍历。

例如迷宫，走到死胡同或者终点时，应该回到上一次走过的点，看其他方向能否到达终点。

注意，dfs是进行所有结果的遍历，所以在到达终点后并不会停止，而是会继续回到上一步运行。

而此时回到上一个节点就意味着，之前走过的一些点，在这个时刻应该是没有走过的，所以的话在写代码的时候应该进行一个状态的回溯。在回到上一个节点之前，本节点对于上一个节点应该是没有遍历过的，所以要进行状态改变。

代码模板

人走迷宫，迷宫情况使用0、1表示，1可行，0不可行。先给定起点与终点，求所有路径中最少要走多少格子。

递归实现

#include<stdio.h>
_Bool map[100][100] = { 0 };//1代表可行，0不可行
_Bool visit[100][100] = { 0 };//0未走，1走过
int mov[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };//右下左上
int endx, endy, startx, starty;
int col, row, t;
_Bool can = 0;
int min = 0x3f3f3f3f;//代表正无穷
void dfs(int x,int y, int value) {//如果value没有被设为参数，回溯的时候需要改变value值
	if (value > min)//最优剪枝1
		return;
	if (x<0 || y<0 || x>=row || y>=col)//判断是否出界
		return;
	if (x == endx && y == endy) {//结束条件，找到终点
		can = 1;
		if (value < min)
			min = value;
		return;//回退，防止继续走下去，已经到达终点了，没必要再走了
	}
	if (value >= min)//最优剪枝2,未到达终点，便value=min，那么到达终点时，一定回value>min
		return;
	for (int i = 0;i < 4;i++) {
		int xx = x + mov[i][0], yy = y + mov[i][1];//人物偏移
		if (map[xx][yy] && !visit[xx][yy]) {//判断是否可以进入下一格，可行性剪枝
            visit[xx][yy] = 1;//先标记再访问
		    dfs(xx, yy, value+1);//让人物移动到下一格
		    visit[xx][yy] = 0;//回溯操作，当递归回到这一层的时候，(xx,yy)应该未访问，所以置为0
			//回溯操作是一层递归一层递归进行回溯，每次只会回溯到上一层，所以每次只用将当前位置的下一个操作的数据回溯
		}
		
	}
}
int main() {
	scanf("%d", &t);
	while (t--) {//t轮数据，每一次数据进行操作时，都要保证所有的状态都为最初状态，不被上一次操作所影响
		scanf("%d%d", &col, &row);
		for (int i = 0;i < row;i++)
			for (int j = 0;j < col;j++) {
				scanf("%d", &map[i][j]);
				visit[i][j] = 0;
			}
		scanf("%d%d%d%d", &startx, &starty, &endx, &endy);
		visit[startx][starty] = 1;
		dfs(startx, starty, 0);
		if (can)
			printf("能,min=%d\n", min);
		else
			printf("不能\n");
        _Bool can = 0;
	}
	return 0;
}

栈实现

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
struct Point {
	int x, y, value, dir;
	Point(int a,int b,int value):x(a),y(b),value(value),dir(0){}
};
typedef struct Point TYPE;
int main(void) {
	stack<TYPE> Stack;//这个类可以用<>指定里面的内容的类型，类似于一个栈
	bool map[100][100] = { 0 }, visited[100][100] = { 0 };
	int mov[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
	int m, n;
	cin >> m >> n;
	int i, j;
	for (i = 0;i < m;i++)
		for (j = 0;j < n; j++)
			cin >> map[i][j];
	int startx, starty, endx, endy;
	scanf("%d%d%d%d", &startx, &starty, &endx, &endy);
	Stack.emplace(startx, starty, 0);
	visited[startx][starty] = 1;
	while (!Stack.empty()) {//栈非空进行循环
		TYPE* cur = &Stack.top();
		if (cur->x == endx && cur->y == endy) {//判断是否到达终点
			printf("%d\n", cur->value);
			visited[cur->x][cur->y] = 0;
			Stack.pop();
			continue;//如果到达，弹栈，回到上一次位置，进行下一轮循环
		}
		if (cur->dir <= 3) {//遍历
			int xx = cur->x + mov[cur->dir][0];
			int yy = cur->y + mov[cur->dir][1];
			cur->dir++;//进入一个新的结点的时候，dir=0，当遍历之后要自增

			if (xx < m && yy < n && xx >= 0 && yy >= 0 && !visited[xx][yy] && !map[xx][yy]) {
				Stack.emplace(xx, yy, cur->value + 1);//压栈
				visited[xx][yy] = 1;
			}
		}
		else {//弹栈
			visited[cur->x][cur->y] = 0;
			Stack.pop();
		}
	}
	return 0;
}

与模板差异

  1. 是否回溯
  2. 遍历方向
  3. 结束条件
  4. 结束处理

超时后的解决方法

  1. 换思路：主要换遍历的方式【mov之类的】
  2. 剪枝

普通无回溯 dfs

例题

海战 - 洛谷

该题与走迷宫不同，走迷宫是从一个点为起点，然后一直走下去，每走完一种情况后需要回过头检查是否有其他路可走，需要进行回溯。该题是需要遍历每一个点，若该点是船只的一部分，需要判断该点是否可以与其它点相连构成船只，且每个点只能使用一次【使用过之后就不能再次使用】，走到头后，不需要回过头检查其他的路径，所以不需要回溯。

#include<stdio.h>
int	R, C, S = 0;
char map[1005][1005] = { 0 };
int mov[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
void dfs(int x, int y) {
	map[x][y] = '.';//因为每只船只能使用一次，所以在使用之后要将‘#’标记为‘.’，后期不可以再使用
	for (int i = 0;i < 4;i++) {
		int xx = x + mov[i][0], yy = y + mov[i][1];
		if (xx >= 0 && xx < R && yy >= 0 && yy < C && map[xx][yy] == '#') {
			dfs(xx, yy);
		}
	}
	return;
}
//判断船的位置是否合法，即在一个正方形中，四个角上如果有三个角有船就是不合理的，那样子会出现一个三角形，不是方形
_Bool d(int i, int j) {
	int c = 0;
	if (map[i][j] == '#')
	    c++;
	if (map[i + 1][j] == '#')
	    c++;
	if (map[i][j + 1] == '#')
	    c++;
	if (map[i + 1][j + 1] == '#')
	    c++;
	if (c == 3)
		return 0;
	return 1;
}
int main() {
	scanf("%d%d", &R, &C);
	for (int i = 0;i < R;i++) {
		scanf("%s", map[i]);
	}
	for (int i = 0;i < R;i++) {
		for (int j = 0;j < C;j++) {
			if (d(i, j) == 0) {
				printf("Bad placement.");
				return 0;
			}
		}
	}
	for (int i = 0;i < R;i++) {
		for (int j = 0;j < C;j++) {
			if (map[i][j] == '#') {
				S++;
				dfs(i, j);
			}
		}
	}
	printf("There are %d ships.", S);

	return 0;
}

剪枝

在搜索树中剪去多余枝干。

另一个结束递归的条件

  1. 可行性剪枝(判断可不可以走，包括有无障碍物和是否走过，……)
  2. 最优剪枝(消耗的能量，若目前未到终点，但是使用的能量已经超过min)
  3. 奇偶性剪枝
  4. 优化搜索顺序(人眼看)
  5. 冗余剪枝
  6. 记忆化搜索
  7. α-β剪枝(博弈算法，可能被人工智能使用)

优化搜索顺序

靠数学功底

可行性剪枝

就像上面的迷宫问题，能否走这个格子就是一个可行性剪枝。这个是根据题意来进行判断，看下一步路线是否可能符合题意，若直接违背则就不用走。

最优剪枝

适用于求最短路径

例题

[USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins - 洛谷

#include<stdio.h>
int v, g, need[30], food[20][30], ans[20], min = 0x3f3f3f3f, temp[20], len;//v所需要v种营养 g有g种饲料 need每种营养成分需要多少 food二维数组，低维:每种营养的含量，高维:饲料总类 ans答案数组 temp存储现在选择的饲料 len目前选了len种饲料 min做优情况，即选最少的种类便可达到所需的营养
_Bool visited[20];//状态数组，表示是否被选过
_Bool check(int len) {//检查是否达到所需的营养
	int nutrition[30] = { 0 };//每种营养现在的含量
	for (int i = 1;i <= len;i++) {
		for (int l = 1;l <= v;l++) {
			nutrition[l] += food[temp[i]][l];
		}	
	}
	for (int i = 1;i <= v;i++) {
		if (need[i] > nutrition[i])//只要有一种营养成分含量不合格，就返回0
			return 0;
	}
	return 1;
}
void dfs() {//搜索
    //最优剪枝
	if (len > g || len > min)//现在的饲料种类超过最优或超过总的饲料种类就退出递归
		return;
	if (check(len) == 1) {//检验是否达到所需的营养含量，若达到，与最优解进行比较，若所需的种类少于目前的最小的，则代替最小成为新的最少，即新的最优情况
		if (min > len) {
			min = len;
			for (int i = 1;i <= min;i++)
				ans[i] = temp[i];
		}
		return;
	}
	for (int i = temp[len]+1;i <= g;i++) {//遍历，注意遍历的开始是上一次选择下一个【遍历选择每一种饲料，不需要每次都从头开始选】
		if (!visited[i]) {
			visited[i] = 1;
			len++;
			temp[len] = i;
			dfs();
			visited[i] = 0;//回溯
			temp[len] = 0;
			len--;
		}
	}

}
int main() {
	scanf("%d", &v);
	for (int i = 1;i <= v;i++) {
		scanf("%d", &need[i]);
	}
	scanf("%d", &g);
	for (int i = 1;i <= g;i++) {
		for (int j = 1;j <= v;j++) {
			scanf("%d", &food[i][j]);
		}
	}
	dfs();
	printf("%d ", min);
	for (int i = 1;i <= min;i++)
		printf("%d ", ans[i]);
	return 0;
}

奇偶性剪枝

横纵坐标从1开始，横纵坐标相加为奇数赋为0，偶数赋为1

1->1:最近的1走两步，任何一个1走偶数步，0->0也是【同偶异奇】

冗余剪枝

重复的删除去

[USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins - 洛谷

#include<stdio.h>
int v, g, need[30], food[20][30], ans[20], min = 0x3f3f3f3f, temp[20], len;//v所需要v种营养 g有g种饲料 need每种营养成分需要多少 food二维数组，低维:每种营养的含量，高维:饲料总类 ans答案数组 temp存储现在选择的饲料 len目前选了len种饲料 min做优情况，即选最少的种类便可达到所需的营养
_Bool visited[20];//状态数组，表示是否被选过
_Bool check(int len) {//检查是否达到所需的营养
	int nutrition[30] = { 0 };//每种营养现在的含量
	for (int i = 1;i <= len;i++) {
		for (int l = 1;l <= v;l++) {
			nutrition[l] += food[temp[i]][l];
		}	
	}
	for (int i = 1;i <= v;i++) {
		if (need[i] > nutrition[i])//只要有一种营养成分含量不合格，就返回0
			return 0;
	}
	return 1;
}
void dfs() {//搜索
    //最优剪枝
	if (len > g || len > min)//现在的饲料种类超过最优或超过总的饲料种类就退出递归
		return;
	if (check(len) == 1) {//检验是否达到所需的营养含量，若达到，与最优解进行比较，若所需的种类少于目前的最小的，则代替最小成为新的最少，即新的最优情况
		if (min > len) {
			min = len;
			for (int i = 1;i <= min;i++)
				ans[i] = temp[i];
		}
		return;
	}
	for (int i = temp[len]+1;i <= g;i++) {//遍历，注意遍历的开始是上一次选择下一个【遍历选择每一种饲料，不需要每次都从头开始选】
		if (!visited[i]) {
			visited[i] = 1;
			len++;
			temp[len] = i;
			dfs();
			visited[i] = 0;//回溯
			temp[len] = 0;
			len--;
		}
	}

}
int main() {
	scanf("%d", &v);
	for (int i = 1;i <= v;i++) {
		scanf("%d", &need[i]);
	}
	scanf("%d", &g);
	for (int i = 1;i <= g;i++) {
		for (int j = 1;j <= v;j++) {
			scanf("%d", &food[i][j]);
		}
	}
	dfs();
	printf("%d ", min);
	for (int i = 1;i <= min;i++)
		printf("%d ", ans[i]);
	return 0;
}

记忆化搜索

将之前计算的结果存储在数组中，当计算同样的数据时，可以直接使用之前计算过的答案。

冗余：重复的直接被删除

记忆化搜索：借用之前重复的数据，而不是舍去

(x,y) data[x][y]

dfs(x,y)

if(data[x][y]算过){

return data[x][y];

}

dfs函数返回值类型不是void

使用条件

1.有限个 2.有重复值

例题

int dp[25][25][25];

int dfs(int a, int b, int c) {

if (a <= 0 || b <= 0 || c <= 0)

return 1;

if (a > 20 || b > 20 || c > 20) {

return dfs(20, 20, 20);

}

if (dp[a][b][c]) //先判断该值是否计算过，如果算过，直接调结果，不需要再次计算，直接返回即可

return dp[a][b][c];

if (a < b && b < c) {

dp[a][b][c] = dfs(a, b, c - 1) + dfs(a, b - 1, c - 1) - dfs(a, b - 1, c);

}

else

dp[a][b][c] = dfs(a - 1, b, c) + dfs(a - 1, b - 1, c) + dfs(a - 1, b, c - 1) - dfs(a - 1, b - 1, c - 1);

return dp[a][b][c];

}

例题——全排列

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 n。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤7

输入样例

3

输出样例

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

#include<stdio.h>
int n;
int a[10],state[10]={0};
void dfs(int step){
    if(step==n+1){
        for(int i=1;i<=n;i++)
            printf("%d ",a[i]);
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++){
        if(state[i]==0){
            a[step]=i;
            state[i]=1;
            dfs(step+1);
            a[step]=0;
            state[i]=0;
        }
    }
    return; 
}
int main(){
    scanf("%d",&n);
    dfs(1);
    return 0;
}

例题——八皇后

[USACO1.5] 八皇后 Checker Challenge - 洛谷

n*n的正方形，i表示行，j表示列，i+j表示其中一条对角线，i-j+n表示另外一条对角线

#include<stdio.h>
int a[15]={0},b[15]={0},c[30]={0},d[30]={0};
int n,sum=0;
void dfs(int i){
    if(i>n){
        if(sum<3){
            for(int k=1;k<=n;k++){
                printf("%d ",a[k]);
            }
            printf("\n");
        }
        sum++;
        return;
    }
    for(int j=1;j<=n;j++){
        if((!b[j])&&(!c[i+j])&&(!d[i-j+n])){
            a[i]=j;//行，第i行是第j个
            b[j]=1;//列
            c[i+j]=1;//对角线1,根据截距给对角线命名
            d[i-j+n]=1;//对角线2
            dfs(i+1);
            b[j]=0;//回溯
            c[i+j]=0;
            d[i-j+n]=0;
        }
    }
}
int main(){
    scanf("%d",&n);
    dfs(1);
    printf("%d",sum);
    return 0;
}

广搜 bfs——一层一层走

一层一层搜索，首先，先把所有第一层的点，即距离为1的点搜完，然后进入下一层，直到搜完。

边权相同时，可以用bfs求最短路。

实现思路

使用队列来实现，每次将要搜索的点放在队列中，刚开始搜索时，队列中只有一个点，然后每次将所有与队头元素相连的且没有访问过的，符合条件的点都放入队列，之后对 队头元素进行处理然后出队。当队列为空则说明搜索停止。

这样就可以保证一层一层遍历，遍历整体深度逐渐增大。

而由这样遍历出来的合法路径，若是两点间权值相同的话，是具有最优性质的。

框架

queue 初始状态

while queue 不空

{

t<--每次取队头

扩展队头t

}

例题——走迷宫

给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。

最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。

数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。

输入格式

第一行包含两个整数n和m。

接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤100

输入样例

5 5

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

输出样例

8

//bfs，使用手写队列实现
//输出路径，只需要再开一个数组prev，记录这个点是由那个点扩展出来即可
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m;
char map[N][N];
int len[N][N];//每个点到起点的距离
PII q[N * N];//实现队列
//PII Prev[N][N];  //输出路径
int bfs() {
    int hh = 0, tt = 0;
    q[0] = { 0,0 };
    memset(len, -1, sizeof len);
    //初始化函数，将某一块内存中的内容全部设置为指定的值，通常为新申请的内存做初始化工作
    //参数1，指针或数组；参数2，赋给参数1的值；参数3，参数1的长度
    len[0][0] = 0;
    int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
    while (hh <= tt) {
        auto t = q[hh++];//每次取出队头元素
        for (int i = 0;i < 4;i++) {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && map[x][y] == '0' && len[x][y] == -1) {
                len[x][y] = len[t.first][t.second] + 1;
                //Prev[x][y] = t;
                q[++tt] = { x,y };//在队尾插入元素
            }
        }
    }
    /*int x = n - 1, y = m - 1;
    while (x || y) {
    cout << x << ' ' << y << endl;
    auto t = Prev[x][y];
    x = t.first, y = t.second;
    }*/
    return len[n - 1][m - 1];
}
int main() {
    cin >> n >> m;
    for (int i = 0;i < n;i++)
        cin >> map[i];
    cout << bfs() << endl;
    return 0;
}

有向图的遍历

宽度优先遍历

一层一层搜索

框架

queue ＜——　将起始状态插入队列中，即将1号点插入队列

while （queue 不空）{

t 每次取队头元素

拓展 t 所有能到的点 x

if（x 未被遍历）{

　queue <——x 将 x 入队

d[x]=d[t]+1

}

}

例题——图中点的层次

给定一个n个点m条边的有向图，图中可能存在重边和自环。

所有边的长度都是1，点的编号为1~n。

请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。

输入格式

第一行包含两个整数n和m。

接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。

输出格式

输出一个整数，表示1号点到n号点的最短距离。

数据范围

1≤n,m≤10^5

输入样例

4 5

1 2

2 3

3 4

1 3

1 4

输出样例

1

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N];
void add(int a, int b) {//插入函数
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
int bfs() {
	int hh = 0, tt = 0;
	q[0] = 1;
	memset(d, -1, sizeof d);//初始化距离，-1代表未被初始化
	d[1] = 0;
	while (hh <= tt) {//判断队列是否为空
		int t = q[hh++];//取队头
		for (int i = h[t];i != -1;i = ne[i]) {//扩展队头
			int j = e[i];
			if (d[j] == -1) {
				d[j] = d[t] + 1;
				q[++tt] = j;
			}
		}
	}
	return d[n];
}
int main() {
	cin >> n >> m;
	memset(h, -1, sizeof h);//初始化表头
	for (int i = 0;i < m;i++) {
		int a, b;
		cin >> a >> b;
		add(a, b);
	}
	cout << bfs() << endl;
}

深度优先遍历

找到一个起点，然后从这个 起点开始，一条路走向黑

邻接表的深度优先遍历

主函数：

for(int i=0;i<n;i++) dfs(i); //枚举起点

dfs：

利用图中结点的编号进行搜索，e存图中结点的编号

int h[N], e[M], ne[M], idx;//h存n个链表的链表头，e存每个结点的值是多少，ne存每个结点的next值

bool st[N];

//树和图的深度优先搜索

void dfs(int u) {//u是当前dfs到的点

st[u] = true;//标记一下，已经被搜过了

for (int i = h[u];i != -1;i = ne[i]) {//遍历u的所有出边

int j = e[i];//链表中该点在图中的编号

if (!st[j])//如果j没有被搜过，那么就进行搜索

dfs(j);

}

例题——树的重心

给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边【无向图】。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数n，表示树的结点数。

接下来n-1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。

输出格式

输出一个整数m，表示重心的所有的子树中最大的子树的结点数目。

数据范围

1≤n≤10^5

输入样例

9

1 2

1 7

1 4

2 8

2 5

4 3

3 9

4 6

输出样例

4

代码

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/221642.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

20款VS Code实用插件推荐

20款VS Code实用插件推荐

前言&#xff1a; VS Code是一个轻量级但功能强大的源代码编辑器&#xff0c;轻量级指的是下载下来的VS Code其实就是一个简单的编辑器&#xff0c;强大指的是支持多种语言的环境插件拓展&#xff0c;也正是因为这种支持插件式安装环境开发让VS Code成为了开发语言工具中的霸主…
阅读更多...
AVFormatContext封装层：理论与实战

AVFormatContext封装层：理论与实战

文章目录 前言一、封装格式简介1、FFmpeg 中的封装格式2、查看 FFmpeg 支持的封装格式 二、API 介绍三、 实战 1&#xff1a;解封装1、原理讲解2、示例源码 13、运行结果 14、示例源码 25、运行结果 2 三、 实战 2&#xff1a;转封装1、原理讲解2、示例源码3、运行结果 前言 A…
阅读更多...
上传文件接口的创建_FastAPI

上传文件接口的创建_FastAPI

上传文件接口的创建 功能描述代码效果演示与注意事项 功能描述 前端用户需要上传文件至平台&#xff0c;就比如CSDN的上传资源部分&#xff0c;都是一样的功能逻辑&#xff0c;想要实现这个功能其实并不难。 这里以上传的JSON格式文件为例&#xff0c;其他格式文件的话可以自…
阅读更多...
Container容器技术简介

Container容器技术简介

本文介绍了容器技术出现背景&#xff0c;docker技术与容器编排技术的简单说明 背景 在传统项目的生产环境中&#xff0c;迁移一个用户态进程往往非常麻烦&#xff0c;因为一个用户态进程背后会附带这非常多例如函数库、中间件等的依赖项&#xff0c;但又没有像apt和yum一样的…
阅读更多...
用pip更新、安装python的包

用pip更新、安装python的包

查看pip的版本&#xff1a;python -m pip --version 例如&#xff0c;查看下pip的版本&#xff0c;在cmd下输入命令python -m pip --version&#xff0c;可以发现当前安装的pip的版本是23.2.1&#xff1a; 查看一个包的详情&#xff1a;python -m pip show 例如&#xff0c…
阅读更多...
Leetcode—2477.到达首都的最少油耗【中等】

Leetcode—2477.到达首都的最少油耗【中等】

2023每日刷题&#xff08;五十&#xff09; Leetcode—2477.到达首都的最少油耗 算法思想 参考自灵茶山艾府 实现代码 class Solution { public:long long minimumFuelCost(vector<vector<int>>& roads, int seats) {int n roads.size() 1;vector<i…
阅读更多...
【IEEE独立出版|EI会议征稿】2024年第四届消费电子与计算机工程国际学术会议（ICCECE 2024）

【IEEE独立出版|EI会议征稿】2024年第四届消费电子与计算机工程国际学术会议（ICCECE 2024）

2024年第四届消费电子与计算机工程国际学术会议&#xff08;ICCECE 2024&#xff09; 2024 4th International Conference on Consumer Electronics and Computer Engineering 进入21世纪以来&#xff0c;计算机技术的高速发展带来了消费电子产品的快速更迭。在技术迅速发展历…
阅读更多...
SOLIDWORKS 2024新功能之Simulation篇

SOLIDWORKS 2024新功能之Simulation篇

SOLIDWORKS 2024 新功能 Simulation篇目录概述 • 自动保存模型文件 • 壳体的接合交互 • 收敛检查图解 • 去耦合混合自由体模式 • Direct Sparse 解算器已停用 • 增强型轴承接头 • 复制算例时排除网格和结果 • 导出模型形状数据 • 网格性能 • 性能增强功能 …
阅读更多...
物联网水表和4G水表的区别有哪些？

物联网水表和4G水表的区别有哪些？

随着科技的发展&#xff0c;水表也不再是传统的机械表&#xff0c;而是经过数字化和智能化改造的物联网水表和4G水表。这两种水表具有很多的不同点。那么&#xff0c;物联网水表和4G水表的区别有哪些&#xff1f; 首先&#xff0c;物联网水表和4G水表的通信方式不同。物联网水表…
阅读更多...
27、pytest实战：一套用例同时验证生产、测试两个环境

27、pytest实战：一套用例同时验证生产、测试两个环境

前提 生产与测试环境接口地址相同&#xff0c;只是域名不同&#xff0c;例&#xff0c;生产环境为http://192.168.1.40&#xff0c;测试环境为http://192.168.1.50生产环境有严格要求&#xff0c;只允许查询操作&#xff0c;不允许进行增删改&#xff1b;测试环境可进行所有操…
阅读更多...
计算机视觉 - 用于基于图切割算法的木材堆叠测量的权重估计（基于圆形霍夫变换和局部圆度测量）

计算机视觉 - 用于基于图切割算法的木材堆叠测量的权重估计（基于圆形霍夫变换和局部圆度测量）

一、背景说明 计算机视觉技术在木材行业中被用于检测和测量成堆木材中的原木。主要是测量原木的数量及其体积和尺寸。很多场景都是手动测量和收集此类数据&#xff0c;耗费人力并且存在人为错误的风险。可靠的替代工业技术是使用激光扫描仪来扫描&#xff0c;然后估计木材堆中每…
阅读更多...
火焰图的基本认识与绘制方法

火焰图的基本认识与绘制方法

火焰图的认识与使用-目录 火焰图的基本认识火焰图有以下特征(on-cpu)火焰图能做什么火焰图类型On-CPU 火焰图和Off-CPU火焰图的使用场景火焰图分析技巧 如何绘制火焰图生成火焰图的流程1.生成火焰图的三个步骤 安装火焰图必备工具1.安装火焰图FlameGraph脚本2.安装火焰图数据采…
阅读更多...
Redis穿透以及解决方法

Redis穿透以及解决方法

Redis穿透是指当一个请求在缓存中和数据库都找不到对应的数据时&#xff0c;导致每次请求都要查询数据库&#xff0c;从而产生了大量的无效数据库查询&#xff0c;大量无效的数据库查询会导致数据库负载增加&#xff0c;降低数据库的性能和响应能力甚至宕机的风险。 这种情况通…
阅读更多...
详细介绍如何使用 SSD 进行实时物体检测：单次 MultiBox 探测器-含源码

详细介绍如何使用 SSD 进行实时物体检测：单次 MultiBox 探测器-含源码

介绍 在实时对象检测中，主流范例传统上采用多步骤方法，包括边界框、像素或特征重采样以及高质量分类器应用的提议。虽然这种方法已经实现了高精度，但其计算需求往往阻碍了其对实时应用的适用性。然而，单次多框检测器 (SSD) 代表了基于深度学习的对象检测的突破性飞跃。SSD…
阅读更多...
RPG项目01_层级设置

RPG项目01_层级设置

基于“RPG项目01_UI面板Game”&#xff0c; 找到狼人 添加组件&#xff0c;让狼人一定区域自动跟随主角进行攻击 解释&#xff1a;【烘培蓝色】因为如果什么都不做就会被烘培成蓝色对应的功能就是 可修改区域功能 当将区域设置成不可行走状态&#xff0c;则不为蓝色 烘培&…
阅读更多...
Web自动化测试怎么做？Web网页测试全流程解析

Web自动化测试怎么做？Web网页测试全流程解析

1、功能测试 web网页测试中的功能测试&#xff0c;主要测试网页中的所有链接、数据库连接、用于在网页中提交或获取用户信息的表单、Cookie 测试等。 &#xff08;1&#xff09;查看所有链接&#xff1a; 测试从所有页面到被测特定域的传出链接。 测试所有内部链接。 测…
阅读更多...
【头歌系统数据库实验】实验4 MySQL单表查询

【头歌系统数据库实验】实验4 MySQL单表查询

目录 第1关. 在users表中新增一个用户&#xff0c;user_id为2019100904学号&#xff0c;name为2019-物联网-李明 第2关. 在users表中更新用户 user_id为robot_2 的信息&#xff0c;name设为 机器人二号 第3关. 将solution表中所有 problem_id 为1003 题目的解答结果&#xf…
阅读更多...
Java抽象类（abstract class）和接口（interface）的区别——面试

Java抽象类（abstract class）和接口（interface）的区别——面试

1.抽象类&#xff08;abstract class&#xff09;和接口&#xff08;interface&#xff09;的区别&#xff1a; 抽象类可以有构造方法&#xff0c;接口中不能有构造方法。 抽象类中可以有普通成员变量&#xff0c;接口中没有普通成员变量。抽象类中可以包含非抽象的普通方法&am…
阅读更多...
C语言进阶之路-指针、数组等混合小boss篇

C语言进阶之路-指针、数组等混合小boss篇

目录 一、学习目标&#xff1a; 二、指针、数组的组合技能 引言 指针数组 语法 数组指针 三、勇士闯关秘籍 四、大杂脍 总结 一、学习目标&#xff1a; 知识点&#xff1a; 明确指针数组的用法和特点掌握数组指针的用法和特点回顾循环等小怪用法和特点 二、指针、数…
阅读更多...
＜Linux＞（极简关键、省时省力）《Linux操作系统原理分析之文件管理（3）》（24）

＜Linux＞（极简关键、省时省力）《Linux操作系统原理分析之文件管理（3）》（24）

《Linux操作系统原理分析之文件管理&#xff08;3&#xff09;》&#xff08;24&#xff09; 7 文件管理7.5 文件存储空间的管理7.6 文件的共享和保护7.6.1 文件存取控制7.6.2 文件共享的实现方法7.6.3 文件的备份转储 7 文件管理 7.5 文件存储空间的管理 位示图 对每个磁盘…
阅读更多...
最新文章

Copyright @ 2022~2023