一、字符串 1、逆序（百度面试题，要求最小的时间复杂度，个人觉得应该是方法1了） （1） 双指针头尾互换（2） 递归互换（3） STL入栈出栈 1. 2. 3. 4. 5. 6. 7. 8. 9. void reverse(char *str) { int len = strlen(str); //双指针头尾互换 char tmp; int start = 0; int end = len - 1; while(start < end) { 10. tmp = *(str + start); 11. *(str + start) = *(str + end); 12. *(str + end) = tmp; 13. start++; 14. end--; 15. } 16. } 2、回文 （1）一个字符串，补充后面的字符组成回文字符串 1. 2. 3. 4. 5. 6. 7. 8. 9. //对原始字符串继续补充成回文 char *palindromes(char* str) { int len = strlen(str); char* str2 = new char[len*2];//创建新的数组，用来对元素进行存放 for(int i = 0; i < len; i++) { *(str2 + i) = *(str + i); } 10. for(int i = 0; i < len; i++) 11. { 12. *(str2 + len + i) = *(str + (len - 1 - i)); 13. } 14. *(str2 + 2*len) = '\\0'; 15. return str2; 16. } （2）在一个字符串中，找出最长的回文字符串 1. 2. 3. 4. 5. 6. 7. 8. 9. //找出一个字符串中最长的回文串，符合回文特征的字符子串 //aba & abba均为回文串，这个要首先明确的的一点 void findLongest(char* str) { //给出的思路1，是在字符之间插入'#'以统一奇数串和偶数串，均为奇数串 //利用现有最长子串为依据，由回文串的对称性，可以减少不必要的计算， //具体分析，对称点的最长子串已知，则当前最长子串的最小长度也就可以确定，对称性 int len = strlen(str); const int lenNew = 2 * len + 1; 10. char* str2 = new char[lenNew]; 11. int* p = new int[lenNew]; 12. int max = 0; 13. int id = 0; 14. for(int i = 0; i < len; ++i) 15. { 16. *(str2 + 2 * i) = '#'; 17. *(str2 + 2 * i + 1) = *(str + i); 18. } 19. *(str2 + 2 * len) = '#'; 20. //完成插入操作 //进行统计过程 21. //p[i] 存储以i位置为中心的最长回文子串长度 22. //max存储当前最优结果，id存储单签最优结果对应的下标 23. for(int i = 1; i < lenNew; ++i) 24. { 25. if (max > i) 26. p[i] = p[2 * id - i] > max - i ? max - i: p[2 * id - i];//由于关于id对称，已判断的回文部分不需要再次判断， 27. else 28. p[i] = 1; 29. for(;str2[i - p[i]] == str2[i + p[i]]; p[i]++) 30. ; 31. p[i]--; 32. if(p[i] > max) 33. { 34. max = p[i]; 35. id = i; 36. } 37. } 38. printf(\"the longest one is %d \\n\",max); 39. } （3）一个字符串中，最多有一个字符出现了奇数次，别的字符都出现了偶数次，要求将这个字符串变成回文字符串（要求最少的交换次数，不能开辟新的存储空间）（百度面试题） 1. 2. 3. 4. 5. 6. 7. 8. 9. //将原有字符串转换成回文串 //给出的测试字符串最多有一个出现奇数次，其他均出现偶数次，在不开辟新的存储空间的前提下，如何实现 //且交换次数尽可能少 void producePralindroms(char* str) { //连续交换，从前向后遍历，并与前面的内容进行比较，如果存在相同则交换到与之对称位置处 //交换的前提条件是对应位置的元素不同，否则，保持原位置继续向后遍历，直至结束 //缺陷，不能够将唯一的奇数元素放到中间位置 //改进,依然是从前向后遍历，在遍历位置，向后遍历到对称位置处，期间存在相同元素，则置换到对称位置，同时跳出内层遍历 10. //不存在相同元素，则将该元素置换到中间位置，并进行下一轮遍历（新一轮遍历起始位置不变） 11. int len = strlen(str); 12. for(int i = 0; i < (len / 2); i++) 13. { 14. char cur = *(str + i); 15. bool change = false; 16. for(int j = i + 1; j < len - i; j++) 17. { 18. if(*(str + j) == cur ) 19. { 20. //交换 21. if(j != len - i - 1) 22. { 23. char tmp = *(str + j); 24. *(str + j) = *(str + len - i - 1); 25. *(str + len - i - 1) = tmp; 26. } 27. change = true; 28. break; 29. } 30. } 31. if(!change)//只有在存在奇数个数元素时，才可能出现这个情况 32. { 33. *(str + i) = *(str + len / 2); 34. *(str + len / 2) = cur; 35. --i; 36. } 37. } 38. printf(\"%s\\n\",str); 39. } 3、左/右移动K位 （有时间复杂度的限制，要用三次交换法（剑指offer 221页） 1. 2. 3. 4. 5. 6. 7. 8. 9. //向左或向右移动k位 //利用翻手法则，三次变换即可 //对[start，end]区间进行翻转操作 void reverse(char* start, char* end) { //最直接的头尾互换即可 while(start < end) { char tmp = *start; 10. *start = *end; 11. *end = tmp; 12. start++; 13. end--; 14. } 15. } 16. void shiftK(char* str,int k) 17. { 18. int len = strlen(str); 19. char* start = str; 20. char* middle = str + len - k; 21. char* end = str + len - 1; 22. reverse(start,middle - 1); 23. reverse(middle, end); 24. reverse(start,end); 25. printf(\"%s\\n\",str); 26. } 4、itoa atoi strcpy strcat等源代码1. 2. 3. 4. 5. 6. 7. 8. 9. char* myitoa(int num, char* str,int radix) { char index[] = \"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\"; char* ptr = str; bool isNegative = false; if (num < 0) { num = -1 * num; isNegative = true; 10. } 11. while(num >= radix) 12. { 13. *ptr++ = index[num % radix]; 14. num = num / radix; 15. } 16. if(num) 17. { 18. *ptr++ = index[num]; 19. } 20. if(isNegative) 21. { 22. *ptr++ = '-'; 23. } 24. *ptr='\\0'; 25. ptr--; 26. //当前ptr指向内容为num的倒序存在，需要将其进行逆序 27. char* start = str; 28. char* end = ptr; 29. while(start < end) 30. { 31. char tmp = *start; 32. *start = *end; 33. *end = tmp; 34. start++; 35. end--; 36. } 37. printf(\"%s\\n\",str); 38. return str; 39. } 40. //将string转化为整型输出 41. int myatoi(const char* str) 42. { 43. const char* ptr = str; 44. int num = 0; 45. bool isNegative = false; 46. if(*ptr == '-') 47. { 48. ptr++; 49. isNegative = true; 50. } 51. while(*ptr != '\\0') 52. { 53. int tmp = *ptr++ - '0'; 54. num = num * 10 + tmp; 55. 56. } 57. if(isNegative) 58. { 59. num = num * -1; 60. } 61. printf(\"%d\\n\",num); 62. return num; 63. } 64. char* myStrcpy(char* dest, char* src) 65. { 66. if(NULL == dest || NULL == src) 67. return NULL; 68. char* ret = dest; 69. while((*dest++ = *src++) != '\\0') 70. ; 71. return ret; 72. }