零、说明

• 第一部分 是平时学习 做真题 做参考书练习 群友提问等等渠道获取到的个人认为比较有价值的题目
• 第二部分和第三部分 是根据真题+题目热度挑选的题目
• 本文的难度仅针对普通院校自命题的编程题!
• 如果一道题确实有两种不同的解法(主要体现在时空复杂度确实有改善 或者思路不一样 比如迭代法和递归法) 本文会分为解法1 解法2进行介绍
• 一般情况下 最多能写到力扣官方题解的第一或者第二层 大概可以应付考研的编程题 而力扣官方题解更高级的 甚至站在数学角度上去思考 我也无能为力用代码或图片讲述清楚!

1. 必要的时候我会写题目描述;
2. 不同的解法思路 我会写上对应的思路+我的错因+我的参考代码 仅供参考
3. 如果有 还会写本题的总结和一些反思

一、程序设计经典编程题(C语言实现)

T1 求1~100的奇数

解法1 暴力求解:

---

解法2: 思考思考 只要知道第一个奇数 后面的+2+2+2不就行了?

---

总结:

1. 解法1 循环一百次 判断一百次
2. 解法2 循环五十次 不需要判断
3. 初步领略一下算法的魅力 要多思考
4. 类似的 下面这道题就可以从3开始打印 每次+3+3+3 而不需要遍历 判断 再打印了
   
5. 还有一种思路:
   

T2 求n!

1. 本题很简单 就是累乘
2. 但是我眼睛瞎起来就把ret定义为0 答案恒为0了

参考代码:

	int n = 5;int i = 0;int ret = 1;//别写成0了for (i = 1; i <= n; i++)ret *= i;printf("%d\n", ret);

T3 求1!+2!+3!+…+10!

解法1:

• 思路:两层循环 第一层循环产生1~10的数据 第二层循环求出1! 2! 3!..并累加
• 注意这种写法 每次求单独求阶乘的时候 ret一定要置为1
  
• 这种解法不够好 因为有大量的重复计算 将在解法2改进

	int n = 3;//求1! + 2! + 3!int i = 0;int j = 0;int ret = 1;//每次求单独的阶乘的时候就用它int sum = 0;for (int j = 1; j <= n; j++){ret = 1;//所以要记得置为1啊!! 要不然第求下一次阶乘的时候 ret就不是从1开始乘的了for (i = 1; i <= j; i++)ret *= i;sum += ret;}printf("%d", sum);

---

解法2:

• 思路:其实在计算10!的时候 已经出现了1! 2! 3! … 9! 既然如此 就可以一边计算 一边累加 避免了重复计算
• 解法2更好 是经过思考的

int main()
{int n = 10;int i = 0;//控制循环int ret = 1;//用于产生1! 2! 3!...10!int sum = 0;for (i = 1; i <= n; i++){ret *= i;//在产生10!的过程中 其实已经产生了1! 2! 3!...sum += ret;//边乘边加}printf("%d ", sum);return 0;
}

T4 在一个有序数组中查找具体的某个数字n(二分查找)

解法1 直接暴力求解:

---

解法2 二分查找:

1. 前提是:有序 所以不能乱给测试数组
2. right = mid-1; left = mid+1; 我一开始没有+-1 会导致死循环
3. int right = len - 1; -1别忘记了 right是下标
4. 出循环之后有两种写法 可以利用flag 也可以直接判断

写法一:

#include<stdio.h>
int main()
{int arr[10] = { 1,2,3,4,5,6,7,8,9,11 };//测试数组 一定是有序的int len = sizeof(arr) / sizeof(int);//数组元素个数int k = 11;//查找目标int flag = 0;//假设一开始默认找不到k 找到了就把第flag置为1int left = 0;int right = len - 1;int mid = 0;// = 也是可以取的 当left=right的时候 肯定还要进去判断一次while (left <= right){//每次进循环 都要算出一个新的mid进行判断mid = (left + right) / 2;if (arr[mid] < k)//说明k在mid的右边{left = mid + 1;}else if (arr[mid] > k)//说明k在mid的左边{right = mid - 1;}else{//这里已经可以输出mid的信息了 但是我放在下面打印//把提示信息统一都放在循环外处理flag = 1;break;}}//程序执行到这 有两种可能//1.while全都判断完 自然结束 也就是最终没找到k 此时flag = 0//2.flag = 1之后 break到这里来if (flag)printf("找到了下标是:%d\n", mid);elseprintf("没找到");return 0;
}

写法二: 主要差异在于出循环之后 我怎么输入"没找到"比较合适

int main()
{int arr[10] = { 1,2,3,4,5,6,7,8,9,10};int num = 0;while (2){printf("输入你要查到的数字:\n");scanf("%d", &num);int left = 0;int right = (sizeof(arr) / sizeof(int))-1;int mid = 0;while (left <= right){mid = (left + right) / 2;if (arr[mid] > num)right = mid-1;else if (arr[mid] < num)left = mid+1;else{printf("找到了 下标是%d\n", mid);break;}}//走到这里 有两种情况 1.找到了break出来 2.没找到 但是left不<=right 循环结束了//我直接判断一下此时mid对应的元素是不是num就能确定找没找到了 不需要flag也行if (arr[mid] != num)printf("没找到\n");}return 0;
}

T5 编写代码，演示多个字符从两端移动，向中间汇聚

题目描述:
打印hello world!
############
h##########!
he########d!
hel######ld!
hell###r#ld!
hello##orld!
hello world!

---

解法1:

1. 双"指针" 一左一右 开始打印有效字符
2. 每次肯定都是打印十个字符 打印几次由while来决定
3. left和right把10个要打印的字符分成三部分 [0,left]打印对应的有效字符 [right,len-1]打印对应的有效字符 剩余部分打印#
4. 相较于思路2 更节省空间

错因:

1. 打印#的判断条件写错了 左右不分??!! 开区间(left,right)范围打印#
2. 每一次for循环结束 不要忘记++和-- 也不要忘记换行

#include<stdio.h>
#include<windows.h>
#include<string.h>
int main()
{char ch[] = "hello world!";int len = strlen(ch);//12int left = 0;int right = len - 1;int i = 0;while (left<=right){for (i = 0; i < len; i++){if (i > left && i < right) //易错printf("#");elseprintf("%c", ch[i]);}printf("\n");Sleep(1000);left++;right--;}return 0;
}

---

解法2:

1. 给出两个数组 一个是字符 一个是# 注意#和字符的个数肯定都是一样的
2. 然后也是用了两个指针 一左一右依次把字符赋给放#的那个数组
3. 打印的时候 用%s专门只打印#的那个数组即可

错因:

1. len–>求的是元素个数 也就是字符个数 故下标最大值是len-1
2. 判断部分是<= 当左右指针指向同一个元素的时候 也要进入循环的

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<windows.h>
#include<string.h>
int main()
{char ch1[] = "zhuchenyang66dds6!";char ch2[] = "******************";int len = strlen(ch1);int left = 0;int right = len - 1;for (left = 0, right = len - 1; left <= right; left++, right--){ch2[left] = ch1[left];ch2[right] = ch1[right];printf("%s\n", ch2);Sleep(100);}return 0;
}

或者写成while循环 都是一样
Sleep()的头文件是windows.h
system()的头文件是stdlib.h

T6 模拟用户登录(三次机会)

题目描述:
编写代码实现，模拟用户登录情景，并且只能登录三次。（只允许输入三次密码，如果密码则提示登录成，如果三次均输入错误，则退出程序。

---

解法1 利用strcmp函数:

1. 定义要输入的密码 正确密码 count是还剩下几次机会
2. 只要count还没==0 就可以进去输入密码

我的错因:

1. 一开始用的是下图这种定义方式 这样定义的话 其实数组大小是确定的 数组里放了一个空格 一个\n 元素个数(strlen)是1 大小(sizeof)是2字节 下面输入密码肯定会越界的

2. 比较字符串是否相等 不能用== 要用strcmp()函数 第一个参数比第二个参数大 就返回>0 相等的话返回0

#include<stdio.h>
#include<string.h>
int main()
{char pswd[100] = " ";char answer[100] = "zhukefu123";int count = 3;while (count>0){printf("您还有%d次机会,请输入密码:\n",count);scanf("%s", pswd);if (strcmp(pswd, answer) != 0){printf("密码错误!\n");count--;continue;}else{printf("密码正确!\n");break;}}if (count == 0)printf("您没有机会了!!\n");return 0;
}

---

解法2 直接暴力求解 相当于模拟实现了strcmp:

1. 这里我犯了一个离谱的错误 多打了一个; 也就是这个if 啥也不干! 然后继续往下执行!
   
2. 下图这部分写错了 左闭右开的话 右边就是循环次数 也就是字符串长度 是不需要-1的 -1会导致少判断最后一个字符 也就是zcygst667也被算成密码正确了
   
3. char ch[10] = " "; 10给的太小了!!! 要么限定用户只能输入多少的字符(一般交给前端限制) 要么给大点 否则 如果我测试的时候输入了一个zcysdshjadhshkd 会有栈溢出err
4. 这个错误算是值得注意的点 我要是用flag这种写法的话 每次给你一次新机会输入密码的时候 flag都应该重置为1!!!! 否则在以下情况会出现问题: 当我第一次输入zcygst667 进入for的时候 把flag置为0 如果我后面输入了正确密码zcygst666 虽然不会执行flag=0 但是for循环出来走到if (flag == 1)的时候 发现flag上次已经给他置为0了 所以不进入if 直接继续下一次循环了 仿佛跳过了这次正确的输入
5. 主要就三个点的错误(下图已经修正)
   

int main()
{int total = 8;int i = 0;char ch[1000];char real[1000] = "zcygst666";int flag = 1;while (total > 0){flag = 1;scanf("%s", ch);if (strlen(real) == strlen(ch)){for (i = 0; i < strlen(ch); i++){if (ch[i] != real[i]){printf("错误\n");total--;flag = 0;printf("还剩%d次机会\n", total);break;}}//程序走到这这里 //1.break出来的  flag已经是0//2.判断发现全相等 循环自然结束 flag仍然是1if (flag == 1){printf("正确\n");break;}}else{printf("两个字符串长度都不一样!!错误\n");total--;printf("还剩%d次机会\n", total);}}return 0;
}

---

• 其实我想说的是 针对解法2那个flag置为1的错误 还是要具体问题具体分析的 具体看自己的思路是什么 灵活编写代码
• 比如下面的代码(一开始给flag初始化的是0 密码正确再改为1) 就不需要每次都置为1 所以要多写多练多反思 该置为1的时候 我自己心里有数就行

int main()
{int i = 10;char real[20] = "zcygst";char input[20];int flag = 0;while (i > 0){scanf("%s", input);if (strcmp(real, input) != 0){//密码错误 那就不要动flag 本身就是0!i--;printf("err还剩%d次机会\n", i);}else{//输对了才改为1flag = 1;printf("yes\n");break;}}//1.要么是break到这里的时候 此时flag为1//2.要么就是一次都没输对 不满足i>0跳到这里来 此时flag一直保持是0if (flag == 0)printf("你没机会了\n");return 0;
}

T7 输入三个数 并从大到小输出

思路:
确定三个数了 用排序似乎有点小题大做了
其实比较三次即可 保证a放的最大 c放的最小 然后打印abc即可
而且三次比较都要交换 不如封装成一个函数 但是注意这个函数就必须要传地址了

#include<stdio.h>void swap(int* x,int* y)
{int tmp = *x;*x = *y;*y = tmp;
}int main()
{int a = 1;int b = 1;int c = 1;printf("请输入三个数:>\n");scanf("%d %d %d", &a, &b, &c);//目标:让a里放最大 b其次 c最小//前两个if可以保证a最大 第三个if让c最小if (a < b)swap(&a, &b);if (a < c)swap(&a, &c);if (c > b)swap(&b, &c);//从大到小输出printf("%d %d %d", a, b, c);return 0;
}

T8 打印100~200的素数(质数)

思路:

1. 素数只能被1和本身整除 如果能找到一个非1非本身的因数 就可以判断不是素数
2. 判断i是不是素数的时候 可以从闭区间[2,i-1]试除
3. 优化1:只要试除[2,根号i] 比如16 如果有因数 一定是成对出现的 比如1-16 2-8 4-4 如果只看一半的话 肯定是不会大于根号16的(≤)
4. 优化2:偶数肯定不是素数 直接从101开始 每次i+2 从奇数里面找素数
   
5. double sqrt (double x);需要math.h的头文件 不放心的话循环里也可以强转成int
6. 以上的方法 都叫"试除法" 推荐博文:<<素数求解的N种境界>>

#include<stdio.h>
#include<math.h>
int main()
{int i = 0;int j = 0;int flag = 1;//产生100-200的素数for (i = 100; i <= 200; i++){//每次产生的i 开始都先认为他是个素数flag = 1;//这里是<=啊 写<的话 49也被判断成素数了for (j = 2; j <= (int)sqrt(i); j++){if (i % j == 0){flag = 0;//那就不是素数break;//只要有一次能进来 就直接break了}}//走到这儿来 可能是//1.break到这儿来 此时flag=0 //2.循环条件结束 此时flag仍未1 也就是i%j一次都不等于0 没机会把flag置为0 说明是素数if (flag)printf("%d ", i);}return 0;
}

T9 打印1000~2000之间的闰年

1. 能被4整除 但是不能被100整除的 是闰年
2. 能被400整除 也是闰年
3. 其实可以i+=4 从1.2.的规则来看 闰年肯定能被4整除

	int i = 0;for (i = 1000; i <= 2000; i++){if ((i % 400 == 0) || ((i % 4 == 0) && (i % 100 != 0)))printf("%d ", i);}

注意了 如果要用if来写的话
就是俩个if(并列关系 都需要判断的)
而不能是else if(非此即彼 只有一个入口)了
如果写的是else if 2000本身是闰年 但是判断他不是 因为只能进去第一个if

T10 求最大公约数(含递归)

解法1:暴力求解
两个数的最大公约数的范围肯定是[1,较小值]
比如18和6 最大公约数不可能超过6 所以从1到6找就行

	int m = 18;int n = 24;//假设m和n的较小值为最大公约数int min = m > n ? n : m;//然后从较小值开始 往下试除int i = 0;for ( i = min; i >= 1; i--){if ((m % i == 0) && (n % i == 0))break;}printf("%d", i);

• 下图是while的写法
  

---

解法2:辗转相除法:
主要用到的一个结论就是:(a,b)的最大公约数等于(b,a%b)的最大公约数
最大公约数：即两个数据中公共约数的最大者。
思路：
例子：18和24的最大公约数
第一次：a = 18 b = 24 c = a%b = 18%24 = 18 再使:a = 24 b=18
第二次：a = 24 b = 18 c = a%b = 24%18 = 6 再使:a = 18 b = 6
第三次：a = 18 b = 6 c=a%b = 18%6 = 0 循环结束 此时的b就是最大公约数
下面有两种不同的风格写法 建议写第二种

int main()
{int m = 18;int n = 24;int k = m % n;while (k != 0){m = n;n = k;k = m % n;}printf("%d", n);return 0;
}

int main()
{int a = 18;int b = 24;int c = 0;//当某一次 c = a%b = 0  为假了 就不进去循环了 此时b就是最大公约数while(c=a%b){a = b;b = c;}printf("%d\n", b);return 0;
}

---

解法3:递归法
可以看出 求18 24->求24 18->求18 6(递归的出口)
递归的关键在于能否找到子问题

#include<stdio.h>void IsCommon(int a, int b)
{if (a % b == 0){printf("最大公约数是%d ", b);return;}elseIsCommon(b, a % b);
}int main()
{int a;int b;while (1){scanf("%d %d", &a, &b);IsCommon(a, b);}}

补充:辗转相除法的证明

详细的证明过程可以参考:
辗转相除法原理

注意除了参考视频里的两个结论,具体实现证明还需要引入一个公理:整数a,b的最大公约数d1一定大于or等于整数a,b,c的最大公约数d2的(当c有一个约数恰好是d1时取等号)

T11 求最小公倍数

设两数的最大公因数=X
则：两数可以表示为：aX,bX(a,b一定互质)
所以aX,bX的最小公倍数=abX=(aX*bX)/X
即最小公倍数=两数之积/最大公约数

那么也可以进一步
证明出两个数的乘积 = 最大公因数与最小公倍数的乘积
即aX*bX = X*(abX)=(aX)*(bX)

代码思路:
暴力求解的话和前面类似 不过这次是拿两者较大的值开始试
比如6和8的最小公倍数 就用[8,6*8]的范围试
或者先求出最大公约数 然后最小公倍数就 = 两数之积/最大公约数
注意:如果用int，最小公倍数可能会溢出 建议结果用long long保存

二、力扣

面试题 17.04. 消失的数字

题目链接

1. 解法一:首先^遵循交换律 且0^N=N N^N=0 把所有的元素都^起来 相同的都成0 剩下一个单独的 就是消失的数字 相当于找单身狗
2. 解法二:既然题目描述里的n 其实应该等于numsSize 也就是我应该有的元素是0,1,2,3,4,n(numsSize) 把他们全都加起来去减数组的值 结果就是那个孤儿
3. 解法二还可以优化 1-n求和直接用公式 都不需要遍历

//我的代码:
int missingNumber(int* nums, int numsSize) {int ret = 0;int sum = 0;for (int i = 0; i < numsSize; i++) {scanf("%d", &nums[i]);ret = ret ^ nums[i];ret = ret ^ i;}ret = ret ^ numsSize;//思路二:// for (int i = 0; i <= numsSize; i++) {//     sum += i;// }// for (int i = 0; i < numsSize; i++) {//     scanf("%d", &nums[i]);//     sum -= nums[i];// }return ret;
}

三、牛客网

BC49 判断两个数的大小关系

题目链接

• 这题很简单 主要是学习一下牛客网多组输入的写法
• 读取失败返回EOF 如果不是EOF那肯定读取成功

#include<stdio.h>
int main() {int n1 = 0;int n2 = 0;while (scanf("%d %d", &n1, &n2) == 2) {if (n1 == n2)printf("%d=%d\n", n1, n2);else if (n1 > n2)printf("%d>%d\n", n1, n2);elseprintf("%d<%d\n", n1, n2);}return 0;
}

循环条件也可以写成:while (scanf("%d %d", &n1, &n2) != EOF)

OR62 倒置字符串

题目链接
● 其实最后我觉得 这里让我混淆的最大原因就是 要考虑空格和\0两个情况 尤其是\0
● 而且感觉最难的一步就是想不到要做两步reverse就行
● 然后我肯定就顺着直接输入一个字符串的思路去想了 鹏哥给的思路是两次reverse 我就想实现他的思路
● 其实我的思路就是第一次整体reverse之后 下面肯定要有两个不断变化的指针 每次都指向首元素和末尾元素(我犯了两个错误 在交换每个元素的时候 一个是没有考虑最后一个元素交换时候的\0 还有一个就是空格是不需要交换)
最终我的代码: 详细过程见语雀笔记

#include <stdio.h>
#include<string.h>void reverse(char* left, char* right) {while (left < right) {char tmp = *left;*left = *right;*right = tmp;left++;right--;}
}
int main() {char arr[100];gets(arr);//整体reversechar* left = arr;char* right = arr + strlen(arr) - 1;reverse(left, right);char* start = arr;//每次记录起始位置char* find = arr;//协助寻找末尾位置//这里必须要定义一个find 相当于临时变量的作用
//要不然的话 会修改start的值 传参就错了while (1) {//寻找末尾while (*find != ' ' && *find != '\0') {find++;}//找到了char* end = find - 1;//reverse当前锁定的元素reverse(start, end);//判断是不是最后一次reverseif (*find == '\0')break;//如果不是 更新收尾 继续reverseelse//这里的写法要小心 如果要继续找 那就是先把find++//然后再作为下一轮reverse的start的值start = ++find;}printf("%s", arr);return 0;
}

BC84 计算y的值

题目链接

• 那么有的朋友就要问了 这么简单的题放进来侮辱我的智商? 举报点踩拉黑了

• 主要还是因为我第一次写的时候居然写了2个if1个else 一般是讨论单值函数的! 只有一个入口!
  

• 正确:x和y是一一映射关系 只有一个入口

#include <stdio.h>int main() {int x;int y;while (scanf("%d", &x) != EOF) {if (x < 0)y = 1;else if (x == 0)y = 0;elsey = -1;printf("%d\n",y);}return 0; 
}

BC101 班级成绩输入输出

题目链接

• 注意点1:每次循环求和之前 sum置为0不要忘记了 否则第一位同学是对的 第二位同学的总分 是接着上一位的sum继续算的
• 注意点2:下面如果写scanf(“%f”,&score); 就是错的 读取到的都是0
• 对于scanf来说 double->%lf; float->%f
• 对于printf来说 浮点数double和float都用%f是没问题的
• 注意点3:看清题目 明明是保留1位小数了!! %.1f
  我写的参考答案:
还是稍微有点投机取巧的 因为这是OJ 一边输入 一边输出 一边求和

#include<stdio.h>
int main()
{double score;double sum = 0;for(int i = 0;i<5;i++){sum = 0;for(int j = 0;j<5;j++){scanf("%lf",&score);printf("%.1f ",score);sum+=score;}printf("%f",sum);printf("%c",'\n');}return 0;
}

弄一个数组逻辑上更好:
下面这个代码还有错 输出那部分的while忘记给j++了 死循环了

BC23 时间转换

题目链接
思路1:分别算时分秒

• 注意是3661s一共是几小时几分钟几秒 而不是分别转换成时分秒
• 小时:3661/3600 看看里面有几个3600s 也就是几个h
• 分钟:3661/60 看看里面有几个60s 也就是几分钟 再%60 因为满60分钟就要进位给h了 剩下的就是不满60分钟不能进位的 也就是分钟数
• 秒:其实很简单 直接%60 或者/1%60 逻辑更统一 先看看有多少个1s 然后再%60 因为满60s就要进位给分钟了 剩下的就是秒数部分

#include <stdio.h>
int main() {int seconds = 0;scanf("%d", &seconds);printf("%d %d %d", seconds / 3600, seconds / 60 % 60, seconds % 60);return 0;
}

#include <stdio.h>
int main() {int a;while (scanf("%d", &a) != EOF) {printf("%d %d %d", a / 3600, a / 60 % 60, a / 1 % 60);}return 0;
}

思路2:连着算

• 一开始算小时数肯定都一样 区别在于后面算分秒的时候 是接着上次的结果算的
• 3661%3600 就把能凑成1h的秒数都去掉了 剩下的秒数/60就是分钟数部分 %60就是秒数部分
• 认为思路二更清晰
  

BC50 计算单位阶跃函数

题目链接

• 这波真没有侮辱智商 而是突然发现printf里可以直接打印字符串 总感觉以前都没注意到过
• 可参考C语言复习第0章 4.7