【leetcode】开密码锁

一、 题目描述

一个密码锁由 4 个环形拨轮组成，每个拨轮都有 10 个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，请给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

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

二、 代码思路

leetcode官方题解

本题并不是动态规划题，而是使用的一种很好的BFS思想。以往BFS总是用在图、树，本题BFS有了更灵活的一种用法。

在图中，BFS的下一个元素可以是四个方向。在二叉树或者多叉树中，BFS的下一个元素是该节点的孩子节点。

本题可以与岛屿问题类比，岛屿问题枚举下一个元素是四个方向，本题枚举是status + 1的所有可能性，status码就是指当前密码锁的值（比如说”0123“），由于每次我们拨动密码锁只能拨动一位数，所以我们从当前status枚举nextStatus，就是status + 1 。并且，可以将其作为下一个元素放入BFS队列。

同样的，本题还借用了BFS求最短路径问题的思想，也可以理解为从"0000"出发，找到从"0000"到 target 正确密码的最短距离。

具体地，我们在一开始将 (0000,0) 加入队列，并使用该队列进行广度优先搜索。在搜索的过程中，设当前搜索到的数字为 status，旋转的次数为 step，我们可以枚举 status 通过一次旋转得到的数字。设其中的某个数字为 next_status，如果其没有被搜索过，我们就将 (nextStatus, step+1) 加入队列。如果搜索到了 target，我们就返回其对应的旋转次数。

为了避免搜索到死亡数字，我们可以使用哈希表存储 deadends 中的所有元素，这样在搜索的过程中，我们可以均摊 O(1) 地判断一个数字是否为死亡数字。同时，我们还需要一个哈希表存储所有搜索到的状态，避免重复搜索。

如果搜索完成后，我们仍没有搜索到 target，说明我们无法解锁，返回 −1。

边界值判断：一定要注意边界值的判断以及访问数组的判断，做任何题都要考虑。

三、代码题解

//动态规划 求最优解
//并不是，而是使用的一种很好的BFS思想。以往BFS总是用在图、树，本题BFS有了更灵活的一种用法。
//可以与岛屿问题类比，岛屿问题枚举下一个元素是四个方向，本题枚举是status码 + 1的可能性
func openLock(deadends []string, target string) int {
	//边界值判断
	if target == "0000" {
		return 0
	}
	//初始化操作，HashMap判断我BFS的数字是否属于死亡数字，可能需要访问数组。
	deads := make(map[string]bool)
	for _, str := range(deadends) {
		deads[str] = true
	}
	//如果target 或者 0000 本身就是deadends
	_,ok := deads[target]
	_,ok1 := deads["0000"]
	if ok || ok1{
		return -1;
	}
	//处理枚举下一个元素
	//这里会出问题，修改nextStatus居然同时也会把statusCharArray修改掉，就离谱，可能是修改的同一块区域
	getNextStatus := func(status string) (ret []string){
		statusCharArray := []byte(status)
		for i,data := range(statusCharArray) {
			nextStaus := statusCharArray
			temp := data + 1
			if temp > '9' {
				nextStaus[i] = '0'
			} else {
				nextStaus[i] = temp
			}
			ret = append(ret, string(nextStaus))
			temp = data - 1
			if temp < '0' {
				nextStaus[i] = '9'
			} else {
				nextStaus[i] = temp
			}
			ret = append(ret, string(nextStaus))
			nextStaus[i] = data
		}
		return ret
	}
	//BFS操作
	//go 中是用切片实现队列的
	type node struct {
		status string
		step int
	}
	//队列辅助BFS
	//var queue []node
	//queue[0] = node{"0000",0}
	queue := []node{{"0000", 0}}
	//访问数组
	visited := make(map[string] bool)
	for len(queue) != 0 {
		statusNode := queue[0]
		queue = queue[1:]
		for _,nextStatus := range getNextStatus(statusNode.status) {
			_,ok = deads[nextStatus]
			//如果元素被访问，那么就会存在于visited数组中，ok1的返回值为ture 反之
			_,ok1 = visited[nextStatus]
			if !ok && !ok1{
				step := statusNode.step
				step++
				if nextStatus == target {
					return step
				}
				nextStatusNode := node{nextStatus, step}
				queue = append(queue, nextStatusNode)
				visited[nextStatus] = true
			}
		}
	}
	/*queue := list.New()
	queue.PushFront("0000")
	for queue.Len() != 0 {
		var status string
		status := queue.Front()
		queue.Remove(status)
		for _,nextStatus := range getNextStatus(string(status)) {
			if nextStatus
		}
	}*/

	return -1
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90