💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍥 本套卷难度较简单

1️⃣ 比较简单，可以直接扔一个BFS或者用数学的做法

2️⃣ 看清本质后发现是求最长连续1

3️⃣ 前几天b站考过的原题，分类讨论下即可

🚙 01.密码箱的最短路径

问题描述

LYA 收到了一个神秘的密码箱作为生日礼物。这个密码箱上有四个数字转盘，每个转盘上的数字范围是 0 到 9。LYA 想要打开这个密码箱，她可以进行以下操作：

1. 将任意一个转盘的数字向下调整一位（例如，9 变成 8，0 变成 9）。
2. 将任意一个转盘的数字向上调整一位（例如，8 变成 9，9 变成 0）。

LYA 知道密码箱的初始状态和目标状态，她想知道最少需要多少次操作才能从初始状态达到目标状态。你能帮助她解决这个问题吗？

输入格式

输入包含两个长度为 4 的字符串，用空格分隔。这两个字符串分别表示密码箱的初始状态和目标状态，每个字符都是一个 0 到 9 之间的数字。

输出格式

输出一个整数，表示从初始状态到达目标状态所需的最小操作次数。

样例输入

9999 8888

样例输出

4

数据范围

• 输入的两个字符串长度均为 4。
• 字符串中的每个字符都是 0 到 9 之间的数字。

题解

直接上BFS 或者 数学的办法考虑一下相减

参考代码

• Python

from collections import deque

def bfs(start, target):
    # 初始化队列和已访问集合
    queue = deque([(start, 0)])
    visited = set([start])
    
    while queue:
        state, steps = queue.popleft()
        # 如果达到目标状态，返回步数
        if state == target:
            return steps
        
        # 尝试所有可能的下一个状态
        for i in range(4):
            for d in (-1, 1):
                # 计算新的状态
                new_digit = (int(state[i]) + d) % 10
                new_state = state[:i] + str(new_digit) + state[i+1:]
                # 如果新状态未被访问过，加入队列
                if new_state not in visited:
                    visited.add(new_state)
                    queue.append((new_state, steps + 1))
    
    # 如果无法到达目标状态，返回-1
    return -1

# 读取输入
start, target = input().split()

# 计算并输出结果
print(bfs(start, target))

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String start = scanner.next();
        String target = scanner.next();
        scanner.close();

        System.out.println(bfs(start, target));
    }

    static int bfs(String start, String target) {
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        Map<String, Integer> steps = new HashMap<>();

        queue.offer(start);
        visited.add(start);
        steps.put(start, 0);

        while (!queue.isEmpty()) {
            String state = queue.poll();
            if (state.equals(target)) {
                return steps.get(state);
            }

            for (int i = 0; i < 4; i++) {
                for (int d = -1; d <= 1; d += 2) {
                    char[] chars = state.toCharArray();
                    chars[i] = (char) (((chars[i] - '0' + d + 10) % 10) + '0');
                    String newState = new String(chars);
                    if (!visited.contains(newState)) {
                        visited.add(newState);
                        queue.offer(newState);
                        steps.put(newState, steps.get(state) + 1);
                    }
                }
            }
        }

        return -1; // 如果无法到达目标状态
    }
}

• Cpp

#include <iostream>
#include <queue>
#include <unordered_set>
#include <string>
using namespace std;

int bfs(string start, string target) {
    queue<pair<string, int>> q;
    unordered_set<string> visited;

    q.push({start, 0});
    visited.insert(start);

    while (!q.empty()) {
        auto [state, steps] = q.front();
        q.pop();

        if (state == target) {
            return steps;
        }

        for (int i = 0; i < 4; ++i) {
            for (int d = -1; d <= 1; d += 2) {
                string new_state = state;
                new_state[i] = ((new_state[i] - '0' + d + 10) % 10) + '0';
                if (visited.find(new_state) == visited.end()) {
                    visited.insert(new_state);
                    q.push({new_state, steps + 1});
                }
            }
        }
    }

    return -1; // 如果无法到达目标状态
}

int main() {
    string s