复试上机练习题

各校历年复试机试试题

清华、北大、华科试题详细笔记部分，少笔记部分与少数leetcode【含个人整理笔记】

一、详细笔记部分:

2018.3.4

[if !supportLists]1. [endif]求给出整数序列的最大序列和

//考点：动态规划，贪心

//S(n) = O(n)

//1.如果sum小于零，sum从下一个位置开始求和

//2.int范围：-2^31~2^31-1，maxSubSum与sum超出范围使用long

#include

using namespace std;

void maxSubStr(int n, int s[]){

long sum = 0;

long maxSubSum = -99999999;

for(int i = 0; i < n;i++){

sum = sum > 0 ? sum :0;

sum += s[i];

maxSubSum = sum >maxSubSum ? sum : maxSubSum;

}

cout<

}

int main(){

int n;

while(cin>>n){

int s[n];

for(int i = 0; i < n;i++){

cin>>s[i];

}

maxSubStr(n, s);

}

return 0;

}

[if !supportLists]2. [endif]求AB两地之间的最小花费(价格与距离有关联)

//考点：dp(动态规划)，最短代价的问题

//S(n)=O(n * n)

//思路：1.使用ticket函数求出每两地的距离相对应的价格(代价)，如果小于L1代价为L1

//2.从A地初始化开始，从A地逐渐到B地；for循环条件是i从A+1开始到B

//3.使用j初试为i-2，在while中循环,循环条件是j>=A，而且两地的距离必须在L3以内,否则退出循环

//4.cost[i] vs cost[j]:上述循环过程中如果A到此地的代价>A到上一地的代价与上一地和此地之间的和，则A到此地的代价被后者代替掉

//5.碎碎念: cost代表代价(代价)最优解，a代表输入的原始路径长度（从起始站A开始的距离）

//6.最终到达的终点B，cost[B]存储A、B之间的最短花费

#include

using namespace std;

int L1, L2, L3, C1, C2, C3;

int A, B;//分别表示起始站和终点站

int N;//路线上的总的火车站数目

//计算两地的票价(代价)

int ticket(int dis){

if(dis <= L1){

return C1;

}else if(dis <= L2){

return C2;

}else{

return C3;

}

int main(){

while(cin>>L1>>L2>>L3>>C1>>C2>>C3){

cin>>A>>B>>N;

//前者表示第一站到达第i个站的原始路径长度，后者表示到达当前地点的最短路径长度

int a[N], cost[N];

for(int i = 2; i <= N;i++){

cin>>a[i];

}

//初始化第一个站台的距离为0，A地没有出发的代价为0

a[1] = 0;

cost[A] = 0;

//开始计算最小的路径

//从序号为A的地点开始，达到B地点，逐次计算最小代价(花费)的方案

for(int i = A + 1; i<= B; i++){

cost[i] = cost[i - 1] + ticket(a[i] - a[i- 1]);

int j = i - 2;

//循环条件：j从A地出发，两地的距离一定要在L3之内(包括L3)

//动态规划核心

while(j >= A&& (a[i] - a[j]) <= L3){

if(cost[i] >cost[j] + ticket(a[i] - a[j])){

cost[i] =cost[j] + ticket(a[i] - a[j]);

}

j--;

}

cout<

}

return 0;

}

[if !supportLists]3. [endif]求给出的0~1000的整数N的阶乘

//考点：大数乘法

//S(n)= O(n*n)

//步骤思路：第一次碰到大数乘法的问题，思路可能比较固定，牢记~

//1.使用digit接收阶乘的最终结果为一个个数组元素，长度设置为较长的10000个元素

//2.初始化digit[size++]=1，size初始为0，即digit[0]=1;

//3.外层循环使用i从2到n,外层循环中添加局部变量k=0,内层循环使用j从0到size-1,使用t接收(digit[j]*i+k)/10,

//digit[i]用(digit[j]*i+k)%10赋值

//4.该循环结束后只要k非零，就将digit[size]赋值为k%10，k/=10作为步长，其中size每循环一次就加一次

//5.下一次的while循环中的size从上一次while循环产生的最新size值到此次while循环条件k!=0的最大size

//6.最后从size-1到0依次输出数组元素值

#include

using namespace std;

int main(){

int n;

while(cin>>n){

int digit[10000];//接收阶乘结果的一位位数字为数组元素

int size = 0;

digit[size++] = 1;

for(int i = 2; i <= n; i++){

int k = 0;

for(int j = 0; j < size; j++){

int t = (digit[j] * i + k) /10;

digit[j] = (digit[j] * i + k) %10;

k = t;

}

while(k != 0){

digit[size++] = k % 10;

k /= 10;

}

for(int i = size - 1; i >= 0; i--){

cout<

}

cout<

}

return 0;

}

2018.3.5

4.挖掉区间里面的树，计算剩余树木的总数

//考点：离散化，数组标记

//时间复杂度：O(L* M + L)

//思路：论坛看到一个算法，思路很清晰，在这里注解一下

//1.初始化数组mark（注意数组长度为N+1）,每个数组值为1，表示没被挖走;

//2.while循环M,每次减去1。在循环里面逐个将每一个在所给的区间里的树（包括边界）去掉，用数组mark标记

//3.从起始树到结束树（0~L,包括边界），如果没有标记就是剩下的树的个数

#include

using namespace std;

int main(){

int L, M;//马路长度为L,输入M组整数,每组一对数字

int count = 0;//多少树没被挖走

while(cin>>L>>M){

int mark[L + 1];//给每一颗树做标记，是否被挖掉(移走^_^)；注意,总共有N+1颗树

int from, to;

//初始化M数组里面每个元素的值是1，表示没被挖走

for(int i = 0; i <= L; i++){

mark[i] = 1;

}

while(M > 0){//M一个个减，只要>0

cin>>from>>to;//在循环里面就不要用数组了，喜

for(int i = from; i <= to; i++){

mark[i] = 0;//移走

}

M--;

}

for(int i = 0; i <= L; i++){//包括第L颗树(从0开始)

if(mark[i] == 1){//没被挖走

count++;

}

cout<

}

return 0;

}

5.大数乘法，将一个长度超过1000的数转换成二进制，然后逆置零，后再由二进制转换成十进制

//考点:大数乘法，十进制转二进制，逆序数

//S()=O(n*n)

//思路：使用字符串类型的a接收1000位以内的大数，定义一个转换函数conversion用于各个进制之间的转换，

//通过调用两次conversion(原进制,原数据，后进制)，得到string a,后reverse(a.begin(),end())

//1.外层循环i从1~a.size(),接收余数t的k初始化为0。注意，使用size.()方法接收字符串的长度

//2.内层循环j从i开始到a.size(),因为要越过高位0

//3.内层循环中将(k * m + a[j] -'0') % n的值给t,a[j]=(k * m + a[j] - '0') / n + '0'(string型)

//4.k接收余数t

//5.在外层循环里将b用char(k +'0')依次连接

//6.外层循环的步长用i决定：a[i]=='0'则i++,即此次产生的是0(高位)，则越过

#include

using namespace std;

string conversion(int m, string a, int n){

int k = 0;

string b;

int l = a.size();

for(int i = 0; i < l;){

k = 0;

for(int j = i; j < l;j++){//比如123/2得到061跳过高位0，继续

int t = (k * m + a[j]- '0') % n;

a[j] = (k * m + a[j]- '0') / n + '0';

k = t;

}

b += char(k + '0');

while(a[i] == '0') i++;

}

return b;

}

int main(){

string a, b;

while(cin>>a){

b = conversion(10, a,2);

a = conversion(2, b, 10);

reverse(a.begin(),a.end());

cout<

}

return 0;

}

6.搜索学生数

//考点:查询

//S(n)=O(n)

//构造对象stu,Stu stu[1000]实例化对象成为一个数组

#include

using namespace std;

typedef struct{

int id;

char name[100];

char sex[20];

int age;

}Student;

int main(){

int i, j, n, m, flag, no;

Student stu[10000];

while(scanf("%d",&n)){

for(int i = 0; i < n;i++){

scanf("%d%s%s%d", &stu[i].id, stu[i].name, stu[i].sex,&stu[i].age);

}

cin>>m;

for(i=0;i

flag=0;

cin>>no;

for(j=0;j

if(no==stu[j].id){

cin>>stu[j].id>>stu[j].name>>stu[j].sex>>stu[j].age;

cout<

//printf("%d %s %s%d\n",stu[j].id,stu[j].name,stu[j].sex,stu[j].grade);

flag=1;

break;

}

if(flag==0)

cout<<"No Answer!"<

}

return 0;

}

2018.3.6

7.我要回家

//考察点：最短距离的一个变体

//N cities,M roads

//S()=O(max(n * n), N + m + n)

//思路及步骤：dijkstra算法，E对象包含两个参数,time与next，

//内层循环中比较当前的总距离与行一次的距离和此次间隔的和的大小，取小的

//1.初始化：三次循环，置空N条边(1~N),连接m条路(m>0),1~n mark置false、dis置-1以及接收leader的输入

//2.1~n-1循环，内层循环为j从0至edge[newP].size(),分别赋值time和next

//3.continue的条件是leader[newP] = 2 &&leader[next]==2 || mark[next] = true

//4.仍在当前循环，如果dis[next] > dis[newP] + time,而且dis[next] = -21则将dis[newP] + time赋值给des[next]

//5.dis[j] = dis[j] + time条件是dis不为-1，

//6.在外层循环(i)接下来从1~n依次判断若dis不是-1，mark为false，dis

//7.mark[newP]=true作为外层循环中的最后一步

//8.在外层循环中外，输出结果dis[2]

#include

using namespace std;

#define N 601//city

#define M 10000//road

typedef struct{

int time;

int next;

}E;

vector edge[M];//roads

bool mark[N];

int dis[N];

int leader[N];

int main(){

int n, m;

while(scanf("%d",&n) != EOF && n != 0){

scanf("%d",&m);

int i, j, a, b, t;

//清空N个城市

for(i = 1; i <= N;i++){

edge[i].clear();

}

//连接m条路，放入属性 //city

while(m--){

scanf("%d%d%d", &a, &b, &t);

E tmp;

tmp.time = t;

tmp.next = b;

edge[a].push_back(tmp);

tmp.next = a;

edge[b].push_back(tmp);

}

//初始化,不标记，距离为-1，接收输入leader

for(i = 1; i <= n;i++){

mark[i] = false;

dis[i] = -1;

scanf("%d",&leader[i]);

}

int time, next, newP;

newP = 1;

mark[1] = true;

dis[1] = 0;

//求解最优路径

for(i = 1; i < n;i++){//1~n-1

for(j = 0; j

time =edge[newP][j].time;

next =edge[newP][j].next;

if(leader[newP]== 2 && leader[next] == 1 || mark[next] == true){

continue;

}

if(dis[next] ==-1 || dis[next] > dis[newP] + time){

dis[next] =dis[newP] + time;

}

int min = 100200300;

for(j = 1; j <= n;j++){

if(dis[j] != -1&& mark[j] != true && dis[j] < min){

newP = j;

min = dis[j];

}

mark[newP] = true;

}

printf("%d\n",dis[2]);

}

return 0;

}

8.谁是你潜在的朋友

//考点：遍历，匹配

//S(n) = O(n * n)

//上层遍历找到自己的朋友就加1,条件是i!=j且相同的书

//count[i]是第i+1个人的朋友数

#include

using namespace std;

int main(){

int n, m;

while(cin>>n>>m){

int book[n];

int i, j, count[n];

for(i = 0; i < n;i++){

count[i] = 0;//默认没朋友

}

for(i = 0; i < n;i++){

cin>>book[i];//n个人所喜欢的书的编号

}

for(i = 0; i < n;i++){

for(j = 0; j < n;j++){

if(book[i] ==book[j] && i != j){

count[i]++;

}

for(i = 0; i < n;i++){

if(count[i] == 0){

cout<<"BeiJu"<

}else{

cout<

}

return 0;

}

9..将一个不超过三十位的十进制数转换为二进制数

//考点：大数进制转换

//S(n)=O(n * n)

//思路:大数类型转换的题型，很经典。

//1.char str接收输入的不超过30位的十进制非负整数。注意，strlen(char类型)接收char类型数组长度

//2.用get数组分别获得一位位数，组成int类型的数组

//3.while(index < l),从index 0到strlen(l) - 1，内层循环在i到l-1，逐位取(get[i]+temp*10)/2为div,即商;

//4.(get[i]+temp*10)%2为num,后get[i]接收div;

//5.余数非0则temp置1,否则为0

//6.内层循环结束后,temp置0，如果get[index]=0，则index++;

//7.接下来将ans[j]接收num,后j++

//8.while循环完毕后，j-1~0,依次输出ans[i]

//9.若有多组数据则换行

#include

using namespace std;

int main(){

int ans[1000], get[100];

char str[100];

int i, j, l, div, num, temp;

l = strlen(str);

j = 0, temp = 0;

while(scanf("%s",str) != EOF){

l = strlen(str);//取字符串长度

for(i = 0; i < l;i++){

get[i] = str[i] -'0';

}

int index = 0;

while(index < l){

for(i = 0; i < l;i++){

div = (get[i] +temp * 10) / 2;

num = (get[i] +temp * 10) % 2;

get[i] = div;//接收商

if(num != 0){

temp = 1;

}else{

temp = 0;

}

temp = 0;

if(get[index] == 0){

index += 1;

}

ans[j] = num;

j++;

}

for(i = j - 1; i >= 0;i--){

printf("%d", ans[i]);

}

printf("\n");

}

return 0;

}

2018.3.7

10.W’s cipher

//考点:W氏密码，多数组，二维数组

//时间复杂度S(n)=O(n), n为输入的数组长度

//思路步骤:1.使用str1、str2、str3分别接收三种不同类型的数组，它们的索引号分别使用site1、site2、site3三个数组存储

//2.初始re作为结果接收的数组，以上三个数组的大小均为MAX_VAL,不放宏定义为1000

//3.从键盘接收三个不全为零的整数k1、k2、k3

//4.输入等待加密的字符串str;

//5.在a~i, j~r, s~z三种类型中对str串进行分类，记录对应字符和字符的位置

//6.完毕后i置0，接收re[site1[(i + k1) % count1]] = str1[i]; i++

//7.重复str2, str3分别对re的赋值

//8.0~count-1，输入结果数组re

#include

using namespace std;

#define MAX_VAL 1000

int main(int argc, char** agrgv){//char类型

string str;

int k1, k2, k3;

while(cin>>k1>>k2>>k3 && (k1 != 0 || k2 != 0|| k3 != 0)){//从键盘接受输入三个不全为零的数

int i = 0, count = 0,count1 = 0, count2 = 0, count3 = 0;

int site1[MAX_VAL],site2[MAX_VAL], site3[MAX_VAL];//接收索引序号

char str1[MAX_VAL],str2[MAX_VAL], str3[MAX_VAL];//接收每个char字符

char re[MAX_VAL];//结果字符数组

if(cin>>str){

count =str.length();//求字符串长度

//一次接收读入的字符与位置到相应的存储数组

while(i < count){

if(str[i] >='a' && str[i] <= 'i'){

str1[count1]= str[i];

site1[count1]= i;

count1++;

}else if(str[i]>= 'j' && str[i] <= 'r'){

str2[count2]= str[i];

site2[count2]= i;

count2++;

}else if(str[i]>= 's' && str[i] <= 'z' || str[i] == '_'){

str3[count3]= str[i];

site3[count3]= i;

count3++;

}

i++;

}

i = 0;

while(i < count1){

re[site1[(i + k1)% count1]] = str1[i];

i++;

}

i = 0;

while(i < count2){

re[site2[(i + k2)% count2]] = str2[i];

i++;

}

i = 0;

while(i < count3){

re[site3[(i + k3) % count3]] = str3[i];

i++;

}

for(i = 0; i < count; i++){

cout<

}

cout<

}

return 0;

}

11.日志排序

//考点:排序

//S(n)取决于sort方法,比如如果是冒泡排序则是S(n) = O(n * n)

//思路:1.定义一个对象，三个属性s,start，time分别表示整条记录的字符串、开始时间以及持续时间

//2.定义持续时间time为double类,size作为总记录条数进行初始化为0

//3.接收输入:gets[r[size].s],并且需要r[size].s的长度(strlen())不为0

//4.sscanf函数！sscanf(r[size].s,"%s%s%lf", start1, start2, &r[size].time),分别以空格区分

//5.将start拼接,通过cmp排序———sort(r, r+size, cmp),时间短的置前（如果时间相同那么就将发生早的置前）

//6.0~size-1输出r[i].s即为每条记录的所有信息

#include

using namespace std;

struct Record{

char s[100];

string name;//用不到但是是属性，得写啊

string start;

double time;

}r[10000];

bool cmp(Record a, Record b){

if(a.time != b.time){

return a.time

}else{

return a.start

}

int main(){

int size = 0;

double time;

char start1[15], start2[15],name[15];

while(gets(r[size].s)&& strlen(r[size].s) != 0){

sscanf(r[size].s,"%s%s%s%lf", name, start1, start2, &r[size].time);

r[size++].start =string(start1) + string(start2);

}

sort(r, r + size, cmp);

for(int i = 0; i < size;i++){

cout<

}

return 0;

}

12.密码翻译

//考点:明文加密

//S(n)=O(n)

//char数组接收输入的字符串，逐次加密

#include

usingnamespace std;

charencrypt(char c){

char res = x;//初始化

if(c == 'z'){

res = 'a';

}else if(c == 'Z'){

res = 'A';

}else if((c >= 'a' && c <='y') || (c >= 'A' && c <= 'Y')){

res = c + 1;

}

return res;

}

intmain(){

char str[80];

while(gets(str)){

for(int i = 0; i < strlen(str);i++){//strlen(str)求数组串长度

cout<

}

cout<

}

return 0;

}

2018.3.8

13.是否为树

//考点:是否是树的问题

//S(N) =O(N), N为预估可以接收的最大结点数

//思路:将一个个数对连接成图，找到根结点，从根结点往下产看如果出现非树的特征则返回false

//步骤:1.k在while(true)循环中初始为1，全局变量mark[N], ans标记是否为树，n表示结点数, root表示是根结点数目

//2.mark[N]初始化为-1,0表示结点出现过，1表示入度数

//3.循环接收x，y数对的输入,如果均为零则退出本场对树的判断

//4.如果均为-1,则退出程序执行

//5.若mark[x]==-1,则赋值为0；若mark[y]==-1,则赋值为1，否则（y出现过）则mark[y]+1，即入度加1;至此，接收输入结束

//6.开始逐渐检查各个结点：如果mark不是-1，则n++;

//7.如果mark>1,那么不是树，break此次循环，否则如果mark为0，则假定是树根,之后判断是否root>1,若是则不是树，break

//8.讨论合计情况:如果root是0,则不是树;如果n是0则是空树

//9.ans标记如果是true则是树，否则不是

//10.别忘了k最后要k++，在最外层循环中

#include

usingnamespace std;

#defineN 10001//那就多开一点空间吧

intmark[N];//0表示出现过，1表示入度为1, -1表示没有出底线过

intmain(){

int k = 1;//case编号

int x, y;

while(true){

bool ans = true;//假定是树

int root, i, n;//，root表示入度为零的节点数，i计数用,n表示结点个数

root = 0, n = 0;//假设为入度为零的结点数，注意一颗空树一定要有root!=0，但是可以有节点数n为零

for(i = 0; i < N; i++){

mark[i] = -1;//假定所有的标记都是-1，即没有出现过

}

while(scanf("%d %d", &x,&y) != EOF){

if(x == 0 && y == 0){//本次数对结束,退出while循环

break;

}else if(x == -1 && y ==-1){

return 0;//退出程序的标志

}

if(mark[x] == -1){//i之前没有出现过

mark[x] = 0;//现在出现了

}

if(mark[y] == -1){//j之前没有出现

mark[y] = 1;//j作为入度

}else{//如果以前出现过b的话，那么现在b的入度要加1

mark[y]++;

}

//逐次检查各个节点的情况

for(i = 0; i < N; i++){

if(mark[i] != -1){//统计一共的结点个数n

n++;

}

if(mark[i] > 1){//入度大于一就不是树

ans = false;

break;

}else if(mark[i] == 0){//怀疑他是根节点

root++;

if(root > 1){//又一次判断不是树的条件

ans = false;

break;

}

}//各个结点检查结束

//讨论合计情况

if(root == 0){

ans = false;

}

if(n == 0){//空树的条件

ans = true;

}

if(ans){

printf("Case %d is atree.\n", k);//输出的时候不需要的&

}else{

printf("Case %d is not atree.\n", k);

}

k++;

}

return 0;

}

14.最简的真分数的个数

//考点:最简真分数，主要是求解gcd(递归)，即是最大公约数的求法

//S(n)=O(n * n)

//思路：是不是最简，还有假分数呢？判断用欧几里得的最大公约数求法

//步骤: 1.s[n]用来接收键盘输入的一串数字

//2.0~n-1双层循环，如果相等自然不是最简真分数(值为1)，内层循环continue;

//3.如果外层循环计数i对应的是s[i]>内层循环计数j对应的s[j]，并且他们的最大公约数是1(即为最简真分数),则最简真分数的计数+1

//4.注意，最简真分数的判断需要用到欧几里得算法gcd(a, b)：b==0则返回a,否则递归返回gcd(b, a % b0)【注意牢记】

//5.输出此次结果后换行

#include

usingnamespace std;

int n;

//欧几里得算法求两个数的最大公约数

intgcd(int a, int b){

if(b == 0){

return a;

}else{

return gcd(b, a % b);

}

intmain(){

while(cin>>n){

int i, j, s[n], count;

count = 0;//记录最简真分数的对数

for(i = 0; i < n; i++){

cin>>s[i];

}

for(i = 0; i < n; i++){

for(j = 0; j < n; j++){

if(s[i] == s[j]){

continue;//不是最简真分数

} else if(s[i] > s[j]&& gcd(s[i], s[j]) == 1){

count++;

}

cout<

}

return 0;

}

15.求中位数

//考点:求中位数

//S(n)=O(n* n)//如果sort()的时间复杂度为n * n, n,n为输入的数据个数

//思路:1.接受输入，从小到大排序(使用系统函数sort)

//2.sort(s,s+n, cmp),其中n为整数数组的长度, cmp注明升序/降序,省略cmp则默认升序

//2.根据数据总数的奇偶性选出中位数，如果是偶数则取平均数((a+b)/2即为向下取整)

#include

usingnamespace std;

boolcmp(int a, int b){

return a < b;

}

intmain(){

int n;

while(cin>>n){

int s[n];

int i, res;

for(i = 0; i < n; i++){

cin>>s[i];

}

sort(s, s + n);//系统函数

if(n % 2 == 0){//偶数

res = (s[n / 2] + s[n / 2 - 1]) /2;

}else{

res = s[n / 2];

}

cout<

}

return 0;

}

16.小白鼠排队

//考点：对象比较的问题

//S(n)=O(n*n),如果是冒泡排序的话

//思路:定义一个包含颜色和重量的小白鼠struct类型，排序，输出重量从大到小的小白鼠的颜色

#include

usingnamespace std;

structMouse{

int weight;

string color;

}s[100];

boolcmp(Mouse a, Mouse b){

return a.weight > b.weight;

}

intmain(){

int n;

while(cin>>n){

for(int i = 0; i < n; i++){

cin>>s[i].weight>>s[i].color;

}

sort(s, s + n, cmp);

for(int i = 0; i < n; i++){

cout<

}

return 0;

}

17.分糖果

//题目:分糖果，老师每吹一次口哨小朋友就分给右手边的小朋友一个糖果

//S(n)取决于每个人的糖果数

//如果分完后小朋友手中的糖果数为奇数，则老师添加一颗给他。

//求出每个小朋友有着相同的糖果数的时候老师共吹了几多少次口哨，以及最后每个人拥有多少糖果

//考点:循环，考虑初始状态(如果初始时糖果数为奇数不会另外获得一颗糖果)

//步骤:1.定义每人拥有相同的糖果数标记con = 0,接收输入n个小朋友，如果只有一个那就是不用吹口哨，最终这个小朋友手里有aa(第二个输入)颗糖

//2.否则0~n逐次将第i个小朋友所有的糖果数放入num[i]（初始定义num[10000]）,rounds表示吹口哨的次数

//3.只要!con就循环，定义x接收为最后一个小朋友的糖果数num[n- 1]，老师吹口哨，游戏开始

//4.从n - 1到1,第i个小朋友增加了第i-1个小朋友糖果数的一半

//5.第i-1个小朋友少了自己的一半的糖果数

//6.如果i不等于n-1并且第i个小朋友的糖果数和1按位与,那么num[i]++

//7.结束内层j循环，num[0]增加x/2,num[n-1]减去x/2

//8.如果num[0]&1，num[0]++,之后num[n - 1]&1,那么num[n - 1]++然后con=1

//9.从0到n-1,定义p =num[0]，如果num[i]不等于p,则con置0,，并退出当前循环

//10.最后输出rounds为口哨数，num[0]为最终每个小朋友拥有的糖果数

//注意：看不懂英文题目多读几遍

#include

usingnamespace std;

intmain(){

int n;//n个小朋友

while(scanf("%d", &n) !=EOF){//& n

int con, rounds, num[10000];

con = 0, rounds = 0;

if(n == 1){//只有一个人好办

int aa;

scanf("%d", &aa);

printf("0 %d\n", aa);

break;

}

for(int i = 0; i < n; i++){//每个小朋友的糖果数

scanf("%d", &num[i]);

}

while(!con){

int x = num[n - 1];

rounds++;

for(int i = n - 1; i >= 1; i--){

num[i] += num[i - 1] / 2;

num[i - 1] -= num[i - 1] / 2;

if(i != n - 1 && num[i]& 1){

num[i]++;

}

num[0] += x / 2;

num[n - 1] -= x / 2;

if(num[0] & 1){

num[0]++;

}

if(num[n - 1] & 1){

num[n - 1]++;

}

con = 1;

for(int i = 0; i < n; i++){

int p = num[0];

if(num[i] != p){

con = 0;

break;

}

printf("%d %d\n", rounds,num[0]);

}

return 0;

}

2018.3.9

18.八皇后问题

//考点:象棋，八皇后；知识点：递归

//S(n) =O(n!),递归

//思路:定义二维数组为92种解法的存储位置,根据题意选择适当的解

//步骤:1.初始化全局变量a[95][10],c[10],total置0；深度优先遍历棋盘，定义函数dfs(cur),cur表示从cur行开始检测通路

//2.0~7进行i循环，根据题意选择其实行对应的解——8位整数串

//3.详细dfs定义：如果cur为8，则total+1,0~7遍历a[total][i]=c[i]

//4.否则0~7循环，c[cur]接收索引i,初始ok为1，内层循环j从0~cur - 1,ok置0并退出内层循环的条件是c[j]== i或cur - i == j - c[j]或cur +i ==c[j] + j。

//5.内层循环结束后如果ok那递归调用dfs(cur + 1)

#include

usingnamespace std;

inta[95][10];//解

intc[10];

inttotal = 0;

//深度优先遍历

voiddfs(int cur){//起始位置

if(cur == 8){

total++;

for(int i = 0; i < 8; i++){

a[total][i] = c[i];

}

}else{

for(int i = 0; i < 8; i++){

c[cur] = i;//标记位置

int ok = 1;//默认是所求的解

for(int j = 0; j < cur; j++){

if(c[j] == i || cur - i == j -c[j] || cur + i == c[j] + j){

ok = 0;

break;//此方案行不通啊

}

if(ok){//i循环中此路可行

dfs(cur + 1);//检测下一行

}

intmain(){

int N;

while(scanf("%d", &N) !=EOF){

dfs(0);//从索引号0开始逐行检测是否有通路

for(int i = 0; i < 8; i++){//8皇后

printf("%d", a[N][i] +1);//根据需要取方案

}

//cout<

printf("\n");

}

return 0;

}

19.大整数因子

//考点：大数求因子

//S()=O()

//思路：用string接收30位以内的整数，写一个函数mod求解余数

//步骤:1.定义flag默认有因子，接收大整数

//2.0~9循环作为除数逐次检测每一位数,循环索引为k

//3.mod函数逐次求出每一位数的余（d=(d*10+(s[i]-'0'))%k），返回余数d

//4.main中k循环里面，如果mod返回的是0,说明能被整除，则意味着找到因子k;

//5.如果flag是1，即标记为有因子，则打印空格，否则置1;输出因子k

//6.k循环结束后判断如果flag为0，说明没有一个因子,则输出none;此轮判断结束，换行

#include

usingnamespace std;

//求余

intmod(string s, int k){

int d = 0;

for(int i = 0; i < s.size(); i++){//字符串长度

d = (d * 10 + (s[i] - '0')) % k;

}

return d;//返回余数

}

intmain(){

string s;

while(cin>>s && s != "-1"){

int flag = 0;//默认没因子

for(int k = 2; k <= 9; k++){

if(!mod(s, k)){//整除

if(flag){

printf(" ");

}else{

flag = 1;

}

printf("%d", k);

}

if(!flag){

printf("none");

}

cout<

}

return 0;

}

20.最小生成树

//考点:最小生成树,本题使用Kruskal方法，适用于边少（点多）的情况

//S(n)=O(e*loge),e为边数；prim算法时间复杂度为O(n * n),n为顶点个数,适用于点少（边多）的情况

//思路:思路就很简单了，分两个集合V1、V2，V1初始为空集, V2存放树中所有顶点，

//逐次将V2中最小边的两个端点放入V1,且要求V1中的点构成的图无环,

//终止条件是V2空

//步骤：1.输入定点数n,逐对接收顶点信息并以pair方式放入vector v中

//2.进入MST函数:v其实赋给了v2,v1为空集，定义res为最小生成树的总长度，返回浮点类型

//3.MST内外层循环终止条件是v2.size()不大于0，循环中r,it,jt分别记录单次选取的最短边长度，及其对应的两个定点序号

//4.0~v1.size()-1循环，其内0~v2.size()-1循环,记录最短边的条件是r==0或dist(v1[i],v2[j])

//5.i循环完成后v1增加v2[jt]这个点，v2中抹掉jt:v2.ersae(v2.begin()+jt), res增加r

//6.v2为空后返回res

//7.dist函数返回两点之间距离

//8.main函数中输出MST的返回值res

#include

usingnamespace std;

//求距离

floatdist(pair p1, pair p2){//pair数对

return sqrt((p1.first - p2.first) *(p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second));

}

//Kruskal

floatMST(vector> &v){//返回浮点数

vector> v1,v2(v);

float res;//最小生成树的长度

while(v2.size() > 0){

float r = 0, it = 0, jt = 0;

for(int i = 0; i < v1.size(); i++){

for(int j = 0; j < v2.size();j++){

if(r == 0 || dist(v1[i], v2[j])< r){//选短边

r = dist(v1[i], v2[j]);

it = i;

jt = j;//记录选中边的顶点

}

v1.push_back(v2[jt]);//v2中的点放入v1

v2.erase(v2.begin() + jt);//抹掉指定点

res += r;

}

return res;

}

intmain(){

int n;

while(cin>>n){

float x, y;

vector>v;

for(int i = 0; i< n; i++){

cin>>x>>y;

v.push_back(pair(x, y));//逐次接收每个点

}

cout<

}

return 0;

}

21.放苹果

//考点:第二类stirling数，即放球问题（允许空盒）,递归求解

//S(n)=O(pow(m,n)),m个苹果，n个盘子

//思路：递推求解

//步骤:1.方案数函数：没有苹果或一个盘子只有一种情况,

//2.苹果数<盘子数则盘子数用苹果数更新,否则返回solve(m, n-1)+solve(m-n, n-1)

//3.在main中接收苹果数和盘子数，根据solve函数输出方案数

#include

usingnamespace std;

intsolve(int m, int n){

if(m == 0){

return 1;

}

if(n == 1){

return 1;//只有一个盘子

}

if(m < n){

return solve(m, m);

}else{

return solve(m, n - 1) + solve(m - n,n);//一般情况的递归

}

intmain(){

int m, n;

while(cin>>m>>n){

cout<

}

return 0;

}

22.大数进制转换

//考点：大数进制转换

//S(n)=O(n* n),n为输入整数的位数

//思路:逆序存储待转换数，i标记最高位，双层循环取余数放入data数组中，

//最高位为零时外层循环的i才会减1。双层循环结束后从高到低输出结果

//步骤:1.gets(s)接收不超过30位数的整数，只要索引i<整数位数strlen(s),就逐次逆序存储数字至d[]中

//2.i从strlen(s)-1至0作为外层循环（此处并非逐次i--），k初始化为0,内层循环j从i到0依次逐减

//3.循环中为t赋值为(d[j] + 10 * k) % 2,即取余，d[j] = (d[j] + 10 * k) / 2,即取商，k= t;【牢记经典步骤】

//4.data[low++]赋值为k，如果此时d[i]为0则i--

//5.双层循环结束，从low-1~0逐个输出data[i];换行END

#include

usingnamespace std;

intmain(){

char s[50];

int d[150], data[150];

int i, j, k, low, t;

while(gets(s)){

int length = strlen(s);

i = 0;

low = 0;

while(i < length){

d[length - 1 - i] = s[i] - '0';

i++;

}

for(i = length - 1; i >= 0;){//i标记最高位，注意i--在最后

k = 0;

for(j = i; j >= 0; j--){

t = (d[j] + 10 * k) % 2;

d[j] = (d[j] + 10 * k) / 2;

k = t;

}

data[low++] = k;

if(d[i] == 0){

i--;

}

for(i = low - 1; i >= 0; i--){

printf("%d", data[i]);

}

printf("\n");

}

return 0;

}

23.全排列

//考点：全排列

//S(n)=O(n!),有n!种序列

//借鉴了很多同学的算法，惊喜的发现python和C++都有全排列的内置函数！强大的next_permutation

//思路：输入待求解串，排序sort(s.begin(), s.end()),

//do-while循环：只要next_permutation(s.begin(), s.end()),就输出一种排列s，注意换行；循环结束后换行END

#include

usingnamespace std;

int main(){

string s;

while(cin>>s){

sort(s.begin(), s.end());

do{

cout<

}while(next_permutation(s.begin(),s.end()));

cout<

}

return 0;

}

二、少笔记部分:

1.整数转八进制输出

#include

using namespace std;

void change(int n){

if(n == 0){

return;

}else{

change(n / 8);

cout<<(n % 8);

}

int main(){

int n;

while(cin>>n){

change(n);

}

return 0;

}

[if !supportLists]2. [endif]n阶上楼问题(非递归)

#include

usingnamespacestd;

intfabonacci(intn){

intcurrent = 1, oneback =

1, twoback = 1;

for(inti = 1; i < n; i++){

twoback

= oneback;

oneback

= current;

current

= oneback + twoback;

}

returncurrent;

}

intmain(){

intn;

while(cin>>n){

cout<

}

return0;

}

[if !supportLists]3. [endif]a+b

#include

usingnamespacestd;

intmain(){

inta, b;

while(cin>>a){

cin>>b;

cout<

}

return0;

}

[if !supportLists]4. [endif]判断是否为回文串

#include

usingnamespacestd;

voidjudge(string s){

boolflag = true;

for(inti = 0; i < s.size() /

2; i++){

if(s[i]

!= s[s.size() - 1 - i]){

flag

= false;

break;

}

if(flag){

cout<<"Yes!";

}else{

cout<<"No!";

}

return;

}

intmain(){

string s;

while(cin>>s){

judge(s);

cout<

}

return0;

}

[if !supportLists]5. [endif]找出给定字符串中有重复的字符及其位置

#include

usingnamespacestd;

voidfind(string s){

inti, j;

for(i = 0; i

< s.size() - 1; i++){

boolrepeat = false;//每次重置为不重复

if(s[i]

== '*'){

continue;

}

for(j

= i + 1; j < s.size(); j++){

if(s[i]

== s[j]){

if(!repeat){

cout<

repeat

= true;

}

cout<<","<

s[j]

= '*';

}

if(repeat){

cout<

}

return;

}

intmain(){

string s;

while(cin>>s){

find(s);

}

return0;

}

[if !supportLists]6. [endif]求y1=1! + 3! + ... + m!,y2 = 2! + 4! +... + p!(m,n分别为小于或等于给定n的最大奇数和偶数)

#include

using namespace std;

int factorial(int n){

if(n == 1){

return 1;

}else{

return factorial(n - 1) * n;

}

int main(){

int n, i, j, y1, y2;

y1 = 0, y2 = 0;

while(cin>>n){

for(i = 1; i <= n; i = i + 2){

y1 += factorial(i);

}

for(j = 2; j <= n; j = j + 2){

y2 += factorial(j);

}

cout<

}

return 0;

}

[if !supportLists]7. [endif]成绩排序

//考点:对象,排序

//题目：输入n为总人数，0表示降序,1表示升序，求按成绩排序后的学生信息

#include

usingnamespacestd;

structStudent{

string name;

intgrade;

};

booldesc(Student a, Student

b){

returna.grade > b.grade;

}

boolasc(Student a, Student

b){

returna.grade < b.grade;

}

intmain(){

intn, order;

vector

stu;

while(cin>>n){

stu.resize(n);

cin>>order;

for(inti = 0; i < n; i++){

cin>>stu[i].name>>stu[i].grade;

}

if(order

== 0){

stable_sort(stu.begin(),

stu.end(), desc);

}else{

stable_sort(stu.begin(),

stu.end(), asc);

}

for(inti = 0; i < n; i++){

cout<

}

return0;

}

[if !supportLists]8. [endif]约数个数

//题目：n个数，以后n行是n个数（1~10^9），分别换行输出约数个数

#include

using namespace std;

int count(int n){

int c = 0;

if(n == 1){

return 1;

}else{

int i;

for(i = 1; i * i < n; i++){

if(n % i == 0){

c = c + 2;

}

if(i * i == n){

c++;

}

return c;

}

int main(){

int num;

while(cin>>num){

int s[num];

for(int i = 0; i < num; i++){

cin>>s[i];

cout<

}

return 0;

}

[if !supportLists]9. [endif]代理服务器个数

//n个服务器被m个代理服务器访问，系统同一时刻只能使用一个代理服务器，求代理服务器切换的最少次数

#include

usingnamespacestd;

intsolve(charp[100][16], intn, chars[500][16],

intm){

inti, j;

intmax = -1;

for(i = 0; i

< n; i++){

for(j

= 0; j < m; j++){

if(!strcmp(s[j],p[i])){//相等

if(max

< j){

max

= j;

}

break;

}

if(j

== m){

return0;//不用切换

}

if(n == 1&& max != -1){//max没有参加最长匹配

return-1;//无法完成

}

return1 + solve(p, n, s + max,

m - max);

}

intmain(){

inti, n, m;

while(cin>>n){

charp[n][16];

for(i

= 0; i < n; i++){

cin>>p[i];

}

cin>>m;

chars[m][16];

for(i

= 0; i < m; i++){

cin>>s[i];

}

cout<

n, s, m);

}

return0;

}

[if !supportLists]10. [endif]反序输出

//将任意字符串反序输出。ps:强大的C++有内置函数reverse啊

#include

usingnamespacestd;

voidreverse(string s){

boolflag = true;

for(inti = 0; i < s.size();

i++){

cout<

- 1 - i];

}

intmain(){

string s;

inti;

while(cin>>s){

reverse(s);

cout<

}

return0;

}

[if !supportLists]11. [endif]手机键盘

//九宫格，相同格子的两个字符如a、c分别需要按1、3次，如果一起按中间还需要等待，按键时间1s，等待时间2s，求输入给定串的时间

#include

usingnamespacestd;

intcount(string s){

intsec, i;

sec = 0;

inttime[26] = {1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4};

inttable[26] =

{1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,8,8,8,8};

charpre = '#';

for(i = 0; i

< s.size(); i++){

if(table[pre

- 97] == table[s[i] - 97]){

sec

+= 2;

}

sec

+= time[s[i] - 97];

pre

= s[i];

}

returnsec;

}

intmain(){

string s;

while(cin>>s){

cout<

}

return0;

}

[if !supportLists]12. [endif]质因数的个数

//求1~10^9之间的一个正整数N的质因数个数

#include

usingnamespacestd;

intcount(intn){

intc = 0;

for(inti = 2; i * i <= n;

i++){

while(n

% i == 0){

/= i;

c++;

}

if(i

<= 1){

break;

}

if(n >

1){

c++;

}

returnc;

}

intmain(){

intn;

while(cin>>n){

cout<

}

return0;

}

[if !supportLists]13. [endif]整数拆分

//不超过10^6的整数n，求其拆分成2的幂的和的方式的数目，输出f(n)%10^9

#include

usingnamespacestd;

intcount(longn){

longi;

intval[1000000];

for(i = 1; i

<= n; i++){

if(i

== 1){

val[1]

= 1;

}elseif(i % 2){//odd

val[i]

= val[i - 1];

}else{

val[i]

= (val[i - 1] + val[i / 2]) % 1000000000;

}

returnval[n];

}

intmain(){

longn;

while(cin>>n){

cout<

}

return0;

}

[if !supportLists]14. [endif]成绩排序

//输入学生信息，按照成绩排序（从低到高）后输出结果，如果成绩相同则学号小的在前

#include

usingnamespacestd;

structStudent{

intnum, grade;

};

boolcmp(Student a, Student

b){

if(a.grade

< b.grade){

returntrue;

}elseif(a.grade == b.grade

&& a.num < b.num){

returntrue;

}else{

returnfalse;

}

intmain(){

intn;

while(cin>>n){

vectorstu(n);//标识对象的长度

for(inti = 0; i < n; i++){

cin>>stu[i].num>>stu[i].grade;

}

stable_sort(stu.begin(),stu.end(), cmp);//cmp标识排序规则

for(inti = 0; i < n; i++){

cout<

}

return0;

}

[if !supportLists]15. [endif]球半径和体积

//已经球的中心电点和球上某一点的坐标，输出保留到三位小数的半径和体积。PI使用arccos(-1)

#include

usingnamespacestd;

intmain(){

doubler, v;

inta, b, c, d, e, f;

while(cin>>a){

cin>>b>>c>>d>>e>>f;

= (double)sqrt((d - a) * (d - a) + (e - b) * (e - b) + (f - c) * (f - c));

= r * r * r * acos(-1) * 4 / 3;

cout<

}

return0;

}

[if !supportLists]16. [endif]遍历二叉树

//根据读入的先序遍历的字符串建树，然后输出中序遍历结果，如abc##de#g##f###，结果为c b e g d f a

#include

using namespace std;

string str;

int i;

struct TreeNode{

char val;

struct TreeNode *lchild, *rchild;

TreeNode(char c): val(c), lchild(NULL), rchild(NULL){};

};

TreeNode *createTree(){

char c = str[i++];

if(c == '#'){

return NULL;

}

TreeNode *root = new TreeNode(c);

root -> lchild = createTree();

root -> rchild = createTree();

return root;

}

void inOrderTraversal(TreeNode *root){

if(!root){

return;

}

inOrderTraversal(root -> lchild);

cout< val<<" ";

inOrderTraversal(root -> rchild);

}

int main(){

while(cin>>str){

TreeNode *root = createTree();

inOrderTraversal(root);

cout<

}

return 0;

}

[if !supportLists]17. [endif]玛雅人的密码

//对只含0、1、2的字符串，通过相邻移动以出现2012来解开密码，求最少移动次数

#include

usingnamespacestd;

conststring match =

"2012";

intmain(){

intN;

string str;

while(cin>>N){

cin>>str;

queue

int> > que;

unordered_set

visit;

for(N

= -1, que.push(make_pair(str, 0)), visit.insert(str); que.size(); que.pop()){

pair

int> p = que.front();

if(p.first.find(match)

!= string::npos){

= p.second;

break;

}

for(inti = 1; i <

p.first.length(); i++){

swap(p.first[i

- 1], p.first[i]);

if(visit.find(p.first)

== visit.end()){

que.push(make_pair(p.first,

p.second + 1));

}

visit.insert(p.first);

swap(p.first[i

- 1], p.first[i]);

}

cout<

}

return0;

}

[if !supportLists]18. [endif]求给定个数的n个整数中的最大最小值，每个数绝对值不大于10^6

#include

using namespace std;

int main(){

int N;

while(cin>>N){

int a[N];

for(int i = 0; i < N; i++){

cin>>a[i];

}

int max = a[0], min = a[0];

for(int i = 0; i < N; i++){

min = min < a[i] ? min : a[i];

max = max < a[i] ? a[i] : max;

}

cout<

}

return 0;

}

[if !supportLists]19. [endif]最小邮票数

//求n张邮票凑成总面值为m所需要的最少邮票数，输入n、m,以及接下来的n张邮票

#include

usingnamespacestd;

#define INF 0xFFFFFF

intminCount(intM, intN, inta[]){

if(N == 0){

if(M

== 0){

return0;

}else{

returnINF;

}

}elseif(M - a[N - 1] >=

0){

returnmin(minCount(M - a[N -

1], N - 1, a) + 1, minCount(M, N - 1, a));

}else{

returnminCount(M, N - 1, a);

}

intmain(){

intM, N, count;

while(cin>>M){

cin>>N;

inta[N];

for(inti = 0; i < N; i++){

cin>>a[i];

}

count

= minCount(M, N, a) >= INF ? 0 : minCount(M, N, a);

cout<

}

return0;

}

[if !supportLists]20. [endif]abc

//求使两个整数abc、bcc满足abc+bcc=532的所有a、b、c的值

//答案为3 2 1

#include

using namespace std;

int main(){

int a, b, c;

for(a = 0; a < 6; a++){

for(b = 0; b < 6; b++){

for(c = 0; c < 7; c++){

if(a * 100 + b * 110 + c * 12== 532){

cout<

}

return 0;

}

[if !supportLists]21. [endif]root(N, k)

//题目：N=2000000000)

#include

using namespace std;

int main(){

for(long x, y, k, r; cin>>x>>y>>k;){

for(r = 1, k -= 1; y; r = (y & 1 ?r * x % k : r) , x = x * x % k , y >>= 1);

cout<<(r ? r : k)<

}

return 0;

}

[if !supportLists]22. [endif]N的阶乘

//求1~20之间的整数的阶乘

#include

using namespace std;

double factorial(double n){

if(n > 0){

return n * factorial(n - 1);

}else{

return 1;

}

int main(){

int n;

while(cin>>n){

cout<

}

return 0;

}

[if !supportLists]23. [endif]特殊乘法

/题目：/对2个小于1000000000的输入，求结果。特殊乘法举例：123* 45 = 1*4 +1*5 +2*4 +2*5 +3*4+3*5

#include

using namespace std;

int special(string m, string n){

int i, j, sum;

sum = 0;

for(i = 0; i < m.length(); i++){

for(j = 0; j < n.length(); j++){

sum += (m[i] - '0') * (n[j] - '0');

}

return sum;

}

int main(){

string m, n;

while(cin>>m){

cin>>n;

cout<

}

return 0;

}

[if !supportLists]24. [endif]今年的第几天

//题目：输入年、月、日，计算该天是本年的第几天

//这么循环非常简练了

#include

using namespace std;

const int month[13] = {0, 31, 28,31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main(){

for(int y, m, d; cin>>y>>m>>d;cout<

for(int i = 1; i < m; d +=month[i++]);

if(y % 400 == 0 || (y % 100 &&y % 4 == 0)){

d += m > 2 ? 1 : 0;

}

return 0;

}

[if !supportLists]25. [endif]完数vs盈数

//题目：一个数如果恰好等于它的各因子(该数本身除外)子和，如：6=3+2+1。则称其为“完数”；若因子之和大于该数，则称其为“盈数”。求出2到60之间所有“完数”和“盈数”。

#include

using namespace std;

int main(){

int n, i, s, c, g[60];

for(cout<<"E:", c = 0, n = 2; n < 61; n++){

for(s = 0, i = 1; i < n; s += (n % i? 0 : i), i++);

if(s == n){

cout<<" "<

}else if(s > n){

g[c++] = n;

}

for(cout<<"\nG:", i = 0; i < c; cout<<""<

cout<

return 0;

}

[if !supportLists]26. [endif]递推数列

//题目：给定a0,a1,以及an=p*a(n-1) + q*a(n-2)中的p,q。这里n >= 2。求第k个数对10000的模。输入：a0、a1、p、q、k,输出：第k个数a(k)对10000的模

//考点:递推，非递归方法

//时间复杂度:O(n)

#include

using namespacestd;

int main(){

int a0, a1, p, q, k, result;

while(cin>>a0>>a1>>p>>q>>k){

for(int i = 2; i <= k; i++){

result = (q * a0 + p * a1) %10000;//中间部分就需要取余

a0 = a1;//相当于将oneback用twoback赋值

a1 = result;

}

cout<<(result %10000)<

}

return 0;

}

三、部分leetcode（少笔记）

1.二叉树的最小深度

//题目：Givena binary tree, find its minimum depth.The minimum depth is the number of nodesalong the shortest path from the root node down to the nearest leaf node.

class Solution{

public:

int run(TreeNode *head){

if(!head){

return 0;

}

int l = run(head -> left);//依次遍历

int r = run(head -> right);

if(l == 0 || r == 0){//为左空或者右空

return 1 + l + r;

}

return 1 + min(l, r);//选小

}

};

[if !supportLists]2. [endif]计算逆波兰表达式

//题目:Evaluatethe value of an arithmetic expression inReverse

Polish Notation. Valid operators are+,-,*,/. Each operand may be aninteger or another expression. Some examples:

["2","1", "+", "3", "*"] -> ((2 + 1) * 3)-> 9

["4","13", "5", "/", "+"] -> (4 + (13 /5)) -> 6

class Solution{

public:

int evalRPN(vector &s){

stack store;

for(auto x : s){

if(x == "+" || x=="-" || x == "*" || x =="/"){//双引号

int a = store.top();store.pop();

int b = store.top();store.pop();

int c = 0;

if(x == "+"){

c = b + a;

}else if(x == "-"){

c = b - a;

}else if(x == "*"){

c = b * a;

}else{

c = b / a;

}

store.push(c);

}else{

store.push(atoi(x.c_str()));

}

return store.top();

}

};

[if !supportLists]3. [endif]最大点数

//题目：Givenn points on a 2D plane, find the maximum number of points that lie on the samestraight line.

class Solution{

public:

int maxPoints(vector&points){

int size = points.size();

int ans = size < 2 ? size : 2;

for(int i = 0; i < size; i++){

int count_i = 0;//与i重合的点数

for(int j = i + 1; j < size;j++){

int count_i_j = 1;//与i,j共线的点数

if(points[i].x == points[j].x&& points[i].y == points[j].y){

count_i++;

}else{

for(int t = j; t < size;t++){

if((points[i].x -points[j].x) * (points[t].y - points[j].y)

== (points[t].x -points[j].x) * (points[i].y - points[j].y)){

count_i_j++;

}

ans = max(ans, count_i +count_i_j);

}

return ans;

}

};

[if !supportLists]4. [endif]列表排序

//题目：Sorta linked list in O(n log n) time using constant space complexity.

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution{

public:

static int cmp(ListNode *a, ListNode *b){

return a -> val < b -> val;

}

ListNode *sortList(ListNode *head){

if(!head){

return NULL;

}

vector arr;

ListNode *p;

p = head;

while(p){

arr.push_back(p);

p = p -> next;

}

sort(arr.begin(), arr.end(), cmp);

p = head = arr[0];

for(int i = 0; i < arr.size(); i++){

p -> next = arr[i];

p = p -> next;

}

p -> next = NULL;

arr[arr.size() - 1] -> next = NULL;

return head;

}

};

[if !supportLists]5. [endif]对列表插入排序

//题目：Sorta linked list using insertion sort.

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution{

public:

ListNode *insertionSortList(ListNode *head){

if(!head || !head -> next){

return head;

}

ListNode L(0), *p;//L：object

L.next = insertionSortList(head ->next);//recursion

p = &L;

while(p && p -> next&& p -> next -> val < head -> val){

p = p -> next;

}

head -> next = p -> next;

p -> next = head;

return L.next;

}

};

复试上机练习题

推荐阅读更多精彩内容