2019-02-23-算法-进化

「爱情、让人受尽委屈。」 2022-03-17 11:07 167阅读 0赞

题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。  
示例 1：

输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
    输出: "bb"

本想用暴力法，穷举所有字符串，但是觉得这种方法时间效率实在是太低，但是苦于没想到更好的解决方案，最终看了LeetCode题目解析，才采用其中心扩展算法，在O(n\`2)解决了这个问题，代码如下：

public static String longestPalindrome(String s) {
            if(s==null||s.length()<1) {
            	return "";
            }else if(s.length() == 1) {
            	return s;
            }
            int len=0,max=0,mid=0;
            
            for(int i=0;i<s.length()-1;i++) {
            	int aMax = fixCenterLongest(s, i, i);
            	int bMax = fixCenterLongest(s, i, i+1);
            	max = Math.max(aMax, bMax);
            	if(max > len) {
            		len = max;
            		mid = i;
            	}
            }
    		return s.substring(mid - (len-1)/2 , mid + len/2+1);
        }
    	
    	public static int fixCenterLongest(String s, int left, int right) {
    		while(left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)) {
    			left--;
    			right++;
    		}
    		return right-left-1;
    	}

题目来源：[https://leetcode-cn.com/articles/longest-palindromic-substring/][https_leetcode-cn.com_articles_longest-palindromic-substring]  
持续精进中···加油！

[https_leetcode-cn.com_articles_longest-palindromic-substring]: https://leetcode-cn.com/articles/longest-palindromic-substring/

发表评论取消回复

表情：

评论列表（有 0 条评论，167人围观）

还没有评论，来说两句吧...

相关阅读

相关进化算法中的差分进化算法（Differential Evolution）

![ee1c15ef04174e8cb1dc52e531d96268.png][] 目录引言算法原理算法特点应用案例总结 ---------------

秒速五厘米/ 2024年02月28日 03:10/ 0 赞/ 62 阅读

相关多目标进化算法(MOEAs)概述

[原文地址][Link 1] 对于大多数多目标优化问题，其各个目标往往是相互冲突的，因此不可能使得所有的目标同时达到最优，而是一组各个目标值所折衷的解集，称之为Pareto最

ゝ一世哀愁。/ 2022年06月09日 07:53/ 0 赞/ 615 阅读

相关 2019-02-25-算法-进化

题目描述：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例1：输入: 123 输出: 321 示例2：

ゝ一世哀愁。/ 2022年03月17日 15:40/ 0 赞/ 201 阅读

相关 2019-02-23-算法-进化

题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: "babad" 输出: "bab"

「爱情、让人受尽委屈。」/ 2022年03月17日 11:07/ 0 赞/ 168 阅读

相关 2019-02-22-算法-进化

题目描述：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: "abcabcbb" 输出: 3 解释:

柔情只为你懂/ 2022年03月17日 06:44/ 0 赞/ 141 阅读

相关 2019-02-21-算法-进化

论代码能力：给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相

怼烎@/ 2022年03月17日 01:10/ 0 赞/ 166 阅读

相关 2019-02-24-算法-进化

题目描述将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：

迈不过友情╰/ 2022年03月16日 20:18/ 0 赞/ 174 阅读

相关 2019-03-13-算法-进化（鸡蛋掉落）

题目描述你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。你知道存在楼层 F

短命女/ 2022年03月09日 11:36/ 0 赞/ 228 阅读

相关 2019-03-19-算法-进化（报数）

题目描述报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下： 1. 1 2. 11 3.

曾经终败给现在/ 2022年03月06日 12:52/ 0 赞/ 209 阅读

相关 2019-03-18-算法-进化（实现strStr()）

题目描述实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第

╰半夏微凉°/ 2022年03月06日 11:58/ 0 赞/ 162 阅读