java回文面试题及答案

java回文面试题及答案1.判断一个字符串是否是回文串```javapublicclassPalindromeChecker{publicstaticbooleanisPalindrome(Stringstr){intleft=0;intright=str.length()-1;while(left<right){if(str.charAt(left)!=str.charAt(right)){returnfalse;}left++;right--;}returntrue;}publicstaticvoidmain(String[]args){Stringtest="radar";System.out.println(isPalindrome(test));}}```答案分析：使用双指针法，从字符串两端向中间移动，比较对应字符，若有不同则不是回文串。2.判断一个整数是否是回文数```javapublicclassPalindromeNumber{publicstaticbooleanisPalindrome(intx){if(x<0)returnfalse;intoriginal=x;intreversed=0;while(x!=0){reversed=reversed10+x%10;x/=10;}returnoriginal==reversed;}publicstaticvoidmain(String[]args){intnum=121;System.out.println(isPalindrome(num));}}```答案分析：将整数反转，与原数比较，若相等则是回文数。负数直接排除。3.找出字符串中最长的回文子串```javapublicclassLongestPalindromicSubstring{publicstaticStringlongestPalindrome(Strings){if(s==null||s.length()<1)return"";intstart=0,end=0;for(inti=0;i<s.length();i++){intlen1=expandAroundCenter(s,i,i);intlen2=expandAroundCenter(s,i,i+1);intlen=Math.max(len1,len2);if(len>end-start){start=i-(len-1)/2;end=i+len/2;}}returns.substring(start,end+1);}privatestaticintexpandAroundCenter(Strings,intleft,intright){while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){left--;right++;}returnright-left-1;}publicstaticvoidmain(String[]args){Stringstr="babad";System.out.println(longestPalindrome(str));}}```答案分析：以每个字符或相邻两个字符为中心向两边扩展，找出最长回文子串。4.找出字符串中所有的回文子串```javaimportjava.util.ArrayList;importjava.util.List;publicclassAllPalindromicSubstrings{publicstaticList<String>findAllPalindromes(Strings){List<String>result=newArrayList<>();for(inti=0;i<s.length();i++){for(intj=i;j<s.length();j++){if(isPalindrome(s.substring(i,j+1))){result.add(s.substring(i,j+1));}}}returnresult;}privatestaticbooleanisPalindrome(Stringstr){intleft=0;intright=str.length()-1;while(left<right){if(str.charAt(left)!=str.charAt(right)){returnfalse;}left++;right--;}returntrue;}publicstaticvoidmain(String[]args){Stringstr="abc";List<String>palindromes=findAllPalindromes(str);System.out.println(palindromes);}}```答案分析：使用两层循环遍历所有子串，判断每个子串是否为回文串。5.判断一个字符串是否可以通过重新排列组成回文串```javaimportjava.util.HashMap;importjava.util.Map;publicclassCanFormPalindrome{publicstaticbooleancanPermutePalindrome(Strings){Map<Character,Integer>map=newHashMap<>();for(charc:s.toCharArray()){map.put(c,map.getOrDefault(c,0)+1);}intoddCount=0;for(intcount:map.values()){if(count%2!=0){oddCount++;}if(oddCount>1){returnfalse;}}returntrue;}publicstaticvoidmain(String[]args){Stringstr="aabbc";System.out.println(canPermutePalindrome(str));}}```答案分析：统计字符出现次数，最多只能有一个字符出现奇数次。6.最小插入次数使字符串成为回文串```javapublicclassMinInsertionsToPalindrome{publicstaticintminInsertions(Strings){intn=s.length();int[][]dp=newint[n][n];for(intlen=2;len<=n;len++){for(inti=0;i<=n-len;i++){intj=i+len-1;if(s.charAt(i)==s.charAt(j)){dp[i][j]=dp[i+1][j-1];}else{dp[i][j]=Math.min(dp[i+1][j],dp[i][j-1])+1;}}}returndp[0][n-1];}publicstaticvoidmain(String[]args){Stringstr="abca";System.out.println(minInsertions(str));}}```答案分析：使用动态规划，`dp[i][j]`表示将`s[i...j]`变成回文串的最小插入次数。7.分割字符串，使每个子串都是回文串，求最少分割次数```javapublicclassPalindromePartitioningII{publicstaticintminCut(Strings){intn=s.length();boolean[][]isPalindrome=newboolean[n][n];int[]dp=newint[n];for(inti=0;i<n;i++){dp[i]=i;for(intj=0;j<=i;j++){if(s.charAt(i)==s.charAt(j)&&(i-j<2||isPalindrome[j+1][i-1])){isPalindrome[j][i]=true;if(j==0){dp[i]=0;}else{dp[i]=Math.min(dp[i],dp[j-1]+1);}}}}returndp[n-1];}publicstaticvoidmain(String[]args){Stringstr="aab";System.out.println(minCut(str));}}```答案分析：使用动态规划，`dp[i]`表示`s[0...i]`的最少分割次数。8.判断一个链表是否是回文链表```javaclassListNode{intval;ListNodenext;ListNode(intx){val=x;}}publicclassPalindromeLinkedList{publicstaticbooleanisPalindrome(ListNodehead){if(head==null||head.next==null)returntrue;ListNodeslow=head;ListNodefast=head;while(fast.next!=null&&fast.next.next!=null){slow=slow.next;fast=fast.next.next;}ListNodesecondHalf=reverseList(slow.next);ListNodep1=head;ListNodep2=secondHalf;while(p2!=null){if(p1.val!=p2.val){returnfalse;}p1=p1.next;p2=p2.next;}returntrue;}privatestaticListNodereverseList(ListNodehead){ListNodeprev=null;ListNodecurr=head;while(curr!=null){ListNodenextTemp=curr.next;curr.next=prev;prev=curr;curr=nextTemp;}returnprev;}publicstaticvoidmain(String[]args){ListNodehead=newListNode(1);head.next=newListNode(2);head.next.next=newListNode(2);head.next.next.next=newListNode(1);System.out.println(isPalindrome(head));}}```答案分析：先找到链表中点，反转后半部分链表，再比较前后两部分。9.找出数组中所有可以组成回文对的索引对```javaimportjava.util.ArrayList;importjava.util.HashMap;importjava.util.List;importjava.util.Map;publicclassPalindromePairs{publicstaticList<List<Integer>>palindromePairs(String[]words){List<List<Integer>>result=newArrayList<>();Map<String,Integer>map=newHashMap<>();for(inti=0;i<words.length;i++){map.put(words[i],i);}for(inti=0;i<words.length;i++){for(intj=0;j<=words[i].length();j++){Stringstr1=words[i].substring(0,j);Stringstr2=words[i].substring(j);if(isPalindrome(str1)){Stringstr2Rev=newStringBuilder(str2).reverse().toString();if(map.containsKey(str2Rev)&&map.get(str2Rev)!=i){result.add(List.of(map.get(str2Rev),i));}}if(str2.length()!=0&&isPalindrome(str2)){Stringstr1Rev=newStringBuilder(str1).reverse().toString();if(map.containsKey(str1Rev)&&map.get(str1Rev)!=i){result.add(List.of(i,map.get(str1Rev)));}}}}returnresult;}privatestaticbooleanisPalindrome(Stringstr){intleft=0;intright=str.length()-1;while(left<right){if(str.charAt(left)!=str.charAt(right)){returnfalse;}left++;right--;}returntrue;}publicstaticvoidmain(String[]args){String[]words={"abcd","dcba","lls","s","sssll"};List<List<Integer>>pairs=palindromePairs(words);System.out.println(pairs);}}```答案分析：使用哈希表存储单词及其索引，对每个单词分割，判断前后部分是否为回文，再找对应反转字符串。10.找出给定字符串的所有回文子序列的数量```javapublicclassCountPalindromicSubsequences{publicstaticintcountPalindromicSubsequences(Strings){intn=s.length();int[][]dp=newint[n][n];for(inti=0;i<n;i++){dp[i][i]=1;}for(intlen=2;len<=n;len++){for(inti=0;i<=n-len;i++){intj=i+len-1;if(s.charAt(i)==s.charAt(j)){dp[i][j]=dp[i+1][j-1]2;intleft=i+1;intright=j-1;while(left<=right&&s.charAt(left)!=s.charAt(i)){left++;}while(left<=right&&s.charAt(right)!=s.charAt(i)){right--;}if(left>right){dp[i][j]+=2;}elseif(left==right){dp[i][j]+=1;}else{dp[i][j]-=dp[left+1][right-1];}}else{dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];}}}returndp[0][n-1];}publicstaticvoidmain(String[]args){Stringstr="bccb";System.out.println(countPalindromicSubsequences(str));}}```答案分析：使用动态规划，`dp[i][j]`表示`s[i...j]`的回文子序列数量。11.判断一个字符串是否是另一个字符串的回文排列```javaimportjava.util.HashMap;importjava.util.Map;publicclassIsPermutationPalindrome{publicstaticbooleanisPermutationPalindrome(Strings1,Strings2){if(s1.length()!=s2.length())returnfalse;Map<Character,Integer>map=newHashMap<>();for(charc:s1.toCharArray()){map.put(c,map.getOrDefault(c,0)+1);}for(charc:s2.toCharArray()){if(!map.containsKey(c)||map.get(c)==0){returnfalse;}map.put(c,map.get(c)-1);}returntrue;}publicstaticvoidmain(String[]args){Strings1="abc";Strings2="bca";System.out.println(isPermutationPalindrome(s1,s2));}}```答案分析：统计字符出现次数，比较两个字符串的字符出现情况。12.找出最短的可以添加到字符串前面使其成为回文串的字符串```javapublicclassShortestPalindrome{publicstaticStringshortestPalindrome(Strings){inti=0;for(intj=s.length()-1;j>=0;j--){if(s.charAt(i)==s.charAt(j)){i++;}}if(i==s.length())returns;Stringsuffix=s.substring(i);StringsuffixRev=newStringBuilder(suffix).reverse().toString();returnsuffixRev+shortestPalindrome(s.substring(0,i))+suffix;}publicstaticvoidmain(String[]args){Stringstr="aacecaaa";System.out.println(shortestPalindrome(str));}}```答案分析：找到最长的从开头开始的回文子串，将剩余部分反转添加到前面。13.判断一个字符串是否是回文串，忽略大小写和非字母数字字符```javapublicclassValidPalindromeIgnore{publicstaticbooleanisPalindrome(Strings){s=s.replaceAll("[^A-Za-z0-9]","").toLowerCase();intleft=0;intright=s.length()-1;while(left<right){if(s.charAt(left)!=s.charAt(right)){returnfalse;}left++;right--;}returntrue;}publicstaticvoidmain(String[]args){Stringstr="Aman,aplan,acanal:Panama";System.out.println(isPalindrome(str));}}```答案分析：先处理字符串，去除非字母数字字符并转换为小写，再用双指针判断。14.找出一个字符串中最长的连续回文子序列的长度```javapublicclassLongestContinuousPalindromicSubsequence{publicstaticintlongestContinuousPalindromicSubsequence(Strings){intn=s.length();intmaxLen=0;for(inti=0;i<n;i++){for(intj=i;j<n;j++){if(isPalindrome(s.substring(i,j+1))){maxLen=Math.max(