杨氏矩阵
题目要求:有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。
示例
分析:我们仔细分析，不难发现，对于杨氏矩阵老说，右上角和左下角的元素是有特点的。右上角的元素是一行中最大的，一列中最小的。左下角的元素是一行中最小的，是一列中最大的。所以我们可以从右上角或者左下角开始查找。比如：从右上角开始查找的时候，右上角的元素比我们要查找元素小，我们就可以去掉右上角元素所在的这一行；右上角的元素比我们要查找的元素大，我们就可以去掉右上角元素所在的这一列。然后依然找右上角的元素继续和要查找的元素与比较。这样每一次比较去掉一行或者去掉一列。这个查找效率是高于遍历数组元素的
代码实现:
1. #include <stdio.h> 2. 3. int findnum(int a[][3], int x, int y, int f) //第一个参数的类型需要调整 4. { 5. int i = 0, j = y - 1; //从右上角开始遍历 6. while (j >= 0 && i < x) 7. { 8. if (a[i][j] < f) //比我大就向下 9. { 10. i++; 11. } 12. else if (a[i][j] > f) //比我小就向左 13. { 14. j--; 15. } 16. else 17. { 18. return 1; 19. } 20. } 21. return 0; 22. } 23. 24. int main() 25. { 26. int a[][3] = { {1, 3, 5}, 27. {3, 5, 7}, 28. {5, 7, 9} }; //一个示例 29. 30. if (findnum(a, 3, 3, 2)) 31. { 32. printf("It has been found!\n"); 33. } 34. else 35. { 36. printf("It hasn't been found!\n"); 37. } 38. 39. return 0; 40. }
字符串左旋
题目要求:
实现一个函数，可以左旋字符串中的k个字符。
例如：
ABCD左旋一个字符得到BCDA
ABCD左旋两个字符得到CDAB
分析:设计循环使其可以旋1次，然后让他执行n次是一个最简单的思路：
实现如下:
1. void leftRound(char * src, int time) 2. { 3. int i, j, tmp; 4. int len = strlen(src); 5. time %= len; //长度为5的情况下，旋转6、11、16...次相当于1次，7、12、17...次相当于2次，以此类推。 6. for (i = 0; i < time; i++) //执行k次的单次平移 7. { 8. tmp = src[0]; 9. for(j = 0; j < len - 1; j++) //单次平移 10. { 11. src[j] = src[j + 1]; 12. } 13. src[j] = tmp; 14. } 15. }
改进一
这个思路当然可以，但是一次一次转毕竟太麻烦，就不能一次到位么？
当然可以，我们可以选择拼接法，一次到位：
实现如下:
1. void leftRound(char * src, int time) 2. { 3. int len = strlen(src); 4. int pos = time % len; //断开位置的下标 5. char tmp[256] = { 0 }; //更准确的话可以选择malloc len + 1个字节的空间来做这个tmp 6. 7. strcpy(tmp, src + pos); //先将后面的全部拷过来 8. strncat(tmp, src, pos); //然后将前面几个接上 9. strcpy(src, tmp); //最后拷回去 10. }
改进二：
改进一要用到一个数组形成的辅助空间，让人觉得有点不爽，还可以有更好的选择，例如ABCDEFG，左旋3次后变成DEFGABC，有一个特殊的操作方式：
先将要左旋的前三个家伙逆序（CBADEFG），然后将后半段也逆序（CBAGFED），最后整体逆序（DEFGABC）即可。这样只需要做数值交换即可，可以写一个函数帮我们完成局部逆序，
代码如下：
1. void reverse_part(char *str, int start, int end) //将字符串从start到end这一段逆序 2. { 3. int i, j; 4. char tmp; 5. 6. for (i = start, j = end; i < j; i++, j--) 7. { 8. tmp = str[i]; 9. str[i] = str[j]; 10. str[j] = tmp; 11. } 12. } 13. 14. void leftRound(char * src, int time) 15. { 16. int len = strlen(src); 17. int pos = time % len; 18. reverse_part(src, 0, pos - 1); //逆序前段 19. reverse_part(src, pos, len - 1); //逆序后段 20. reverse_part(src, 0, len - 1); //整体逆序 21. }
字符串旋转结果
题目要求:
写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。
例如：给定s1 =AABCD和s2 = BCDAA，返回1
给定s1=abcd和s2=ACBD，返回0.
分析:
本题当然可以将所有旋转后的结果放到一个数组里，然后进行查找，但是这种做法既不好操作，也太费事，但是这题有一个很简单的做法：
其实ABCDE无论怎么旋，旋转后的所有结果，都包含在了ABCDEABCD这个字符串里了。
所以做法很简单，只需要将原字符串再来一遍接在后面，然后找一找待查找的字符串是不是两倍原字符串的子集即可。
1. int findRound(const char * src, char * find) 2. { 3. char tmp[256] = { 0 }; //用一个辅助空间将原字符串做成两倍原字符串 4. strcpy(tmp, src); //先拷贝一遍 5. strcat(tmp, src); //再连接一遍 6. return strstr(tmp, find) != NULL; //看看找不找得到 7. }
方法二:
只需要进行一一比较就好
1. #include<stdio.h> 2. #include<string.h> 3. 4. 5. void panduan(char* p1,char* p2,int len) 6. { 7. int count = 0; 8. int n = 0; 9. for (n = 0; n < len; n++) 10. { 11. count = 0; 12. int i = 0; 13. for (i = 0; i <= n; i++) 14. { 15. if (*(p1 + i) == *(p2 + len - n - i-1)) 16. { 17. 18. count++; 19. } 20. } 21. if (count == n + 1&& *(p1 + i+1) != *(p2 + len - n - i)) 22. { 23. printf("%s左旋%d个字符得到%s", p1, count+1 , p2); 24. break; 25. } 26. } 27. if (count == 0) 28. { 29. printf("没有左旋"); 30. } 31. } 32. 33. 34. int main() 35. { 36. char s1[10] = "abcd"; 37. char s2[10] = "dabc"; 38. gets(s1); 39. gets(s2); 40. int len = strlen(s1); 41. panduan(s1, s2, len); 42. return 0; 43. }
若有更多做题方法,题目讲解有误或还有不懂的地方,欢迎评论区留言或者私信!!!
