链接：https://www.nowcoder.com/ta/hust-kaoyan
这里不做详细说明了，可以练练手，代码有的写的并不一定是最优解，仅供参考
矩阵转置
/*** 题目描述 输入一个N*N的矩阵，将其转置后输出。要求：不得使用任何其他数组(就地逆置)。 输入描述: 输入的第一行包括一个整数N,(1<=N<=100)，代表矩阵的维数。 接下来的N行每行有N个整数，分别代表矩阵的元素。 输出描述: 可能有多组测试数据，对于每组数据，将输入的矩阵转置后输出。 示例1 输入 3 1 2 3 4 5 6 7 8 9 输出 1 4 7 2 5 8 3 6 9 ***/ #include<cstdio> #include<iostream> using namespace std; int main() { int ant[105][105]; int n; while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { scanf("%d",&ant[i][j]); } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { printf("%d",ant[j][i]); if(j+1 == n) printf("\n"); else printf(" "); } } } return 0; }
统计单词
/*** 题目描述 编一个程序，读入用户输入的，以“.”结尾的一行文字，统计一共有多少个单词，并分别输出每个单词含有多少个字符。 （凡是以一个或多个空格隔开的部分就为一个单词） 输入描述: 输入包括1行字符串，以“.”结束，字符串中包含多个单词，单词之间以一个或多个空格隔开。 输出描述: 可能有多组测试数据，对于每组数据， 输出字符串中每个单词包含的字母的个数。 示例1 输入 hello how are you. 输出 5 3 3 3 ****/ #include<cstdio> #include<cstring> #include<string> #include<iostream> using namespace std; int main() { char str[1000007]; while(gets(str)) { int len = strlen(str); int cnt = 0; if (str[len-1]!='.') continue; for(int i=0;i<len;i++) { if (str[i]=='.') { if (cnt > 0) printf("%d",cnt); printf("\n"); break; } if (str[i]==' ') { if (cnt > 0) printf("%d ",cnt); cnt=0; } else cnt++; } } return 0; }
IP地址
/*** 题目描述 输入一个ip地址串，判断是否合法。 输入描述: 输入的第一行包括一个整数n(1<=n<=500)，代表下面会出现的IP地址的个数。 接下来的n行每行有一个IP地址，IP地址的形式为a.b.c.d，其中a、b、c、d都是整数。 输出描述: 可能有多组测试数据，对于每组数据，如果IP地址合法则输出"Yes!”，否则输出"No!”。 合法的IP地址为： a、b、c、d都是0-255的整数。 示例1 输入 2 255.255.255.255 512.12.2.3 输出 Yes! No! ***/ #include<cstdio> #include<cstring> #include<string> #include<iostream> using namespace std; int main() { int n; scanf("%d",&n); while(n--) { char str[25]; scanf("%s",str); //cout<<"str = "<<str<<endl; int len = strlen(str); //cout<<"len = "<<len<<endl; int ans = 0; bool bo = true; for(int i=0;i<len;i++) { if(str[i]=='.') { //cout<<ans<<endl; if(ans<0 or ans>255){bo = false; break;} ans = 0; } else if(str[i] >= '0' and str[i] <= '9') { ans = ans * 10 + str[i] - '0'; } } if(bo and (ans<0 or ans>255)) bo = false; if (bo) printf("Yes!\n"); else printf("No!\n"); } } /* #include <cstdio> int main() { int ip[4]; int n; while (scanf("%d", &n) != EOF) { for (int i = 0; i < n; i++) { scanf("%d.%d.%d.%d", &ip[0], &ip[1], &ip[2], &ip[3]); bool flag = true; for (int j = 0; j < 4; j++) { if (ip[j] < 0 || ip[j] > 255) { flag = false; break; } } if (flag) printf("Yes!\n"); else printf("No!\n"); } } return 0; } */
二叉排序树
/** 题目描述 二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树： 1. 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值； 2. 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值； 3. 左、右子树本身也是一颗二叉排序树。 现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中， 每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。 输入描述: 输入包含多组测试数据，每组测试数据两行。 第一行，一个数字N（N<=100），表示待插入的节点数。 第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过10^8。 输出描述: 输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值。 示例1 输入 5 2 5 1 3 4 输出 -1 2 2 5 3 **/ #include<cstdio> #include<cstring> #include<iostream> #include<stdlib.h> using namespace std; struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; void createTree(TreeNode* &node,int num,int parent) { if(node == NULL) { printf("%d\n",parent); node = new TreeNode(num); } else { if(num > node->val) { createTree(node->left,num,node->val); } else { createTree(node->right,num,node->val); } } } void destory(TreeNode* &node) { if(node) { destory(node->left); destory(node->right); delete node; } } int main() { int n,num; while(scanf("%d",&n)!=EOF) { TreeNode *root = NULL;//初始化(否则会变成悬垂指针) for(int i=0;i<n;i++) { scanf("%d",&num); //cout<<num<<endl; createTree(root,num,-1); } destory(root); } return 0; }
字符串连接
/** 题目描述 不借用任何字符串库函数实现无冗余地接受两个字符串，然后把它们无冗余的连接起来。 输入描述: 每一行包括两个字符串，长度不超过100。 输出描述: 可能有多组测试数据，对于每组数据， 不借用任何字符串库函数实现无冗余地接受两个字符串，然后把它们无冗余的连接起来。 输出连接后的字符串。 示例1 输入 abc def 输出 abcdef **/ //无冗余...没理解 #include<cstdio> #include<cstring> #include<string> #include<iostream> using namespace std; int main() { string str1,str2; while(cin>>str1>>str2) cout<<str1<<str2<<endl; return 0; }
a+b
写了一个大数模板，大数加法，大数减法，大数乘法和大数除法，这里是写好后代入的。虽然看起来有点麻烦，但是模板是可以重复利用的。哈~完善之后再发详细的。
#include <cstdio> #include <iostream> #include <string> #include <cstring> #include <vector> #include <cmath> #include <algorithm> using namespace std; #define System 1000000 // class BigNumber{ public: string x,y; int op; //运算 1:+; -1:-; 2:*; -2:/ int posx,posy; int oop;//符号位 1: + ; -1: - ; int opx,opy;// 先取x,y的符号 int dim; //进位 BigNumber(string xx,string yy): x(xx), y(yy), op(1), posx(0),posy(0),oop(1),opx(1),opy(1),dim(0) {} BigNumber(string xx,string yy,int ope): x(xx), y(yy), op(ope), posx(0),posy(0),oop(1),opx(1),opy(1),dim(0) {} vector<int> res; vector<int> remainder;//余数 string subX,subY; bool SwapXY() { if(x.size()>0 and y.size()>0)//x,y 非空 { //cout<<"S: operate: ans = "<<x<<" ("<<op<<") "<<y<<" ="<<endl; if(x[0]=='-') {opx = -1; posx = 1;} if(y[0]=='-') {opy = -1; posy = 1;if(op == 1 || op == -1){ op = -1*op; opy = -1*opy;} }//2 - (-16) == 2 + (+16) || 2 + (-16) == 2 - (+16) subX = x.substr(posx); subY = y.substr(posy); int lenX = x.length()-posx; int lenY = y.length()-posy; //cout<<"F: subX="<<subX<<" ,lenX="<<lenX<<" ; subY="<<subY<<" ,lenY="<<lenY<<endl; //cout<<"F: operate: ans = "<<"("<<opx<<")*"<<subX<<" ("<<op<<") "<<"("<<opy<<")*"<<subY<<" ="<<endl; if (op == 1) // + {// -x + y || x + y if(lenX < lenY || (lenX == lenY && subX < subY)) // |x| < |y| { oop = 1; if (opx < 0) op = -1; //-x + y = y - x subX.swap(subY); } else if(lenX == lenY && subX == subY) // |x| == |y| { oop = 1; if (opx < 0) // y - x = 0 { res.push_back(0); return false; } } else //|x| > |y| { if ( opx < 0 ) // -x + y = -(x-y) { oop = -1; op = -1; } } } else if(op == -1) // - {// -x - y || x - y if(lenX < lenY || (lenX == lenY && subX < subY)) // |x| < |y| { oop = -1; // x - y = - (y - x) || -x - y = -(y+x) if (opx < 0) op = 1; subX.swap(subY); } else if(lenX == lenY && subX == subY) // |x| == |-y| { if (opx > 0) { oop = 1; res.push_back(0); // x - y = 0 return false; } else // -x -y = -(x+y) ; -5 - 5 = -(5+5) = -10 { oop = -1; op = 1; } } else //|x| > |y| { if(opx < 0) // -x -y = -(x+y) ; -10 - 5 = -(10+5) = -15 { oop = -1; op = 1; } } } else if(op == 2 || op == -2) { if(opx * opy < 0) { oop = -1;} //一正一负 else { oop = 1;}//两正数,两负数 if(op == -2 && lenX == lenY && subX == subY) // |x| == |-y| { res.push_back(1); // x - y = 0 return false; } } //cout<<"L: subX="<<subX<<" , subY="<<subY<<" ; X="<<x<<" , Y="<<y<<endl; return true; } else return false; } void operate() { if (SwapXY())//|x|>|y| { //计算... //cout<<"operate: ans = ("<<oop<<") ("<<subX<<" ("<<op<<") "<<subY<<") ="<<endl; if(op == 1) Plus(subX,subY); else if(op == -1) Subtract(subX,subY); else if(op == 2 ) Multiply(subX,subY); else if(op == -2) Divide(subX,subY);// -5/15= 1/3 } } void Plus(string X,string Y) // + { //cout<<"Plus: "<<endl; string::reverse_iterator ritX = X.rbegin(); string::reverse_iterator ritY = Y.rbegin(); for(; ritY < Y.rend(); ritY++,ritX++ ) { int num = *ritX - '0' + *ritY - '0' + dim; //cout<<num<<endl; dim = num / 10; res.push_back(num % 10); } for(;ritX < X.rend(); ritX++) { int num = *ritX - '0' + dim; dim = num / 10; res.push_back(num % 10); } if(dim) res.push_back(dim); while (res.back() == 0)//删前导0 { res.pop_back(); } } void Subtract(string X,string Y) // - { //cout<<"Subtract: "<<endl; string::reverse_iterator ritX = X.rbegin(); string::reverse_iterator ritY = Y.rbegin(); for(; ritY < Y.rend(); ritY++,ritX++ ) { int num = (*ritX - '0' - dim ) - (*ritY - '0') ; //cout<<num<<endl; if(num < 0) {num = (num + 10 ) % 10; dim = 1;}//借位 else dim = 0;//复位 res.push_back(num); } for(;ritX < X.rend(); ritX++) { int num = (*ritX - '0' - dim ) ; //cout<<num<<endl; if(num < 0) {num = (num + 10 ) % 10; dim = 1;}//借位 else dim = 0;//复位 res.push_back(num); } if(dim){res.clear();} //最后还有dim 则 X<Y 需要清表 while (res.back() == 0)//删前导0 { res.pop_back(); } } /**思路：乘法利用加法原则，1.积的位数 = X位数+Y位数 **/ void Multiply(string X,string Y) { //cout<<"Multiply: "<<endl; string::reverse_iterator ritX = X.rbegin(); string::reverse_iterator ritY = Y.rbegin(); //vector<int> arr(X.size()+Y.size()) ;// 位数K = x + y; res.resize(X.size()+Y.size()); //重划定大小 vector<int>::iterator it; for(int i = 0;i < X.size();i++) { for(int j = 0;j < Y.size();j++) { res[i+j] += (*(ritX+i) - '0') * (*(ritY+j) - '0');//从左到右 相乘 相加 } } for(it = res.begin();it < res.end();++it) { *it = (*it) + dim; dim = (*it) / 10; *it = (*it) % 10; } /* int p = 0; for(it = arr.begin();it<arr.end();++it) { cout<<p<<" : "<<*it<<"\t"<<arr[p]<<endl; p++; } */ if(dim){res.clear();} //最后还有dim 需要清表 while (res.back() == 0)//删前导0 { res.pop_back(); } } //大数除法与求余 (整除) -- 辗转相除法 X / Y void Divide(string X,string Y)//输出是正序输出... { int lenX = X.length(); int lenY = Y.length(); string::reverse_iterator ritX = X.rbegin(); string::reverse_iterator ritY = Y.rbegin(); if(lenX < lenY || (lenX == lenY && X < Y)) //余数 ：Y { res.push_back(0); for(;ritY < Y.rend();ritY++) remainder.push_back((*ritY - '0')); } else if(lenX == lenY && X == Y) { res.push_back(1); remainder.push_back(0); } else // 987654321 / 15999 { string sub_X = X.substr(0,lenY); //cout<<"First: sub_X = "<<sub_X<<" ,Y = "<<Y<<endl; string ans(""); if(sub_X > Y) { solveXY(sub_X,Y,0,ans); } else if(sub_X == Y) { res.push_back(1); ans.clear(); } else //sub_X < Y { ans = sub_X; } //cout<<"Second: sub_X = "<<sub_X<<" ,Y = "<<Y<<", ans = "<<ans<<endl; for(int i = lenY;i < lenX;i++) { if(X[i]-'0' > 0) ans.push_back(X[i]); int len = ans.length(); if(len < lenY) { res.push_back(0); continue; } else { if(len == lenY) { if(ans == Y)//151515600 / 15 = 10101040 { res.push_back(1); ans.clear(); } else if(ans < Y) { res.push_back(0); continue; } else //ans > Y { sub_X = ans; ans.clear(); solveXY(sub_X,Y,0,ans); } } else //len > lenY { sub_X = ans; ans.clear(); solveXY(sub_X,Y,0,ans); } } } if(ans == "") remainder.push_back(0); else //余数 { for(int i = 0;i<ans.length();i++) { if(ans[i] - '0' == 0) continue; remainder.push_back(ans[i] - '0'); } } } } //辗转相除法 void solveXY(string X,string &Y,int d,string &ans) //X > Y { //cout<<"Divide_Subtract: "<<X<<" / "<<Y<<" ; d = "<<d<<", ans = "<<ans<<endl; string::reverse_iterator ritX = X.rbegin(); string::reverse_iterator ritY = Y.rbegin(); string rem(""); int dimX = 0; if(dimX){rem.clear();} //最后还有dim 则 X<Y 需要清表 for(; ritY < Y.rend(); ritY++,ritX++ ) { int num = (*ritX - '0' - dimX ) - (*ritY - '0') ; //cout<<num<<endl; if(num < 0) {num = (num + 10 ) % 10; dimX = 1;}//借位 else dimX = 0;//复位 char ch = num + '0'; rem.push_back(ch); } for(;ritX < X.rend(); ritX++) { int num = (*ritX - '0' - dimX ) ; //cout<<num<<endl; if(num < 0) {num = (num + 10 ) % 10; dimX = 1;}//借位 else dimX = 0;//复位 char ch = num + '0'; rem.push_back(ch); } // 删前导0 //string::reverse_iterator ritM = rem.rbegin(); int dy = 0; int sm = rem.length(); for(int i=sm-1;i >= 0;i--) { if(rem[i]-'0' == 0) { dy++; continue; } else break; } rem = rem.substr(0,sm-dy); //cout<<"处理余数 :"; d++; for(int i = rem.length()-1;i >= 0;i--) { //cout<<rem[i]; ans.push_back(rem[i]); } //cout<<endl; int len = ans.length(); int lenY = Y.length(); if(len < lenY || (len == lenY && ans < Y))// 下一次减数小于被减数 { //商存起来 res.push_back(d); // //cout<<"余数要返回 :"<<ans<<endl; return ; } else if(len == lenY && ans == Y) // 下一次减数和被减数相等 { d++; res.push_back(d); ans.clear(); //15999897654 / 15999 = 1000056 return ; } else 下一次减数大于被减数,做下一次减法运算 { X = ans; ans.clear(); solveXY(X,Y,d,ans); } } }; int main() { string str1,str2; while(cin>>str1>>str2) { BigNumber bn(str1,str2); //cout<<bn.x<<endl<<bn.y<<endl<<bn.op<<endl; bn.operate(); //cout<<"-------------"<<endl<<bn.x<<endl<<bn.y<<endl<<bn.op<<endl; //cout<<"result: = "; if(bn.oop<0) cout<<"-"; for (vector<int>::reverse_iterator it = bn.res.rbegin() ; it != bn.res.rend(); ++it) cout<< *it; cout<<endl; } return 0; }
排序
/** 题目描述 对输入的n个数进行排序并输出。 输入描述: 输入的第一行包括一个整数n(1<=n<=100)。 接下来的一行包括n个整数。 输出描述: 可能有多组测试数据，对于每组数据，将排序后的n个整数输出，每个数后面都有一个空格。 每组测试数据的结果占一行。 示例1 输入 4 1 4 3 2 输出 1 2 3 4 **/ #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<vector> #include <algorithm> using namespace std; #define MAXN 105 int main() { int N; while(scanf("%d",&N) != EOF) { vector<int> arr; for(int i=0;i<N;i++) { int num; scanf("%d",&num); arr.push_back(num); } vector<int>::iterator iter; sort(arr.begin(),arr.end()); for(iter = arr.begin();iter < arr.end();iter++) { cout<<*iter<<" "; } cout<<endl; } return 0; }
有空再补一个快排手写的。
特殊排序
/** 题目描述 输入一系列整数，将其中最大的数挑出，并将剩下的数进行排序。 输入描述: 输入第一行包括1个整数N，1<=N<=1000，代表输入数据的个数。 接下来的一行有N个整数。 输出描述: 可能有多组测试数据，对于每组数据， 第一行输出一个整数，代表N个整数中的最大值，并将此值从数组中去除，将剩下的数进行排序。 第二行将排序的结果输出。 示例1 输入 4 1 3 4 2 输出 4 1 2 3 **/ #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<vector> #include <algorithm> using namespace std; #define MAXN 105 int main() { int N; while(scanf("%d",&N) != EOF) { vector<int> arr; for(int i=0;i<N;i++) { int num; scanf("%d",&num); arr.push_back(num); } if(N == 1) { cout << arr[0] << endl << -1 << endl; continue; } vector<int>::iterator iter = arr.end(); sort(arr.begin(),arr.end()); cout<<*(iter-1)<<endl; for(iter = arr.begin();iter < arr.end()-2;iter++) { cout<<*iter<<" "; } cout<<*iter<<endl; } return 0; }
二叉树遍历
/*** 题目描述 二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树； 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。 输入描述: 两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。 输出描述: 输入样例可能有多组，对于每组测试样例， 输出一行，为后序遍历的字符串。 示例1 输入 ABC BAC FDXEAG XDEFAG 输出 BCA XEDGAF **/ // http://blog.csdn.net/u010579068/article/details/48416491 #include<cstdio> #include<cstring> #include<string> #include<iostream> #include<algorithm> using namespace std; struct TreeNode{ TreeNode *left; TreeNode *right; char val; TreeNode(char x): val(x), left(NULL), right(NULL) { } }*root; string preTree,midTree; TreeNode *Create(string::iterator pTree, string::iterator mTree,int len) { TreeNode *node; for(int i=0;i<len;i++) { //前 FDXEAG if(*(mTree+i) == *pTree) // 定根 中 XDEFAG { node = new TreeNode(*pTree); //根 F node->left = Create(pTree+1,mTree,i); //左 XDE node->right = Create(pTree+i+1,mTree+i+1,len-i-1); //右 AG return node; } } return NULL; //退出条件 } void PrintTree(TreeNode *head) { if(head == NULL) return ; PrintTree(head->left); PrintTree(head->right); if(head == root)//最后一个 cout<<head->val<<endl; else cout<<head->val; } void destory(TreeNode* &node) { if(node) { destory(node->left); destory(node->right); delete(node); } } int main() { while(cin>>preTree>>midTree) { //前序定根,中序定左右 if(preTree.size() == midTree.size()) { root = Create(preTree.begin(),midTree.begin(),midTree.size()); PrintTree(root); destory(root); } } return 0; }
奇偶校验
/*** 题目描述 输入一个字符串，然后对每个字符进行奇校验，最后输出校验后的二进制数(如'3'，输出：10110011)。 输入描述: 输入包括一个字符串，字符串长度不超过100。 输出描述: 可能有多组测试数据，对于每组数据， 对于字符串中的每一个字符，输出按题目进行奇偶校验后的数，每个字符校验的结果占一行。 示例1 输入 3 3a 输出 10110011 10110011 01100001 **/ /**思想就是：转为2进制后1的个数为偶数最高位要补1，注意ascii码最大就是127*/ #include<cstdio> #include<string> #include<cstring> #include<bitset> #include<iostream> using namespace std; int main() { char c; bitset<8> bit; while(cin>>c) { if(c == ' ' || c == '\n') continue; bit = c;//转ASCII码, //printf("%d\n",c); if((bit.count()&1) == 0) bit.set(7);//偶数位,最高位变1 cout<<bit<<endl; } return 0; }
最大的两个数
/** 题目描述 输入一个四行五列的矩阵，找出每列最大的两个数。 输入描述: 输入第一行包括一个整数n(1<=n<=1000)，接下来有n个四行每行包括五个整数。代表一个四行五列的矩阵，矩阵元素全部是整数。 输出描述: 可能有多组测试数据，对于每组数据，按照样例输出的格式将每列最大的两个数输出，如果最大的两个数中的一个数在这一列中有多个相同的值，则行值取行值小的那一个。 输出时要保留原矩阵的行列顺序，即在原矩阵中行值小的，在输出矩阵中的行值依然小。 示例1 输入 2 1 2 4 9 8 -1 4 9 8 8 12 9 8 7 0 7 8 9 7 0 1 8 4 9 8 -1 4 9 8 8 12 9 8 7 0 7 8 9 7 0 输出 12 9 9 9 8 7 8 9 8 8 12 8 9 9 8 7 9 9 8 8 **/ /**解：最关键是每列最大两个数的行顺序不变,还有个坑最后换行前有空格**/ #include<cstdio> #include<stack> #include<iostream> using namespace std; #define row 4 #define column 5 void solve(int &x1,int &x2,int x) { if(x1 > x2) { if(x >= x1) x2 = x; else if(x > x2 && x < x1) x2 = x; } else if(x1 == x2) { if(x > x1) x2 = x; } else // x1 < x2 { if(x >= x2) {x1 = x2; x2 = x;} else if(x > x1 && x < x2) {x1 = x2; x2 = x;} } } int main() { int n; while(cin>>n) { for(int t=0;t<n;t++) { int ans[row][column]; int res[2][column]; stack<int> S; for(int i=0;i<row;i++) { for(int j=0;j<column;j++) { cin>>ans[i][j]; if(i<2) res[i][j] = ans[i][j]; } } for(int j=0;j<column;j++) { int r1 = res[0][j]; int r2 = res[1][j]; for(int i=2;i<row;i++) { solve(r1,r2,ans[i][j]); } res[0][j] = r1; res[1][j] = r2; } for(int i=0;i<2;i++) { int j=0; for(;j<column;j++) { cout<<res[i][j]<<" "; } cout<<endl; } } } return 0; }
成绩排序
/*** 题目描述 有N个学生的数据，将学生数据按成绩高低排序，如果成绩相同则按姓名字符的字母序排序， 如果姓名的字母序也相同则按照学生的年龄排序，并输出N个学生排序后的信息。 输入描述: 测试数据有多组，每组输入第一行有一个整数N（N<=1000），接下来的N行包括N个学生的数据。 每个学生的数据包括姓名（长度不超过100的字符串）、年龄（整形数）、成绩（小于等于100的正数）。 输出描述: 将学生信息按成绩进行排序，成绩相同的则按姓名的字母序进行排序。 然后输出学生信息，按照如下格式： 姓名 年龄 成绩 学生姓名的字母序区分字母的大小写，如A要比a的字母序靠前(因为A的ASC码比a的ASC码要小)。 示例1 输入 3 abc 20 99 bcd 19 97 bed 20 97 输出 bcd 19 97 bed 20 97 abc 20 99 **/ /**解：这里没有明确最后按年龄的排序。默认从小到大 **/ #include<cstdio> #include<iostream> #include<cstring> #include<string> #include<vector> #include<algorithm> using namespace std; struct Info{ string name; int age; int grade; Info(string N,int x,int y): name(N), age(x),grade(y) { } }; bool comp (Info A,Info B) { if(A.grade == B.grade) { if(A.name == B.name) { return A.age < B.age; } return A.name < B.name; } return A.grade < B.grade; } int main() { int n; while(scanf("%d",&n)!=EOF) { vector<Info> arr; string str; int a,g; for(int i=0;i<n;i++) { cin>>str>>a>>g; Info in(str,a,g); arr.push_back(in); } sort(arr.begin(),arr.end(),comp); for(vector<Info>::iterator iter = arr.begin();iter<arr.end();iter++) { cout<<(*iter).name<<" "<<(*iter).age<<" "<<(*iter).grade<<endl; } } return 0; }
遍历链表
/** 题目描述 建立一个升序链表并遍历输出。 输入描述: 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出描述: 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 示例1 输入 4 3 5 7 9 输出 3 5 7 9 **/ //感觉这题是要考链表的排序吗？O((n+1)n/2) = O(n^2) #include<cstdio> #include<cstring> #include<iostream> #include <climits> using namespace std; struct LNode{ LNode *next; int data; LNode(int x): data(x), next(NULL){ } }; void Insert_LNode(LNode * &head,int num) { LNode *pre = head; LNode *p = pre->next; LNode *L = new LNode(num); //if(p == NULL){ pre->next = L; return ;} while(p) { if(p->data < num) { pre = pre -> next; p = p -> next; } else break; } //cout<<p->data<<endl; pre -> next = L; pre -> next -> next = p; } void Print_LNode(LNode * head) { while(head) { if(head->next == NULL) cout<<head->data<<endl; else cout<<head->data<<" "; head = head -> next; } } void Clear_LNode(LNode* &node) { if(node) { Clear_LNode(node->next); delete(node); } } int main() { int n; while(scanf("%d",&n)!=EOF) { LNode *root = new LNode(INT_MIN); //#include <climits> int num; for(int i=0;i<n;i++) { scanf("%d",&num); Insert_LNode(root,num); } Print_LNode(root->next); Clear_LNode(root); } return 0; }
守形数
/** 题目描述 守形数是这样一种整数，它的平方的低位部分等于它本身。 比如25的平方是625，低位部分是25，因此25是一个守形数。 编一个程序，判断N是否为守形数。 输入描述: 输入包括1个整数N，2<=N<100。 输出描述: 可能有多组测试数据，对于每组数据， 输出"Yes!”表示N是守形数。 输出"No!”表示N不是守形数。 示例1 输入 25 4 输出 Yes! No! **/ #include<cstdio> #include<cmath> #include<iostream> using namespace std; int main() { int N; while(scanf("%d",&N)!=EOF) { if(N*N0 == N || N*N == N) printf("Yes!\n"); //其实只有5,6,25和76 else printf("No!\n"); } return 0; }
矩阵最大值
/** 题目描述 编写一个程序输入一个mXn的矩阵存储并输出，并且求出每行的最大值和每行的总和。 要求把每行总和放入每行最大值的位置，如果有多个最大值，取下标值最小的那一个作为最大值。 最后将结果矩阵输出。 输入描述: 输入的第一行包括两个整数m和n(1<=m,n<=100)，分别代表矩阵的行和列的维数。 接下来的m行每行有n个数，代表矩阵的元素。 输出描述: 可能有多组测试数据，对于每组数据，输出按题目要求执行后的矩阵。 示例1 输入 3 3 1 1 1 1 1 1 1 1 1 3 3 3 2 3 2 3 2 3 2 3 输出 3 1 1 3 1 1 3 1 1 8 2 3 2 7 2 8 2 3 **/ #include<cstdio> #include<vector> #include<climits> #include<iostream> using namespace std; #define MAXN 105 int main() { int arr[MAXN][MAXN]; int m,n; while(scanf("%d%d",&m,&n)!=EOF) { for(int i=0;i<m;i++) { int pos = 0, sum = 0;; for(int j=0;j<n;j++) { scanf("%d",&arr[i][j]); sum += arr[i][j]; if(arr[i][pos] < arr[i][j]) {pos = j;} } arr[i][pos] = sum; } for(int i=0;i<m;i++) { for(int j=0;j<n-1;j++) { printf("%d ",arr[i][j]); } printf("%d\n",arr[i][n-1]); } } return 0; }
最小年龄的3个职工
/** 题目描述 职工有职工号，姓名，年龄.输入n个职工的信息，找出3个年龄最小的职工打印出来。 输入描述: 输入第一行包括1个整数N，1<=N<=30，代表输入数据的个数。 接下来的N行有N个职工的信息： 包括职工号(整数)， 姓名(字符串，长度不超过10)， 年龄(1<=age<=100)。 输出描述: 可能有多组测试数据，对于每组数据， 输出结果行数为N和3的较小值，分别为年龄最小的职工的信息。 关键字顺序：年龄>工号>姓名，从小到大。 示例1 输入 5 501 Jack 6 102 Nathon 100 599 Lily 79 923 Lucy 15 814 Mickle 65 输出 501 Jack 6 923 Lucy 15 814 Mickle 65 **/ #include<cstdio> #include<string> #include<cstring> #include<vector> #include<iostream> #include<algorithm> using namespace std; struct StaffInfo{ int staffID; string name; int age; StaffInfo(int id,string n,int old): staffID(id), name(n), age(old) { } }; bool comp (StaffInfo A,StaffInfo B) { if(A.age == B.age) { if(A.staffID == B.staffID) { return A.name < B.name; } return A.staffID < B.staffID; } return A.age < B.age; } int main() { int N; while(scanf("%d",&N)!=EOF) { int age,id; string name; vector<StaffInfo> arr; for(int i=0;i<N;i++) { cin>>id>>name>>age; StaffInfo info(id,name,age); arr.push_back(info); } sort(arr.begin(),arr.end(),comp); for(int i=0;i<N && i<3;i++) { printf("%d %s %d\n",arr[i].staffID,arr[i].name.c_str(),arr[i].age); } } return 0; }
对称矩阵
/** 题目描述 输入一个N维矩阵，判断是否对称。 输入描述: 输入第一行包括一个数：N(1<=N<=100)，表示矩阵的维数。 接下来的N行，每行包括N个数，表示N*N矩阵的元素。 输出描述: 可能有多组测试数据，对于每组数据， 输出"Yes!”表示矩阵为对称矩阵。 输出"No!”表示矩阵不是对称矩阵。 示例1 输入 4 16 19 16 6 19 16 14 5 16 14 16 3 6 5 3 16 2 1 2 3 4 输出 Yes! No! **/ //对称矩阵,貌似只要考虑 arr[i][j] == ar[j][i],有时候不能想太多啊.... #include<cstdio> #include<iostream> using namespace std; int main() { int N; //1<=N<=100 while(scanf("%d",&N)!=EOF) { int arr[N][N]; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { scanf("%d",&arr[i][j]); } } bool bo = true; for(int i=0;i<N;i++) { if (bo) { for(int j=i;j<N;j++) { if(arr[i][j] != arr[j][i]) {bo = false; break;} } } else break; } if(bo) printf("Yes!\n"); else printf("No!\n"); } return 0; }
A+B
/**** 给定两个整数A和B，其表示形式是：从个位开始，每三位数用逗号","隔开。 现在请计算A+B的结果，并以正常形式输出。 输入描述: 输入包含多组数据数据，每组数据占一行，由两个整数A和B组成（-10^9 < A,B < 10^9）。 输出描述: 请计算A+B的结果，并以正常形式输出，每组数据占一行。 输入例子: -234,567,890 123,456,789 1,234 2,345,678 输出例子: -111111101 2346912 *******/ #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<math.h> using namespace std; #define LL long long LL changeLL(char (&x)[20]) { int op = 1; //+ int len = strlen(x); LL xi = 0; for(int i=0;i<len;i++) { if (x[i]=='-') {op = 0;continue;} if (x[i]==',') continue; xi = xi * 10 + x[i]-'0'; } if(op == 0) xi = xi*(-1); return xi; } int main() { char a[20]={'\0'},b[20]={'\0'}; while(scanf("%s%s",&a,&b)!=EOF) { printf("%lld\n",changeLL(a)+changeLL(b)); } return 0; }
打印日期
/** 题目描述 给出年分m和一年中的第n天，算出第n天是几月几号。 输入描述: 输入包括两个整数y(1<=y<=3000)，n(1<=n<=366)。 输出描述: 可能有多组测试数据，对于每组数据， 按 yyyy-mm-dd的格式将输入中对应的日期打印出来。 示例1 输入 2000 3 2000 31 2000 40 2000 60 2000 61 2001 60 输出 2000-01-03 2000-01-31 2000-02-09 2000-02-29 2000-03-01 2001-03-01 **/ #include<cstdio> #include<iostream> using namespace std; int monthDay[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; int main() { int year,day; while(scanf("%d%d",&year,&day)!=EOF) { if(year%4==0&&year0!=0 || year@0==0) monthDay[2] = 29; else monthDay[2] = 28; int month = 1; for(;month<13;month++) { if(day <= monthDay[month]) break; day -= monthDay[month]; } printf("d-d-d\n",year,month,day); } return 0; }
二叉树排序
/** 题目描述 输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。 输入描述: 输入第一行包括一个整数n(1<=n<=100)。 接下来的一行包括n个整数。 输出描述: 可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。 每种遍历结果输出一行。每行最后一个数据之后有一个空格。 输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。 示例1 输入 5 1 6 5 9 8 输出 1 6 5 9 8 1 5 6 8 9 5 8 9 6 1 **/ // 题意中有重复元素，但不同输出说明建树时插在同个位置 #include<cstdio> #include<cstring> #include<string> #include<iostream> using namespace std; struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int v): val(v), left(NULL), right(NULL) { } }; void createTree(TreeNode * &p,int num) { if(p==NULL) {p = new TreeNode(num); return;} if(p->val > num) createTree(p->left,num); else if(p->val < num) createTree(p->right,num); else return ; } //前序遍历 :根左右 void PreorderTraversal(TreeNode *p) { if(p==NULL) return; printf("%d ",p->val); PreorderTraversal(p->left); PreorderTraversal(p->right); } //中序遍历 :左根右 void InorderTraversal(TreeNode *p) { if(p==NULL) return; InorderTraversal(p->left); printf("%d ",p->val); InorderTraversal(p->right); } //后序遍历 :左右根 void PostorderTraversal(TreeNode *p) { if(p==NULL) return; PostorderTraversal(p->left); PostorderTraversal(p->right); printf("%d ",p->val); } void destoryTree(TreeNode * &p) { if(p == NULL) return; destoryTree(p->left); destoryTree(p->right); delete p; } void PrintTree(TreeNode * &p) { PreorderTraversal(p); //前序遍历 cout<<endl; InorderTraversal(p); //中序遍历 cout<<endl; PostorderTraversal(p); //后序遍历 cout<<endl; destoryTree(p); //回收 } int main() { int N; //1<=N<=100 while(scanf("%d",&N)!=EOF) { TreeNode *root = NULL; int num; for(int i=0;i<N;i++) { scanf("%d",&num); createTree(root,num); } PrintTree(root); } return 0; }
大整数排序
/** 题目描述 对N个长度最长可达到1000的数进行排序。 输入描述: 输入第一行为一个整数N，(1<=N<=100)。 接下来的N行每行有一个数，数的长度范围为1<=len<=1000。 每个数都是一个正数，并且保证不包含前缀零。 输出描述: 可能有多组测试数据，对于每组数据，将给出的N个数从小到大进行排序，输出排序后的结果，每个数占一行。 示例1 输入 3 11111111111111111111111111111 2222222222222222222222222222222222 33333333 输出 33333333 11111111111111111111111111111 2222222222222222222222222222222222 **/ //不用处理负数和前导0... #include<cstdio> #include<cstring> #include<string> #include<iostream> #include<algorithm> using namespace std; #define MAXN 105 bool comp(string a,string b) { if(a.size() == b.size()) return a < b; return a.size() < b.size(); } int main() { int N; while(cin>>N) { string str[MAXN]; for(int i=0;i<N;i++) { cin>>str[i]; } sort(str,str+N,comp); for(int i=0;i<N;i++) cout<<str[i]<<endl; } return 0; }
N阶楼梯上楼问题
/** 题目描述 N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归） 输入描述: 输入包括一个整数N,(1<=N<90)。 输出描述: 可能有多组测试数据，对于每组数据， 输出当楼梯阶数是N时的上楼方式个数。 示例1 输入 4 输出 5 **/ //打表 #include<cstdio> #include<iostream> using namespace std; #define MAXN 90 long long arr[MAXN]; void init() { arr[1] = 1; arr[2] = 2; for(int i=3;i<MAXN;i++) arr[i] = arr[i-1] + arr[i-2]; } int main() { init(); int N; while(scanf("%d",&N)!=EOF) { if(arr[N]) cout<<arr[N]<<endl; } return 0; }
a+b
/** 题目描述 计算a+b的和 每行包行两个整数a和b 对于每行输入对应输出一行a和b的和 输入 1 5 输出 6 **/ #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<math.h> using namespace std; #define LL long long LL changeLL(char (&x)[20]) { int op = 1; //+ int len = strlen(x); LL xi = 0; for(int i=0;i<len;i++) { if (x[i]=='-') {op = 0;continue;} if (x[i]==',') continue; xi = xi * 10 + x[i]-'0'; } if(op == 0) xi = xi*(-1); return xi; } int main() { char a[20]={'\0'},b[20]={'\0'}; while(scanf("%s%s",&a,&b)!=EOF) { printf("%lld\n",changeLL(a)+changeLL(b)); } return 0; }
回文字符串
/*** 题目描述 给出一个长度不超过1000的字符串，判断它是不是回文(顺读，逆读均相同)的。 输入描述: 输入包括一行字符串，其长度不超过1000。 输出描述: 可能有多组测试数据，对于每组数据，如果是回文字符串则输出"Yes!”，否则输出"No!"。 示例1 输入 hellolleh helloworld 输出 Yes! No! **/ #include<cstdio> #include<cstring> #include<string> #include<iostream> using namespace std; int main() { string str; while(cin>>str) { int str_size = str.size(); if(str_size == 0) continue; if(str_size == 1) printf("Yes!\n"); bool bo = true; for(int i=0,j=str_size-1;i<j;i++,j--) { if (str[i] != str[j]) {bo = false; break;} } if(bo) printf("Yes!\n"); else printf("No!\n"); } return 0; }
找位置
/** 题目描述 对给定的一个字符串，找出有重复的字符，并给出其位置， 如：abcaaAB12ab12 输出：a，1；a，4；a，5；a，10，b，2；b，11，1，8；1，12， 2，9；2，13。 输入描述: 输入包括一个由字母和数字组成的字符串，其长度不超过100。 输出描述: 可能有多组测试数据，对于每组数据， 按照样例输出的格式将字符出现的位置标出。 1、下标从0开始。 2、相同的字母在一行表示出其出现过的位置。 示例1 输入 abcaaAB12ab12 输出 a:0,a:3,a:4,a:9 b:1,b:10 1:7,1:11 2:8,2:12 ***/ //hush or 暴力 #include<vector> #include<cstdio> #include<cstring> #include<string> #include<iostream> #include<map> using namespace std; int main() { string str; while(cin>>str) { vector< vector<int> > vec; vector<char> ch; string::iterator its; int len = str.size(); for(int i=0;i<len;i++) { if(str[i]=='-') continue; int rf = str.rfind(str[i]); if(rf != i)//存在多个 { //cout<<rf<<"---"<<i<<endl; int j=i; ch.push_back(str[i]); vector<int> tmp; while(j<=rf) { //cout<<str[j]<<" ~ "<<str[i]<<endl; if(str[j]==str[rf]) { tmp.push_back(j); str[j] = '-'; } j++; } vec.push_back(tmp); } } vector<char>::iterator itch; vector< vector<int> >::iterator iter; for(itch=ch.begin(),iter=vec.begin();itch<ch.end() && iter<vec.end();itch++,iter++) { vector<int>::iterator in = (*iter).begin(); cout<<*itch<<":"<<*in; for(++in;in<(*iter).end();in++) { cout<<","<<*itch<<":"<<*in; } cout<<endl; } } return 0; }
阶乘
/** 题目描述 输入n， 求y1=1!+3!+...m!(m是小于等于n的最大奇数） y2=2!+4!+...p!(p是小于等于n的最大偶数)。 输入描述: 每组输入包括1个整数：n 输出描述: 可能有多组测试数据，对于每组数据， 输出题目要求的y1和y2 示例1 输入 4 输出 7 26 **/ //题目没有说N的范围,简直了。不过考察的重点应该是那个等式,可以O(n)来做 #include<cstdio> #include<cstring> #include<string> #include<iostream> #include<algorithm> using namespace std; int main() { int N; //N<=20 while(scanf("%d",&N)!=EOF) { long long y1 = 0,y2 = 0; long long factorial = 1; for(int i=1;i<=N;i++) { factorial *= i; if(i&1) y1 += factorial; //奇数 else { y2 += factorial; } //偶数 } cout<<y1<<" "<<y2<<endl; //printf("%I64d %I64d",y1,y2); // 用%iid why y2 = 0? } return 0; } 八进制
/** 题目描述 输入一个整数，将其转换成八进制数输出。 输入描述: 输入包括一个整数N(0<=N<=100000)。 输出描述: 可能有多组测试数据，对于每组数据， 输出N的八进制表示数。 示例1 输入 7 8 9 输出 7 10 11 **/ //题目原来意思可能是要我们模拟进制转换吧.... #include<cstdio> #include<iostream> using namespace std; int main() { int N; while(scanf("%d",&N)!=EOF) { printf("%o\n",N); } return 0; } 题量还是挺多，考研的题正好练练手~
