为了锻炼自己的代码思维能力，空余时间时不时的刷下LeetCode的题目，防止老年痴呆，并且将自己认为比较经典的算法题目通过笔记的形式记录在这里。
题目 给定一个字符串，要求反向输出这个字符串。 例如：给定abcd 则输出dcba。
解题思路（一） 找到字符串的末尾索引，然后反向遍历这个字符串即可。
示例代码 易错知识点：
char型的字符数组一定要初始化，不然会出现乱码；指针一定要初始化，可以让其指向一个已经初始化的字符数组。指针函数中返回值，一定不能是栈地址。所以一般指针函数中都会有一个接收参数。 #include <stdio.h> #include <stdint.h> #include <assert.h> #include <string.h> const char* reverseStr(const char* src, char* des) { assert(src != NULL && des != NULL); //这个地方的指针，是需要返回的指针，不能是栈地址 char* retStr = des; int length = strlen(src); int i = 0; int j = 0; for(i = length - 1; i >= 0; i--) { retStr[j++] = src[i]; } retStr[j] = '\0';// 可要可不要，如果是字符数组一定需要加\0 return retStr; } int main() { char* testStr = "dayDayUp"; char retVal[20]; memset(retVal, 0, sizeof(retVal)); //字符数组的初始化， 按byte初始化 reverseStr(testStr, retVal); printf("Reverse the string: %s\n", retVal); return 0; } 优化方法 上边找字符串的末尾索引是通过数组遍历的方式。下边是直接通过指针找到末尾索引。易错点 在使用while(*p++)的时候，在退出循环的时候，p的位置为p = p[\0] + 1了。代码示例 #include <stdio.h> #include <string.h> #include <assert.h> const char* const reverseString(char* srcStr_p) { assert(srcStr_p); char* retStr_p = srcStr_p; int length = strlen(srcStr_p); char srcCopy[20]; memset(srcCopy, 0, sizeof(srcCopy)); while(*srcStr_p++); --srcStr_p; --srcStr_p; for (int i = 0; i < length; i++) { srcCopy[i] = *srcStr_p; --srcStr_p; } //make the srcStr_p = 0 srcStr_p++; for (int i = 0; i < length; i++) { srcStr_p[i] = srcCopy[i]; } return retStr_p; } int main() { char str[20] = {"guo xue ping"}; char temp[20]; memset(temp, 0, sizeof(temp)); const char *str_p = temp; str_p = reverseString(str); printf("%s\n", str_p); return 0; } 解题思路（二） 将字符串的头尾，相互交换，一直到遇到最中间的字符，则停止交换。示例代码 易错知识点：字符数组初始化的时候，需要加上\0。 e.g. char str_p1[] = {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘\0’};strlen()函数统计的是有效字符的个数。 #include <stdio.h> #include <stdint.h> #include <assert.h> #include <string.h> void swap(char* x, char* y); const char* const rotateStr(char* src); const char* const rotateStr(char* src) { assert(src != NULL); int i = 0; int j = 0; j = strlen(src) - 1; char* temp_p = src; for (i = 0; i < j; i++, j--) { swap(&temp_p[i], &temp_p[j]); } return temp_p; } void swap(char* x, char* y) { char temp; temp = *x; *x = *y; *y = temp; } int main() { char str_p1[] = {'a', 'b', 'c', 'd', 'e', '\0'}; rotateStr(str_p1); printf("%s\n", str_p1); return 0; }题目 这个是对最长子串的扩展，只需要求出最长无重复子串的长度。 这个题目是对滑动窗口算法的一个很好的应用。
解题思路 最长子串长度，实际上是滑动窗口的大小，用左右两个索引，分别记录窗口的两端位置，一旦发现右边窗口插入的字符跟左边的字符相等，就讲左窗口位置右移一位。
易错点 什么时候窗口开始滑动，是本题目的重点。
示例代码（滑动窗口）
#include <stdio.h> #include <string.h> #include <assert.h> int lengthOfLongestSubstr(const char* const str_p) { assert(str_p != NULL); int headIndex = 0; int tailIndex = 0; int tempIndex = 0; int maxLength = 0; int length = strlen(str_p); for (tailIndex = 0; tailIndex < length; tailIndex++) { for (tempIndex = headIndex; tempIndex < tailIndex; tempIndex++) { if (str_p[tempIndex] == str_p[tailIndex]) { headIndex = tempIndex + 1; break; } } maxLength = (tailIndex - headIndex) + 1 > maxLength ? (tailIndex - headIndex) + 1 : maxLength; } return maxLength; } int main() { char* str1_p = "guoxueping"; int length = 0; length = lengthOfLongestSubstr(str1_p); printf("the length of the longest string: %d\n", length); } 输出结果 the length of the longest string: 8 //oxueping = 8 个 [Finished in 1.0s] 解法2示例代码（hash表算法） 主要是建立字符与索引的关系。 #include <stdio.h> #include <string.h> int lengthOfLongestSubstring(char* s) { int len = strlen(s); int hash[256]; int maxLen = 0; int maxRet = 0; memset(hash, -1, 256 * sizeof(int)); int left = 0; int right = 0; while(right < len) { if((hash[(int)s[right]] != -1) && (hash[(int)s[right]] >= left)) { left = hash[(int)s[right]]; left++; } hash[(int)s[right]] = right; maxLen = right - left + 1; maxRet = maxRet > maxLen ? maxRet : maxLen; right++; } return maxRet; } int main() { char * src_p = "gggguoxyz"; int ret = lengthOfLongestSubstring(src_p); printf("%d\n", ret); }题目 给定一个英文句子，每个单词用空格分开，求：在不改变原来单词顺序下，反向输出每个单词。 e.g. 给定字符串，“guo xue ping” 则输出： “oug eux gnip”
解题思路 两种解题方式：
遍历整个字符串，一旦遇到空格，就将当前的这个单词反转。先反向输出整个字符串，当前的单词顺序 跟 源字符串位置相反，这个时候可以把这个字符串的每个单词反向输出。这里主要讨论这种方法。 易错点 反转单词的时候，因为最后一个单词没有空格可以判断，所条件判断语句是 if (str[i] == ’ ’ || i == length).遍历字符串的时候，需要取到length，这样才会反转到最后一个单词。 示例代码 #include <stdio.h> #include <string.h> int main() { char str[20] = {"guo xue ping"}; char * str_p = str; int length = strlen(str_p); while(*str_p) { str_p++; } --str_p; char strDest[20]; memset(strDest, 0, sizeof(strDest)); for (int i = 0; i < length; i++) { strDest[i] = *str_p--; } int counter = 0; for (int i = 0; i <= length; i++) { if (str[i] == ' ' || i == length) { for (int j = i - counter, k = length - i; j < i; j++, k++) { str[j] = strDest[k]; } counter = 0; } else { counter++; } } printf("After reverse the string, string:\n%s\n", str); return 0; }k为奇数的解法 状态转移法
#include <stdio.h> int main() { int array[7] = {3, 3, 3, 5, 5, 5, 6}; int once = 0; int twice = 0; for (int i = 0; i < 7; i++) { once = (once ^ array[i]) & (~twice); twice = (twice ^ array[i]) & (~once); } printf("the single number is: %d\n", once); return 0; }k为奇数的解法 统计每个数二进制位的“1”的总数，模k，然后返回最后的统计值，就是仅仅出现一次的值。
运行代码有问题，没有找到为什么，先记录在这里，有时间再研究吧。
int singleNumber(int* arr_p) { int result = 0; //loop 32bit for every number statistic the number of 1 for (int i = 0; i < 32; i++) { int counter = 0; for (int j = 0; j < LENGTH; j++) { counter += ((arr_p[i] >> i) & 0x01); } //注意这个地方取的是模3的结果 result |= (counter % 3) << i; } return result; }题目 给定一个字符串，找出所有回文子串。
什么是回文 回文就是源字符串和逆序字符串是同一个字符串。
解题思路 用枚举法找出所有的子串，然后判断每个子串，是否满足回文条件。
易错点 二维数组或者指针数组可以存储多个单词，一定要注意数组或者指针的初始化。
示例代码
#include <stdio.h> #include <string.h> #define bool _Bool #define TRUE 1 #define FALSE 0 /** *判断回文字符串 */ bool isPalindrome(char* str_p) { if (NULL == str_p) { return FALSE; } int leftIdx = 0; int rightIdx = strlen(str_p) - 1; while (rightIdx > leftIdx) { if (str_p[rightIdx] != str_p[leftIdx]) { return FALSE; } else { --rightIdx; ++leftIdx; } } return TRUE; } int main() { char* str_p = "123321125"; int subLen = 0; int strLen = strlen(str_p); //用一个二维数组来保存回文字符串，指针数组也可以 char result[10][20]; for (int i = 0; i < 10; i++) { memset(&result[i], 0, 20); } //枚举法求所有的回文字符串 char arrStr[20]; static int cnt = 0; for (subLen = 2; subLen <= strLen; ++subLen) //注意取= { for (int i = 0; i <= strLen - subLen; ++i) { memset(arrStr, 0, sizeof(arrStr)); strncpy(arrStr, str_p+i, subLen); if (isPalindrome(arrStr)) { strcpy(&result[cnt], arrStr); cnt++; } } } for (int i = 0; i < cnt; i++) { if (strlen(&result[i]) > 0) { printf("result[%d] = %s\n", i, result+i); } } return 0; } Java version public class Palindrome{ public static void main(String[] args) { String str = "123321125775165561"; //List list = new ArrayList<>(); for (int len = 2; len <= str.length(); len++) { for (int i = 0; i <= str.length() - len; i++) { String subStr = str.substring(i, i+len); if (isPalindrome(subStr)) { System.out.println(subStr); } } } } //判断字符串是否是回文 public static boolean isPalindrome(String str) { if (null == str) { return false; } int i = 0; int j = str.length() - 1; while (j > i) { if (str.charAt(i) != str.charAt(j)) return false; ++i; --j; } return true; } }题目 某某公司面试题。 给定一个字符串，去掉重复字符，然后升序输出这个字符串。
解题思路
首先判断字符是否空字符其次判断字符串是否重复如果重复，就去重，再排序如果不重复，就直接排序 易错点 判断空字符情况如果是一个字符的情况，直接返回，代码里没有考虑这一步。可以作为优化项。 示例代码 #include <stdio.h> #include <string.h> #include <assert.h> #define INVALID ~0 #define bool _Bool #define true 1 #define false 0 /** *swap func */ void swap(char* p1, char* p2) { char temp = 0; temp = *p1; *p1 = *p2; *p2 = temp; } /** *判断字符串是否有重复字符 */ bool isRepeatStr(char* src_p) { assert(NULL != src_p); unsigned int length = strlen(src_p); for (int i = 0; i < length; ++i) { for (int j = i + 1; j < length; ++j) { if (src_p[i] == src_p[j]) { return true; } } } return false; } /** *sort the string */ void sortStr(char* src_p) { assert(NULL != src_p); unsigned int length = strlen(src_p); for (int i = 0; i < length; ++i) { for (int j = i + 1; j < length; ++j) { if (strcmp(&src_p[i], &src_p[j]) > 0) swap(&src_p[i], &src_p[j]); } } } int main() { char * src_p = "defgggabccd"; //define a variable to store the result unsigned int length = strlen(src_p); char uniqStr[length + 1]; //one more space to store '\0' memset(uniqStr, 0, sizeof(uniqStr)); //是否是空字符串 if (*src_p == 0) { printf("[ERROR]: This string is NULL\n"); } //if the character is already unique if (!isRepeatStr(src_p)) { strcpy(uniqStr, src_p); } //if the character is repeat unsigned int counter = 0; bool flag = false; if (isRepeatStr(src_p)) { while (*src_p) { //注意这个地方必须取=，不然进不了循环 for (int i = 0; i <= counter; ++i) { if (*src_p == uniqStr[i]) { flag = false; break; } else { flag = true; } } if (true == flag) { uniqStr[counter] = *src_p; counter++; } src_p++; } } //sort the string sortStr(uniqStr); //print the result printf("The unique string is : %s\n", uniqStr); }猜测题目来源---->快速排序的分区算法
题目 给定一个整数数组array和一个整数target，划分数组，使得： 所有小于target的元素，移到左边所有大于target的元素，移到右边返回数组划分的位置。使得array[index] >= target.
举例说明 输入: {3, 2, 2, 1}, 2 输出：1 解释： 真是的数组为{1, 2, 2, 3}, 2的左边都是小于2的数，右边都是大于等于2的数，所以返回1.
解题思路 左右指针法 通过左指针跳过小于target的前缀 通过右指针跳过大于等于target的后缀 然后将左边大于target的数和右边小于target的数字交换 如果两个指针相遇，则完成分组。
易错点 因为是要找到target的左边界，所以对于左边数字的判断，arr_p[left] < target, 此处不能取等号。
示例代码
#include <stdio.h> #include <stdint.h> #include <assert.h> #define ARR_LENGTH 5 //declaration void swap(uint16_t* x, uint16_t* y); const uint16_t arrPartitionIdx(uint16_t * const arr_p, const uint16_t target); /** *array partition */ const uint16_t arrPartitionIdx(uint16_t * const arr_p, const uint16_t target) { //null point assert(NULL != arr_p); uint16_t left = 0; uint16_t right = ARR_LENGTH - 1; while (left < right) //note: no equal operation { while (left < right && arr_p[left] < target) ++left; while (left < right && arr_p[right] >= target) --right; if (left < right) //also: if (left != right) swap(arr_p + left, arr_p + right); } return left; } /** *swap funciton */ void swap(uint16_t* x, uint16_t* y) { assert(NULL != x && NULL != y); uint16_t temp = 0; temp = *x; *x = *y; *y = temp; } int main() { uint16_t array[ARR_LENGTH] = {1, 4, 4, 4, 5}; uint16_t index = arrPartitionIdx(array, 4); printf("After partition, the index = %u\n", index); return 0; }题目 给定一个数字字符串，例如： S = “123456579”, 拆分成斐波那契数列[123, 456, 579] 示例2： 输入：“11235813” 输出：[1, 1, 2, 3, 5, 8, 13]
实例3： 输入：“112358130” 输出：[] 解释：这个无法拆分成斐波那契数列
回溯算法（试探算法） 回溯算法就是当条件不满足的时候，回退一步，开始试探是否满足条件，如果不满足，再回退一步，相反，如果满足条件，则进行下一步操作。
回溯算法的特点 在递归调用的时候，满足条件才递归，如果不满足条件则不会继续递归。
解题思路 简单来说，就是枚举思想，如果暴力枚举，时间复杂度太大。 遍历所有可能的前缀，通过回溯算法，剪枝不满足条件部分，最后得到结果。
易错点
斐波那契数列个数必须大于等于3个。
拆分的数字，不能以0开头，除非这个块是数字0本身。
因为要将字符转化为数字来运算，注意字符—> 数字的转化，是减去一个字符零’0’。
示例代码 C++
#include <iostream> #include <vector> #include <stdio.h> using namespace std; /** *回溯算法 *遍历出所有可能的前缀，以这个前缀来划分字符，判断是否满足Fibonacci数列 */ class Solution{ public: /** *@param str: input string */ vector<int> splitToFibonacci(string str) { vector<int> list; backTrack(list, str, str.length(), 0, 0, 0); return list; } /** *@return list: return the list *@param str: input string *@param length: the length of the input string *@param startPosition: index for string prefix *@param sum: the value of (prev + curr) *@param prev: 上一次划分的数字，需要用这个数字来计算prev+curr */ bool backTrack(vector<int>& list, const string str, const int length, int startPosition, long long sum, int prev) { //如果遍历完整个字符长度后，list中还没有3个或者3个以上的元素，则拆分失败 if (startPosition == length) { return list.size() >= 3; } long long curr = 0; for (int index = startPosition; index < length; ++index) { //剪枝1 //当前缀字符为0，不需要以此为前缀的字符划分了 if (index > startPosition && '0' == str[index]) { break; } //convert char to integer curr = curr * 10 + str[index] - '0'; //剪枝2 //curr溢出，退出 if (curr > INT_MAX) { break; } //剪枝3 //如果当前划分的数字，已经大于前边两个数之和，说明再往后划分，没有意义 if (list.size() >= 2) { if (curr < sum) continue; else if (curr > sum) break; } list.push_back(curr); //递归调用的时候判断是否满足Fibonacii数列特征，如果满足则继续，否则中断 if (backTrack(list, str, length, index + 1, prev + curr, curr)) { return true; } //这里相当于一个回溯的步骤 //不满足fibonacci数列，删除当前元素 list.pop_back(); } //如果是break出去的，就需要这里返回false return false; } }; int main() { string str = "11235813"; vector<int> listRet; Solution * solution = new Solution(); listRet = solution->splitToFibonacci(str); printf("After splitting the string, the Fibonacci list is:\n"); for (vector<int>::iterator iter = listRet.begin(); iter != listRet.end(); ++iter) { printf("%d ", *iter); } printf("\n"); string str2 = "123456579"; listRet = solution->splitToFibonacci(str2); printf("\n"); printf("After splitting the string, the Fibonacci list is:\n"); for (vector<int>::iterator iter = listRet.begin(); iter != listRet.end(); ++iter) { printf("%d ", *iter); } printf("\n"); }C code 易错点： 在加入元素到列表时，可能会用自增运算符，list_p[*listSize++]这个地方没有用括号，把指针括起来，运算的时候可能会计算listSize的地址，最终变为野指针。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #define true 1 #define false 0 #define INT_MAX 0xFFFFFFFF typedef _Bool bool; //declaration int* splitToFibonacci(char* str_p, int* retSize); bool backTrack(int* list_p, int* listSize, char* str_p, const int strLen, int startPosition, long long sum, int prev); /** *回溯算法 *遍历出所有可能的前缀，以这个前缀来划分字符，判断是否满足Fibonacci数列 */ /** *@param str_p: input string *@return retSize: return the list size */ int* splitToFibonacci(char* str_p, int* retSize) { assert(NULL != str_p); int len = strlen(str_p); //将字符转换为int数据了，所以分配空间的时候要用sizeof(int) int * list = (int*)malloc(sizeof(int)*len); *retSize = 0; backTrack(list, retSize, str_p, strlen(str_p), 0, 0, 0); return list; } /** *@return list_p: return the list *@param str_p: input string *@param strLen: the strLen of the input string *@param startPosition: index for string prefix *@param sum: the value of (prev + curr) *@param prev: 上一次划分的数字，需要用这个数字来计算prev+curr */ bool backTrack(int* list_p, int* listSize, char* str_p, const int strLen, int startPosition, long long sum, int prev) { assert(NULL != list_p && NULL != listSize && NULL != str_p); //如果遍历完整个字符长度后，list中还没有3个或者3个以上的元素，则拆分失败 if (startPosition == strLen) { return (*listSize >= 3); } long long curr = 0; for (int index = startPosition; index < strLen; ++index) { //剪枝1 //当前缀字符为0，不需要以此为前缀的字符划分了 if (index > startPosition && '0' == str_p[index]) { break; } //convert char to integer curr = curr * 10 + str_p[index] - '0'; //剪枝2 //curr溢出，退出 if (curr > INT_MAX) { break; } //剪枝3 //如果当前划分的数字，已经大于前边两个数之和，说明再往后划分，没有意义 if (*listSize >= 2) { if (curr < sum) continue; else if (curr > sum) break; } //list.push_back(curr); list_p[*listSize] = curr;//note: if list_p[*listSize++], then 野指针，因为这个坑，调了好久 (*listSize)++; //递归调用的时候判断是否满足Fibonacii数列特征，如果满足则继续，否则中断 if (backTrack(list_p, listSize, str_p, strLen, index + 1, prev + curr, curr)) { return true; } //这里相当于一个回溯的步骤 //不满足fibonacci数列，删除当前元素 //list.pop_back(); (*listSize)--; } //如果是break出去的，就需要这里返回false return false; } int main() { char strArr[] = {"11235813"}; char* strSrc_p = strArr; int retListSize = 0; int* arrList = NULL; arrList = splitToFibonacci(strSrc_p, &retListSize); printf("\nSplit the string into Fibonacci list:\n"); for (int index = 0; index < retListSize; ++index) { printf("%d ", arrList[index]); } printf("\n"); }题目 给定一包含n个整数的数组arr，找到与给定target最接近的三元组，返回这三个数之和。
样例1 输入：[2, 7, 11, 15], 3 输出：20 解释： 2+7+11 = 20 与3的绝对值之差最小。
解题思路
将数组排序，方便后边步骤遍历每个元素，固定这个元素，建立左右指针，比较当前元素和跟target的大小，如果相等，则返回。 3.如果不等，比较三元素之和与target大小，移动左右指针。 易错点 xxx示例代码 C++ code #include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <assert.h> using namespace std; #define arrLen 4 class Solution{ public: int threeSumClosest(int* arr_p, const int target) { assert(NULL != arr_p); //int arrLen = sizeof(arr)/sizeof(int); //sort the array sort(arr_p, arr_p+arrLen); int nearest = INT_MAX; int tempSum = 0; //loop the array for (int i = 0; i < arrLen - 2; ++i) { //剪枝1 if (i > 0 && arr_p[i] == arr_p[i - 1]) continue; //define double pointer int left = i + 1; int right = arrLen - 1; //双指针相向而行 while (left < right) { //calculate sum of the three elem tempSum = arr_p[left] + arr_p[right] + arr_p[i]; if (tempSum == target) return target; //update the nearest if (abs(tempSum - target) < abs(nearest - target)) nearest = tempSum; //move the pointer if (tempSum > target) { --right; //剪枝2 while (right >= 0 && arr_p[right] == arr_p[right+1]) --right; } else { ++left; //剪枝3 while (left < arrLen && arr_p[left] == arr_p[left - 1]) ++left; } } }//end loop return nearest; } }; int main() { Solution * solution = new Solution(); int array[] = {2, 7, 11, 15}; int retNearest = 0; retNearest = solution->threeSumClosest(array, 3); printf("The nearest num = %d\n", retNearest); return 0; }