一.14. 最长公共前缀题目描述编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀返回空字符串。示例 1输入strs [flower,flow,flight]输出fl示例 2输入strs [dog,racecar,car]输出解释输入不存在公共前缀。解题思路将第一个字符串当作基准前n个字符作为最长公共前缀随后遍历字符串与基准做比较如果不一样则输出最长公共前缀。代码实现char* longestCommonPrefix(char** strs, int strsSize) { //核心思路将第一个字符串当作基准前n个字符作为最长公共前缀 //遍历字符串与基准做比较如果不一样则输出最长公共前缀 //实现 //1.边界值判断和初始化 if(strsSize 0){ char *res (char*)malloc(sizeof(char) * 1); res[0] \0; return res; } //2.以第一个字符串为基准 int first_len strlen(strs[0]); int i; //逐个字符对比 for(i 0; i first_len; i){ char c strs[0][i]; //对比所有字符串 for(int j 1; j strsSize; j){ if(strs[j][i] \0 || strs[j][i] ! c){ char *res (char*)malloc(i 1); strncpy(res, strs[0], i); res[i] \0; return res; } } } //全部匹配malloc返回完整的字符串 char *res (char*)malloc(i 1); strcpy(res, strs[0]); return res; }问题解决1.为什么是strs[j][i]?因为以第一个字符串为基准第i个就是第一个字符串的第几个字符相当于列而j是从零遍历到strsSize相当于第几个字符串就是第几行。2.res[i] \0为什么要写字符串最后一定要加上‘\0’,如果结果没有\0打印会乱码3.为什么要处理“全部匹配”的情况因为当字符串都完全一样的时候最长公共前缀就是其本身这时候循环会直接跑完不返回return我们需要将基准字符串返回4.strncpy(res, strs[0], i)翻译过来就是 把基准字符串strs[0]的前 i 个字符复制到结果 res 里。总结只需要以第一个字符串作为基准作为前缀与后面的字符串进行比较不等时或遍历完时即可找到最长公共前缀。二.5. 最长回文子串题目描述给你一个字符串s找到s中最长的 回文 子串。示例 1输入s babad输出bab解释aba 同样是符合题意的答案。示例 2输入s cbbd输出bb解题思路暴力解法可以利用双指针来判断是否为回文字符串因为回文字符串首尾字符是相同的可以设置一个函数判断其是否为回文字符串。再寻找最长的回文子串即可。中心扩展算法从中心向左右两边扩散只要左右字符相等就是回文代码实现暴力//回文寻找函数 bool Palindrome(char *s, int left, int right){ while(left right){ if(s[left] ! s[right]) return false; left; right--; } return true; } char* longestPalindrome(char* s) { //回文字符串首尾一样 //核心思路不断存入字符串当符合回文寻找函数时满足题意 //回文寻找函数首尾是相同的双指针来遍历即可如果不一样则返回false否则返回true //1.初始化与边界值判断 int len strlen(s); if(len 1){ char *res (char*)malloc(len 1); strcpy(res, s); return res; } int maxLen 1; //最长回文长度最小为1 int start 0; //最长回文起始下标 //2.枚举所有子串的起始位置i for(int i 0; i len; i){ for(int j len - 1; j i; j--){ //判断是否为回文字符串 if(Palindrome(s, i, j)){ int curLen j - i 1; //更新最大长度 if(curLen maxLen){ maxLen curLen; start i; } break; } } } //3.分配结果内存并拷贝 char *res (char*)malloc(maxLen 1); strncpy(res, s start, maxLen); res[maxLen] \0; return res; }中心扩展算法int expandCenter(char *s, int l, int r){ while(l 0 s[l] s[r]){ l--; r; } return r - l - 1; } char* longestPalindrome(char* s) { int len strlen(s); if(len 1){ char *res malloc(len 1); strcpy(res, s); return res; } int start 0, maxLen 0; for(int i 0; i len; i){ int len1 expandCenter(s, i, i); int len2 expandCenter(s, i, i1); int curMax len1 len2 ? len1 : len2; if(curMax maxLen) { maxLen curMax; start i - (maxLen - 1) / 2; } } char *res malloc(maxLen 1); strncpy(res, s start, maxLen); res[maxLen] \0; return res; }总结暴力 分成两部分①找到回文字符串 ②找到最长的回文字符串①利用对撞双指针首尾相同为回文字符串②枚举遍历字符串找出回文字符串与已记录最长长度作比较中心扩展算法从中间开始往两边扩展如果相同则为回文子串同样分成两种①中心为奇数 ②中心为偶数三.67. 二进制求和题目描述给你两个二进制字符串a和b以二进制字符串的形式返回它们的和。示例 1输入:a 11, b 1输出100示例 2输入a 1010, b 1011输出10101解题思路二进制加法分成①无进位 0 0 0 0 1 1 1 0 1 和②有进制 1 1 1加法其实就是两数相加再加上进制我们从右往左加最后翻转即可代码实现char* addBinary(char* a, char* b) { //核心思路从后往前加用carry记录进位每一位计算分成当前位计算加上进位最后存到字符串里 //1.初始化 int lenA strlen(a); int lenB strlen(b); int carry 0; int maxLen lenA lenB ? lenA : lenB; //结果长度最多比最长的多1位 char *res (char*)malloc(maxLen 2); int index 0; //结果数组下标 //从后往前加 int i lenA - 1, j lenB - 1; while(i 0 || j 0 || carry 0){ //取当前位没有了就是0 int bitA (i 0) ? (a[i--] - 0) : 0; int bitB (j 0) ? (b[j--] - 0) : 0;// - 0 从字符转化为数字 //当前位总和 int sum bitA bitB carry; //当前位结果 res[index] (sum % 2) 0; //新的进位 carry sum / 2; } //字符串结束符 res[index] \0; //反转字符串 int left 0, right index - 1; while(left right) { char temp res[left]; res[left] res[right]; res[right] temp; left; right--; } return res; }总结二进制相加从右往左加总和等于当前位之和再加上进制再模2存入结果。
