Java
https://leetcode-cn.com/problems/open-the-lock/
使用图的广度优先遍历思想来实现,字符串处理得比较慢,可以使用哈希方法转换成对应的整型。再者图比较大,搜索速度受限于广度,可以使用双向广度优先遍历优化(没实现,同学们可以自己尝试)。
在求解问题的时候,之前的都是实实在在给出了可以遍历的情况,从而很明显可以看出那个问题是个图论问题,而在这个问题中,并没有很明显的给出图论问题的模型,需要我们自己去建模。在本问题中,锁的每个状态可以看做是图中的每个顶点,而从一种状态变成另一种状态就是求其“路径”的过程,如上图所示,对于0000这个状态,与其直接连接的(即可以通过一步操作变成的)状态就有8种,随之这8种状态还有很多种,而“1000”与“0100”也都可以通过一步操作到达“1100”状态,所以更加说明其是个多对多的关系,即图所描述的关系,这类问题是关于状态表达的问题。有了以上的转换,那么这个题就转换成了无权无向图的最短路径问题。
import java.util.ArrayList; import java.util.HashMap; /** * @author Minuy * @time 21:04 * @date 2021/11/20 */ public class Solution { int[] deadends; /** * 优化, * 1. 死亡数组可以转成哈希的形式加快判断 * 2. 目标不可达可以直接返回 * 3. 是否遍历跟距离可以一并存储处理 * 4. 字符串范围为0-9999,整个可以使用整型数字来代替以加快速度 */ public int openLock(String[] deadends, String target) { // 转换成对应的哈希值,加快判定速度 this.deadends = new int[deadends.length]; for (int i = 0; i < deadends.length; i++) { this.deadends[i] = hash(deadends[i]); } int sta = hash("0000"); int tar = hash(target); if(isDead(tar)){ // 目标不可达 return -1; } // 同时承担是否被遍历和存储当前距离的存储任务 HashMap<Integer, Integer> isVisited = new HashMap<>(); if (!isDead(sta)) { // 最开始的这个也要判断是不是凉凉的 ArrayList<Integer> queue = new ArrayList<>(); queue.add(sta); isVisited.put(sta, 0); if (tar == sta){ // 目标就是起始位置 return isVisited.get(tar); } while (!queue.isEmpty()) { sta = queue.remove(0); for (int s : getNextStats(sta)) { if (!isVisited.containsKey(s)) { queue.add(s); // isVisited.add(s); isVisited.put(s, isVisited.get(sta) + 1); if (s == tar) { return isVisited.get(tar); } } } } } return -1; } // 把分散的数组值合并 private int chartsToInt(int[] str) { int num = str[3]; num+=str[2]*10; num+=str[1]*100; num+=str[0]*1000; return num; } // 把字符串转换成对应的哈希值 private int hash(String str) { int hash = str.charAt(3) - '0'; hash += (str.charAt(2) - '0') * 10; hash += (str.charAt(1) - '0') * 100; hash += (str.charAt(0) - '0') * 1000; return hash; } // 获取与sta相邻的状态 private Iterable<Integer> getNextStats(int sta) { ArrayList<Integer> ret = new ArrayList<>(); int[] chars = new int[4]; chars[0] = sta / 1000; chars[1] = (sta / 100) % 10; chars[2] = (sta / 10) % 10; chars[3] = sta % 10; for (int i = 0; i < chars.length; i++) { int o = chars[i]; // 备份 // ---------------------加一操作 if (chars[i] == 9) { chars[i] = 0; } else { chars[i] += 1; } int next = chartsToInt(chars); if (!isDead(next)) { ret.add(next); } chars[i] = o; // 恢复一下 // ---------------------减一操作 if (chars[i] == 0) { chars[i] = 9; } else { chars[i] -= 1; } next = chartsToInt(chars); if (!isDead(next)) { ret.add(next); } chars[i] = o; // 恢复一下 } return ret; } // 判断有没有触碰到死亡密码 private boolean isDead(int str) { for (int dead : deadends) { if (dead == str) { return true; } } return false; } }