题目链接
题目描述
探险家发现了一串以数字 0
作为结束标志的整数序列。为了触发机关,需要将这串数字(不含结束标志0
)倒序读取。
输入描述:
在一行内输入若干非负整数,以 0
作为结束标志,整数之间用空格分隔。
输出描述:
在一行内按空格分隔输出倒序后的整数序列,不包含结束标志 0
。
解题思路
本题的核心要求是将一个未知长度的序列逆序输出。由于我们必须先读取完所有数字,才能知道最后一个数字是什么(也就是我们第一个要输出的数字),所以我们无法在读取的同时进行输出。
这就要求我们使用一种数据结构,先把所有有效的数字(即 0
之前的所有数字)按顺序存储起来。一个可以动态调整大小的数组(或列表)是完成这个任务的完美工具。
算法可以分为两个清晰的阶段:
-
数据读取与存储阶段:
- 创建一个动态数组(在 C++ 中是
std::vector
,在 Java 中是ArrayList
,在 Python 中是list
)。 - 循环读取输入的整数。对于每个读到的数:
- 检查它是否是结束标志
0
。 - 如果是
0
,则停止读取,跳出循环。 - 如果不是
0
,则将其添加到动态数组的末尾。
- 检查它是否是结束标志
- 当循环结束后,我们的数组中就按原始顺序保存了所有需要处理的数字。
- 创建一个动态数组(在 C++ 中是
-
逆序输出阶段:
- 现在,我们需要从后往前遍历我们存储好的数组。
- 一个标准的
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
个输入的整数。