java算法题：最长回文串

Honwhy 发布于2019-08-19 11:47 / 3372人阅读

摘要：给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。比如不能当做一个回文字符串。注意假设字符串的长度不会超过。代码实现最长回文串回文串是一个正读和反读都一样的字符串，比如或者等等就是回文串。

LeetCode: 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如"Aa"不能当做一个回文字符串。注意:假设字符串的长度不会超过 1010。

思路：利用hashset，遍历字符串数组，判断字符是否在hashset中，如果在则加2，并在hashset中移除改字符，反之则放入hashset中
，最后判断count是否大于字符串长度。

代码实现：

/**
 * @author:eason
 * @desc:最长回文串（“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。）
 * @思路:利用hashset，遍历字符串数组，判断字符是否在hashset中，如果在则加2，并在hashset中移除改字符，反之则放入hashset中
 * ，最后判断count是否大于字符串长度
 */
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));
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77885.html

[算法总结] 搞定 BAT 面试——几道常见的子符串算法题

摘要：第一种方法常规方法。如果不存在公共前缀，返回空字符串。注意假设字符串的长度不会超过。说明本题中，我们将空字符串定义为有效的回文串。示例输入输出一个可能的最长回文子序列为。数值为或者字符串不是一个合法的数值则返回。说明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站点：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 评论0 收藏0
JS算法题之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回，若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 JS算法题之leetcode(1~10) 前言一直以来，前端开发的知识储备在数据结构以及算法层面是有所暂缺的，可能归根于我们的前端开发的业务性质，但是我认为任何的编程岗位都离不开数据结构以及算法。因此，我作为...

SoapEye 2019-08-26 10:44 评论0 收藏0
最长回文子串——Manacher 算法

摘要：问题定义最长回文子串问题给定一个字符串，求它的最长回文子串长度。可以采用动态规划，列举回文串的起点或者终点来解最长回文串问题，无需讨论串长度的奇偶性。 0. 问题定义最长回文子串问题：给定一个字符串，求它的最长回文子串长度。如果一个字符串正着读和反着读是一样的，那它就是回文串。下面是一些回文串的实例： 12321 a aba abba aaaa tatt...

mingzhong 2019-07-24 18:10 评论0 收藏0
LeetCode——Longest Palindromic Substring

摘要：题目即求最长回文子序列原题链接此篇博客仅为学习记录我的解法及代码暴力解决，用及进行两层遍历循环中套一层循环，用遍历，求最长回文序列字符串，同时用变量记录最长子序列这种写法很暴力，效率很低，一层循环，一层循环，回文序列对比一层，时间复杂度为辣题目： Given a string s, find the longest palindromic substring in s. You ma...

shevy 2019-08-23 18:26 评论0 收藏0
2017年校招全国统一模拟笔试(第五场)编程题集合(Javascript版)

摘要：地址年校招全国统一模拟笔试第五场编程题集合偶串如果一个字符串由两个相同字符串连接而成就称这个字符串是偶串。第个提示是或者表示牛牛选择的数是否是的倍数。牛牛决定换掉一些瓷砖的颜色使得相邻两块瓷砖的颜色均不相同。地址：2017年校招全国统一模拟笔试(第五场)编程题集合偶串 (AC) 如果一个字符串由两个相同字符串连接而成,就称这个字符串是偶串。例如xyzxyz和aaaaaa是偶串,但...

hedge_hog 2019-08-23 11:42 评论0 收藏0