比较简单的一种有套路的算法,套路如下

  1. 根据题意提取关键节点node,利用队列queue
  2. 找出业务中的分层逻辑,将node按层加入queue,加入时注意,不要将已加入过的节点重复放入,一半使用和入参相同结构的visited数组
  3. 找到业务中的终点逻辑,在从queue中取时,判断是否遍历结束

例题如下

  1. 二进制矩阵中的最短路径(1091)

给你一个 n x n 的二进制矩阵 grid 中,返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径,返回 -1 。 ​

二进制矩阵中的 畅通路径 是一条从 左上角 单元格(即,(0, 0))到 右下角 单元格(即,(n - 1, n - 1))的路径,该路径同时满足下述要求: ​

路径途经的所有单元格都的值都是 0 。 路径中所有相邻的单元格应当在 8 个方向之一 上连通(即,相邻两单元之间彼此不同且共享一条边或者一个角)。 畅通路径的长度 是该路径途经的单元格总数

套用套路如下

  1. 关键节点node应存储的信息时矩阵的x,y的坐标,首个队列中的节点为(0,0)
  2. 每个node的下一层为其周围8个点中值不为1的,可以利用二维数组visited将加入过的节点进行标记
  3. 当节点的坐标为n-1时,即遍历结束,一共经历了多少层即为所求

  1. 完全平方数(279)

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 ​

给你一个整数 n ,返回和为 n 的完全平方数的 最少数量 。 ​

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

套用套路如下

  1. 关键节点node即为正整数,首个队列中的节点为n
  2. 每个node的下一层应该是目标值target - xx,x∈[1,n](nn < target)
  3. 当x*x=target时,即遍历结束,一共经历了多少层即为所求

  1. 单词接龙

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列: ​

序列中第一个单词是 beginWord 。 序列中最后一个单词是 endWord 。 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典 wordList 中的单词。 给你两个单词 beginWord 和 endWord 和一个字典 wordList ,找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0。

套用套路如下

  1. 关键节点node为单词,首个队列中的节点为beginWord
  2. 每个节点node的下一层为和字典中和node相差一个字母的单词
  3. 当队列中的node和endWord相等时遍历结束,一共经历了多少层即为所求