先看这样一个小故事,有一天,婷婷去超超的大学,想给异地已久的超超一个惊喜。但是方向感不好的婷婷很快就在大学迷路了。超超得知后便去寻找思恋已久的婷婷。此时超超的妈妈也在来学校的路上,现在超超要以最快的速度去寻找婷婷(不然可能会出现我和你妈同时迷路你先救谁的问题了)。那么,问题来了,你可以制定一种策略帮超超尽快找到婷婷吗?
下面将依次介绍广度优先搜索的定义,算法模板,俩种常见的题型,以及常见的出题点于易错点,帮助超超解决问题的同时,再顺手拿个offer!
广搜定义:又译作宽度优先搜索,或横向优先搜索,是一种图形搜索方法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法终止。
显然广度优先遍历就是树的层次遍历。
广搜步骤:
代码如下:
//树的节点
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func bfs(root *TreeNode) {
//初始化队列
que := make([]*TreeNode, 0, 100)
que = append(que, root)
//循环队列所有元素
for len(que) != 0 {
curSize := len(que)
//循环遍历每层节点
for i := 0; i < curSize; i++ {
//取出队列中节点
tnode := que[0]
que = que[1:]
//遍历该节点所能到达的节点,入队列
if tnode.Left == nil && tnode.Right == nil {
continue
}
if tnode.Left != nil {
que = append(que, tnode.Left)
}
if tnode.Right != nil {
que = append(que, tnode.Right)
}
}
}
}
抽象为模板如下
func bfs(root *TreeNode) int {
//初始化队列
que := make([]*TreeNode, 0, 100)
que = append(que, root)
dep := 1
//循环队列所有节点
for len(que) != 0 {
curSize := len(que)
//循环遍历每层节点
for i := 0; i < curSize; i++ {
//取出队列节点
tnode := que[0]
que = que[1:]
for 当前节点所有方向{
//对移动后的节点做坐标值变化
//特殊值,是否为边界,障碍物
...
//结果值判断,是否到达题目要求的目标点
...
//入队列
...
}
}
//深度变化(步数)
dep++
}
return 0
}
易错点:
下面来看看广搜怎么解决超超的问题,用0表示空地,1表示障碍物,假设超超在地图左上角,婷婷在地图的右下角,超超每一步可以沿着八个方向移动,那么地图可以抽象为下图所示,超超希望的也就是用最少的移动步数从左上角移动到右下角:
分析:看到图中求最短路径问题,明显属于广度优先求解的一种题型,下面上模板
func bfs(root *TreeNode) int {
//初始化队列
que := make([]*TreeNode, 0, 100)
que = append(que, root)
dep := 1
//循环队列所有节点
for len(que) != 0 {
curSize := len(que)
//循环遍历每层节点
for i := 0; i < curSize; i++ {
//取出队列节点
tnode := que[0]
que = que[1:]
for 当前节点所有方向{
//对移动后的节点做坐标值变化
//特殊值,是否为边界,障碍物
...
//结果值判断,是否到达题目要求的目标点
...
//入队列
...
}
}
//深度变化(步数)
dep++
}
return 0
}
完整代码如下:
func shortestPathBinaryMatrix(grid [][]int) int {
width := len(grid)
//若起点和终点是障碍物则地图有问题
if grid[0][0] == 1 || grid[width-1][width-1] == 1 {
return -1
}
//地图中起点和终点是一个点
if width == 1 {
return 1
}
//初始化队列和visit
que := make([]*Node, 0, width*width)
visit := make([][]bool, width)
for i := 0; i < len(visit); i++ {
visit[i] = make([]bool, width)
}
dep := 1
//每个节点所能走的八个方向
next := [][]int{
{
1, 0}, {
-1, 0}, {
0, 1}, {
0, -1}, {
1, 1}, {
1, -1}, {
-1, 1}, {
-1, -1}}
que = append(que, &Node{
0, 0})
visit[0][0] = true
//开始搜索
for len(que) != 0 {
current := len(que)
//按层遍历
for i := 0; i < current; i++ {
top := que[0]
que = que[1:]
//对队列中的节点做八个方向的坐标变化
for i := 0; i < 8; i++ {
var temp *Node = new(Node)
temp.x = top.x + next[i][0]
temp.y = top.y + next[i][1]
//移动后坐标越界
if temp.x >= width || temp.x < 0 || temp.y >= width || temp.y < 0 {
continue
}
//找到终点(右下角)
if temp.x == width-1 && temp.y == width-1 {
return dep + 1
}
//不是障碍物并且没有被遍历过入队列
if grid[temp.x][temp.y] != 1 && !visit[temp.x][temp.y] {
que = append(que, temp)
visit[temp.x][temp.y] = true
}
}
}
//层数加1
dep++
}
return -1
}
分析:帮助完超超之后,也要为我们的offer好好准备下了,面试算法很少会直接出一个图的bfs题型,比较常见的是这种题型。这题看似和bfs没有关系,起点hit能匹配的字符串为it,h * t,hi,与worldList中可以匹配的节点就可以连接了,这样依次连接下去是不是就可以练成图了!这题也就变成了求hit到cog的最短距离。
分析:
代码:
func ladderLength(beginWord string, endWord string, wordList []string) int {
//定义并初始化visit
visit := map[string]bool{
}
for _, w := range wordList {
visit[w] = false
}
que := []string{
beginWord}
dep := 1
//遍历所有元素
for len(que) != 0 {
curSize := len(que)
for i := 0; i < curSize; i++ {
top := que[0]
que = que[1:]
if top == endWord {
return dep
}
//判断能连接的字符串
for c := 0; c < len(top); c++ {
for j := 'a'; j <= 'z'; j++ {
newWord := top[:c] + string(j) + top[c+1:]
if visit[newWord] == false {
que = append(que, newWord)
visit[newWord] = true
}
}
}
}
dep++
}
return 0
}
出题点:题型一共是三种,树的层次遍历,图的最短路径,字符串匹配最短路径,找准关键字“最短路径”,“层次遍历”
模板记忆:水纹波动有规律,层次遍历层层清(cursize,visit),找准特殊位置点(墙,终点,是否便利过),判断条件定先后(特殊点判断先后顺序)
思路:拿到题目,我们首先可以捕捉关键词,一旦看到有“最短路径”、“层次遍历”这种词语,那么我们应该第一反应想到BFS。但是有时候题目会隐藏这种暴露语句,例如单词接龙一样,这时我们需要抽象它的本质。确定了方案之后,我们就可以直接套模板了。但是,需要注意的是,在遍历时或许会有重复路径的可能,这时不要忘了设visted的备忘录。同时,我们需要注意障碍物,边界值,终点位置的先后判断
易错点:循环队列中节点用curSize记录当前队列长度,而不是用len(que)
文章浏览阅读4.3k次,点赞3次,收藏14次。我们想在windows系统中想用linux系统,用的最多的就是虚拟机了吧,今天介绍一种不用装虚拟机在windows也能使用linux系统的一个方法,该方法全程使用命令,但对于常用linux的人来说也不是什么难事,最主要是精简,不用打开虚拟机,非常方便,特此记录一下。_windows安装linux子系统
文章浏览阅读9.3k次,点赞8次,收藏38次。用到的指令介绍 AT+CWMODE 配置wifi模式 AT+CWJAP 连接AP AT+CIPSTART 建立TCP连接 AT+CIPSEND 透传发送数据API接口:http://cgi.im.qq.com/cgi-bin/cgi_svrtime具体过程 先配置WiFi,esp8266连上路由器AT+CWMODE=3AT+CWJAP=&amp;amp;quot;HONOR9&amp;amp;quot;,&amp;amp;quot;12_esp8266wifi模块获取网络时间
文章浏览阅读871次。第九章结构体9.1结构体的概念结构体是一种可以由我们自己定义的数据类型#include <stdio.h>struct student{ int num; int score; float average;};int main(void){ //定义变量,存放学生的序号、成绩、平均分 struct student Tom;//Tom是变量,struct student是数据类型 struct student cla_c语言谭浩强第五版宏定义在哪章
文章浏览阅读2.9k次,点赞3次,收藏12次。package pers.machi;import com.google.common.base.Joiner;import org.apache.calcite.avatica.util.Casing;import org.apache.calcite.config.Lex;import org.apache.calcite.sql.*;import org.apache.calcite.sql.parser.SqlParseException;import org.apache.calci_calcite 血缘分析
文章浏览阅读6.4k次,点赞12次,收藏90次。一、摄像头结构和工作原理. 拍摄景物通过镜头,将生成的光学图像投射到传感器上,然后光学图像被转换成电信号,电信号再经过模数转换变为数字信号,数字信号经过DSP加工处理,再被送到电脑中进行处理,最终转换成手机屏幕上能够看到的图像。数字信号处理芯片DSP(DIGITAL SIGNAL PROCESSING)功能:主要是通过一系列复杂的数学算法运算,对数字图像信号参数进行优化处理,并把处理后的信号通过USB等接口传到PC等设备。DSP结构框架: 1. ISP(image signal pro.._avdd dvdd 对图像信号的影响
文章浏览阅读137次。Linux以rpm方式安装Mysql,Centos7通过rpm安装Mysql5.5,Linux Mysql rpm安装================================Copyright 蕃薯耀 2020-11-10https://www.cnblogs.com/fanshuyao/一、上传rpm包到Linux服务器,然后进入目录,接着安装rpm -ivh MySQL-server..._package perl-4:5.16.3-293.el7.x86_64 was already added, replacing with perl-
文章浏览阅读144次。博主介绍:全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战精彩专栏 推荐订阅2023-2024年最值得选的微信小程序毕业设计选题大全:100个热门选题推荐2023-2024年最值得选的Java毕业设计选题大全:500个热门选题推荐Java精品实战案例《500套》微信小程序项目精品案例《500套》文末获取源码+数据库。_图书馆座位管理系统
文章浏览阅读8.4k次。前一阵有一个项目是采用Vue.js作为前端技术栈开发的,在实际部署的时候采用的是Webpack打包,然后用Nginx作为代理服务器,然后采用Daocloud平台,将其作为Docker容器部署。由于后台也是采用Docker部署,所以我们并不知道后台的IP地址,没有办法采用常见的将自己定义的Nginx配置文件default.conf替换默认文件,常见方式的实现是:RUN rm /etc/nginx/c..._cloudbuild上vue项目的dockerfile怎么写
文章浏览阅读391次,点赞4次,收藏9次。在Python中,类变量和实例变量是面向对象编程的两个重要概念。它们在定义、存储和访问方式上有很大的不同,这主要源于它们所关联的对象不同:类变量与类本身相关联,而实例变量则与类的实例(或对象)相关联。这个示例清晰地展示了类变量和实例变量在定义、存储、访问和修改方面的区别。理解这些区别对于有效地使用Python进行面向对象编程至关重要。_python中类变量和实例变量的区别
文章浏览阅读1.7w次,点赞6次,收藏43次。FPS游戏内的十字瞄准视角其实就是一个视角摄像机这个应该不难理解吧,如何调整摄像机的视角就要用到一个叫“姿态角(Euler角)”的数据,即: yaw , pitch , roll。这3个值的解释如下:pitch是围绕X轴旋转,也叫做俯仰角yaw是围绕Y轴旋转,也叫偏航角roll是围绕Z轴旋转,也叫翻滚角用张图来解释比较直观:首先我们要先知道自己的Euler角值,然后_自瞄的瞄准角度是什么
文章浏览阅读871次。2017年12月31日做一次技术总结,人生第一次框架选型:assertJ+Junit+powemockito+mockito+maven/ant/gradle+jacoco+jenkins+sonarqube单元测试中,要测试目标模块的时候比如测试 service 方法的时候,service 方法中我们有可能会去调用数据库的执行结果,会取 redis 中缓存数据,也有可能会使用当前的系统时间,根据..._java 单元测试 接口如何覆盖
陇剑杯 省赛 攻击者1 CTF wireshark 流量分析