区块链技术博客
www.b2bchain.cn

leetcode总结-回文串,回文序列

这篇文章主要介绍了leetcode总结-回文串,回文序列,通过具体代码讲解7996并且分析了leetcode总结-回文串,回文序列的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了leetcode总结-回文串,回文序列。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7996.html。具体如下:

5. 最长回文子串    从头到尾 需要得到最大子串结果

 //给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。  // // 示例 1:  // // 输入: "babad" //输出: "bab" //注意: "aba" 也是一个有效答案。 //  // // 示例 2:  // // 输入: "cbbd" //输出: "bb" //  // Related Topics 字符串 动态规划     //leetcode submit region begin(Prohibit modification and deletion) //DP问题 先移动j后移动i class Solution {     public String longestPalindrome(String s) {         if(s==null ||s.length()==0) return "";        int len=s.length();        boolean[][] dp=new boolean[len][len];        int maxlen=0;       String res=null;         for (int j = 0; j <len ; j++) {             for (int i = 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-i+1>maxlen){                      //切分beginIndex -- 起始索引(包括), 索引从 0 开始。endIndex -- 结束索引(不包括)。                      //更新长度                      maxlen=j-i+1;                      res=s.substring(i,j+1);                  }             }         }         return res;     } } //leetcode submit region end(Prohibit modification and deletion)

 

647. 回文子串  计算个数,从头到尾计数 

 //给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。  // // 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。  // // 示例 1:  // //  //输入: "abc" //输出: 3 //解释: 三个回文子串: "a", "b", "c". //  // // 示例 2:  // //  //输入: "aaa" //输出: 6 //说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa". //  // // 注意:  // //  // 输入的字符串长度不会超过1000。  //  // Related Topics 字符串 动态规划   //leetcode submit region begin(Prohibit modification and deletion) class Solution {     public int countSubstrings(String s) {        int len=s.length();        boolean [][] dp=new boolean[len][len];        int ans=0;         for (int j = 0; j <len ; j++) {             dp[j][j]=true;             for (int i = 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;     } } //leetcode submit region end(Prohibit modification and deletion) 

 

516. 最长回文子序列   从尾到头 求长度

 class Solution {     public int longestPalindromeSubseq(String s) {         int len=s.length();         //直接定义为int          int[][] dp=new int[len][len];          int maxLen=0;          //从右往左遍历          for(int i=len-1;i>=0;i--){              //单字符              dp[i][i]=1;                for(int j=i+1;j<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) 

 

本文地址https://www.b2bchain.cn/7996.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » leetcode总结-回文串,回文序列
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们