敲黑板划重点!这个大厂都考的题型你掌握了吗?

大家都知道，在面试之前大量刷题

是提升面试成功率的有效途径

但是如果面试准备时间有限

没空刷Lintcode上所有的题怎么办呢？

那当然就要划！重！点！

吃透大厂最近常考的热门题型

一个不小心就押中题了呢！

今天领扣猫要给大家划的重点题型就是

搜索算法中的

bfs（广度优先搜索算法）

这种题型在亚马逊、微软最近的面试中经常出现

是名副其实的热门题型

话不多说，先来看看LintCode里的经典bfs题吧！

描述

给定表示地图上坐标的2D数组，地图上只有值0,1,2.0表示可以通过，1表示不可通过，2表示目标位置。从坐标[0,0]开始，你只能上，下，左，右移动。找到可以到达目的地的最短路径，并返回路径的长度。

（地图一定存在且不为空，并且只存在一个目的地）

样例1

输入:

[

 [0, 0, 0],

 [0, 0, 1],

 [0, 0, 2]

]

输出: 4

说明: [0,0] -> [1,0] -> [2,0] -> [2,1] -> [2,2]

样例2:

输入:

[

    [0,1],

    [0,1],

    [0,0],

    [0,2]

]

输出: 4

说明: [0,0] -> [1,0] -> [2,0] -> [3,0] -> [3,1]

1.此题类似骑士遍历题，但骑士遍历题的检查target是检查坐标，这题是检查value。所以如果在struct Point里面加上value这一项要确保target=2的值没有被改掉。

2.此题不需要visited map，因为可以简单的将targetMap[i][j]设为1，这样下次就不用再访问了。

3.In the validPlace(), 要确保先检查p.x和p.y的范围，然后再检查grid[p.x][p.y]的值，不然就segment fault。

在LintCode搜索“1563”直达题目，查看参考代码

（注：需成为领扣VIP才能在“参考答案”tab中查看参考代码哦）

划完了重点，领扣猫要来送福利啦！

这次的福利是精心整理的

大厂最新面试真题大礼包！

有Amazon等五家公司的最新真题哦！

无屏蔽转发本条推送到朋友圈

或转发至100人以上CS相关微信群

扫以下二维码加“九章算法-小梦”为好友

将转发截图发给小梦，并发送“大厂真题礼包”

小梦会在2个工作日内给您发送大礼包哦~

※活动截至时间为2019年5月24日

PS：如果想要在线刷题、看参考代码

可以访问LintCode的ladder页面

会不定期更新各大公司的最新面试真题

成为LintCode VIP之后

就可以免！密！刷！题！啦！

点击“阅读原文”即可购买VIP啦~