😁算法小白欢迎加入此社区：https://bbs.csdn.net/forums/hero?category=0
由英雄大佬带领的抱团学算法队伍，从0开始，期待你的加入🥳
本博文是对此文章习题所作的题解，如有不足，请多指教：https://blog.csdn.net/WhereIsHeroFrom/article/details/121327072
今日题解：
第一题：https://leetcode-cn.com/problems/palindrome-permutation-lcci/
本题的思路是先把每一位字母存进去，然后统计个数，最后如果某个字母个数是偶数是符合题意的，但是如果有一个奇数个数的字母就到达极限了，再多一个的话，就无法构成回文数了。
class Solution {
public boolean canPermutePalindrome(String s) {
char[] cz = s.toCharArray();
int[] target = new int[800];
for (char c : cz){
target[c] = target[c] + 1;
}
int count = 0;
for (int i : target) {
if(i % 2 != 0) {
count++;
}
if(count > 1) {
return false;
}
}
return true;
}
}
第二题：https://leetcode-cn.com/problems/XltzEq/
定义一个左指针，定义一个右指针，然后依次往中间挪动，因为题目说了不考虑大小写了，所以使用java里面的toLowerCase方法来实现。
class Solution {
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while(left <= right){
if(!Character.isLetterOrDigit(s.charAt(left))){
left = left + 1;
}else if(!Character.isLetterOrDigit(s.charAt(right))){
right = right - 1;
}else{
char char1 = Character.toLowerCase(s.charAt(left++));
char char2 = Character.toLowerCase(s.charAt(right--));
if (char1 != char2) {
return false;
}
}
}
return true;
}
}
第三题：https://leetcode-cn.com/problems/valid-palindrome/
和上面的题思路一样。
class Solution {
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while(left <= right){
if(!Character.isLetterOrDigit(s.charAt(left))){
left = left + 1;
}else if(!Character.isLetterOrDigit(s.charAt(right))){
right = right - 1;
}else{
char char1 = Character.toLowerCase(s.charAt(left++));
char char2 = Character.toLowerCase(s.charAt(right--));
if (char1 != char2) {
return false;
}
}
}
return true;
}
}
第四题：https://leetcode-cn.com/problems/longest-palindrome/
我们首先把小写字母和大写字母的数量分别统计下来，然后我们遍历数组，如果我们的个数是偶数，直接算进去即可，如果是奇数，我们先减掉一个一，然后把定义的布尔类型变量的值进行改变，然后当flag为true时，代表中间还有一个没有算进去的，所以再加一，否则，直接返回即可。
class Solution {
public int longestPalindrome(String s) {
int[] array = new int[52];
for(char c : s.toCharArray()){
if(c >= 'a' && c <= 'z'){
array[c-'a']++;
}else{
array[c-'A'+26]++;
}
}
int number = 0;
boolean flag = false;
for(int n : array){
if(n % 2 == 0){
number = number + n;
}else{
number = number + n - 1;
flag = true;
}
}
if(flag){
return number + 1;
}else{
return number;
}
}
}
第五题：https://leetcode-cn.com/problems/RQku0D/
定义两个指针，一个左指针，一个右指针，然后想法和上面的题是一样的。
class Solution{
public boolean validPalindrome(String s){
int left = 0;
int right = s.length() - 1;
while(left < right){
if(s.charAt(left) == s.charAt(right)){
left = left + 1;
right = right - 1;
}else{
break;
}
}
if(left >= right || isPalindrome(s,left+1,right) || isPalindrome(s,left,right-1)){
return true;
}else{
return false;
}
}
public boolean isPalindrome(String s, int p1, int p2){
while(p1 < p2){
if (s.charAt(p1) == s.charAt(p2)){
p1 = p1 + 1;
p2 = p2 - 1;
}else{
break;
}
}
if(p1 >= p2){
return true;
}else{
return false;
}
}
}
第六题：https://leetcode-cn.com/problems/valid-palindrome-ii/
同上，题目一样。
class Solution{
public boolean validPalindrome(String s){
int left = 0;
int right = s.length() - 1;
while(left < right){
if(s.charAt(left) == s.charAt(right)){
left = left + 1;
right = right - 1;
}else{
break;
}
}
if(left >= right || isPalindrome(s,left+1,right) || isPalindrome(s,left,right-1)){
return true;
}else{
return false;
}
}
public boolean isPalindrome(String s, int p1, int p2){
while(p1 < p2){
if (s.charAt(p1) == s.charAt(p2)){
p1 = p1 + 1;
p2 = p2 - 1;
}else{
break;
}
}
if(p1 >= p2){
return true;
}else{
return false;
}
}
}
第七题：https://leetcode-cn.com/problems/remove-palindromic-subsequences/
根据题意可以得知，删除的字符串不一定是相连的，所以我们如果字符串为空，那么直接返回0，如果字符串定义左右指针遍历时发现有不一样的，那么最多两次就可以全部删除。
class Solution {
public int removePalindromeSub(String s) {
if(s.equals("")){
return 0;
}
int l = 0;
int r = s.length() - 1;
for( ;l < r; l++,r--){
if(s.charAt(l) != s.charAt(r)){
return 2;
}
}
return 1;
}
}
第八题：https://leetcode-cn.com/problems/shortest-palindrome/
留下题目，欢迎各位大佬去玩耍。
有问题欢迎留言，欢迎加入“万人千题”社区，在这里一起努力。