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(