这道题是在LeetCode探索,队列&栈模块中刷到的,属于广度优先搜索的题目。之前没有接触过此类题目,因此用普通的广搜思想,做题的时候表示一脸懵逼,后无奈看了一波题解,将解题的思路记入博客中,方便日后复习诸如此类的问题。小伙伴们对于代码有什么疑惑或者改进的地方,欢迎在评论区留言哈!
算法:广度优先搜索
数据结构:队列+哈希表
解题思路:
①把问题转化成图的最短路径问题,这里的最短路径指的是由起始状态”0000”转换为目标状态所需要的最少变换次数
②我们用广度优先搜索来找到最短路径,从 0000 开始搜索。对于每一个状态,它可以扩展到最多 8 个状态,即将它的第 i = 0, 1, 2, 3 位增加 1 或减少 1(0减一变为9,9加一变为0)
③将这些状态中==没有搜索过==并且==不在 deadends 中==的状态全部加入到队列中,并继续进行搜索
④使用set来保存deadends中的状态以及访问过的状态(0000也有可能在deadends中)
1 | class Solution { |
时间复杂度:O(N^2 * A^N + D), A 表示数字的个数,N 表示状态的位数,D表示数组 deadends 的大小。在最坏情况下,我们需要搜索完所有状态,状态的总数为 O(A^N)。对于每个状态,我们要枚举修改的位置,需要 O(N) 的时间,枚举后得到新的状态同样需要 O(N)的时间
空间复杂度:O(A^N+D),用来存储队列以及 deadends 的集合
- 本文作者: a_Gen
- 本文链接: http://imaginee.cn/2020/01/21/LeetCode 752.打开转盘锁/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!