5 .最长回文子串需要从头到尾得到最大部分分列的结果
//给定字符串s，找出s中最长的回文子串。 可以假设s的最大长度为1000。 //例1: ////输入： 'babad'//输出： 'bab'//注意： 'aba '也是有效的答案。 ////示例2:///: ' cbbd '//: ' bb '///related topics字符串动态规划//leetcodesubmitregionbegin (prohibitmopics DP问题int len=s.length (； boolean [ ] [ ] DP=new boolean [ len ] [ len ]； 输入最大值=0； String res=null； for(intj=0； j len； j ) for(intI=0； i=j； I () DP[I](j ) ) s.charat ) I )=) s.charat ) j ) ) j-i=2 || dp[i 1][j-1]； if(DP[I][j]j-I1maxlen ) (/beginindex ) -起始索引(包括)，索引从0开始。 结束索引- -结束索引。 //更新长度maxlen=j-i 1； RES=s.substring(I，j 1 )； } } } return res； }//leetcodesubmitregionend (prohibitmodificationanddeletion ) )。
647 .回文部分列数个数，自始至终
给定//字符串，计算该字符串中有多少个回文子串是你的任务。 //开始位置和结束位置不同的部分列即使由同一字符构成，也作为不同的部分列来计数。 //示例1: ///////输入： 'abc'//输出： 3//解释：的三个回文子串： 'a '、' b '、(c ) )////示例233606///////Related Topics字符串动态规划//leetcodesubmitregionbegin (prohibitmodificationanddeletion ) class solution { publicintcountcounts } int ans=0； for(intj=0； j len； j({DP[j][j]=true； for(intI=0； i=j； I () DP[I](j ) ) s.charat ) I )=) s.charat ) j ) ) j-i=2 || dp[i 1][j-1]； if(DP[I][j] ) ans； } } return ans； }//leetcodesubmitregionend (prohibitmodificationanddeletion ) )。
516 .最长回文子序列求从末尾到末尾的长度
class solution { publicintlongestpalindromesubseq (strings ) { int len=s.length )； //直接int int[][] dp=new int[len][len]； 输入最大值=0；//从右到左遍历for (inti=len-1； i=0； (i-- ) ) /单字符dp[i][i]=1； for(intj=I1； Jj
len;j++){ if(s.charAt(i)==s.charAt(j)) dp[i][j]=dp[i+1][j-1]+2; else dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]); } } return dp[0][len-1]; }}
125. 验证回文串 双指针判断
//给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 //// 说明：本题中，我们将空字符串定义为有效的回文串。 //// 示例 1: //// 输入: "A man, a plan, a canal: Panama"//输出: true// //// 示例 2: //// 输入: "race a car"//输出: false// // Related Topics 双指针 字符串//leetcode submit region begin(Prohibit modification and deletion)class Solution { public boolean isPalindrome(String s) { int i=0,j=s.length()-1; while(i<j){ //需要i<j && 保证不会超限 while(i<j && !Character.isLetterOrDigit(s.charAt(i))) i++; while(i<j && !Character.isLetterOrDigit(s.charAt(j))) j--; //这里也需要判断一下，保证此时满足条件 if(i<j) { if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) return false; i++; j--; } } return true; }}//leetcode submit region end(Prohibit modification and deletion)
234. 回文链表 旋转链表，判断
//请判断一个链表是否为回文链表。 //// 示例 1: //// 输入: 1->2//输出: false //// 示例 2: //// 输入: 1->2->2->1//输出: true// //// 进阶： //你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ // Related Topics 链表 双指针//leetcode submit region begin(Prohibit modification and deletion)/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public boolean isPalindrome(ListNode head) { if(head == null ) return true; ListNode slow=head; ListNode fast=head; while(fast!=null && fast.next!=null){ slow=slow.next; fast=fast.next.next; } ListNode mid=rev(slow); ListNode curr1=head; ListNode curr2=mid; while(curr1!=null && curr2 != null){ if(curr1.val != curr2.val) return false; curr1 = curr1.next; curr2 = curr2.next; } return true; } private ListNode rev(ListNode head){ ListNode cur=null; ListNode pre=head; while(pre!=null){ ListNode t=pre.next; pre.next=cur; cur=pre; pre=t; } return cur; }}//leetcode submit region end(Prohibit modification and deletion)409. 最长回文串 根据字符构建长度 map维护
//给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。 //// 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 //// 注意: //假设字符串的长度不会超过 1010。 //// 示例 1: //// //输入://"abccccdd"////输出://7////解释://我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。// // Related Topics 哈希表import java.util.HashMap;import java.util.Map;//leetcode submit region begin(Prohibit modification and deletion)class Solution { public int longestPalindrome(String s) { Map<Character,Integer> mymap=new HashMap<>(); //转换为字符 for(Character str:s.toCharArray()){ mymap.put(str,mymap.getOrDefault(str,0)+1); } int ans=0; for(Character key:mymap.keySet()){ int val=mymap.get(key); if(val%2==0) ans+=val; else ans+=val-1; } if(ans<s.length()) ans+=1; return ans; }}//leetcode submit region end(Prohibit modification and deletion)