网易有道晚上笔试题交流

#include <iostream> #include <vector> #include <deque> #include <queue> using namespace std; // 2 1 3 // 1 3 2,输出1 // 3 2 // 2 3，输出2 // 3 // 3，输出3 // 逆向过程： // 3 // 3 // 2 3，把2插到队头 // 3 2，把队尾3插到队头 // 1 3 2，把1插到队头 // 2 1 3，把队尾2插到队头 // 通过观察就是： // k从n~1，依次进行：把k插到队头，把队尾元素插到队头 //得到顺序序列的过程是： //1、队头pop出来，push进队尾 //2、队头pop出来，打印结果 //举例： //2 1 3，输入 //1 3 2，队头2pop出来插入队尾 //打印1，队头1pop出来，打印1 //3 2 //2 3，队头3pop出来插入队尾 //打印2，队头2pop出来，打印2 //3 //3，队头3pop出来插入队尾 //打印3，队头3pop出来，打印3 //队列为空，处理完毕 //逆向过程：从n~1依次做如下处理 //1、push元素进队头 //2、队尾元素pop出来，push进队头 //举例： //3，push3进队头 //3，队尾3pop出来，push3进队头 //23，push2进队头 //32，队尾3pop出来，push3进队头 //132，push1进队头 //213，队尾2pop出来，push2进队头 //处理完毕 int main() { int t; cin >> t; // queue<int> num; // while (t--) // { // int temp; // cin >> temp; // num.push(temp); // } while (t--) { // while (!num.empty()) // { // int n; // n = num.front(); // num.pop(); int n; cin >> n; deque<int> q; for (int i = n; i > 0; i--) { q.push_front(i); int x = q.back(); q.pop_back(); q.push_front(x); } for (int i = 0; i < n - 1; i++) { cout << q[i] << " "; } cout << q[n - 1]; cout << endl; // } } } 被输入输出搞死，一直说没有通过，修改了好多次输入输出

有没有知道选择题怎么复习啊。。每次笔试，选择题感觉都没见过，完全不像是课本上的。。

构造原始队列，有点类似于一堆人报数，每次偶数的人出列，求最后出列顺序。 可以直接利用他给的队列那部分代码，假设队列里是1，2，。。。n，按它那样输出x，输出的x其实就对应的位置，比如第一次输出位置2，则位置2对应的就是数字1，接着输出位置4，则位置4对应的就是数字2.。。直到队列为空。 洗牌就是每次把数组前半部分和后半部分混合，1-n映射到 2*i-1, 2*i的位置放 n+1到2*n 不知道是oj的问题还是代码确实有问题，交上去一直对答案不对。。测试样例都过了啊。。顺便吐槽第一题测试样例原来都给错了，后来有道自己更正了。。 矩形那题同求解。。。

构造原始队列： import java.util.*; public class Main { public static void main(String args[]) { Scanner cin = new Scanner(System.in); int n; while (cin.hasNextInt()) { n = cin.nextInt(); while(n-- > 0) { int m = 0; m = cin.nextInt(); Deque<Integer> deque = new ArrayDeque<Integer>(); Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int i = 0;i < m;i++) { deque.add(i); } int i = 1; while(deque.isEmpty() == false) { int x = deque.pollFirst(); deque.add(x); x = deque.pollFirst(); map.put(x, i++); } for(i = 0;i < m;i++) { if(i > 0) { System.out.print(" "); } System.out.print(map.get(i)); } System.out.println(""); } } } }

所有测试数据均未输出正确结果！ 大家有这种情况么？？？？？

#include<stdio.h> #include<iostream> #include<vector> using namespace std; //洗牌 vector<int> xipai(int n,int k,vector<int> data){ int number = 2*n; for(int j=0;j<k;++j){ vector<int> copy(number); for(int i=1;i<=n;++i){ copy[2*i-2] = data[i-1]; copy[2*i-1] = data[i+n-1]; } data.assign(copy.begin(),copy.end()); } return data; } int main(){ int m; cin>>m; vector<vector <int>> printdata; while(m-->0){ vector<int> temp2; int n,k; cin>>n>>k; vector<int> temp(2*n); for(int j=0;j<2*n;++j){ cin>>temp[j]; } temp2 = xipai(n,k,temp); printdata.push_back(temp2); } for(int i=0;i<printdata.size();++i){ for(int j=0;j<printdata[i].size();++j){ cout<<printdata[i][j]<<" "; } cout<<endl; } return 0; }

#include <iostream> #include<stdio.h> #include<vector> #include<queue> #include<algorithm> using namespace std; //构造原始序列 vector<int> generatequeue(int length){ vector<int> afterlist(length); vector<int> beforelist(length); std::queue<int> queuelist; for(int i=1;i<=length;++i){ queuelist.push(i); } int cnt = 0; while(!queuelist.empty()){ int x = queuelist.front(); queuelist.pop(); queuelist.push(x); x = queuelist.front(); afterlist[cnt] = x; queuelist.pop(); cnt++; } for(int i=1;i<=length;++i){ beforelist[afterlist[i-1]-1] = i; } return beforelist; } int main() { int T; cin>>T; vector<vector <int>> printdata; while(T--){ int n; cin>>n; vector<int> temp = generatequeue(n); printdata.push_back(temp); } for(int i=0;i<printdata.size();++i){ for(int j=0;j<printdata[i].size();++j){ cout<<printdata[i][j]<<" "; } cout<<endl; } return 0; }

#include <iostream> #include <vector> #include <algorithm> #include <deque> using namespace std; void play(vector<int>& card) { const size_t N = card.size(); vector<int> cardO = card; int idx = 0; for (int i = 0; i < N / 2; i++) { card[idx++] = cardO[i]; card[idx++] = cardO[i + N / 2]; } } int main() { int nTest; cin >> nTest; while (nTest--) { int n, k; cin >> n >> k; vector<int> card(2 * n); for (int i = 0; i < 2 * n; i++) cin >> card[i]; for (int i = 0; i < k; i++) play(card); for (int i = 0; i < card.size() - 1; i++) cout << card[i] << " "; cout << card[2 * n - 1]; cout << endl; } }

有人有原题截图吗？

构造队列题： 我不知道自己的为啥输出有问题；求教各位牛友。。 import java.util.Collection; import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args) {     Scanner scan=new Scanner(System.in);     LinkedList<Integer> p=new LinkedList<Integer>();     while(scan.hasNext())     {         int x=scan.nextInt();         int[] z=new int[x];         for(int ii=0;ii<x;ii++)         {         z[ii]=scan.nextInt();}         for(int o=0;o<z.length;o++){             p.add(z[o]);         if(z[o]==1)             System.out.print(z[o]);         else         {int pp=z[o]--;             p.addFirst(pp);         while(z[o]!=0)         {             z[o]--;             int t=p.getLast();             p.removeLast();             p.addFirst(t);             p.addFirst(z[o]);         }         Iterator<Integer> itertor=p.iterator();         int i=0;         while(itertor.hasNext())         {             if(i>=1)                 System.out.print(" ");             else             System.out.print(itertor.next());             i++;         }}     }} } }

矩形暴力解法，测试用例过了，最后没来得及提交。 #include <iostream> #include <set> #include <vector> using namespace std; struct Line{ int x1, x2, y1, y2; }; // 判断是否水平平行线段 bool is_hor(const Line &l){ return l.y1 == l.y2; } struct LineComp{ bool operator()(const Line &l1, const Line &l2) const{ if(l1.y1 == l2.y1) { return l1.x1 < l2.x2; } else{ return l1.y1 < l2.y2; }; } }; int main () { int n; cin >> n; set<Line, LineComp> vertical; set<Line, LineComp> ho; for(int i=0; i<n; i++){ int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; Line cur_line = {x1, x2, y1, y2}; if(is_hor(cur_line)){ ho.insert(cur_line); } else{ vertical.insert(cur_line); } } int min_x1, min_y1, min_x2, min_y2; for(auto it=ho.begin(); it!=ho.end(); ++it){ auto it2 = it; it2 ++; while(it2 != ho.end()){ if(it->x1 == it2->x1 && it->x2 == it2->x2){ int tmp_x1 = it->x1, tmp_x2 = it->x2; int tmp_y1 = (it->y1) < (it2->y1) ? (it->y1) : (it2->y1); int tmp_y2 = (it->y1) > (it2->y1) ? (it->y1) : (it2->y1); Line tmp_1 = {tmp_x1, tmp_x1, tmp_y1, tmp_y2}; Line tmp_2 = {tmp_x2, tmp_x2, tmp_y1, tmp_y2}; if(vertical.find(tmp_1) != vertical.end() && vertical.find(tmp_2) != vertical.end()){ cout << tmp_x1 << " " << tmp_y1 << " " << tmp_x2 << " " << tmp_y2 << endl; return 0; } } it2 ++; } } return 0; }

#include <stdio.h> long card[201]; long tcard[201]; int main() {     int t;     scanf("%d", &t);     while (t--) {         int n, k;         scanf("%d%d", &n, &k);         int i, j;         for (i = 0; i < 2*n; ++i) {             scanf("%ld", &card[i]);         }         for (i = 0; i < 2*n; ++i) {             int p = i;             for (j = 0; j < k; ++j) {                 if (p < n) {                     p = p * 2;                 } else {                     p = (p - n) * 2 + 1;                 }             }             tcard[p] = card[i];         }         for (i = 0; i < 2*n; ++i) {             printf("%ld%c", tcard[i], i == 2*n - 1 ? '\n':' ');         }     }     return 0; }

洗牌的题是用的递归吗？构造队列的题好像是约瑟夫环的变种。不过，都没做出来(。﹏。*)

#include "iostream" using namespace std; void washcard( int a[], int length) {     int n=length/ 2 ;     int tmp[ 201 ];          for ( int i= 1 ; i<= 2 *n; ++i) {         tmp[i]=a[i];     }          for ( int i= 0 ; i<n; ++i) {         a[ 2 *n- 2 *i]=tmp[ 2 *n-i];         a[ 2 *n- 2 *i- 1 ]=tmp[n-i];     }      } int main() { int T; int n,k;     int a[ 201 ];     cin>>T; while (T--)     {         cin>>n>>k;         for ( int i= 1 ;i<= 2 *n;++i)             cin>>a[i];                  while (k--)             washcard(a, 2 *n);                           cout<<a[ 1 ];         for ( int i= 2 ; i<= 2 *n; ++i) {             cout<< ' ' <<a[i];         }         cout<<endl;     }          return 0 ; }

我一直以为不能用本地IDE,没仔细看要求。

提交后半天都看不到结果，估计编程题全跪……

n = raw_input() for i in range(int(n)): input = raw_input().split() num = [int(x) for x in raw_input().split()] n = int(input[0]) k = int(input[1]) res = [x for x in num] while k != 0: k = k - 1 res[0] = num[0] res[-1] = num[-1] step = 1 f = 1 while step != n: res[f] = num[n + step - 1] res[f+1] = num[step] f += 2 step += 1 num = [x for x in res] for x in res: print x, print 求教，这个代码在我本地可以运行样例 3 3 1 1 2 3 4 5 6 3 2 1 2 3 4 5 6 2 2 1 1 1 1 可以输出运行结果 1 4 2 5 3 6 1 5 4 3 2 6 1 1 1 1 但是提交就提示全错 请问是不是我输入输出的问题？

洗牌和队列的一次通过。。矩形搞了一个多小时　过了ｃａｓｅ。然后交上去全错。

我的三道题目均是：所有测试数据均未输出正确结果。。。

2、洗牌 3、构造原始队列 这两个都是模拟，矩形的没有思路