首页 > 试题广场 >

操作序列

[编程题]操作序列
  • 热度指数:332 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小易有一个长度为n的整数序列,a_1,...,a_n。然后考虑在一个空序列b上进行n次以下操作:
1、将a_i放入b序列的末尾
2、逆置b序列
小易需要你计算输出操作n次之后的b序列。

输入描述:
输入包括两行,第一行包括一个整数n(2 ≤ n ≤ 2*10^5),即序列的长度。
第二行包括n个整数a_i(1 ≤ a_i ≤ 10^9),即序列a中的每个整数,以空格分割。


输出描述:
在一行中输出操作n次之后的b序列,以空格分割,行末无空格。
示例1

输入

4
1 2 3 4

输出

4 2 1 3
//不知道楼上整链表干啥
#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<int> a;
    for(int i = 0; i<n; i++) {
        int temp;
        cin>>temp;
        a.push_back(temp);
    };
    int i;
    for(i=n-1;i>=0;i-=2) {
        cout<<a[i]<<' ';
    }
    if(n%2 == 0)   for(int i = 0; i<n; i+=2)    cout<<a[i]<<' ';
    else for(int i = 1; i<n;i+=2)    cout<<a[i]<<' ';
    //cin>>n;
    return 0;
}

发表于 2020-04-24 09:36:43 回复(0)
反转其实等价于插入的位置从前面换成后面或者从后面换成前面,最后读取的顺序是最后一次插入的位置往反方向读取。因此只要用链表解决即可。
import java.util.Scanner;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        LinkedList<Integer> list = new LinkedList<>();
        boolean left = false;
        for (int i = 0; i < n; i++) {
            if (left) { list.addFirst(scanner.nextInt()); }
            else { list.addLast(scanner.nextInt()); }
            left = !left;
        }
        if (!left) {
            for (Integer i : list) {
                System.out.print(i + " ");
            }
        } else {
            while (!list.isEmpty()) {
                System.out.print(list.removeLast() + " ");
            }
        }
    }
}

发表于 2020-02-17 22:44:25 回复(0)
双端队列
#include<iostream>
#include<deque>
using namespace std;
int main(){
    int n;
    cin>>n;
    deque<int> a;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(i%2==0)
            a.push_back(x);
        else
            a.push_front(x);
    }
    if(n%2==0){
        while(!a.empty()){
            cout<<a.front()<<" ";
            a.pop_front();
        }
        cout<<endl;
    }else{
        while(!a.empty()){
            cout<<a.back()<<" ";
            a.pop_back();
        }
        cout<<endl;
    }
    return 0;
}

发表于 2022-09-17 15:48:01 回复(0)
根据观察可得,假设输入1,2,3....,n,最终输出为倒序遍历,n插入第一位,n-1插入最后一位,n-2插入第二位,n-3插入倒数第二位....
#include <iostream>
#include <vector>
#include <string>
using namespace std;

void reverseArr(vector<int>& arr) {
	 int size = arr.size();
	 vector<int> res(size, 0);
	 int head = 0;
	 int tail = size - 1;
	 bool isHead = true;
	 for (int i = tail; i >= 0; i--) {
		 int val = arr[i];
		 if (isHead) {
			 res[head] = val;
			 head++;
		 }
		 else {
			 res[tail] = val;
			 tail--;
		 }
		 isHead ^= 1;
	 }

	 for (int i = 0; i < size; i++) {
		 cout << res[i];
		 if (i != size - 1) {
			 cout << " ";
		 }
	 }

	 cout << endl;

	 return;
 }

 vector<string> split(string str, string pattern)
 {
	 string::size_type pos;
	 vector<string> result;

	 str += pattern;
	 int size = str.size();

	 for (int i = 0; i<size; i++) {
		 pos = str.find(pattern, i);
		 if (pos<size) {
			 std::string s = str.substr(i, pos - i);
			 result.push_back(s);
			 i = pos + pattern.size() - 1;
		 }
	 }
	 return result;
 }

 int main()
 {
	 string s;
	 getline(cin, s);
	 getline(cin, s);
	 vector<string> tmp = split(s, " ");
	 vector<int> input;
	 for (int i = 0; i < tmp.size(); i++) {
		 input.push_back(atoi(tmp[i].c_str()));
	 }
	 reverseArr(input);
	 return 0;
 }



发表于 2020-02-17 10:36:56 回复(0)