@SomeBottleLeetcode每日一题 —— 3629. 通过质数传送到达终点的最少跳跃次数 中发帖

难不成这周是跳跃周? 😇 

思路
对于每个下标 i 处:

可以移动到相邻格子。
如果 nums[i] 是质数,可以跳转到任意其他可以被 nums[i] 整除的数字。

要求最小跳跃次数,且起点终点确定,这题可以采用 BFS。
对于第 1 点转移自然不必多说,注意标记访问情况,减少重复即可。
对于第 2 点,可以用埃式筛法列出素数,然后咱们可以用哈希表 pMap 记录每个素数 p 及其倍数在 nums 中出现的下标列表 (pMap[p])。
BFS 过程中在下标 idx 遇到素数 p 的时候,下一步可以转移到 pMap[p] 列表中除了 idx 以外的所有下标。
如此推进直至首次走到 n-1 这个位置为止。

代码
这题还是很容易被卡用例的,很多小细节。咱的思路也比较暴力,于是写成屎山了…有很大可优化空间。
一顿操作猛如虎,一看击败百分五
class Solution...