零、写在前面
今天是打卡的第26天，好像用力过猛了，好困好累，幸亏有你们一起，不然还真坚持不下来呢。老规矩，知识点在。
《算法零基础100讲》(第26讲) 字符串算法(六) - 回文串https://blog.csdn.net/WhereIsHeroFrom/article/details/121327072
https://blog.csdn.net/WhereIsHeroFrom/article/details/121327072
一、主要知识点
1.判断字符串是否是回文字符串
从前往后判断就好了，判断前半段是否等于后半段。
bool judgePalindrome(char *s) { // 判断是否是回文串 int i; int len = strlen(s); for(i = 0; i < len/2; ++i) { if(s[i] != s[len-1-i]) { return false; } } return true; }
二、课后习题
面试题 01.04. 回文排列
面试题 01.04. 回文排列
https://leetcode-cn.com/problems/palindrome-permutation-lcci/
题目描述
给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。
思路
其实很简单，相同元素的个数必须是偶数，如果有是奇数的最多只有一个。看代码把
bool canPermutePalindrome(char* s){ int hash[256] = {0},count = 0; for(int i = 0;s[i];i++) hash[s[i]]++; //统计相同元素个数 for(int i = 0;i < 256;i++) if(hash[i] & 1) count++;//计算奇数个数 return count < 2; }
剑指 Offer II 018. 有效的回文
剑指 Offer II 018. 有效的回文
https://leetcode-cn.com/problems/XltzEq/
题目描述
给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。
思路
利用hash表记录所有的值，记录过程中顺带大写改成小写，然后进行回文串的判定就好了。
bool isPalindrome(char * s){ char hash[200010]; int size = 0; for(int i = 0;s[i];i++)//插入 并替换大写字母 if(s[i] >= 'a' && s[i] <= 'z') hash[size++] = s[i]; else if(s[i] >= 'A' && s[i] <= 'Z') hash[size++] = s[i] + ' '; else if(s[i] >= '0'&&s[i]<='9') hash[size++] = s[i]; int i,j; for(i =0,j = size - 1;i < j;i++,j--) //查看是否是回文数组 if(hash[i] != hash[j]) return false; return true; }
125. 验证回文串
125. 验证回文串
https://leetcode-cn.com/problems/valid-palindrome/
题目描述
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
思路
看上题，，，一毛一样？？？？水题。。。
125. 验证回文串
125. 验证回文串
https://leetcode-cn.com/problems/valid-palindrome/
题目描述
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
思路
这个其实就是扫描偶数个数的元素来组嘛。如果全是偶数个数，就是全部，如果有多个是奇数。就+1。
int longestPalindrome(char * s){ int hash[256],size = 0,ans = 0; memset(hash,0,sizeof(hash)); for(int i = 0;s[i];i++) //记录元素个数 hash[s[i]]++,size++; for(int i = 0;i <256;i++) if(hash[i]/2) ans += (hash[i]/2)*2;//统计元素个数能组成多少对 if(ans < size) ans++; //还有元素 就+1 return ans; }
剑指 Offer II 019. 最多删除一个字符得到回文
剑指 Offer II 019. 最多删除一个字符得到回文
https://leetcode-cn.com/problems/RQku0D/
题目描述
给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
思路
双指针，扫描，当扫到不一致的时候，判断去掉左端点或者右端点之后剩余元素是否是回文串即可。
bool isPalindome(char *s,int i, int j){ //判断i-j是否回文串 while(i < j) if(s[i++]!=s[j--]) return false; return true; } bool validPalindrome(char * s){ int i = 0,j = strlen(s) - 1; while(i < j){ //找到第一个不相等元素 if(s[i]!=s[j]) return isPalindome(s,i,j-1)||isPalindome(s,i+1,j); i++; j--; } return true; }
1332. 删除回文子序列
1332. 删除回文子序列
https://leetcode-cn.com/problems/remove-palindromic-subsequences/
题目描述
给你一个字符串 s，它仅由字母 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。
返回删除给定字符串中所有字符（字符串为空）的最小删除次数。
「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。
思路
想了三分钟，复杂度好高啊。但是。这是简单题啊！！简单题 emmm，不对劲。子序列好像不要求连续。那一共好像就俩字母，把这俩分别抽出来不就是子序列？那不就两次？最多两次？空串零次？回文串一次？
int removePalindromeSub(char * s){ if(!s[0]) return 0; //空串 for(int i = 0,j = strlen(s) - 1;i<j;i++,j--){ if(s[i]!=s[j]) return 2; //非回文串 } return 1; //回文串 }
214. 最短回文串
214. 最短回文串
https://leetcode-cn.com/problems/shortest-palindrome/
题目描述
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
思路
这个其实是去找到S和S的反序串的匹配长度。可以用kmp算法优化时间。kmp算法最重要的东西是next数组。
char * shortestPalindrome(char * s){ int n = strlen(s); int next[n + 1]; memset(next, -1, sizeof(next));//next数组初始化 for (int i = 1; i < n; ++i) { int j = next[i - 1]; while (j != -1 && s[j + 1] != s[i]) //找到上个元素的匹配，看下一个是否匹配 j = next[j]; //不匹配继续查看上个元素的匹配项 if (s[j + 1] == s[i]) //找到则更新值 next[i] = j + 1; } int base = -1; for (int i = n - 1; i >= 0; --i) { while (base != -1 && s[base + 1] != s[i]) //开始匹配 base = next[base]; //匹配失败更新值 if (s[base + 1] == s[i]) //匹配成功增加base ++base; } int qian_len = n - base - 1,retsize =0;//前面需要添加元素个数 char* ret = malloc(sizeof(char) * (qian_len + n + 1));//申请空间 for (int i = 0; i < qian_len; i++) ret[retsize++] = s[n - i - 1];//写入前面元素 for (int i = 0; i < n; i++) ret[retsize++] = s[i];//写入s ret[retsize++] = 0; //返回 return ret; }
写在最后
好累啊，但是等下要去找外教聊聊天。希望不要睡着。0.0
