【C语言】解题训练
目录
字符串左旋
方法1
方法2
字符串旋转结果判断
方法1
方法2
杨氏矩阵
位段
题目1
题目2
联合体
题目1
题目2
有序序列合并
变种水仙花
找单身狗
字符串左旋
实现一个函数，可以左旋字符串中的k个字符。
例如：
ABCD左旋一个字符得到BCDA
ABCD左旋两个字符得到CDAB
解题：
方法1
不可能把a直接放到f上，因为会覆盖掉f，所以需要另找一块空间。
第一步：找一块空间放a；
第二步：把a后面的元素分别都向前移一位；（知道总元素个数，用下标做到）
第三步：在原本放f的位置上放a；
这三步实现一次左旋。
#include
#include
void left_move(char* str, int k)
{int i = 10;//左旋k个字符：for (i = 0; i < k; i++){//每次左旋一个字符：char tmp = *str;int len = strlen(str);int j = 0;//把所有元素都向前移了一步，数据不会覆盖、丢失：for (j = 0; j < len - 1; j++)//处理len-1次，处理len-1个字符,len最大len-2{*(str + j) = *(str + j + 1);//len-2+1是len-1，len-1+str就是把最后一个字符向前移一下}*(str + len - 1) = tmp;//f的下标是5，所以是len-1}
}
int main()
{char arr[] = "abcdef";int k = 0;scanf("%d", &k);left_move(arr, k);printf("%s\n", arr);return 0;
} 方法2
假设对abcdef进行左旋两个字符：
1. 把两个字符逆序：bacdef
2. 把两个字符后面的字符也逆序：bafedc
3. 把整个字符串逆序：cdefab，即实现了左旋两个字符
这是经典的方法：三步翻转法——对前一部分进行逆序，后一部分逆序，整个字符串再逆序。
#include
#include
//逆序字符串
void reverse(char* left, char* right)
{//逆序while (left < right){//一次逆序char tmp = *left;*left = *right;*right = tmp;left++;right--;}
}
void left_move(char* str, int k)
{//逆序k个字符，第k个字符的下标是k-1,则第k个字符的地址是str+k-1//第k+1个字符的下标是k,则第k个字符的地址是str+k//最后一个字符的下标是len-1,则其地址是str+len-1//若输入的k过大就会导致越界，则对k进行取模处理：//若k=10,而只有6个字符，因为前6次左旋后逆序又变成自己原来的字符串的顺序，所以k%lenint len = strlen(str);k %= len;//此时左旋10个字符和左旋4个字符是一样的reverse(str, str + k - 1);//逆序k个字符的前部分reverse(str + k, str + len - 1);//逆序后一部分reverse(str, str + len - 1);//整体逆序
}
int main()
{char arr[] = "abcdef";int k = 0;scanf("%d", &k);left_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
解题：
就是判断s2是不是s1旋转得来的：
即把s1先左旋转1个判断是否相等，s1先左旋转2个判断是否相等，s1先左旋转3个判断是否相等……旋转、判断；旋转、判断……把所有旋转的结果可能性都判断一下，若都不相等则就不是旋转得来的。
注意：共有5个字符时，左旋转5个和左旋转0个是一个意思。
方法1
旋转1次：ABCDA
旋转2次：BCDAA
旋转3次：CDAAB
旋转4次：DAABC
旋转5次：AABCD
#include
#include
void left_move(char* str, int k)
{int i = 10;for (i = 0; i < k; i++){//每次左旋一个字符：char tmp = *str;int len = strlen(str);int j = 0;for (j = 0; j < len - 1; j++)//处理len-1次，处理len-1个字符,len最大len-2{*(str + j) = *(str + j + 1);//len-2+1是len-1，len-1+str就是把最后一个字符向前移一下}*(str + len - 1) = tmp;//f的下标是5，所以是len-1}
}
int is_left_move(char* arr1, char* arr2)
{int len = strlen(arr1);int i = 0;for (i = 0; i < len; i++){left_move(arr1, 1);//arr1每次旋转1个字符if (strcmp(arr1, arr2)){return 1;}}return 0;
}
int main()
{char arr1[] = "AABCD";char arr2[] = "BCDAA";//判断arr2是不是arr1旋转得到的int ret = is_left_move(arr1, arr2);printf("%d\n", ret);
} 长度不同、大小写不同则都会返回0，不是旋转得到的。
方法2
使用库函数：
对AABCD字符串旋转是想得到它旋转之后的可能性。
则可以用一种快捷的方法：
AABCDAABCD
（在AABCD后面追加上一个AABCD）这个新的字符串里就包含了AABCD所有旋转的可能性：
旋转一个：AABCDAABCD
旋转两个：AABCDAABCD
旋转三个：AABCDAABCD
旋转四个：AABCDAABCD
旋转五个：AABCDAABCD
即思路：自己给自己追加一个自己，看是否为它包含的字符串，如果是就是旋转得来的。
用追加函数——strncat()、字符串查找函数——strstr()
#include
#include
int is_left_move(char* arr1, char* arr2)
{int len1 = strlen(arr1);int len2 = strlen(arr2);//判断长度：if (len1 != len2){return 0;}strncat(arr1, arr1, len1);if (strstr(arr1, arr2)){return 1;}else{return 0;}
}int main()
{char arr1[20] = "AABCD";char arr2[] = "BCDAA";//判断arr2是不是arr1旋转得到的int ret = is_left_move(arr1, arr2);printf("%d\n", ret);
}//1 注意：用strcat()函数追加自己的时候，可能会有bug：
当追加到\0的时候，把a赋值给\0，即\0已经被该成a了，没有\0了，则这个追加是不会停下来的。追加的时候是把源数据拷贝放到目标中，而此时源和目标的空间会有重叠。自己把自己的结束标志给断送了，会导致问题，所以不用strcat自己给自己追加。
杨氏矩阵
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。
要求：时间复杂度小于O(N);
解题：
如杨氏矩阵：
1 2 3
4 5 6
7 8 9
再如：
1 2 3
2 3 4
3 4 5
查找某个元素——若遍历二维数组，若数组有n个元素，
则最坏情况下找n次，即时间复杂度为O(N)，而题目要求时间复杂度小于n。
时间复杂度小于O(N)的算法：
把要找的元素如7与右上角的元素相比，要么去掉一行要么去掉一列。
若要找的元素是k＝2，比右上角的3小，因为3是一列中最小的元素，所以去掉一列；
若要找的元素是k＝7，比右上角的3大，因为3是一行中最大的元素，所以去掉一行；7比在剩下的元素中右上角的6还要大，则又去掉一行；7与剩下元素中右上角的9小，则在这一行中查找7，（因为9已经是剩下元素所在列中最小的元素）去掉一列；8比7大说明还在8的左边，去掉一列；7与7相等则找到；如果7还找不到则结果就是找不到。
#include
void find_int_arr(int arr[3][3], int r, int c, int k)
{//右上角元素：int x = 0;int y = c-1;//列-1，（下标）while (y>=0&&x<=r-1){//找一次：if (arr[x][y] < k){x++;}else if (arr[x][y] > k){y--;}else{printf("找到了，下标是:x=%d y=%d\n", x, y);return;}}printf("找不到\n");
}int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int k = 0;scanf("%d", &k);find_int_arr(arr, 3, 3, k);//传arr和行、列、要找的元素return 0;
} 虽然封装了函数，但是找到的下标是自己打印的，这不是好的解决办法。
解决办法：用函数查找，用函数带回或返回找不到。
但是return不能直接带回两个值。
更好的代码实现：
#include
void find_int_arr(int arr[3][3], int* px, int* py, int k)
{int x = 0;int y = *py - 1;//*py就是3while (y >= 0 && x <= *px - 1)//*px就是3{if (arr[x][y] < k){x++;}else if (arr[x][y] > k){y--;}else{//printf("找到了，下标是:x=%d y=%d\n", x, y);*px = x;*py = y;return;}}/*printf("找不到\n");*///数组中合理的坐标不可能是-1和-1*px = -1;*py = -1;
}int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int k = 0;//函数中会用到:int x = 3;int y = 3;scanf("%d", &k);find_int_arr(arr, &x, &y, k);//传x和y的地址，则在函数中所求的下标就可以通过这两个地址放到x、y中//函数返回后判断：if (x == -1 && y == -1){printf("找不到\n");}else{printf("找到了，下标是：%d %d\n", x, y);}return 0;
} 这里传&x和&y的好处：
既可以带进函数两个值：3和3，在函数中使用；又可以在函数结束的时候带回值——这种设计是返回型参数（输出型参数），用指针修改，把数值带回去。
会发现右上角元素和左下角元素都满足查找的特点：
右上角元素：一行中最大，一列中最小；
左下角元素：一列中最小，一列中最大。
而左上角元素和右下角元素不行。
位段
题目1
有如下宏定义和结构定义：
#define MAX_SIZE A+B
struct _Record_Struct
{unsigned char Env_Alarm_ID : 4;unsigned char Para1 : 2;unsigned char state;unsigned char avail : 1;
}*Env_Alarm_Record;
struct _Record_Struct *pointer = (struct _Record_Struct*)malloc
(sizeof(struct _Record_Struct) * MAX_SIZE);当A=2， B=3时，pointer分配（ ）个字节的空间。
解题：
#define MAX_SIZE A+B//位段式的结构体：
struct _Record_Struct
{unsigned char Env_Alarm_ID : 4;//1个字节unsigned char Para1 : 2;unsigned char state;//一个变量，用完1个字节unsigned char avail : 1;//再开辟1字节，所以这个位段式的结构体的大小是3个字节
}*Env_Alarm_Record;//用这个位段式的结构体指针创建了一个指针//struct _Record_Struct* pointer = (struct _Record_Struct*)malloc
//(sizeof(struct _Record_Struct) * MAX_SIZE);
//pointer为malloc开辟的一个(……)里的结构体大小，由上述计算简写为：//struct _Record_Struct* pointer = (struct _Record_Struct*)malloc
//(3 * A+B);
//则：struct _Record_Struct* pointer = (struct _Record_Struct*)malloc
(3 * 2+3);
注意：是直接替换！
答案：9
题目2
下面代码的结果是（ ）（在VS环境下）
int main()
{unsigned char puc[4];struct tagPIM{unsigned char ucPim1;unsigned char ucData0 : 1;unsigned char ucData1 : 2;unsigned char ucData2 : 3;}*pstPimData;pstPimData = (struct tagPIM*)puc;memset(puc,0,4);pstPimData->ucPim1 = 2; pstPimData->ucData0 = 3;pstPimData->ucData1 = 4;pstPimData->ucData2 = 5;printf("%02x %02x %02x %02x\n",puc[0], puc[1], puc[2], puc[3]);return 0;
}解题：
#include
#include
int main()
{unsigned char puc[4];//数组puc，4个元素，每个元素是char //定义了一个位段式的结构体：struct tagPIM{unsigned char ucPim1;//用完1个字节unsigned char ucData0 : 1;unsigned char ucData1 : 2;unsigned char ucData2 : 3;//这个位段式的结构体占2个字节}*pstPimData;//是结构体指针pstPimData = (struct tagPIM*)puc;//意思是结构体指针指向了数组puc，把字符数组强制类型转换为struct tagPIM*这样一个在结构体指针赋给pstPimData//即pstPimData指针指向了4个字符类型元素的数组//但是由于pstPimData是结构体指针类型，这个结构体大小是一个2字节大小的//则pstPimData这个位段式的结构体指针最多能访问2个字节memset(puc, 0, 4);//把puc的4个字节设置为0//pstPimData访问其成员：pstPimData->ucPim1 = 2;//放2，因为ucPim1这个变量大小的空间是1个字节，即第1个字节放的是2:00000010，8个比特位全放下了pstPimData->ucData0 = 3;//00000011，因为ucData0只有1个比特位，所以只能放1，另外的丢了pstPimData->ucData1 = 4;//00000100,只能放2个比特位，所以放00pstPimData->ucData2 = 5;//00000101,只能放3个比特位，所以放101printf("%02x %02x %02x %02x\n", puc[0], puc[1], puc[2], puc[3]);return 0;
} 答案：02 29 00 00
注意：
%x——打印十六进制，%02x是打印2位十六进制。
在一个字节内部是从低位向高位使用的，所以先使用低位存数字。
作为一个指针，什么类型的指针，就访问多少空间。
联合体
题目1
下面代码的结果是：（ ）
#include
union Un
{short s[7];int n;
};
int main()
{printf("%d\n", sizeof(union Un));return 0;
} 解题：
#include
union Un
{short s[7];//7个短整型，14个字节，对齐数是2int n;//4个字节，对齐数是4
};
//这个联合体的大小必须是4的倍数，14不是，则浪费2个字节为16
int main()
{printf("%d\n", sizeof(union Un));return 0;
} 答案：16
题目2
在X86下，小端字节序存储，有下列程序，输出结果是（ ）
#include
int main()
{union{short k;char i[2];}*s, a;s = &a;s->i[0] = 0x39;s->i[1] = 0x38;printf(“%x\n”,a.k);return 0;
} 解题：
因为联合体的成员共用同一块空间，即k和i共用同一块空间，k和i各占2个字节一样大。所以结构体对象a的空间是k的也可以是i的。s是联合体指针。
0x39表示：十六进制的39；
0x38表示：十六进制的38。
当要把内存中的数据打印出来时，打印结构体对象a中的k成员，此时k变成一个短整型了，放的就是一个数字。当把它拿出来时就涉及了大小端字节序的问题。对于小端存储来讲，低字节内容放在低地址处，高字节内容放在高地址处。因为39作为它的低字节内容，放在低地址处，38作为高字节内容放在高地址处，即是0x38 39。（表示成十六进制）
放进去的数字是38 39，打印出的是39 38。
答案：38 39
这里共用体，给i中放数据时把k也改了。
有序序列合并
输入两个升序排列的序列，将两个序列合并为一个有序序列并输出。
数据范围：1 ≤ n，m ≤ 1000 ， 序列中的值满足：30000 ≤ val ≤30000
输入描述：
输入包含三行，
第一行包含两个正整数n, m，用空格分隔。n表示第二行第一个升序序列中数字的个数，m表示第三行第二个升序序列中数字的个数。
第二行包含n个整数，用空格分隔。
第三行包含m个整数，用空格分隔。
输出描述：
输出为一行，输出长度为n+m的升序序列，即长度为n的升序序列和长度为m的升序序列中的元素重新进行升序序列排列合并。
示例:
输入：
5 6 1 3 7 9 22 2 8 10 17 33 44
输出：
1 2 3 7 8 9 10 17 22 33 44
解题：
如果是：
arr数组中：1 3 5 7 9
brr数组中：2 4 6
创建1个数组crr，1和2
基本思路：
1和2相比，1小，放在crr中；3和2相比，2小，2放进crr中；3和4相比，3小，3放进crr中；5和4相比，4小，则4放进crr中，5和6相比，5小，5被放入crr中；6和7相比，6小，6被放入crr中；6找完后brr数组已经找完了，此时把arr数组中剩下的元素直接放进去就可以了。
优化思路：可以不把合并起来的数字单独创建一个数组存起来，只要把它打印出来就可以了。
实现代码：
#include
int main()
{int n = 0;int m = 0;scanf("%d %d\n", &n, &m);int arr1[n];int arr2[m];//输入第一个数组int i = 0;for (i = 0; i < n; i++){scanf("%d ", &arr1[i]);}//输入第2个数组for (i = 0; i < m; i++){scanf("%d ", &arr2[i]);}//合并输出：//用i作为arr1的下标控制arr1;当i为n时就不再访问arr1//用j作为arr2的下标控制arr2；当j为m时也不再访问arr2i = 0;int j = 0;while (i < n && j < m){if (arr1[i] < arr2[j]){printf("%d ", arr1[i]);i++;}else{printf("%d ", arr2[j]);j++;}}if (j == m){for (; i < n; i++){printf("%d ", arr1[i]);}}else{for (; j < m; j++){printf("%d ", arr2[j]);}}return 0;
} 或创建第三个数组:
#include
int main()
{int n = 0;int m = 0;scanf("%d %d\n", &n, &m);int arr1[n];int arr2[m];int arr3[m + n];//输入第一个数组int i = 0;int k = 0;for (i = 0; i < n; i++){scanf("%d ", &arr1[i]);}//输入第2个数组for (i = 0; i < m; i++){scanf("%d ", &arr2[i]);}//合并输出：i = 0;int j = 0;while (i < n && j < m){if (arr1[i] < arr2[j]){arr3[k++] = arr1[i];//赋值后k++i++;}else{arr3[k++] = arr2[j];j++;}}if (j == m){for (; i < n; i++){arr3[k++] = arr1[i];}}else{for (; j < m; j++){arr3[k++] = arr2[j];}}for (i = 0; i < m + n; i++){printf("%d ", arr3[i]);}return 0;
} 变种水仙花
变种水仙花数 - Lily Number：把任意的数字，从中间拆分成两个数字，比如1461 可以拆分成（1和461）,（14和61）,（146和1),如果所有拆分后的乘积之和等于自身，则是一个Lily Number。
例如：
655 = 6 * 55 + 65 * 5
1461 = 1*461 + 14*61 + 146*1
求出 5位数中的所有 Lily Number。
输入描述：
无
输出描述：
一行，5位数中的所有 Lily Number，每两个数之间间隔一个空格。
#include
#include
int main()
{int i = 0;//12345://1234 5——12345/10得到1234，12345%10得到5//123 45——12345/100得到123,12345%100得到45//12 345——12345/1000得到12，12345%1000得到345//1 2345——12345/10000得到1.12345%10000得到2345//需要产生10、100、1000、10000这样的4个数字（因为是5位数）for (i = 10000; i <= 99999; i++){int j = 0;int sum = 0;for (j = 1; j <= 4; j++){int m = i / (int)pow(10, j);int n = i % (int)pow(10, j);sum += m * n;}if (sum == i){printf("%d ", i);}}return 0;
}//14610 16420 23610 34420 65500 注意：pow()函数的返回值是double类型的，而%操作符的左右两边都必须是整数，所以需要对pow()函数的返回值进行强转。
找单身狗
一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
编写一个函数找出这两个只出现一次的数字。
举例：如1 2 3 4 5 1 2 3 4 6，在这组数字中找5和6。
如果一组数字中只有一个数字出现一次如5只出现一次（一个单身狗）
把所有数字异或在一起，1和1异或是0，2和2异或是0，3和3异或是0，4和4异或是0，0和5异或结果是5，此时可以找到。
但是如果是两个数字出现一次（两个单身狗）
把所有数字异或在一起，得到的结果就是5和6异或的结果，不能提出来5和6，就不能找到。
则：对数字进行分组，一定把5和6分在不同的组中。
对1 1 3 3 5这组数字异或得到的结果是5；对2 2 4 4 6这组数字异或得到的结果是6；或分成：
1 1 5和2 2 3 3 4 4 6这两组数字。
那么怎么分组？
分组的前提条件是：
1. 只出现1次的数字，分别到2个组中，一个组中有1个；
2. 每个组都满足，只有1个数字出现一次，其他数字是成对出现的。
在不知道数字是什么的情况下把两个单身狗找出来，分到不同的组中——把所有数字进行异或，这组数字异或的结果是5和6异或的结果，5：101；6:110；5^6 = 011是3，因为这两个数字不相同，所以这两个数字对应的二进制位肯定有不同位，异或的特点是相异为1，则看5异或6的结果这个数字哪一位为1，如果发现的二进制序列的最低位是1（只用找1个就可以），则所有数字中二进制序列中最低位为1的放一组，二进制序列中最低位为0的放一组，此时5和6必然放在不同的组中。这样的两个组再各自异或在一起。
1 2 3 4 5 1 2 3 4 6
二进制序列最低位为1的：
1 1 3 3 5
二进制序列最低位为0的：
2 2 4 4 6
假设发现5和6异或的结果倒数第二位为1，则就把倒数第二位为1的放在一组中，为0的放一组中，则这次分组结果就是：
1 2 3 4 5 1 2 3 4 6
二进制序列倒数第二位为0的：
1 1 4 4 5
二进制序列倒数第二位为1的：
2 2 3 3 6
实现代码：
#include
int main()
{int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
//先异或在一起：//——不相同的数字异或的结果肯定是非0，非0则二进制序列中肯定有1，通过这个位，这一位上的两个数字不相同就可以把5和6放在不同的组中int i = 0;int ret = 0;int sz = sizeof(arr) / sizeof(arr[0]);for (i = 0; i < sz; i++){ret ^= arr[i];}//计算ret的二进制中第几个位是1：int pos = 0;//记录这个位for (i = 0; i < 32; i++){if (((ret >> i) & 1) == 1){pos = i;break;}}
//按照第pos位为1或0来分组：int n = 0;int m = 0;for (i = 0; i < sz; i++){if (((arr[i] >> pos) & 1) == 1){n^= arr[i];//不创建数组，异或的结果就是那个单身狗}}for (i = 0; i < sz; i++){if (((arr[i] >> pos) & 1) == 0){m ^= arr[i];}}printf("%d %d\n", n, m);return 0;
}//5 6 优化代码：
#include
int main()
{int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
//先异或在一起：//——不相同的数字异或的结果肯定是非0，非0则二进制序列中肯定有1，通过这个位，这一位上的两个数字不相同就可以把5和6放在不同的组中int i = 0;int ret = 0;int sz = sizeof(arr) / sizeof(arr[0]);for (i = 0; i < sz; i++){ret ^= arr[i];}//计算ret的二进制中第几个位是1：int pos = 0;//记录这个位for (i = 0; i < 32; i++){if (((ret >> i) & 1) == 1){pos = i;break;}}
//按照第pos位为1或0来分组：int n = 0;int m = 0;for (i = 0; i < sz; i++){if (((arr[i] >> pos) & 1) == 1){n^= arr[i];//不创建数组，异或的结果就是那个单身狗}}//for (i = 0; i < sz; i++)//{// if (((arr[i] >> pos) & 1) == 0)// {// m ^= arr[i];// }//}//因为ret已经是5和6异或的结果了m = ret ^ n;//就相当于m =m^n^nprintf("%d %d\n", n, m);return 0;
}//5 6 语法小题分析：int (*(*F)(int, int))(int)
int (*( *F)(int, int) ) (int)中函数的返回类型是int (*)(int)，是一个函数指针，这个函数指针的参数int，返回类型是int。
int (*( *p)[10] )(int *)中指针指向的数组有10个元素，每个元素都是函数指针，即数组是存放函数指针的数组。函数指针存放的数组的参数是int*，返回类型是int。
对数组名取地址取出的是数组的地址，数组的地址应该放到数组指针中，注意不应该放到整型指针等其他不匹配的指针中。
函数名也是地址。