15
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

5
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

from collections import deque

# 读取输入
n = int(input())

def min_steps(n):
    # 使用 deque 来实现队列，初始化队列中的第一个元素为 (n, 0)，表示起始数字 n 和步数为 0
    queue = deque([(n, 0)])
    
    # 用一个集合来记录已经访问过的数字，避免重复处理
    visited = set()

    while queue:
        # 从队列中取出一个元素
        current, steps = queue.popleft()

        # 如果当前数字已经是 1，说明找到了最短的转换路径，返回步数
        if current == 1:
            return steps

        # 如果当前数字是偶数，则下一步可以是 current // 2
        if current % 2 == 0:
            next_step = current // 2
        else:
            # 如果是奇数，则下一步可以选择加 1 或减 1
            next_step = current + 1

        # 如果这个下一步数字没有被访问过，则加入队列
        if next_step not in visited:
            visited.add(next_step)  # 标记该数字已访问
            queue.append((next_step, steps + 1))  # 将下一步数字和步数加入队列

        # 如果当前数字是奇数，则还可以进行减 1 操作
        if current % 2 != 0:
            prev_step = current - 1
            if prev_step not in visited:
                visited.add(prev_step)  # 标记该数字已访问
                queue.append((prev_step, steps + 1))  # 将减 1 操作的结果加入队列

# 输出从 n 到 1 的最小步数
print(min_steps(n))

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42

java解法

• 解题思路
• 解题思路
  题目要求找到从一个整数 n 转换为 1 的最小步骤数。在每一步中，你可以做以下操作：

如果当前数字是偶数，可以将其除以 2。
如果当前数字是奇数，可以选择加 1 或减 1。
由于我们需要寻找最小的转换步数，使用 广度优先搜索（BFS） 是非常合适的。BFS 的特点是可以确保我们在找到目标（1）时，所经过的路径是最短的。也就是说，通过 BFS 的层次遍历，我们可以保证每一层的步数都是最小的。

BFS 实现步骤
队列初始化：

使用一个队列来存储当前数字及其对应的步数。队列中的每个元素是一个包含当前数字和当前步数的二元组 (current, steps)。
使用一个集合 visited 来记录已经访问过的数字，避免重复处理同一数字。
BFS 处理：

从 n 开始进行 BFS，队列中的元素会逐一被弹出并处理。
对于当前数字 current，如果是偶数，则可以选择 current / 2 作为下一步。
如果是奇数，可以选择 current + 1 或 current - 1 作为下一步。
将所有未访问的下一步数字加入队列，并标记为已访问。
终止条件：

如果当前数字为 1，则返回当前的步数。
返回最小步数：

BFS 的特性保证了我们在找到 1 时，已经是最短的路径

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

public class Main {
    public static void main(String[] args) {
        // 创建扫描器对象读取输入
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入的数字 n
        int n = scanner.nextInt();
        
        // 关闭扫描器
        scanner.close();

        // 调用 minSteps 方法并打印结果
        System.out.println(minSteps(n));
    }

    // minSteps 方法：求从 n 转换为 1 的最小步数
    public static int minSteps(int n) {
        // 创建队列用于 BFS，队列中存储的元素是 int[] 数组，包含当前数字和当前步数
        Queue<int[]> queue = new LinkedList<>();
        
        // 创建一个集合来记录已访问过的数字，避免重复处理
        Set<Integer> visited = new HashSet<>();

        // 将初始数字 n 和步数 0 放入队列
        queue.add(new int[]{n, 0});
        // 将初始数字 n 标记为已访问
        visited.add(n);

        // BFS 队列处理
        while (!queue.isEmpty()) {
            // 从队列中取出当前的数字和步数
            int[] current = queue.poll();
            int value = current[0];  // 当前数字
            int steps = current[1];  // 当前步数

            // 如果当前数字已经是 1，说明找到了最小步数，返回结果
            if (value == 1) {
                return steps;
            }

            // 如果当前数字是偶数，可以进行除以 2 操作
            if (value % 2 == 0) {
                int nextStep = value / 2;
                // 如果 nextStep 没有访问过，将其加入队列
                if (!visited.contains(nextStep)) {
                    visited.add(nextStep);
                    queue.add(new int[]{nextStep, steps + 1});
                }
            } else {
                // 如果当前数字是奇数，可以进行加 1 操作
                int nextStep = value + 1;
                if (!visited.contains(nextStep)) {
                    visited.add(nextStep);
                    queue.add(new int[]{nextStep, steps + 1});
                }

                // 也可以进行减 1 操作
                int prevStep = value - 1;
                if (!visited.contains(prevStep)) {
                    visited.add(prevStep);
                    queue.add(new int[]{prevStep, steps + 1});
                }
            }
        }

        // 理论上不会到达这里，因为我们已经在 BFS 中找到了目标
        return -1;
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">