动态规划—最长回文子串LEETCODE第5题深度剖析
2024-08-28 05:05:48
动态规划对于笔者来说有很重要的意义
一、题目如下:
对于此类题目,笔者常用的的办法是先做个暴力解题思路,然后再对暴力法进行优化。
二、暴力法
//字串遍历
public static String longestPalindrome(String s) {
String result="";
if(s.length()==1) return s;
for(int i=0;i<s.length();i++) {
for(int j=i+1;j<s.length()+1;j++) {if(test(s.substring(i,j))&&s.substring(i,j).length()>result.length())result=s.substring(i,j);}}
return result;}
//回文判断
public static boolean test(String str)
{for(int i=0;i<str.length()/2;i++) {if(str.charAt(i)!=str.charAt(str.length()-1-i))
return false;}
return true;
}
这段代码虽然不出意外的超时了,但是确实是我们第一步要考虑的。这个暴力法很简单,一个一个字串的检测,直到检测完所有的字符串。可是这不是我们想要的。
三、动态规划方法
首先要修改的就是我们的第一个字符串遍历的方法。思路为,既然我们知道了一个串为回文,那这个串左字母和右字母如果相同的话,不就又是一个回文字符串了吗。
不过这个思路要解决的问题有俩个:
1.找到所有起始字符串,并且将这些字符串下标保存到ArrayList数组里面
2.对每个字符串进行动态扩张。扩张到不能再扩为止。
public static String longestPalindrome(String s) {
//定义一个结构保存所有字串
class Str{
Str(int i,int j){
this.i=i;
this.j=j;
}
int i;
int j;
}
if(s.length()==1) return s;
ArrayList<Str> al =new ArrayList<>();
for(int i=0;i<s.length();i++) {
Str str = new Str(i,i);
al.add(str);
if(i!=s.length()-1) {
if(s.charAt(i)==s.charAt(i+1)) {
Str str2 = new Str(i,i+1);
al.add(str2);
}
}
}
Str large = new Str(0,0);
for(Str str:al) {
while(str.i!=0&&str.j!=s.length()-1) {
if(s.charAt(str.i-1)==s.charAt(str.j+1)) {
str.i--;
str.j++;
}else {
break;
}
}
if((str.j-str.i)>=(large.j-large.i)) large=str;
}
return s.substring(large.i,large.j+1); }
四、笔者对动态规划法的看法。
动态规划没有确切的定义,但拿这题来说,笔者只是把所有需要的数据存储在内存中。再把这些数据拿出来进行动态扩张。
最新文章
- 原创: How to build a query based on Definition Updates installed
- [BZOJ 3123]森林
- gedit脚本
- POJ 2155 2维线段树 || 2维BIT
- MyEclipse使用总结——设置MyEclipse使用的Tomcat服务器 设置JDK
- <;转>;如何进行code review
- js判断url是否有效
- [saiku] 通过 saiku 的 DEMO 分析 connection
- PHP面向对象中常用的关键字和魔术方法
- sass中mixin常用的CSS3
- 百度地图Api详解之地图标注
- 实现jsp网站添加到收藏夹
- Ubuntu Nginx搭建Gitweb服务器
- 理论制作 Windows 开机动画
- ios 图片截取功能 图片拼接功能
- 比之前那个版本更简单的C语言实现的比较大小
- BZOJ3210: 花神的浇花集会
- List学习笔记
- 深入理解yield(转)
- 获取用户IP地址的三个属性的区别 (HTTP_X_FORWARDED_FOR,HTTP_VIA,REMOTE_ADDR)