本文由zhc撰写
小测1 - 字符串的反转
问题描述：
给定一个字符串，你需要颠倒一个句子中每个单词中的字符顺序，同时保留空格和初始单词顺序。
输入样例：
Let's take the contest
输出样例：
s'teL ekat eht tsetnoc
#include<iostream>
using namespace std;
// #include<string>
int main(){
string s="";
while(cin>>s){
for(int j = s.size()-1 ; j >= 0 ; j--) cout<<s.at(j);
cout<<" " ;
}
return 0;
}小测2 - 数一数叶数
问题：
请你实现下列函数，计算给定二叉树的叶数：
#include "BinaryNode.h"
int leaves(const BinaryNode* root);
#include "BinaryNode.h"
int leaves(const BinaryNode* root);
//BinaryNode.h
#include <iostream>
using namespace std;
typedef int T;
struct BinaryNode{
T data;
BinaryNode *left, *right;
BinaryNode(T d, BinaryNode *l=NULL, BinaryNode* r=NULL):data(d), left(l), right(r) {};
};//num_leaves.cpp
#include "BinaryNode.h"
int leaves(const BinaryNode* root){
if(root==NULL) return 0;
if(root->left==NULL&&root->right==NULL) return 1;
return leaves(root->left)+leaves(root->right);
}小测3 - 求两个集合的交集
假定用下列顺序结构存储一个集合，集合元素按照从小到大顺序存储：
typedef int ElemType;
typedef struct
{
ElemType elem[MAXSIZE]; // 线性表占用的数组空间
int last; /*记录线性表中最后一个元素在数组 elem[ ] 中的位置（下标值），空表置为-1*/
} SeqList;请实现下面求集合交集的函数：
//LC是LA和LB表示集合的交集
void merge(SeqList LA, SeqList LB, SeqList *LC);
\\SeqList.h
#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/
typedef int ElemType;
typedef struct
{
ElemType elem[MAXSIZE]; // 线性表占用的数组空间
int last; /*记录线性表中最后一个元素在数组 elem[ ] 中的位置（下标值），空表置为-1*/
} SeqList;#include"SeqList.h"
void merge(SeqList *LA, SeqList *LB, SeqList *LC){
int len1 = LA->last;
int len2 = LB->last;
int i=0;
int j=0;
int k=-1;
while(true){
while(LA->elem[i]<LB->elem[j]&&LA->elem[i]!=-1) ++i;
while(LA->elem[i]>LB->elem[j]&&LB->elem[i]!=-1) ++j;
if(i>len1||j>len2||LA->elem[i]==-1||LB->elem[j]==-1) break;
if(LA->elem[i]==LB->elem[j]){
++k;
LC->elem[k]=LA->elem[i];
++i;
++j;
}
}
LC->last=k;
}小测4 - 检查一个序列是否构成堆 实时评测
问题描述：
给定一个整数序列，请检查该序列是否构成堆。
问题补充：
输入: 第一行是一个整数n(0 < n < 10000)，第二行是n个整数。
输出: 如果序列是极小堆，即堆顶是最小元，则输出"min heap"；如果是极大堆，即堆顶是最大元，则输出“max heap”； 否则不是堆，则输出“no”。如果既是极大堆，又是极小堆，则输出“both”。
输出包括一行，最后有换行。
输入输出格式样例：
输入
5
3 4 2 1 1
输出
no
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int data[n+1];//2*k,2*k+1
for(int i=1;i<=n;++i){
cin>>data[i];
}
int key=1;
int min_heap=1;
while(key<n){
int left=2*key;
if(left+1<=n){
if(data[key]<=data[left]&&data[key]<=data[left+1])
key+=1;
else{
min_heap=0;
break;
}
}else if(left==n){
if(data[key] <=data[left])
key+=1;
else{
min_heap=0;
break;
}
}else if(left>n){
key+=1;
}
}
key=1;
int max_heap=1;
while(key<n){
int left=2*key;
if(left+1<=n){
if(data[key]>=data[left]&&data[key]>=data[left+1])
key+=1;
else{
max_heap=0;
break;
}
}else if(left==n){
if(data[key]>=data[left])
key+=1;
else{
max_heap=0;
break;
}
}else if(left>n){
key+=1;
}
}
if(min_heap==1&&max_heap==1) cout<<"both"<<endl;
else if(min_heap==1) cout<<"min heap"<<endl;
else if(max_heap==1) cout<<"max heap"<<endl;
else cout<<"no"<<endl;
}
小测5 - 验证回文字符串
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
输入：
一行字符串
输出：
是否能成为回文字符串（0：不能；1：能）
示例输入
abca
示例输出
1
注意:
示例当中，你可以删除c字符，使其成为回文字符串。
//abctttca
//actttcba
#include<iostream>
#include<string>
using namespace std;
int main(){
string str;
cin>>str;
int times=0;
int i=0;
int j=str.size()-1;
while(i<j){
if(str[i]==str[j]){
++i;
--j;
}
else{
if(str[i+1]==str[j]){
i+=2;
--j;
++times;
}
else if(str[i]==str[j-1]){
i++;
j-=2;
++times;
}
else{
times+=2;
break;
}
}
}
if(times<=1) cout<<1;
else cout<<0;
}小测6 - 最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
输入：
一个只包含 '(' 和 ')' 的字符串。
输出：
最长的包含有效括号的子串的长度。
示例输入：
)()())
示例输出:
4
注：
示例中的最长有效括号子串为 "()()"
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int length(string str,int start,int end){
stack<char> s;
int len=0;
int i=start;
while(i<=end){
char t = str[i];
if(s.empty()&&t==')') return 0;
if(t=='(') s.push('(');
if(!s.empty()&&t==')'){
s.pop();
len+=2;
}
++i;
}
if(s.empty()) return len;
else return 0;
}
int main(){
string str;
cin>>str;
int max_len=0;
/*for(int i=0;i<str.size()-1;++i){
for(int j=i+1;j<str.size()&&str[i]=='(';j+=2){
if(str[j]!=')') continue;
int len=length(str,i,j);
if(len>max_len) max_len=len;
}
}
*/
for(int i=0;i<str.size()-1;++i){
for(int j=i+1;j<str.size();++j){
int len=length(str,i,j);
if(len>max_len) max_len=len;
}
}
cout<<max_len;
}小测7 - 坐缆车
问题描述:
M山上设置了n个只下山不上山的缆车点1,2…n。游客可以从山上的某一点上缆车，并从其下方任意点下缆车。缆车点i到缆车点j之间的费用为r（i，j），1<=i<=j<=n。试计算从山顶1到山脚n坐缆车所需的最少费用。
输入格式：
第一行一个正整数n，表示有n个缆车点，接下来n-1行是一个半矩阵,当前行表示当前点按顺序到其下方点的费用r(i，j)，从点1开始。
输出格式：
一个整数，表示最小费用
输入样例
3
5 15（1到2的费用为5,1到3的费用为15）
7（2到3的费用为7）
输出样例
12
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int d[n+1][n+1];
int best[n+1];
for(int i=1;i<n;++i){
for(int j=i+1;j<=n;++j){
cin>>d[i][j];
}
best[i+1]=d[1][i+1];
}
best[1]=0;
if(n==1){
cout<<0;
return 0;
}
if(n==2){
cout<<d[1][2];
return 0;
}
for(int k=3;k<=n;++k){
for(int i=1;i<k;++i){
if(best[k]> best[i]+d[i][k])
best[k]=best[i]+d[i][k];
}
}
cout<<best[n]<<endl;
return 0;
}