LeetCode实战：最长回文子串
题目英文
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
题目中文
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
示例 3：
输入: "a"
输出: "a"
算法实现
回文是一个正读和反读都相同的字符串，例如，“aba”是回文，而“abc”不是。
实现一：暴力法，列举所有的子串，判断该子串是否为回文。
public class Solution {public string LongestPalindrome(string s) {if (string.IsNullOrEmpty(s))return string.Empty;if (s.Length == 1)return s;int start = 0;int end = 0;int len = int.MinValue;for (int i = 0; i < s.Length; i++){for (int j = i + 1; j < s.Length; j++){string str = s.Substring(i, j - i + 1);if (isPalindrome(str)&&str.Length>len){len = str.Length;start = i;end = j;}}}return s.Substring(start, end - start + 1); }public bool isPalindrome(string s){for (int i = 0, len = s.Length/2; i < len; i++){if (s[i] != s[s.Length - 1 - i])return false;}return true;}
}
- 执行结果：超出时间限制
实现二：动态规划
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。
我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
具体的动态规划算法多种多样，但它们具有相同的填表格式。
使用记号 s[l, r] 表示原始字符串的一个子串，l、r 分别是区间的左右边界的索引值，使用左闭、右闭区间表示左右边界可以取到。
dp[l, r] 表示子串 s[l, r]（包括区间左右端点）是否构成回文串，是一个二维布尔型数组。
- 当子串只包含 1 个字符，它一定是回文子串；
- 当子串包含 2 个以上字符的时候：
s[l, r]是一个回文串，那么这个回文串两边各往里面收缩一个字符（如果可以的话）的子串s[l + 1, r - 1]也一定是回文串。
故，当 s[l] == s[r] 成立的时候，dp[l, r]的值由 dp[l + 1, r - l] 决定，这里还需要再多考虑一点点：“原字符串去掉左右边界”的子串的边界情况。
- 当原字符串的元素个数为 3 的时候，如果左右边界相等，那么去掉它们以后，只剩下 1 个字符，它一定是回文串，故原字符串也一定是回文串；
- 当原字符串的元素个数为 2 的时候，如果左右边界相等，那么去掉它们以后，只剩下 0 个字符，显然原字符串也一定是回文串。
综上，如果一个字符串的左右边界相等，判断为回文只需以下二者之一成立即可：
- 去掉左右边界以后的字符串不构成区间，即
s[l + 1, r - 1]包含元素少于2个，即：r - l <= 2。 - 去掉左右边界以后的字符串是回文串，即
dp[l + 1, r - 1] == true。
参考文献：
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
public class Solution {public string LongestPalindrome(string s) {if (string.IsNullOrEmpty(s))return string.Empty;int len = s.Length;if (len == 1)return s;int longestPalindromelen = 1;string longestPalindromeStr = s.Substring(0, 1);bool[,] dp = new bool[len, len];for (int r = 1; r < len; r++){for (int l = 0; l < r; l++){if (s[r] == s[l] && (r - l <= 2 || dp[l + 1, r - 1] == true)){dp[l, r] = true;if (longestPalindromelen < r - l + 1){longestPalindromelen = r - l + 1;longestPalindromeStr = s.Substring(l, r - l + 1);}}}}return longestPalindromeStr; }
}
实验结果
- 状态：通过
- 103 / 103 个通过测试用例
- 执行用时: 232 ms, 在所有 C# 提交中击败了 46.79% 的用户
- 内存消耗: 40.9 MB, 在所有 C# 提交中击败了 5.43% 的用户
相关图文
1. “数组”类算法
- LeetCode实战：两数之和
- LeetCode实战：三数之和
- LeetCode实战：缺失的第一个正数
- LeetCode实战：求众数
- LeetCode实战：快乐数
2. “链表”类算法
- LeetCode实战：两数相加
- LeetCode实战：删除链表的倒数第N个节点
- LeetCode实战：合并两个有序链表
- LeetCode实战：合并K个排序链表
- LeetCode实战：两两交换链表中的节点
- LeetCode实战：旋转链表
- LeetCode实战：环形链表
3. “栈”类算法
- LeetCode实战：有效的括号
- LeetCode实战：最长有效括号
- LeetCode实战：逆波兰表达式求值
4. “队列”类算法
- LeetCode实战：设计循环双端队列
5. “递归”类算法
- LeetCode实战：爬楼梯
6. “字符串”类算法
- LeetCode实战：反转字符串
- LeetCode实战：翻转字符串里的单词
7. “树”类算法
- LeetCode实战：相同的树
- LeetCode实战：对称二叉树
- LeetCode实战：二叉树的最大深度
- LeetCode实战：将有序数组转换为二叉搜索树
8. “搜索”类算法
- LeetCode实战：搜索二维矩阵
9. “数值分析”类算法
- LeetCode实战：x 的平方根
相关文章：
2017年9月11日 梁勇 java教材 编程练习题 第二章 2.15 键盘 读取两个点的坐标值（小数），控制台输出两点间距离。...
package com.swift;import java.util.Scanner;public class PToP {public static void main(String[] args) {Scanner scannew Scanner(System.in);System.out.println("请输入第一个点的坐标值x1");Double x1Double.parseDouble(scan.nextLine());System.out.printl…
学习java技术有前途吗
java技术在我国的普及已经是非常广泛的了，很多人都知道，java行业的发展前景是非常好的，但竞争压力也是非常大的，到底学习java技术有前途吗?来看看下面的详细介绍。 学习java技术有前途吗?目前按照各类招聘来看，Java的…
充分理解表达式——《狂人C》习题解答2(第二章习题5)
/* 编程求1357911。 */ #include <stdio.h> #include <stdlib.h>int main( void ) {printf ("1357911") ; printf ("%d\n" , 1 3 5 7 9 11 ) ;system("PAUSE"); return 0;}这个题目的主要目的有两个： 1.掌握写整…
LeetCode实战：整数反转
题目英文 Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321Example 2: Input: -123 Output: -321Example 3: Input: 120 Output: 21Note: Assume we are dealing with an environment which could only store integers …
深度洞悉2017企业IT三大关注焦点
本文讲的是深度洞悉2017企业IT三大关注焦点【IT168 云计算】随着经济走向整体放缓，2017有哪些议题会受到企业IT的关注? 一：如何提升员工工作体验 随着80后、90后成为职场主力军，数字化工作场所的推行与建立日渐成为主流，企业将更…
APP测试和传统软件测试有什么区别
APP测试和传统软件测试有什么区别?APP测试和传统测试是有一些区别的，移动APP的特点使得它与传统软件在开发、测试方面都有所不同。比较移动APP测试与传统软件测试的不同，要从以下几个方面进行考虑： (1) 页面布局不同 对于传统软件࿰…
LeetCode实战：字符串转换整数 (atoi)
题目英文 Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or…
[C#] enum 枚举
默认情况下，枚举第一个值是0， 可显式为枚举赋值。 可以定义枚举的基础类型，如enum E : short {}, sizeof(E) 2；默认情况下是int。 枚举的继承链：ValueType->Enum->enum 枚举类型和基础类型之间的转换都是显式的…
制作Windows Mobile程序安装包
使用Visual Studio 2005制作wm上的cab安装包 打开项目，解决方案中添加新项，添加"智能设置CAB项目"；或者在空VS中新建一个"智能设置CAB项目" 添加新项 左侧的Program Files文件夹，没用可以删除 添加项目主输出…
学Java需要下载什么软件?都有什么作用?
学习java并非大家想象中的那么简单，除了书本和老师面授，软件的使用也有很大的作用，接下来小编为大家分享的就是关于“学Java需要下载什么软件?都有什么作用?”的内容，希望能够给正在学习java知识的同学带来帮助。 学Java需要下载…
一种新的攻击方式：使用Outlook 表单进行横向渗透和常驻
本文讲的是一种新的攻击方式：使用Outlook 表单进行横向渗透和常驻，背景最近我们针对CrowdStrike服务进行例行调查，发现了一种攻击方法，其主要用于横向渗透和系统常驻，而且是以前我们没有看到过的。这种攻击利用Microso…
ACM 1740 A New Stone Game http://acm.pku.cn/JudgeOnline/problem?id=1740
题目大意:有N堆石头,每堆石头数目在1到100之间,最多有10堆.两人分别取走石头.取石头的规则是:每次只能从1堆中取,每次取走至少1个.取过后还可以把这堆的石头任意分配到其它堆上(这些堆必须有石头,废话呵呵),当然也可以不分配.问给定这些石头堆的情况,两人轮流取,谁先取完谁胜利…
LeetCode实战：回文数
题目英文 Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. Example 1: Input: 121 Output: trueExample 2: Input: -121 Output: false Explanation: From left to right, it reads -121. From ri…
安全测试的基本原则有哪些?
软件测试顾名思义就是要进行软件安全方面的测试，对于软件测试人员来说，软件安全是一个广泛而复杂的主题，完全避免软件安全缺陷问题是不切实际的，但通过安全测试可以发现并修复软件大部分安全缺陷。下面介绍一些安全测试的基本原则…
LeetCode实战：盛最多水的容器
题目英文 Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a conta…
微软极品Sysinternals Suite工具包使用指南
微软极品Sysinternals Suite工具包使用指南 按照名称首字母排序，点击每个蓝色标题链接都可以转到微软的对应官方页面，有对这些工具包的直接下载地址和更详尽的用法。因为每个软件几乎都可以长篇大论的介绍，所以，在此就只做简介和罗…
【布局】圣杯布局双飞翼布局
背景 随着前端技术的发展推进，web端的布局方式已基本成熟，那么在网站布局方式中，三列布局最为常用，布局方式也有很多，渐渐的开发者们开始从效率的角度优化自己的代码“如果三排布局能将中间的模块放在dom树前面&#x…
UI设计师面试如何操作才能获得高薪
UI设计师在近几年是非常吃香的，求职招聘网站上对于UI设计师的要求也越来越高，那么在面试的过程中UI设计师面试如何操作才能获得高薪呢?来看看下面的详细解析。 UI设计师面试如何操作才能获得高薪? 1、行为举止得体大方 我们先从仪态体态方面说…
HDU2673-shǎ崽（水题）
如果不能够直接秒杀的题，就不算水题。又应证了那句话，有时候，如果在水题上卡住，那么此题对于你来说，也就不算是水题了额~~ 刚睡醒，迷迷糊糊。 题目的意思很简单，求一个最大的，再求一…
center os7 安装mysql
安装mariadb MariaDB数据库管理系统是MySQL的一个分支，主要由开源社区在维护，采用GPL授权许可。开发这个分支的原因之一是：甲骨文公司收购了MySQL后，有将MySQL闭源的潜在风险，因此社区采用分支的方式来避开这个风险。M…
LeetCode实战：最长公共前缀
题目英文 Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string “”. Example 1: Input: ["flower","flow","flight"] Output: "fl"…
软件测试培训需要学习什么技术
软件测试技术相对于IT行业的其他技术，学习起来是比较简单的，大多数零基础学员想要进入到IT行业都会优先选择软件测试，那么具体软件测试培训需要学习什么技术呢?来看看下面的介绍就知道了。 软件测试培训需要学习什么技术? 每个软件在上线之…
检测晃动的三种方法
http://stackoverflow.com/questions/150446/how-do-i-detect-when-someone-shakes-an-iphone 我的实现（基于Eran Talmor）： 没必要application.applicationSupportsShakeToEdit YES; Set the applicationSupportsShakeToEdit property in th…
android随手记
Linearlayout: gravity：本元素中所有子元素的重力方向 layout_gravity：本元素对于父元素的重力方向 自定义权限:http://www.cnblogs.com/it-tomorrow/p/4115161.html 注意:1 .在被调用时就算是normal权限也需要在加入,不然会permission Deney,在…
LeetCode实战：最接近的三数之和
题目英文 Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Example: Given ar…
零基础学习UI设计有哪些简单有效的方法
UI设计的普及让越来越多的人对UI有了重新的认识，很多企业对UI设计这个岗位都是非常重视的，如今很多零基础学员都想要转行做UI设计，那么针对零基础学习UI设计有哪些简单有效的方法呢?来看看下面的详细介绍吧。 零基础学习UI设计有哪些简单有效…
(转)linux下oracle instant client安装和运行
1.首先要知道什么是ORACLE的客户端： Oracle Instant client 是oracle提供的简便客户端, 支持多种平台. 可从oracle网站下载, 下载地址为http://www.oracle.com/technology/tech/oci/instantclient/index.html 包括如下内容: Instant client Package - Basic 运行OCI…
LeetCode实战：删除排序数组中的重复项
题目英文 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra me…
16G 手机清理
1.16G 手机清理 清理top 5 的应用的缓存即可 2,hw wife 连接模块 低于 app wifi 的连接模块。 在同样的电脑热点面前，hw 连补上电脑热点，apple 可以连上电脑热点。 其他差异不大。 2.奇兔刷机 tencent应用宝 and 手机管理，备份软件 http://w…
java培训有哪些收费标准
随着学习java技术的人越来越多，市面上的java培训机构也越来越多，每家机构的收费标准都不一样，这让很多想要学习java技术的小伙伴都比较头疼，下面小编就为大家详细的介绍一下java培训有哪些收费标准?如何来评判适合自己的java培训…