leetcode 探索 队列与栈 打开转盘锁

题目

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。 字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。 示例 1:

输入：deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202” 输出：6 解释： 可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。 注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的， 因为当拨动到 “0102” 时这个锁就会被锁定。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/open-the-lock/

分析

解体思路，来自题解里的不是归人。

仍然是广度优先搜索，广度优先搜索需要结合队列。广度优先搜索是有模板的，即把第一个节点加入队列，然后找该节点的相邻的节点，是为第一层，第一层取完了，判断完了，再取第二层，进行判断。判断过的节点，要注意设置为已经访问，同时如果是deadends，就不要作为判断节点了，即不要再加入待判断的队列了。

这里的step计算，要注意。

其中每一步都有八种可能，四个元素每个都可上可下，即4*2，我们要把这八种可能都加入到带判断的队列。这里通过将string转换成char型数组，然后将其对应位置+1或者-1进行修改，生成新的解锁钥匙key。

另外一个小技巧，将byte里的数字，减去’0’ 即可转换为10进制，再加回’0’ 即可转换回byte

解法

func openLock(deadends []string, target string) int { var deadset = make(map[string]bool, len(deadends)) for _, v:= range deadends { deadset[v] = true } if deadset["0000"] { return -1 } if "0000" == target { return 0 } queue := make([]string, 0) visited := make(map[string]bool) queue = append(queue, "0000") // visited["0000"] = struct{}{} step := 0 for len(queue) > 0 { // step 要在何时加啊，不能每次取出一个就加。而是每次拨动一次之后，再加 step++ size := len(queue) // 把当前的queue 遍历完了，就是一次拨片，即一次拨片的所有拨法 for i:=0; i < size; i++ { // front := queue[0] // queue = queue[1:] front := queue[i] // fmt.Printf("front: %s, %v\n", front, queue) // 是否访问过，没有就将其设为访问 if visited[front] { continue } visited[front] = true // 找出front的八个周边,然后加入到队列 for i := range front { downKey := down(front, i) // 是否是key if downKey == target { return step } // 是不是dead lock if !deadset[downKey] && !visited[downKey] { queue = append(queue, downKey) } upKey := up(front, i) // 是否是key if upKey == target { return step } // 是不是dead lock if !deadset[upKey] && !visited[upKey] { queue = append(queue, upKey) } } } queue = queue[size:] } return -1 } // 往上拨 func up(s string, i int) string { chars := []byte(s) chars[i] = (chars[i] - '0' + 1) % 10 + '0' return string(chars) } // 往下拨 func down(s string, i int) string { chars := []byte(s) // 将byte里的数字，减去'0' 即可转换为10进制，再加回'0' 即可转换回byte chars[i] = (chars[i]- '0' - 1 + 10) % 10 + '0' return string(chars) }