- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
声明( 叠甲 ):鄙人水平有限,本文为作者的学习总结,仅供参考.
搜索算法包括深度优先搜索(DFS)和广度优先搜索(BFS)这两种,从起点开始,逐渐扩大寻找范围,直到找到需要的答案为止。从时间复杂度来说这与一般的暴力枚举来说没来太大的区别,这样的话我们为什么要使用搜索算法,而不直接使用暴力法呢?首先,搜索算法是暴力法一种优雅的写法,即优雅的暴力,可以为我们的代码减少冗长的嵌套 for 循环。其次搜索通过剪枝操作可以跳过一些无效状态,降低问题规模,从而使效率比直接的枚举所有答案要高.
类别 | DFS | BFS |
---|---|---|
搜索类型 | 试探搜索 | 地毯搜索 |
所用的数据结构 | 栈(vector也是可以的) | 队列 |
适用的题目 | 求方案总数 | 求最短路径 |
实现方法 | 一般结合回溯算法一同实现 | 将可行行方案放入队列,然后一一遍历 |
有一个 $ n * m $ 的棋盘,在某个点 $ (x, y) (x,y) $上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步.
这是一道经典 BFS 题,可说使模板题了,在解题前先介绍一下 BFS 的实现思路如下:
【1】 构建对应结构体与队列 【2】 初始化数据和初始点 【3】 根据初始点与遍历关系遍历其它符合要求的点 【4】 查询答案 。
根据 BFS 的实现思路可以容易的得到该题的代码如下 。
#include <bits/stdc++.h>
#define N_MAX 400
using namespace std;
int mp[N_MAX][N_MAX]; // mp[i][j] 表示马到(i,j)点所需的最少次数
int n,m,x,y;
// 定义 dx dy 便于运算
int dx[] = {-1,1,2,2,1,-1,-2,-2};
int dy[] = {-2,-2,-1,1,2,2,1,-1};
// [1] 定义数据结构体与duilie
struct point{
int x,y; // 点的坐标
int t; // 马到该点的最少次数
};
queue<point> que;
int main()
{
// [2] 初始化数据
memset(mp,-1,sizeof(mp));
cin >> n >> m >> x >> y;
mp[x][y] = 0; // 初始点为 0
// [3] 搜索
que.push((point){x,y,mp[x][y]}); // 先向队列中压入初始点
while(!que.empty())
{
// 从队列中一个一个的遍历
point p = que.front();
que.pop(); // 记得弹出
// 寻找满足条件的点,并压入队列中
for(int i = 0;i < 8;i++)
{
int nx = p.x + dx[i];
int ny = p.y + dy[i];
// 判断是否合法
if(nx >= 1 && ny >= 1 && nx <= n && ny <= m && mp[nx][ny] == -1)
{
mp[nx][ny] = p.t + 1;
que.push((point){nx,ny,mp[nx][ny]});
}
}
}
// 输出结果
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
cout << mp[i][j] << " ";
}
cout << endl;
}
return 0;
}
呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第 \(i\) 层楼( \(1 \le i \le N\) )上有一个数字 \(K_i\) ( \(0 \le K_i \le N\) )。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如: \(3, 3, 1, 2, 5\) 代表了 \(K_i\) ( \(K_1=3\) , \(K_2=3\) ,……),从 \(1\) 楼开始。在 \(1\) 楼,按“上”可以到 \(4\) 楼,按“下”是不起作用的,因为没有 \(-2\) 楼。那么,从 \(A\) 楼到 \(B\) 楼至少要按几次按钮呢?
这题也是一道 BFS 的模板题了,算是用于巩固了,具体 AC 代码如下 。
#include <bits/stdc++.h>
using namespace std;
#define N_MAX 201
struct point{
int f; // 所在层数
int ki; // 拥有的数字
int t; // 需要按的次数
};
queue<point> que;
int ans[N_MAX];
int n,a,b;
int k[N_MAX];
int main()
{
memset(ans,-1,sizeof(ans));
cin >> n >> a >> b;
for(int i = 1;i <= n;i++)
{
cin >> k[i];
}
ans[a] = 0;
// bfs
que.push((point){a,k[a],ans[a]});
while(!que.empty())
{
point p = que.front();
que.pop();
int nf = p.f + p.ki; // 上
if(nf <= n && ans[nf] == -1)
{
ans[nf] = p.t+1;
que.push((point){nf,k[nf],ans[nf]});
}
nf = p.f - p.ki; // 下
if(nf >= 1 && ans[nf] == -1)
{
ans[nf] = p.t+1;
que.push((point){nf,k[nf],ans[nf]});
}
}
cout << ans[b] << endl;
return 0;
}
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案.
这是一到典型的 DFS 题,DFS 组要就是利用回溯算法进行解决,回溯的具体思路如下,其难点在于确定递归参数的确定 。
【1】 写递归出口(收果子) 【2】 循环遍历搜索,并进行剪枝优化 【3】 处理节点 【4】 递归 【5】 回溯,即取消处理节点时的朝左 该题代码如下:
class Solution {
public:
vector<vector<int>> ret; // 用于存储最后的结果
vector<int> path; // 用于存储中间的结果
void bnf(int st,int n,int k)
{
// 收果子 (中止条件)
if(path.size() == k)
{
ret.push_back(path);
return;
}
// 循环,并进行剪枝优化
for(int i = st;i <= n - k + path.size() + 1;++i)
{
// 处理节点
path.push_back(i);
// 递归
bnf(i+1,n,k);
// 回溯
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
bnf(1,n,k);
return ret;
}
};
代码随想录 洛谷搜索算法推荐题库 马的遍历的洛谷题解 本文到此结束,希望对您有所帮助.
最后此篇关于算法总结--搜索的文章就讲到这里了,如果你想了解更多关于算法总结--搜索的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我在我的应用程序中使用 Hibernate Search。其中一个子集合被映射为 IndexedEmbedded。子对象有两个字段,一个是 id,另一个是日期(使用日期分辨率到毫秒)。当我搜索 id=
The App Engine Search API有一个 GeoPoint 字段。可以用它来进行半径搜索吗?例如,给定一个 GeoPoint,查找位于特定半径内的所有文档。 截至目前,它看起来像 Ge
客户对我正在做的员工管理项目提出了这个新要求,以允许他们的用户进行自定义 bool 搜索。 基本上允许他们使用:AND、OR、NOT、括号和引号。 实现它的最佳方法是什么?我检查了 mysql,它们使
很想知道哪个更快 - 如果我有一个包含 25000 个键值对的数组和一个包含相同信息的 MySQL 数据库,搜索哪个会更快? 非常感谢大家! 最佳答案 回答这个问题的最好方法是执行基准测试。 关于ph
我喜欢 smartcase,也喜欢 * 和 # 搜索命令。但我更希望 * 和 # 搜索命令区分大小写,而/和 ?搜索命令遵循 smartcase 启发式。 是否有隐藏在某个地方我还没有找到的设置?我宁
我有以下 Marklogic 查询,当在查询控制台中运行时,它允许我检索具有管理员权限的系统用户: xquery version "1.0-ml"; import schema namespace b
我希望当您搜索例如“A”时,所有以“A”开头的全名都会出现。因此,如果名为“Andreas blabla”的用户将显示 我现在有这个: $query = "SELECT full_name, id,
我想在我的网站上添加对人名的搜索。好友列表已经显示在页面上。 我喜欢 Facebook 这样做的方式,您开始输入姓名,Facebook 只会显示与查询匹配的好友。 http://cl.ly/2t2V0
您好,我在我的网站上进行搜索时遇到此错误。 Fatal error: Uncaught Error: Call to undefined function mysql_connect() in /ho
声明( 叠甲 ):鄙人水平有限,本文为作者的学习总结,仅供参考。 1. 搜索介绍 搜索算法包括深度优先搜索(DFS)和广度优先搜索(BFS)这两种,从起点开始,逐渐扩大
我正在为用户列表使用 FuturBuilder。我通过 futur: fetchpost() 通过 API 获取用户。在专栏的开头,我实现了一个搜索栏。那么我该如何实现我的搜索栏正在搜索呢? Cont
我正在使用 MVC5,我想搜索结果并停留在同一页面,这是我在 Controller (LiaisonsProjetsPPController) 中执行搜索操作的方法: public ActionRes
Azure 搜索中的两种方法 Upload 与 MergeOrUpload 之间有什么区别。 他们都做完全相同的事情。即,如果文档不存在,它们都会上传文档;如果文档已经存在,则替换该文档。 由于这两种
实际上,声音匹配/搜索的当前状态是什么?我目前正在远程参与规划一个 Web 应用程序,该应用程序将包含和公开记录的短音频剪辑(最多 3-5 秒,人名)的数据库。已经提出了一个问题,是否可以实现基于用户
在商业应用程序中,具有数百个面并不罕见。当然,并非所有产品都带有所有这些标记。 但是在搜索时,我需要添加一个方面查询字符串参数,其中列出了我想要返回的所有方面。由于我事先不知道相关列表,因此我必须在查
当我使用nvcc 5.0编译.cu文件时,编译器会为我提供以下信息。 /usr/bin/ld: skipping incompatible /usr/local/cuda-5.0/lib/libcud
我正在使用基于丰富的 Lucene 查询解析器语法的 Azure 搜索。我将“~1”定义为距离符号的附加参数)。但我面临的问题是,即使存在完全匹配,实体也没有排序。 (例如,“blue~1”将返回“b
我目前有 3 个类,一个包含 GUI 的主类,我在其中调用此方法,一个包含数据的客户类,以及一个从客户类收集数据并将其放入数组列表的 customerList 类,以及还包含搜索数组列表方法。 我正在
假设我有多个 6 字符的字母数字字符串。 abc123、abc231、abc456、cba123、bac231 和 bac123 。 基本上我想要一个可以搜索和列出所有 abc 实例的选择语句。 我只
我有这个表 "Table"内容: +--------+ | Serial | +--------+ | d100m | <- expected result | D100M | <- expect
我是一名优秀的程序员,十分优秀!