• 【C语言】解题训练

    目录

    字符串左旋

    方法1

    方法2

    字符串旋转结果判断

    方法1

    方法2

    杨氏矩阵

    位段

    题目1

    题目2

    联合体

    题目1

    题目2

    有序序列合并

    变种水仙花

    找单身狗

    字符串左旋

    实现一个函数，可以左旋字符串中的k个字符。

    例如：

    ABCD左旋一个字符得到BCDA

    ABCD左旋两个字符得到CDAB

    解题：

    方法1

    不可能把a直接放到f上，因为会覆盖掉f，所以需要另找一块空间。

    第一步：找一块空间放a；

    第二步：把a后面的元素分别都向前移一位；（知道总元素个数，用下标做到）

    第三步：在原本放f的位置上放a；

    这三步实现一次左旋。

    1. #include 
    2. #include 
    3. void left_move(char* str, int k)
    4. {
    5. 	int i = 10;
    6. 	//左旋k个字符：
    7. 	for (i = 0; i < k; i++)
    8. 	{
    9. 		//每次左旋一个字符：
    10. 		char tmp = *str;
    11. 		int len = strlen(str);
    12. 		int j = 0;
    13. 		//把所有元素都向前移了一步，数据不会覆盖、丢失：
    14. 		for (j = 0; j < len - 1; j++)//处理len-1次，处理len-1个字符,len最大len-2
    15. 		{
    16. 			*(str + j) = *(str + j + 1);//len-2+1是len-1，len-1+str就是把最后一个字符向前移一下
    17. 		}
    18. 		*(str + len - 1) = tmp;//f的下标是5，所以是len-1
    19. 	}
    20. }
    21. int main()
    22. {
    23. 	char arr[] = "abcdef";
    24. 	int k = 0;
    25. 	scanf("%d", &k);
    26. 	left_move(arr, k);
    27. 	printf("%s\n", arr);
    28. 	return 0;
    29. }

    方法2

    假设对abcdef进行左旋两个字符：

    1. 把两个字符逆序：bacdef

    2. 把两个字符后面的字符也逆序：bafedc

    3. 把整个字符串逆序：cdefab，即实现了左旋两个字符

    这是经典的方法：三步翻转法——对前一部分进行逆序，后一部分逆序，整个字符串再逆序。

    1. #include 
    2. #include 
    3. //逆序字符串
    4. void reverse(char* left, char* right)
    5. {
    6. 	//逆序
    7. 	while (left < right)
    8. 	{
    9. 		//一次逆序
    10. 		char tmp = *left;
    11. 		*left = *right;
    12. 		*right = tmp;
    13. 		left++;
    14. 		right--;
    15. 	}
    16. }
    17. void left_move(char* str, int k)
    18. {
    19. 	//逆序k个字符，第k个字符的下标是k-1,则第k个字符的地址是str+k-1
    20. 	//第k+1个字符的下标是k,则第k个字符的地址是str+k
    21. 	//最后一个字符的下标是len-1,则其地址是str+len-1
    22. 	
    23. 	//若输入的k过大就会导致越界，则对k进行取模处理：
    24. 	//若k=10,而只有6个字符，因为前6次左旋后逆序又变成自己原来的字符串的顺序，所以k%len
    25.  
    26. 	int len = strlen(str);
    27. 	k %= len;//此时左旋10个字符和左旋4个字符是一样的
    28. 	reverse(str, str + k - 1);//逆序k个字符的前部分
    29. 	reverse(str + k, str + len - 1);//逆序后一部分
    30. 	reverse(str, str + len - 1);//整体逆序
    31. }
    32. int main()
    33. {
    34. 	char arr[] = "abcdef";
    35. 	int k = 0;
    36. 	scanf("%d", &k);
    37. 	left_move(arr, k);
    38. 	printf("%s\n", arr);
    39. 	return 0;
    40. }

    字符串旋转结果判断

    写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。

    例如：

    给定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

    1. #include 
    2. #include 
    3. void left_move(char* str, int k)
    4. {
    5. 	int i = 10;
    6. 	for (i = 0; i < k; i++)
    7. 	{
    8. 		//每次左旋一个字符：
    9. 		char tmp = *str;
    10. 		int len = strlen(str);
    11. 		int j = 0;
    12. 		for (j = 0; j < len - 1; j++)//处理len-1次，处理len-1个字符,len最大len-2
    13. 		{
    14. 			*(str + j) = *(str + j + 1);//len-2+1是len-1，len-1+str就是把最后一个字符向前移一下
    15. 		}
    16. 		*(str + len - 1) = tmp;//f的下标是5，所以是len-1
    17. 	}
    18. }
    19. int is_left_move(char* arr1, char* arr2)
    20. {
    21. 	int len = strlen(arr1);
    22. 	int i = 0;
    23. 	for (i = 0; i < len; i++)
    24. 	{
    25. 		left_move(arr1, 1);//arr1每次旋转1个字符
    26. 		if (strcmp(arr1, arr2))
    27. 		{
    28. 			return 1;
    29. 		}
    30. 	}
    31. 	return 0;
    32. }
    33. int main()
    34. {
    35. 	char arr1[] = "AABCD";
    36. 	char arr2[] = "BCDAA";
    37. 	//判断arr2是不是arr1旋转得到的
    38. 	int ret = is_left_move(arr1, arr2);
    39. 	printf("%d\n", ret);
    40. }

    长度不同、大小写不同则都会返回0，不是旋转得到的。

    方法2

    使用库函数：

    对AABCD字符串旋转是想得到它旋转之后的可能性。
    则可以用一种快捷的方法：
    AABCDAABCD
    （在AABCD后面追加上一个AABCD）这个新的字符串里就包含了AABCD所有旋转的可能性：
    旋转一个：AABCDAABCD
    旋转两个：AABCDAABCD
    旋转三个：AABCDAABCD
    旋转四个：AABCDAABCD
    旋转五个：AABCDAABCD
    即思路：自己给自己追加一个自己，看是否为它包含的字符串，如果是就是旋转得来的。
    用追加函数——strncat()、字符串查找函数——strstr()

    1. #include 
    2. #include 
    3. int is_left_move(char* arr1, char* arr2)
    4. {
    5. 	int len1 = strlen(arr1);
    6. 	int len2 = strlen(arr2);
    7. 	//判断长度：
    8. 	if (len1 != len2)
    9. 	{
    10. 		return 0;
    11. 	}
    12.  
    13. 	strncat(arr1, arr1, len1);
    14. 	if (strstr(arr1, arr2))
    15. 	{
    16. 		return 1;
    17. 	}
    18. 	else
    19. 	{
    20. 		return 0;
    21. 	}
    22. }
    23.  
    24. int main()
    25. {
    26. 	char arr1[20] = "AABCD";
    27. 	char arr2[] = "BCDAA";
    28. 	//判断arr2是不是arr1旋转得到的
    29. 	int ret = is_left_move(arr1, arr2);
    30. 	printf("%d\n", ret);
    31. }//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还找不到则结果就是找不到。

    1. #include 
    2. void find_int_arr(int arr[3][3], int r, int c, int k)
    3. {
    4. 	//右上角元素：
    5. 	int x = 0;
    6. 	int y = c-1;//列-1，（下标）
    7.  
    8. 	while (y>=0&&x<=r-1)
    9. 	{
    10. 		//找一次：
    11. 		if (arr[x][y] < k)
    12. 		{
    13. 			x++;
    14. 		}
    15. 		else if (arr[x][y] > k)
    16. 		{
    17. 			y--;
    18. 		}
    19. 		else
    20. 		{
    21. 			printf("找到了，下标是:x=%d y=%d\n", x, y);
    22. 			return;
    23. 		}
    24. 	}
    25. 	printf("找不到\n");
    26. }
    27.  
    28. int main()
    29. {
    30. 	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
    31.  
    32. 	int k = 0;
    33. 	scanf("%d", &k);
    34. 	find_int_arr(arr, 3, 3, k);//传arr和行、列、要找的元素
    35.  
    36. 	return 0;
    37. }

    虽然封装了函数，但是找到的下标是自己打印的，这不是好的解决办法。

    解决办法：用函数查找，用函数带回或返回找不到。

    但是return不能直接带回两个值。

    更好的代码实现：

    1. #include 
    2. void find_int_arr(int arr[3][3], int* px, int* py, int k)
    3. {
    4. 	int x = 0;
    5. 	int y = *py - 1;//*py就是3
    6.  
    7. 	while (y >= 0 && x <= *px - 1)//*px就是3
    8. 	{
    9. 		if (arr[x][y] < k)
    10. 		{
    11. 			x++;
    12. 		}
    13. 		else if (arr[x][y] > k)
    14. 		{
    15. 			y--;
    16. 		}
    17. 		else
    18. 		{
    19. 			//printf("找到了，下标是:x=%d y=%d\n", x, y);
    20. 			*px = x;
    21. 			*py = y;
    22. 			return;
    23. 		}
    24. 	}
    25. 	/*printf("找不到\n");*/
    26. 	//数组中合理的坐标不可能是-1和-1
    27. 	*px = -1;
    28. 	*py = -1;
    29. }
    30.  
    31. int main()
    32. {
    33. 	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
    34.  
    35. 	int k = 0;
    36. 	
    37. 	//函数中会用到:
    38. 	int x = 3;
    39. 	int y = 3;
    40. 	
    41. 	scanf("%d", &k);
    42. 	find_int_arr(arr, &x, &y, k);
    43. 	//传x和y的地址，则在函数中所求的下标就可以通过这两个地址放到x、y中
    44.  
    45. 	//函数返回后判断：
    46. 	if (x == -1 && y == -1)
    47. 	{
    48. 		printf("找不到\n");
    49. 	}
    50. 	else
    51. 	{
    52. 		printf("找到了，下标是：%d %d\n", x, y);
    53. 	}
    54.  
    55. 	return 0;
    56. }

    这里传&x和&y的好处：

    既可以带进函数两个值：3和3，在函数中使用；又可以在函数结束的时候带回值——这种设计是返回型参数（输出型参数），用指针修改，把数值带回去。

    会发现右上角元素和左下角元素都满足查找的特点：
    右上角元素：一行中最大，一列中最小；
    左下角元素：一列中最小，一列中最大。
    而左上角元素和右下角元素不行。

    位段

    题目1

    有如下宏定义和结构定义：

    1. #define MAX_SIZE A+B
    2. struct _Record_Struct
    3. {
    4.   unsigned char Env_Alarm_ID : 4;
    5.   unsigned char Para1 : 2;
    6.   unsigned char state;
    7.   unsigned char avail : 1;
    8. }*Env_Alarm_Record;
    9. struct _Record_Struct *pointer = (struct _Record_Struct*)malloc
    10. (sizeof(struct _Record_Struct) * MAX_SIZE);
    当A=2， B=3时，pointer分配（ ）个字节的空间。

    解题：

    1. #define MAX_SIZE A+B
    2.  
    3. //位段式的结构体：
    4. struct _Record_Struct
    5. {
    6. 	unsigned char Env_Alarm_ID : 4;//1个字节
    7. 	unsigned char Para1 : 2;
    8. 	unsigned char state;//一个变量，用完1个字节
    9. 	unsigned char avail : 1;//再开辟1字节，所以这个位段式的结构体的大小是3个字节
    10. }*Env_Alarm_Record;//用这个位段式的结构体指针创建了一个指针
    11.  
    12. //struct _Record_Struct* pointer = (struct _Record_Struct*)malloc
    13. //(sizeof(struct _Record_Struct) * MAX_SIZE);
    14. //pointer为malloc开辟的一个(……)里的结构体大小，由上述计算简写为：
    15.  
    16. //struct _Record_Struct* pointer = (struct _Record_Struct*)malloc
    17. //(3 * A+B);
    18. //则：
    19.  
    20. struct _Record_Struct* pointer = (struct _Record_Struct*)malloc
    21. (3 * 2+3);

    注意：是直接替换！

    答案：9

    题目2

    下面代码的结果是（ ）（在VS环境下）

    1. int main()
    2. {
    3.   unsigned char puc[4];
    4.   struct tagPIM
    5.   {
    6.     unsigned char ucPim1;
    7.     unsigned char ucData0 : 1;
    8.     unsigned char ucData1 : 2;
    9.     unsigned char ucData2 : 3;
    10.   }*pstPimData;
    11.   pstPimData = (struct tagPIM*)puc;
    12.   memset(puc,0,4);
    13.   pstPimData->ucPim1 = 2; 
    14.   pstPimData->ucData0 = 3;
    15.   pstPimData->ucData1 = 4;
    16.   pstPimData->ucData2 = 5;
    17.   printf("%02x %02x %02x %02x\n",puc[0], puc[1], puc[2], puc[3]);
    18.   return 0;
    19. }

    解题：

    1. #include 
    2. #include 
    3. int main()
    4. {
    5.     unsigned char puc[4];//数组puc，4个元素，每个元素是char 
    6.     //定义了一个位段式的结构体：
    7.     struct tagPIM
    8.     {
    9.         unsigned char ucPim1;//用完1个字节
    10.         unsigned char ucData0 : 1;
    11.         unsigned char ucData1 : 2;
    12.         unsigned char ucData2 : 3;//这个位段式的结构体占2个字节
    13.     }*pstPimData;//是结构体指针
    14.    
    15.     pstPimData = (struct tagPIM*)puc;
    16.     //意思是结构体指针指向了数组puc，把字符数组强制类型转换为struct tagPIM*这样一个在结构体指针赋给pstPimData
    17.     //即pstPimData指针指向了4个字符类型元素的数组
    18.     //但是由于pstPimData是结构体指针类型，这个结构体大小是一个2字节大小的
    19.     //则pstPimData这个位段式的结构体指针最多能访问2个字节
    20.  
    21.     memset(puc, 0, 4);//把puc的4个字节设置为0
    22.    
    23.     //pstPimData访问其成员：
    24.     pstPimData->ucPim1 = 2;//放2，因为ucPim1这个变量大小的空间是1个字节，即第1个字节放的是2:00000010，8个比特位全放下了
    25.     pstPimData->ucData0 = 3;//00000011，因为ucData0只有1个比特位，所以只能放1，另外的丢了
    26.     pstPimData->ucData1 = 4;//00000100,只能放2个比特位，所以放00
    27.     pstPimData->ucData2 = 5;//00000101,只能放3个比特位，所以放101
    28.     printf("%02x %02x %02x %02x\n", puc[0], puc[1], puc[2], puc[3]);
    29.     return 0;
    30. }

    答案：02 29 00 00

    注意：

    %x——打印十六进制，%02x是打印2位十六进制。

    在一个字节内部是从低位向高位使用的，所以先使用低位存数字。

    作为一个指针，什么类型的指针，就访问多少空间。

    联合体

    题目1

    下面代码的结果是：（ ）

    1. #include 
    2. union Un
    3. {
    4. 	short s[7];
    5. 	int n;
    6. };
    7. int main()
    8. {
    9.   printf("%d\n", sizeof(union Un));
    10.   return 0;
    11. }

    解题：

    1. #include 
    2. union Un
    3. {
    4. 	short s[7];//7个短整型，14个字节，对齐数是2
    5. 	int n;//4个字节，对齐数是4
    6. };
    7. //这个联合体的大小必须是4的倍数，14不是，则浪费2个字节为16
    8. int main()
    9. {
    10. 	printf("%d\n", sizeof(union Un));
    11. 	return 0;
    12. }

    答案：16

    题目2

    在X86下，小端字节序存储，有下列程序，输出结果是（ ）

    1. #include
    2. int main()
    3. {
    4.   union
    5.   {
    6.     short k;
    7.     char i[2];
    8.   }*s, a;
    9.   s = &a;
    10.   s->i[0] = 0x39;
    11.   s->i[1] = 0x38;
    12.   printf(“%x\n”,a.k);
    13.   return 0;
    14. }

    解题：

    因为联合体的成员共用同一块空间，即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数组中剩下的元素直接放进去就可以了。

    优化思路：可以不把合并起来的数字单独创建一个数组存起来，只要把它打印出来就可以了。

    实现代码：

    1. #include 
    2. int main()
    3. {
    4. 	int n = 0;
    5. 	int m = 0;
    6. 	scanf("%d %d\n", &n, &m);
    7. 	int arr1[n];
    8. 	int arr2[m];
    9. 	//输入第一个数组
    10. 	int i = 0;
    11. 	for (i = 0; i < n; i++)
    12. 	{
    13. 		scanf("%d ", &arr1[i]);
    14. 	}
    15. 	//输入第2个数组
    16. 	for (i = 0; i < m; i++)
    17. 	{
    18. 		scanf("%d ", &arr2[i]);
    19. 	}
    20. 	//合并输出：
    21. 	//用i作为arr1的下标控制arr1;当i为n时就不再访问arr1
    22. 	//用j作为arr2的下标控制arr2；当j为m时也不再访问arr2
    23. 	i = 0;
    24. 	int j = 0;
    25. 	while (i < n && j < m)
    26. 	{
    27. 		if (arr1[i] < arr2[j])
    28. 		{
    29. 			printf("%d ", arr1[i]);
    30. 			i++;
    31. 		}
    32. 		else
    33. 		{
    34. 			printf("%d ", arr2[j]);
    35. 			j++;
    36. 		}
    37. 	}
    38. 	if (j == m)
    39. 	{
    40. 		for (; i < n; i++)
    41. 		{
    42. 			printf("%d ", arr1[i]);
    43. 		}
    44. 	}
    45. 	else
    46. 	{
    47. 		for (; j < m; j++)
    48. 		{
    49. 			printf("%d ", arr2[j]);
    50. 		}
    51. 	}
    52. 	return 0;
    53. }
    54.

    或创建第三个数组:

    1. #include 
    2. int main()
    3. {
    4. 	int n = 0;
    5. 	int m = 0;
    6. 	scanf("%d %d\n", &n, &m);
    7. 	int arr1[n];
    8. 	int arr2[m];
    9. 	int arr3[m + n];
    10. 	//输入第一个数组
    11. 	int i = 0;
    12. 	int k = 0;
    13. 	for (i = 0; i < n; i++)
    14. 	{
    15. 		scanf("%d ", &arr1[i]);
    16. 	}
    17. 	//输入第2个数组
    18. 	for (i = 0; i < m; i++)
    19. 	{
    20. 		scanf("%d ", &arr2[i]);
    21. 	}
    22. 	//合并输出：
    23. 	i = 0;
    24. 	int j = 0;
    25. 	while (i < n && j < m)
    26. 	{
    27. 		if (arr1[i] < arr2[j])
    28. 		{
    29. 			arr3[k++] = arr1[i];//赋值后k++
    30. 			i++;
    31. 		}
    32. 		else
    33. 		{
    34. 			arr3[k++] = arr2[j];
    35. 			j++;
    36. 		}
    37. 	}
    38. 	if (j == m)
    39. 	{
    40. 		for (; i < n; i++)
    41. 		{
    42. 			arr3[k++] = arr1[i];
    43. 		}
    44. 	}
    45. 	else
    46. 	{
    47. 		for (; j < m; j++)
    48. 		{
    49. 			arr3[k++] = arr2[j];
    50. 		}
    51. 	}
    52. 	for (i = 0; i < m + n; i++)
    53. 	{
    54. 		printf("%d ", arr3[i]);
    55. 	}
    56. 	return 0;
    57. }

    变种水仙花

    变种水仙花数 - 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，每两个数之间间隔一个空格。

    1. #include 
    2. #include 
    3. int main()
    4. {
    5.     int i = 0;
    6.     //12345:
    7.     //1234 5——12345/10得到1234，12345%10得到5
    8.     //123 45——12345/100得到123,12345%100得到45
    9.     //12 345——12345/1000得到12，12345%1000得到345
    10.     //1 2345——12345/10000得到1.12345%10000得到2345
    11.     
    12.     //需要产生10、100、1000、10000这样的4个数字（因为是5位数）
    13.     for (i = 10000; i <= 99999; i++)
    14.     {
    15.         int j = 0;
    16.         int sum = 0;
    17.         for (j = 1; j <= 4; j++)
    18.         {
    19.             int m = i / (int)pow(10, j);
    20.             int n = i % (int)pow(10, j);
    21.             sum += m * n;
    22.         }
    23.         if (sum == i)
    24.         {
    25.             printf("%d ", i);
    26.         }
    27.     }
    28.     return 0;
    29. }//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

    实现代码：

    1. #include 
    2. int main()
    3. {
    4. 	int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
    5. //先异或在一起：
    6. 	//——不相同的数字异或的结果肯定是非0，非0则二进制序列中肯定有1，通过这个位，这一位上的两个数字不相同就可以把5和6放在不同的组中
    7. 	int i = 0;
    8. 	int ret = 0;
    9. 	int sz = sizeof(arr) / sizeof(arr[0]);
    10. 	for (i = 0; i < sz; i++)
    11. 	{
    12. 		ret ^= arr[i];
    13. 	}
    14.  
    15. //计算ret的二进制中第几个位是1：
    16. 	int pos = 0;//记录这个位
    17. 	for (i = 0; i < 32; i++)
    18. 	{
    19. 		if (((ret >> i) & 1) == 1)
    20. 		{
    21. 			pos = i;
    22. 			break;
    23. 		}
    24. 	}
    25. //按照第pos位为1或0来分组：
    26. 	int n = 0;
    27. 	int m = 0;
    28. 	for (i = 0; i < sz; i++)
    29. 	{
    30. 		if (((arr[i] >> pos) & 1) == 1)
    31. 		{
    32. 			n^= arr[i];//不创建数组，异或的结果就是那个单身狗
    33. 		}
    34. 	}
    35. 	for (i = 0; i < sz; i++)
    36. 	{
    37. 		if (((arr[i] >> pos) & 1) == 0)
    38. 		{
    39. 			m ^= arr[i];
    40. 		}
    41. 	}
    42. 	printf("%d %d\n", n, m);
    43. 	return 0;
    44. }//5 6

    优化代码：

    1. #include 
    2. int main()
    3. {
    4. 	int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
    5. //先异或在一起：
    6. 	//——不相同的数字异或的结果肯定是非0，非0则二进制序列中肯定有1，通过这个位，这一位上的两个数字不相同就可以把5和6放在不同的组中
    7. 	int i = 0;
    8. 	int ret = 0;
    9. 	int sz = sizeof(arr) / sizeof(arr[0]);
    10. 	for (i = 0; i < sz; i++)
    11. 	{
    12. 		ret ^= arr[i];
    13. 	}
    14.  
    15. //计算ret的二进制中第几个位是1：
    16. 	int pos = 0;//记录这个位
    17. 	for (i = 0; i < 32; i++)
    18. 	{
    19. 		if (((ret >> i) & 1) == 1)
    20. 		{
    21. 			pos = i;
    22. 			break;
    23. 		}
    24. 	}
    25. //按照第pos位为1或0来分组：
    26. 	int n = 0;
    27. 	int m = 0;
    28. 	for (i = 0; i < sz; i++)
    29. 	{
    30. 		if (((arr[i] >> pos) & 1) == 1)
    31. 		{
    32. 			n^= arr[i];//不创建数组，异或的结果就是那个单身狗
    33. 		}
    34. 	}
    35. 	//for (i = 0; i < sz; i++)
    36. 	//{
    37. 	//	if (((arr[i] >> pos) & 1) == 0)
    38. 	//	{
    39. 	//		m ^= arr[i];
    40. 	//	}
    41. 	//}
    42.  
    43. 	//因为ret已经是5和6异或的结果了
    44. 	m = ret ^ n;//就相当于m =m^n^n
    45. 	printf("%d %d\n", n, m);
    46. 	return 0;
    47. }//5 6

    语法小题分析：int (*(*F)(int, int))(int)

    int (*( *F)(int, int) ) (int)中函数的返回类型是int (*)(int)，是一个函数指针，这个函数指针的参数int，返回类型是int。

    int (*( *p)[10] )(int *)中指针指向的数组有10个元素，每个元素都是函数指针，即数组是存放函数指针的数组。函数指针存放的数组的参数是int*，返回类型是int。

    对数组名取地址取出的是数组的地址，数组的地址应该放到数组指针中，注意不应该放到整型指针等其他不匹配的指针中。
    函数名也是地址。

  • 相关阅读:
    洛谷 P7302 [NOI1998] 免费的馅饼
    指针扩展之——数组指针
    【LeetCode】在非有序数组中使用二分
    解决dockerfile创建镜像时pip install报错的bug
    LC926. 将字符串翻转到单调递增(JAVA - 动态规划)
    如何利用Requestly提升前端开发与测试的效率，让你事半功倍?
    c++ primer中文版第五版作业第二章
    正则表达式练习
    【新知实验室】实现视频应用
    Windows 安装，配置Tomcat
  • 原文地址：https://blog.csdn.net/m0_60624580/article/details/127429344