题目链接

神秘石像的镜像序列

题目描述

探险家发现了一串以数字 0 作为结束标志的整数序列。为了触发机关,需要将这串数字(不含结束标志0)倒序读取。

输入描述: 在一行内输入若干非负整数,以 0 作为结束标志,整数之间用空格分隔。

输出描述: 在一行内按空格分隔输出倒序后的整数序列,不包含结束标志 0

解题思路

本题的核心要求是将一个未知长度的序列逆序输出。由于我们必须先读取完所有数字,才能知道最后一个数字是什么(也就是我们第一个要输出的数字),所以我们无法在读取的同时进行输出。

这就要求我们使用一种数据结构,先把所有有效的数字(即 0 之前的所有数字)按顺序存储起来。一个可以动态调整大小的数组(或列表)是完成这个任务的完美工具。

算法可以分为两个清晰的阶段:

  1. 数据读取与存储阶段:

    • 创建一个动态数组(在 C++ 中是 std::vector,在 Java 中是 ArrayList,在 Python 中是 list)。
    • 循环读取输入的整数。对于每个读到的数:
      • 检查它是否是结束标志 0
      • 如果是 0,则停止读取,跳出循环。
      • 如果不是 0,则将其添加到动态数组的末尾。
    • 当循环结束后,我们的数组中就按原始顺序保存了所有需要处理的数字。
  2. 逆序输出阶段:

    • 现在,我们需要从后往前遍历我们存储好的数组。
    • 一个标准的 for 循环,索引从 数组长度 - 1 开始,递减到 0,即可实现逆序遍历。
    • 在循环中,依次输出每个元素。
    • 注意处理输出格式:在数字之间需要用空格隔开,但行末不能有-多余的空格。一个简单的处理技巧是,先输出第一个倒序的数,然后在一个循环里先输出空格再输出数字。

对于 Python 这样的语言,可以利用其内置的强大功能,如列表的 reverse() 方法或 reversed() 函数,以及 join 方法来更简洁地完成任务。

代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> numbers;
    int num;
    
    // 1. 读取数据阶段
    while (cin >> num) {
        if (num == 0) {
            break; // 遇到0,结束读取
        }
        numbers.push_back(num);
    }
    
    // 2. 逆序输出阶段
    if (!numbers.empty()) {
        // 先输出最后一个元素(即倒序的第一个)
        cout << numbers.back();
        // 从倒数第二个元素开始往前遍历
        for (int i = numbers.size() - 2; i >= 0; --i) {
            cout << " " << numbers[i];
        }
    }
    cout << endl;
    
    return 0;
}
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> numbers = new ArrayList<>();
        
        // 1. 读取数据阶段
        while (sc.hasNextInt()) {
            int num = sc.nextInt();
            if (num == 0) {
                break;
            }
            numbers.add(num);
        }
        
        // 2. 逆序输出阶段
        if (!numbers.isEmpty()) {
            // 可以直接使用Collections工具类反转列表
            Collections.reverse(numbers);
            
            // 输出第一个数
            System.out.print(numbers.get(0));
            // 从第二个数开始,先打印空格再打印数
            for (int i = 1; i < numbers.size(); i++) {
                System.out.print(" " + numbers.get(i));
            }
        }
        System.out.println();
    }
}
# 1. 读取所有数字直到0
# input().split() 会读取整行并按空格分割成字符串列表
all_inputs = input().split()

# 找到 '0' 的位置,并只保留它之前的部分
# 将这些字符串转换为整数
stop_index = all_inputs.index('0')
numbers = [int(x) for x in all_inputs[:stop_index]]

# 2. Pythonic 的逆序和输出
# numbers.reverse() 会原地反转列表
numbers.reverse()

# 使用 * 操作符解包列表,sep=' ' 指定分隔符
print(*numbers)

算法及复杂度

  • 算法:使用动态数组缓存输入,然后逆序遍历输出。
  • 时间复杂度:,其中 N 是输入的整数个数(不包括0)。整个过程包括一次遍历读取()和一次遍历输出()。
  • 空间复杂度:,因为我们需要一个数组来存储所有 N 个输入的整数。