搜索引擎中注册网站,网站专题页面策划,在南海建设工程交易中心网站,哈尔滨企业展示型网站建设题目链接
leetcode在线oj题——打开轮盘锁
题目描述
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字#xff1a; ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转#xff1a;例如把 ‘9’ 变为 ‘0’#xff0…题目链接
leetcode在线oj题——打开轮盘锁
题目描述
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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” 时这个锁就会被锁定。
示例2: 输入: deadends [“8888”], target “0009” 输出1 解释把最后一位反向旋转一次即可 “0000” - “0009”。
示例3: 输入: deadends [“8887”,“8889”,“8878”,“8898”,“8788”,“8988”,“7888”,“9888”], target “8888” 输出-1 解释无法旋转到目标数字且不被锁定。
题目提示
1 deadends.length 500deadends[i].length 4target.length 4target 不在 deadends 之中target 和 deadends[i] 仅由若干位数字组成
解题思路
使用广度优先搜索将所有情况遍历出来
创建一个队列queue将起始位置放进队列 首先从起始位置出发将其从队列中拿出来将其所有位置的字符向上波动或向下波动如果不是死亡位置并且没有被遍历过就放入队列中step
然后再将队列中所有元素都拿出来分别对其每个位置都向上波动或向下波动如果匹配target则直接返回step如果不是死亡位置并且没有被遍历过就放入队列中step
一直重复上述操作直到队列为空都没有找到target说明无法达到目标返回-1
代码
class Solution {public int openLock(String[] deadends, String target) {HashSetString deadDict new HashSet();for (int i 0; i deadends.length; i) {deadDict.add(deadends[i]);}HashSetString isUsed new HashSet();if(deadDict.contains(0000)){return -1;}QueueString queue new LinkedList();queue.offer(0000);isUsed.add(0000);int step 0;while(!queue.isEmpty()){int size queue.size();while (size ! 0){String curString queue.poll();if(curString.equals(target)){return step;}for (int i 0; i curString.length(); i) {char ch1 curString.charAt(i);char ch2 curString.charAt(i);//向下波动或者向上波动if(ch1 9){ch1 0;} else {ch1;}if(ch2 0){ch2 9;} else {ch2--;}StringBuffer sb1 new StringBuffer(curString);StringBuffer sb2 new StringBuffer(curString);sb1.setCharAt(i, ch1);sb2.setCharAt(i, ch2);if(!deadDict.contains(sb1.toString()) !isUsed.contains(sb1.toString())){queue.offer(sb1.toString());isUsed.add(sb1.toString());}if(!deadDict.contains(sb2.toString()) !isUsed.contains(sb2.toString())){queue.offer(sb2.toString());isUsed.add(sb2.toString());} }size--;}step;}return -1;}
}
