开锁

[编程题]开锁

热度指数：630 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个四位密码锁，每个拨轮有十个数字，从 '0' 到 '9' 每个拨轮可以自由旋转，例如一次从 '0' 转到 '1' 或 '9'。

锁初始数字是 "0000" ，给定一组特定的字符串形式的数字和一个字符串形式的目标值，要求你在不让锁上的数字达到这组数字中的任意一个的同时达到目标值，请你输出最少旋转次数，如果不可能达到，则输出-1。

数据范围：这一组数字的长度满足 $1 \le n \le 500 \$ ，给定的所有数字长度都是四位，并且保证目标值不在特定数字中

示例1

输入

["9999","9998","1000"],"1001"

输出

算法知识视频讲解

查看答案及解析

Java

o0草

1.使用广度优先算法

2.处理当前是‘9’或‘0’的加减

2.记录已经遍历过的元素，保证不要重复选择

3.判断条件增加，遇到输入字符串和遍历到的字符串一样的时候，跳出当前循环，执行下一次循环

4.判断条件增加，找到目标值跳出循环

发表于 2022-04-20 11:58:44 回复(0)

C++

牛客804813431号

bfs

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param vec string字符串vector 
     * @param tar string字符串 
     * @return int整型
     */
    int open(vector<string>& vec, string tar) {
        // write code here
        if (tar == "0000") return 0;
        unordered_set<string> deadset(vec.begin(), vec.end());
        if (deadset.count(tar)) return -1;
        auto prev = [](char s) -> char {return s == '0' ? '9' : s - 1;};
        auto succ = [](char s) -> char {return s == '9' ? '0' : s + 1;};
        auto get = [&](string& status) -> vector<string> {
            vector<string> ret;
            for (int i = 0; i < 4; ++i) {
                char num = status[i];
                status[i] = prev(num);
                ret.push_back(status);
                status[i] = succ(num);
                ret.push_back(status);
                status[i] = num;
            }
            return ret;
        };
        queue<pair<string, int>> q;
        q.emplace("0000", 0);
        unordered_set<string> seen;
        while (!q.empty()) {
            auto [status, step] = q.front();
            q.pop();
            for (auto&& next_status : get(status)) {
                if (!deadset.count(next_status) && !seen.count(next_status)) {
                    if (next_status == tar) return step + 1;
                    q.emplace(next_status, step + 1);
                    seen.insert(next_status);
                }
            }
        }
        return -1;
    }
};

发表于 2025-03-13 22:35:43 回复(0)

Python2

菜鸡升职记

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param vec string字符串一维数组
# @param tar string字符串
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/e7cbabbf7e0a41ec98055ee5f3d33bbe?tpId=196&tqId=40453&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    参考：
        大神：fred-coder
    算法：
        BFS
        初始："0000"入队queue
        我们对queue中的每一个密码，按位进行扩展，选取所有可行的密码，作为下一次的扩展队列，直到找到解或者queue为空。每对当前queue的所有密码进行一次扩展，旋转次数+1。
    复杂度：
        时间复杂度：待分析
        空间复杂度：待分析
    """

    def open(self, vec, tar):
        # write code here
        def up(num):  # 向上旋转：0 -> 1 -> ... -> 9 -> 0
            if num == 9:
                num = 0
            else:
                num += 1
            return str(num)

        def down(num):  # 向下旋转：9 -> 8 -> ... -> 0 -> 9
            if num == 0:
                num = 9
            else:
                num -= 1
            return str(num)

        queue, hashSet, visited = ["0000"], set(vec), set("0000")

        res = 0
        while queue:
            sonQueue = []
            for strNum in queue:
                if strNum == tar:
                    return res
                for i in range(4):  # 密码为4位，按位枚举
                    upNum = strNum[:i] + up(int(strNum[i])) + strNum[i + 1:]
                    if upNum not in hashSet and upNum not in visited:  # 判断向上旋转得到的密码是否有效（未出现过且不在vec中）
                        sonQueue.append(upNum)
                        visited.add(upNum)
                    downNum = strNum[:i] + down(int(strNum[i])) + strNum[i + 1:]
                    if downNum not in hashSet and downNum not in visited:  # 判断向下旋转得到的密码是否有效（未出现过且不在vec中）
                        sonQueue.append(downNum)
                        visited.add(downNum)
            res += 1  # 每经过一轮对queue所有元素的枚举，旋转次数+1
            queue = sonQueue
        return -1


if __name__ == "__main__":
    sol = Solution()

    # vec, tar = ["9999", "9998", "1000"], "1001"

    vec, tar = ["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"], "8888"

    res = sol.open(vec, tar)

    print res

发表于 2022-07-05 21:55:24 回复(0)