java算法題：最長(zhǎng)回文串

Honwhy 發(fā)布于2019-08-19 11:47 / 3415人閱讀

摘要：給定一個(gè)包含大寫(xiě)字母和小寫(xiě)字母的字符串，找到通過(guò)這些字母構(gòu)造成的最長(zhǎng)的回文串。比如不能當(dāng)做一個(gè)回文字符串。注意假設(shè)字符串的長(zhǎng)度不會(huì)超過(guò)。代碼實(shí)現(xiàn)最長(zhǎng)回文串回文串是一個(gè)正讀和反讀都一樣的字符串，比如或者等等就是回文串。

LeetCode: 給定一個(gè)包含大寫(xiě)字母和小寫(xiě)字母的字符串，找到通過(guò)這些字母構(gòu)造成的最長(zhǎng)的回文串。在構(gòu)造過(guò)程中，請(qǐng)注意區(qū)分大小寫(xiě)。比如"Aa"不能當(dāng)做一個(gè)回文字符串。注意:假設(shè)字符串的長(zhǎng)度不會(huì)超過(guò) 1010。

思路：利用hashset，遍歷字符串?dāng)?shù)組，判斷字符是否在hashset中，如果在則加2，并在hashset中移除改字符，反之則放入hashset中
，最后判斷count是否大于字符串長(zhǎng)度。

代碼實(shí)現(xiàn)：

/**
 * @author:eason
 * @desc:最長(zhǎng)回文串（“回文串”是一個(gè)正讀和反讀都一樣的字符串，比如“l(fā)evel”或者“noon”等等就是回文串。）
 * @思路:利用hashset，遍歷字符串?dāng)?shù)組，判斷字符是否在hashset中，如果在則加2，并在hashset中移除改字符，反之則放入hashset中
 * ，最后判斷count是否大于字符串長(zhǎng)度
 */
public class LongestPalindromic {
    public int getLonestLength(String s){
        int count = 0;
        char[] chars = s.toCharArray();
        HashSet set = new HashSet();
        for(int i = 0;i < chars.length; i++){
            char b = chars[i];
            if(set.contains(b)){
                count += 2;
                set.remove(b);
            }else{
                set.add(b);
            }
        }
        if(count < s.length()){
            count ++;
        }
        return count;
    }

    public static void main(String[] args) {
        String s = "assdsdgggggaa";
        LongestPalindromic longestPalindromic = new LongestPalindromic();
        System.out.println(longestPalindromic.getLonestLength(s));
    }
}

GPU云服務(wù)器云服務(wù)器 java拼湊回文串 java有趣算法題 java算法題冒泡回文字符串算法c語(yǔ)言

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/77885.html

相關(guān)文章

[算法總結(jié)] 搞定 BAT 面試——幾道常見(jiàn)的子符串算法題

摘要：第一種方法常規(guī)方法。如果不存在公共前綴，返回空字符串。注意假設(shè)字符串的長(zhǎng)度不會(huì)超過(guò)。說(shuō)明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個(gè)可能的最長(zhǎng)回文子序列為。數(shù)值為或者字符串不是一個(gè)合法的數(shù)值則返回。說(shuō)明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點(diǎn)：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 評(píng)論0 收藏0
JS算法題之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一個(gè)字符，判斷正負(fù)符號(hào)，若是英文直接返回，若數(shù)字則不取。回文數(shù)題目描述判斷一個(gè)整數(shù)是否是回文數(shù)。回文數(shù)是指正序從左向右和倒序從右向左讀都是一樣的整數(shù)。 JS算法題之leetcode(1~10) 前言一直以來(lái)，前端開(kāi)發(fā)的知識(shí)儲(chǔ)備在數(shù)據(jù)結(jié)構(gòu)以及算法層面是有所暫缺的，可能歸根于我們的前端開(kāi)發(fā)的業(yè)務(wù)性質(zhì)，但是我認(rèn)為任何的編程崗位都離不開(kāi)數(shù)據(jù)結(jié)構(gòu)以及算法。因此，我作為...

SoapEye 2019-08-26 10:44 評(píng)論0 收藏0
最長(zhǎng)回文子串——Manacher 算法

摘要：?jiǎn)栴}定義最長(zhǎng)回文子串問(wèn)題給定一個(gè)字符串，求它的最長(zhǎng)回文子串長(zhǎng)度。可以采用動(dòng)態(tài)規(guī)劃，列舉回文串的起點(diǎn)或者終點(diǎn)來(lái)解最長(zhǎng)回文串問(wèn)題，無(wú)需討論串長(zhǎng)度的奇偶性。 0. 問(wèn)題定義最長(zhǎng)回文子串問(wèn)題：給定一個(gè)字符串，求它的最長(zhǎng)回文子串長(zhǎng)度。如果一個(gè)字符串正著讀和反著讀是一樣的，那它就是回文串。下面是一些回文串的實(shí)例： 12321 a aba abba aaaa tatt...

mingzhong 2019-07-24 18:10 評(píng)論0 收藏0
LeetCode——Longest Palindromic Substring

摘要：題目即求最長(zhǎng)回文子序列原題鏈接此篇博客僅為學(xué)習(xí)記錄我的解法及代碼暴力解決，用及進(jìn)行兩層遍歷循環(huán)中套一層循環(huán)，用遍歷，求最長(zhǎng)回文序列字符串，同時(shí)用變量記錄最長(zhǎng)子序列這種寫(xiě)法很暴力，效率很低，一層循環(huán)，一層循環(huán)，回文序列對(duì)比一層，時(shí)間復(fù)雜度為辣題目： Given a string s, find the longest palindromic substring in s. You ma...

shevy 2019-08-23 18:26 評(píng)論0 收藏0
2017年校招全國(guó)統(tǒng)一模擬筆試(第五場(chǎng))編程題集合(Javascript版)

摘要：地址年校招全國(guó)統(tǒng)一模擬筆試第五場(chǎng)編程題集合偶串如果一個(gè)字符串由兩個(gè)相同字符串連接而成就稱(chēng)這個(gè)字符串是偶串。第個(gè)提示是或者表示牛牛選擇的數(shù)是否是的倍數(shù)。牛牛決定換掉一些瓷磚的顏色使得相鄰兩塊瓷磚的顏色均不相同。地址：2017年校招全國(guó)統(tǒng)一模擬筆試(第五場(chǎng))編程題集合偶串 (AC) 如果一個(gè)字符串由兩個(gè)相同字符串連接而成,就稱(chēng)這個(gè)字符串是偶串。例如xyzxyz和aaaaaa是偶串,但...

hedge_hog 2019-08-23 11:42 評(píng)論0 收藏0