⭐博客主页：️CS semi主页
⭐欢迎关注：点赞收藏+留言
⭐系列专栏：C语言进阶
⭐代码仓库：C Advanced
家人们更新不易，你们的点赞和关注对我而言十分重要，友友们麻烦多多点赞＋关注，你们的支持是我创作最大的动力，欢迎友友们私信提问，家人们不要忘记点赞收藏＋关注哦！！！

---

一、杨氏三角

（一）题目描述

有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。
要求：时间复杂度小于O(N);

（二）解题思路（三种思路）

大家第一个想到的就是遍历一整个数组，但我们此题的要求是时间复杂度小于O（N），所以就需要另辟蹊径了。
我们可以发现，杨氏三角是每行每列都是自左往右递增的，那就是右上角为整个二维数组中行中最大的，一列中最小的，左下角为整个二维数组中行最小的，一列中最大的，所以只要我们找一行中最大（或最小）的一列中最小（或最大）的元素与需要查找的数进行比较舍弃一整行或者一整列即可，缩断了很多时间。
所以此题有三种解法：
第一种解法是最简单理解的，但时间复杂度为O（N），就是直接全部遍历。
第二种解法是直接传值调用，就需要我们把行列的值传过去直接进行查找。
第三种解法是传址调用，将地址传到函数里面，然后通过指针去访问地址进行查找后告诉main函数找没找到。

（三）解题代码（三种解法）

//方法一、遍历整个数组
#include<stdio.h>
int main() {int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int k = 7;int x = sizeof(arr) / sizeof(arr[0]);int y = sizeof(arr[0]) / sizeof(arr[0][0]);int i = 0;int j = 0;int flag = 0;for (i = 0; i < x; i++) {for (j = 0; j < y; j++) {if (arr[i][j] == k) {flag = 1;goto out;}}}out:if (flag) {printf("找到啦，坐标为%d %d", i + 1, j + 1);}else {printf("找不到\n");}return 0;
}

//方法二、找地址直接通过访问地址改变值
#include<stdio.h>
int find_key(int arr[3][3], int *row, int *col, int k)
{	int i = 0;int j = *col - 1;while (i <= *row-1 && j >= 0)//判断条件不越界{if (arr[i][j] < k){i++;}else if (arr[i][j] > k){j--;}else{*row = i;//解引用找到的地址的值是i*col = j;//解引用找到的地址的值是ireturn 1;}}return 0;
}int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int k = 7;//查找的值int x = sizeof(arr) / sizeof(arr[0]);//行数int y = sizeof(arr[0]) / sizeof(arr[0][0]);//列数int ret = find_key(arr, &x, &y, k);if (ret == 0)printf("找不到\n");elseprintf("找到了，下标是:%d %d", x + 1, y + 1);return 0;
}

//方法三、通过传递行列元素进行比较
#include<stdio.h>
void find_key(int arr[3][3], int r, int c, int k)
{int i = 0;int j = c - 1;int flag = 0;while (i <= r - 1 && j>=0) {if (arr[i][j] > k) {j--;}else if (arr[i][j] < k) {i++;}else {printf("找到啦，坐标为：%d %d", i + 1, j + 1);flag = 1;break;}}if (flag = 0) {printf("找不到\n");}}int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int k = 7;//查找的值int x = sizeof(arr) / sizeof(arr[0]);//行数int y = sizeof(arr[0]) / sizeof(arr[0][0]);//列数find_key(arr, x, y, k);return 0;
}

那同样，我们选的是左下角的那个元素是同样的思路，这里不再过多赘述了。直接来代码：

//方法一、传值
#include<stdio.h>
void find_key_left (int arr[3][3], int r, int c, int k)
{int i = r - 1;int j = 0;int flag = 0;while (i >= 0 && j <= c - 1){if (arr[i][j] > k) {j++;}else if (arr[i][j] < k) {i--;}else {printf("找到啦，坐标为：%d %d", i + 1, j + 1);//flag = 1;break;}}if (flag = 0) {printf("找不到\n");}}int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int k = 7;//查找的值int x = sizeof(arr) / sizeof(arr[0]);//行数int y = sizeof(arr[0]) / sizeof(arr[0][0]);//列数find_key_left(arr, x, y, k);return 0;
}

//方法二、传址
#include<stdio.h>
int find_key(int arr[3][3], int *row, int *col, int k)
{	int i = *row - 1;int j = 0;while (i >= 0 && j <= *col - 1){if (arr[i][j] < k){i--;}else if (arr[i][j] > k){j++;}else{*row = i;*col = j;return 1;}}return 0;
}int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int k = 7;//查找的值int x = sizeof(arr) / sizeof(arr[0]);//行数int y = sizeof(arr[0]) / sizeof(arr[0][0]);//列数int ret = find_key(arr, &x, &y, k);if (ret == 0)printf("找不到\n");elseprintf("找到了，下标是:%d %d", x + 1, y + 1);return 0;
}

---

二、字符串左旋

（一）题目描述

实现一个函数，可以左旋字符串中的k个字符。
例如：
ABCD左旋一个字符得到BCDA
ABCD左旋两个字符得到CDAB

（二）解题思路（三种思路）

这里解题思路给三种解题思路，一次常规思路加上两次改进思路。
常规思路：
一个个拿，将前面的元素放到临时变量temp中再将临时变量的temp放到数组的结尾并将整个数组往左移动。

改进一：
逆序法。需要三次逆序，先逆序左边需要被左旋的字符串，再逆序右边不需要左旋的字符串，再逆序整体就可以得到想要的结果了。

改进二：
拼接法。先把需要左旋的后面的字符全部拷贝到一个临时的字符数组，再来个拼接需要左旋的那几个字符串，再拷贝回去。

（三）解题代码（三种解法）

//方法一、用临时变量
#include<stdio.h>
#include<string.h>void left_move(char arr[], int k) {//旋转1个并执行k次int i = 0;int len = strlen(arr);k %= len;//除去重复性工作for (i = 0; i < k; i++) {//旋转一个字符//1.先备份第一个元素char temp = arr[0];//2.整体往前移动int j = 0;for (j = 0; j < len - 1; j++) {arr[j] = arr[j + 1];}//3.把元素放到数组尾arr[len - 1] = temp;}
}int main() {char arr[] = "abcdef";int k = 2;//左旋转超过len的个数，是做了很多重复性的工作left_move(arr, k);printf("%s\n", arr);return 0;
}

#include<stdio.h>
#include<assert.h>
#include<string.h>
void Reverse(char* left, char* right) {assert(left);assert(right);while (left < right) {int temp = *left;*left = *right;*right = temp;left++;right--;}
}void left_move(char arr[], int k) {int len = strlen(arr);k %= len;//先逆序左边Reverse(arr, arr + k - 1);//再逆序右边Reverse(arr + k, arr + len - 1);//再逆序整体Reverse(arr, arr + len - 1);
}int main() 
{char arr[] = "abcdef";int k = 2;left_move(arr, k);printf("%s\n", arr);return 0;
}

//方法三、拼接法
#include<stdio.h>
#include<string.h>
void left_move(char arr[], int k)
{int len = strlen(arr);k %= len; //断开位置的下标char temp[100] = { 0 }; //更准确的话可以选择malloc len + 1个字节的空间来做这个tempstrcpy(temp, arr + k); //先将后面的全部拷过来strncat(temp, arr, k); //然后将前面几个接上strcpy(arr, temp); //最后拷回去
}int main() {char arr[] = "abcdef";int k = 2;//左旋转超过len的个数，是做了很多重复性的工作left_move(arr, k);printf("%s\n", arr);return 0;
}

---

三、字符串右旋

（一）题目描述

实现一个函数，可以左旋字符串中的k个字符。
例如：AABCD右旋一个字符得到DAABC。

（二）解题思路（两种思路）

常规思路：
只需要从最后一个字符出发，然后跟左旋一样的操作即可。
改进：
右旋2次岂不是左旋6-2次得来的吗，那不就是右旋k次是左旋len-k次来的吗！？

（三）解题代码（两种解法）

//方法一、创建临时变量
#include<stdio.h>
#include<string.h>void right_move(char arr[], int k) {//旋转1个并执行k次int i = 0;int len = strlen(arr);k %= len;//除去重复性工作for (i = 0; i < k; i++) {//旋转一个字符//1.先备份末尾元素char temp = arr[len - 1];//2.整体往后移动int j = 0;for (j = len - 1; j > 0; j--) {arr[j] = arr[j - 1];}//3.把元素放到数组末尾arr[0] = temp;}
}int main() {char arr[] = "abcdef";int k = 2;//右旋转超过len的个数，是做了很多重复性的工作right_move(arr, k);printf("%s\n", arr);return 0;
}

//方法二、字符串右移 -就是字符串左移len-k次
#include<stdio.h>
#include<string.h>void right_move(char arr[], int k) {//旋转1个并执行k次int i = 0;int len = strlen(arr);k %= len;//除去重复性工作k = len - k;for (i = 0; i < k; i++) {//旋转一个字符//1.先备份首元素char temp = arr[0];//2.整体往前移动int j = 0;for (j = 0; j < len - 1; j++) {arr[j] = arr[j + 1];}//3.把元素放到数组末尾arr[len - 1] = temp;}
}int main() {char arr[] = "abcdef";int k = 2;//右旋转超过len的个数，是做了很多重复性的工作right_move(arr, k);printf("%s\n", arr);return 0;
}

---

四、判断是否是左旋或右旋

（一）题目描述

一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。
例如：给定s1 =AABCD和s2 = BCDAA，返回1
给定s1=abcd和s2=ACBD，返回0.
AABCD左旋一个字符得到ABCDA
AABCD左旋两个字符得到BCDAA
AABCD右旋一个字符得到DAABC

（二）解题思路（两种思路）

常规思路：
直接将第一个数组进行左旋n次，看是不是有一次是和第二个数组是一样的即可，如果是一样的，那就第二个数组是第一个数组左旋来的，如果没有一样的，那就是第二个数组不是第一个数组左旋过来的。
改进：
再复制一份将复制的一份粘贴在原本的字符串后面，只需要判断第二个数组是不是第一个数组拼接后的字串即可。这里涉及了strncat和strtstr库函数的使用。那就在这块简单介绍一下，后期也会有博客链接进入我所制作的所有库函数的使用。

这是strcat库函数的使用。

这是strncat库函数的使用。

这是strstr函数的使用。

（三）解题代码（两种解法）

//方法一、将第一个字符串每次左旋1个字符
//并进入循环左旋整个字符串的数量次进行比较
#include<stdio.h>
#include<string.h>void left_move(char arr[], int k) {//旋转1个并执行k次int i = 0;int len = strlen(arr);k %= len;//除去重复性工作for (i = 0; i < k; i++) {//旋转一个字符//1.先备份第一个元素char temp = arr[0];//2.整体往前移动int j = 0;for (j = 0; j < len - 1; j++) {arr[j] = arr[j + 1];}//3.把元素放到数组尾arr[len - 1] = temp;}
}int is_left_move(char arr1[], char arr2[]) {int len1 = strlen(arr1);int len2 = strlen(arr2);if (len1 != len2) {return 0;}int i = 0;for (i = 0; i < len1; i++) {left_move(arr1, 1);if (strcmp(arr1, arr2) == 0) {return 1;}}return 0;
}int main() {char arr1[] = "AABCD";char arr2[] = "BCDAA";int ret = is_left_move(arr1, arr2);if (ret == 1) {printf("YES\n");}else {printf("NO\n");}}

//方法二、再复制一份一模一样的
//看是不是已经复制了一份的字串即可
//AABCDAABCD
//判断BCDAA是不是上面的字串
#include<stdio.h>
#include<string.h>
int is_left_move(char arr1[], char arr2[]) {int len1 = strlen(arr1);int len2 = strlen(arr2);char arr3[100] = { 0 };if (len1 != len2) {return 0;}strcpy(arr3, arr1);strncat(arr3, arr3, len1);if (strstr(arr3, arr2) != NULL) {return 1;}else {return 0;}
}int main() {char arr1[] = "AABCD";char arr2[] = "BCDAA";int ret = is_left_move(arr1, arr2);if (ret == 1) {printf("YES\n");}else {printf("NO\n");}}

---

五、猜凶手

（一）题目描述

日本某地发生了一件谋杀案，警察通过排查确定杀人凶手必为4个嫌疑犯的一个。
以下为4个嫌疑犯的供词:
A说：不是我。
B说：是C。
C说：是D。
D说：C在胡说
已知3个人说了真话，1个人说的是假话。
现在请根据这些信息，写一个程序来确定到底谁是凶手。

（二）解题思路（一种思路）

所以结果是C是凶手。
那我们用C语言实现的思路是我们将凶手进行遍历从A到D，再进行ABCD这四个人说的话进行真假判断，只要是三个成立的条件相加以后等于3即可，是不是很奇妙。

（三）解题代码（一种解法）

#include<stdio.h>
//假定有凶手名字叫killer
int main() {int killer = 0;for (killer = 'A'; killer <= 'D'; killer++) {if ((killer != 'A') + (killer == 'C') + (killer == 'D') + (killer != 'D') == 3) {printf("凶手是：%c\n", killer);}}return 0;
}

---

六、杨辉三角

（一）题目描述

在屏幕上打印杨辉三角。
1
1 1
1 2 1
1 3 3 1
……

（二）解题思路（一种思路）

杨辉三角，是二项式系数在三角形中的一种几何排列。在欧洲，这个表叫做帕斯卡三角形。帕斯卡（1623----1662）是在1654年发现这一规律的，比杨辉要迟393年，比贾宪迟600年。杨辉三角是中国古代数学的杰出研究成果之一，它把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。
在进行杨辉三角形的打印的时候，我们发现第一行和第二行全是1，当第三行以后，中间的值是根据上面的数相加所获得的的，而对角线是全1，按照题设的场景，能发现数字规律为：d[i][j] = d[i - 1][j] + d[i - 1][j - 1]。所以我们只要按照这个方法填表即可。

（三）解题代码（一种解法）

#include<stdio.h>void YHTriangle(int n){//第一行直接填1int yhs[30][30] = { 1 }; //第二行填两个1yhs[1][0] = 1;yhs[1][1] = 1;int i = 0;int j = 0;//从第三行开始填for (i = 2; i < n; i++) {yhs[i][0] = 1; //每行的第一列都是1for (j = 1; j <= i; j++) //从第二列开始填{yhs[i][j] = yhs[i - 1][j] + yhs[i - 1][j - 1]; //递推方程}}//打印for (i = 0; i < n; i++) {for (j = 0; j <= i; j++){printf("%3d ", yhs[i][j]);}if (i < n - 1) {//最后一行不换行printf("\n");}}
}int main() {int n = 0;scanf("%d", &n);YHTriangle(n);return 0;
}

---

七、猜名次

（一）题目描述

5位运动员参加了10米台跳水比赛，有人让他们预测比赛结果：
A选手说：B第二，我第三；
B选手说：我第二，E第四；
C选手说：我第一，D第二；
D选手说：C最后，我第三；
E选手说：我第四，A第一；
比赛结束后，每位选手都说对了一半，请编程确定比赛的名次。

（二）解题思路（一种思路）

思路1：比较常规的思路是，直接遍历5个人的名次，判断话为真则输出为1，话为假则输出为0，所以只需要将一个人的两句话的判断加起来即可，只要是等于1即可，然后五个人的话各自参半用&&符号连接即可，但不要忘了的是每个人的名次是独立的，仅仅判断每个人是一半话是正确的那有很多种情况，有可能导致有两个第5名的情况，所以就需要再加一个条件就是相乘等于120。

（三）解题代码（一种解法）

//方法一、常规思路
//直接按照A,B,C,D,E五个人的名次从1遍历到5即可
//同时每个人的话的一半是正确的
//所以第一句话判断是否为真再加上第二句话判断是否为真即可
#include<stdio.h>
int main() 
{int A = 0;int B = 0;int C = 0;int D = 0;int E = 0;for (A = 1; A <= 5; A++) {for (B = 1; B <= 5; B++) {for (C = 1; C <= 5; C++) {for (D = 1; D <= 5; D++) {for (E = 1; E <= 5; E++) {//只要是两句话中相加等于1即可，即一半是对的if ((B == 2) + (A == 3) == 1 &&(B == 2) + (E == 4) == 1 &&(C == 1) + (D == 2) == 1 &&(C == 5) + (D == 3) == 1 &&(E == 4) + (A == 1) == 1&&(A * B * C * D * E == 120)) //保证A，B，C，D，E五个人的名次是独立的{printf("A=%d B=%d C=%d D=%d E=%d", A, B, C, D, E);}}}}}}return 0;
}

---

总结

编程题的联系会让自身的代码能力得到很大的提升，不仅仅是掌握了知识，更是应用了这些知识，唯一有遗憾的是猜名次这道题，有更多种解法，这种解法也只是最简单的解法，还有哈希法进行解决，所以，待我学成归来，一定将这道题目进行改造，改造的更加方便完美。

---

客官，阅读到这儿了，来个三连支持一下吧！！！