752. 打开转盘锁

原创
01/12 19:55
阅读数 236

题目描述

解题思路

  1. 对于密码锁的任何一个位置,我们都可以选择向上或者向下旋转。
  2. 我们可以对每一个位置进行旋转,然后获取到对应的字符串,判断字符串是否是死亡字符串,如果是继续寻找,如果不是,判断和目标字符串是否相等,如果相等,返回步数,否则继续寻找,最终都无法找到则返回-1。
  3. 思维分析:如果目标字符串不是“0000”,那我们第一轮可以获得的密码情况有 2222=16种,这16种情况都是只需要拨动一次转轮就可以获得,如果没找到目标字符串,则需要在16中情况下对每一种情况的密码进行拨动,第二轮得到的情况则为1616,不断的向下寻找,其实这就是类似于寻找二叉树的最小深度。一旦找到,立即停止,否则继续向下寻找。

解题代码

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @description:
 * @author: lilang
 * @version:
 * @modified By:1170370113@qq.com
 */
public class TreeSolution {

    private Queue<String> stringQueue = new LinkedList<String>();

    private String lockDefault = "0000";

    /**
     * byte[]或char[]转化为String时不能使用toString()方法,而应使用new String()。
     * 锁旋转向上
     *
     * @param str
     * @param index
     * @return
     */
    private String upLock(String str, int index) {
        char[] chars = str.toCharArray();


        if (chars[index] == '9') {

            chars[index] = '0';
        } else {
            chars[index] += 1;
        }


        return new String(chars);
    }

    /**
     * 锁向下旋转
     *
     * @return
     */
    private String downLock(String str, int index) {
        char[] chars = str.toCharArray();


        if (chars[index] == '0') {

            chars[index] = '9';
        } else {
            chars[index] -= 1;
        }


        return new String(chars);

    }

    public int openLock(String[] deadends, String target) {

        int dept = 0;

        HashSet<String> deadSet = new HashSet<String>();

        HashSet<String> visitedString = new HashSet<String>();

        for (String dead : deadends) {
            deadSet.add(dead);
        }

        stringQueue.offer("0000");

        while (!stringQueue.isEmpty()) {


            int size = stringQueue.size();

            for (int i = 0; i < size; i++) {

                String lockString = stringQueue.poll();

                if (deadSet.contains(lockString)) {
                    continue;
                }

                if (lockString.equals(target)) {
                    return dept;
                }

                for (int j = 0; j < 4; j++) {
                    /**
                     * 每个节点都有向上,向下旋转的情况
                     */
                    String upLockString = upLock(lockString, j);

                    String downLockString = downLock(lockString, j);

                    if (!visitedString.contains(upLockString)) {

                        stringQueue.offer(upLockString);
                        visitedString.add(upLockString);
                    }

                    if (!visitedString.contains(downLockString)) {

                        stringQueue.offer(downLockString);
                        visitedString.add(downLockString);
                    }
                }


            }
            /**
             * 弹出数组中的一个元素表示旋转了一次
             */
            dept++;
        }


        return -1;

    }

}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部