算法笔记 02 —— 入门模拟

本系列为胡凡编著的算法笔记当中代码部分的精简版整理，笔者也在同时准备Leetcode刷题和实习面试，希望为有一定编码和数据结构基础的同学提供一份系统型的参考，以方便遗忘时的算法查阅、期末复习总览以及C++学习参照。

目录

01 简单模拟

Ⅰ害死人不偿命的（3*n+1）思想

Ⅱ 挖掘机技术哪家强

02 查找元素 —— 找 x

03 图形输出 —— 跟奥巴马一起编程

04 日期处理 —— 日期差值

05 进制转换

Ⅰ D 进制的 A+B

06 字符串处理

Ⅰ 回文串

Ⅱ 说反话

---

01 简单模拟

Ⅰ害死人不偿命的（3*n+1）思想

#include <iostream>
using namespace std;int CalCallatz(int n){int k = 0;while(n != 1){if(n % 2 == 0){n /= 2;}else{n = (n * 3 + 1) / 2;}k++;}return k;
}int main(){int n;scanf("%d", &n);int count;count = CalCallatz(n);printf("%d", count);return 0;
}

Ⅱ 挖掘机技术哪家强

#include <iostream>
using namespace std;int main(){int N;scanf("%d", &N);//输入名单int school[100000] = {0};int k, score, flag1 = 0;for(int i = 0; i < N; i++){scanf("%d%d", &k, &score);school[k] += score;if(k > flag1) flag1 = k; //flag1记录学校个数}//查找最大int maxScore = 0, flag2 = 0;for(int i=0; i<=flag1; i++){if(school[i] > maxScore){maxScore = school[i];flag2 = i; //flag2记录最大学校编号}}printf("%d %d", flag2, maxScore);return 0;
}

02 查找元素 —— 找 x

#include <iostream>
using namespace std;
const int MAXN = 210;int main(){int n, x, num[MAXN] = {0};while(scanf("%d", &n) != EOF){ //1 输入多组数据for(int i=0; i<n; i++){scanf("%d", &num[i])}scanf("%d", &x);for(int i=0; i<n; i++){if(num[i] == x){printf("%d\n", i);break; //2 节省查找时间}}if(i == n){printf("-1\n") //3 没找到也要答复一下}}return 0;
}

03 图形输出 —— 跟奥巴马一起编程

#include <iostream>
using namespace std;int main(){int N;char c;scanf("%d %c", &N,,&c); //1 注意%d和%c之间的空格for(int i=0; i<N; i++){printf("%c", c);}printf("\n");for(int i=0; i<(int)((N + 1) / 2 - 2); i++){printf("%c", c);for(int j=0; j<(N-2); j++){printf(" ");}printf("%c\n", c);}for(int i=0; i<N; i++){printf("%c", c);}return 0;
}

04 日期处理 —— 日期差值

#include <iostream>
using namespace std;//1 分解年月日
//2 年分365、366天，月分29、30、31天
//3 数据比大小，小的做加法int specialYear(int x){if(x % 4 == 0 && x % 100 != 0)return 1;else return 0;
}int main(){int data1, data2;int y1, y2, m1, m2, d1, d2;//4 二维数组，巧妙地把月份和年份联结起来int month[13][2] = {{-1,-1}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31}, {31, 31},{30, 30},{31, 31}, {30, 30}, {31, 31}};while(scanf("%d%d", &data1, &data2) != EOF){if((data1 - data2) < 0){int temp = data1;data1 = data2;data2 = temp;}d1 = data1 % 100, m1 = (data1 / 100) %100, y1 = data1 / 10000;d2 = data2 % 100, m2 = (data2 / 100) %100, y2 = data2 / 10000;int count = 0;while(!(y1 == y2 && m1 == m2 && d1 == d2)){d2++;count++;if(d2 == month[m2][specialYear(y2)] + 1){m2++;d2 = 1;if(m2 == 13){m2 = 1;y2++;}} }printf("%d\n", count);}return 0;
}

05 进制转换

对一个 P 进制的数，如果要转换为 Q 进制，需要分为两步：

① 将 P 进制数 x 转换为十进制数 y。

int x, P;
scanf("%d%d", &x, &P);int y = 0, product = 1;
while(x != 0){y = y + (x % 10) * product;x = x / 10;product = product * P;
}

② 将十进制数 y 转换为 Q 进制数 z。

采用 “除基取余法”。每次将待转换数 y 除以 Q，得到的余数作为低位存储，得到的商继续除以 Q 并重复上述操作，最后商为 0 时，将所有位从高到底输出得到 z。

int Q;
scanf("%d", &Q);int z[40], i = 0;
//如果十进制数y恰好等于0，那么使用while语句会使循环直接跳出，而非存放z[0]=0
do{z[i] = y % Q;y = y / Q;i++;
}while(y != 0);while(i != -1){printf("%d", z[i]);i--;
}

Ⅰ D 进制的 A+B

#include <iostream>
using namespace std;int main(){int A, B, D;scanf("%d%d%d", &A, &B, &D);int C = A + B;//除基取余法int num[40], i = 0;do{num[i++] = C % D;C /= D;}while(C != 0);while(i != -1){printf("%d", num[--i])}return 0;
}

06 字符串处理

Ⅰ 回文串

#include <iostream>
using namespace std;int main(){char str[255];gets(str);int len = strlen(str); //1 字符串长度strlen()for(int i = 0; i < (len / 2); i++){if(str[i] != str[len - 1 - i]){ printf("NO.");}}if(i == len / 2){printf("Yes.")}return 0;
}

Ⅱ 说反话

#include <iostream>
using namespace std;int main(){char str[80], word[80][80] = {(0, 0)};while(gets(str) != EOF){int m = 0, n = 0;for(int i=0; i<strlen(str); i++){if(str[i] != ' '){word[m][n++] = str[i];}else{word[m][n] = '\0'; //1 末尾是结束符\0m++;n = 0;}}while(m != 0){puts(word[m--]);printf(" ");}//2 最后一个单词之后输出空格会导致 “格式错误”puts(word[0]);}return 0;
}