LeetCode[5] - 最长回音子串 && 动态编程
题目
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
tips: 回文字符串:正读反读都一样
叙事
这道题目level为中等,读第一遍我就觉得可能会很棘手,当然立刻就有一个简单的解题思路,因为知道这种解法很烂所以一直没有coding。直到有一天····
强迫症患者根本无法继续愉快coding了。。。只好不拖延,解决这个棘手的问题····当然肯定是因为自己菜才觉得棘手···
分析
最简单能想到的解决方案就是把字符串的所有子串枚举出来,每一个都判断是否是回文字符串,然后选长度最长的回文子串。。。后来我才知道这个算法叫暴力算法···名字很酷···暴力足以解决很多问题····代码很简单
public String longestPalindrome(String s) {
if(s.isEmpty()){
return s;
}
String res=s.substring(0,1);
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
String k=s.substring(i,j);
String rk=new StringBuffer(k).reverse().toString();
if(k.equals(rk)&&k.length()>res.length()){
res=k;
}
}
}
return res;
}
一段不加注释都能看得懂的代码···我们执行了一下····
果然···暴力的leetcode都看不过去···
现有的知识和智慧已经不够用了。然后去google解法。最强的是一个叫马拉车的算法,看起来有点复杂,而且对其他算法题帮助不大,所以拖拉的楼主决定晚点再学这个马拉车。接下来就是动态规划算法。。。等我起一个title。
动态规划
为什么单独将动态规划罗列出来呢,因为这在算法问题中好像十分普遍和重要。楼主之前刷面试题,很多算法问题的answer 作者都直接甩一句动态规划···好,今天就直面曾经欠下的债。动态规划颇有点“大事化小,小事化了”的感觉。在动态规划中有三个重要的元素最优子结构,边界,状态转移公式,我们稍后结合一个例子理解一下这仨概念~
理解动态规划有一个最典型的例子:
有面值分别为1,3,5的三种硬币若干,需要凑成11元最少需要多少硬币,凑成n元最少需要多少硬币?
和往常一样我们来一起找规律:
假如:
- 凑成0元需要0个硬币 //d(0)=0
- 凑成1元需要1个1元硬币 //d(1)=d(0)+1
- 凑成2元需要2个1元硬币 //d(2)=d(1)+1
- 凑成3元需要3个1元硬币或者1个3元硬币,那么我们选择1个3元硬币 //d(3)=min{d(2)+1,d(3-3)+1}
- 凑成4元需要1个3元硬币,1个1元硬币 //d(4)=d(3)+1;
- 凑成5元需要1个3元硬币,2个1元硬币或者1个5元硬币,那么我们选择1个5元硬币 //d(5)=min{d(4)+1,d(5-5)+1}
- 。。。。
- 抽离出来d(i)=min{ d(i-1)+1,d(i-vj)+1 },其中i-vj >=0,vj表示第j个硬币的面值;
这里d(i-1)+1和d(i-vj)+1是d(i)的最优子结构,d(0)=0是边界,d(i)=min{ d(i-1)+1,d(i-vj)+1 }是状态转移公式。其实我们根据边界+状态转移公式就能得到最终动态规划的结果。
上述程序的java实现
public int dp(int n) {
n++;
int min[] = new int[n];
int[] V = {1, 3, 5};
min[0]=0;
for (int i = 1; i < n; i++) {
min[i] = min[i-1]+1;
for (int j = 0; j < V.length; j++) {
if (V[j] > i) {
break;
}
if (min[i - V[j]] < min[i-1]) {
min[i] = min[i - V[j]] + 1;
}
}
}
return min[n - 1];
}
因为我也是今天才去了解动态规划,所以有可能有些理解不对表述不对的地方。欢迎指出。
关于动态规划我看了的两篇文章:
动态规划:从新手到专家
参考:程序员小灰动态规划
动态规划解决最长回文子串
我们创建一个二维数组,boolean[][]dp,其中dp[i][j]表示字符串第i到j是否为回文。那么边界值其实很清楚了,j-i=1的都为true 字符串长度为1的都为true。状态转换如何设定呢?当字符串i所在的字符等于字符串j所在的字符,并且它的内部(dp[i+1][j-1])为回文那么dp[i][j]为true。因为这样的规律,我们要保证判断dp[i][j]的时候dp[i+1][j-1]已经判断,所以我们遍历采用i降序j升序的嵌套遍历的方式
public String longestPalindrome(String s) {
if (s.isEmpty()) {
return s;
}
int n = s.length();
boolean[][] dp = new boolean[n][n];
int left = 0;
int right = 0;
for (int i = n - 2; i >= 0; i--) {
dp[i][i] = true;
for (int j = i + 1; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) &&( j-i<3||dp[i+1][j-1]);//小于3是因为aba一定是回文
if(dp[i][j]&&right-left<j-i){
left=i;
right=j;
}
}
}
return s.substring(left,right+1);
}
这次我们再运行,发现顺利通过leetcode的考验~~
测试用例:dsfsdhadhfkdsdsfsdhadhdsfsdhadhfkddsfsdhadhfkdsahfksadhdsfsdhadhfkdsahfksadhfksddsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskfdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhsksahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhsk
哈哈好不好奇特别暴力算法呀哈哈哈哈哈~~~时间复杂度和空间复杂度达到极致的算法!!
希望大家能教教我马拉车算法!!
上一篇: 回文字符串
下一篇: [NC13230] 合并回声子串
推荐阅读
-
[LeetCode] 动态编程 - 5.最长回声子串(含完整 Python/C++ 代码) - 前言
-
2024/4/3-力扣-最长回溯子串-解 1:动态编程-回溯子串
-
[字符串] 最长回声子字符串(动态编程算法) ★ - I. 回声字符串、子字符串、后续字符串
-
leetcode 5 最长回文子串 - 最长回文字符串
-
寻找最长回文子串的五种方法(暴力、中点扩散、DP、哈希+分叉、马纳赫尔) - 动态编程 O ( n 2 ) O(n^2) O(n2)
-
Leetcode(5) - 最长的回文子串 - Java 版本 - 完整解释
-
[Leetcode 5] 最长回声字符串 -- 动态编程
-
LeetCode[5] - 最长回音子串 && 动态编程
-
5. 最长的回文子串 - 从递归到动态编程的逐步优化
-
Grid++Report 锐浪报表开发常见问题解答集锦-报表设计 问:怎样在设计时打印预览报表? 答:为了及时查看报表的设计效果,Grid++Report 报表设计应用程序提供了四种查看视图:普通视图、页面视图、预览视图与查询视图。通过窗口下边的 Tab 按钮可以在四种视图中任意切换。在预览视图中查看报表的打印预览效果,在查询视图中查看报表的查询显示效果。如果在报表的记录集提供了数据源连接串与查询 SQL,在进入预览视图与查询视图时会利用数据源连接串与查询 SQL 从数据源中自动取数,否则 Grid++Report 将自动生成模拟数据进行模拟打印预览与查询显示。注意:在预览视图与查询视图中看到的报表运行结果有可能与在你程序中的最终运行结果有差异,因为在报表的生成过程中我们可以在程序中对报表的生成行为进行一定的控制。 问:怎样用 Grid++Report 设计交叉表? 答:Grid++Report 没有提供专门实现交叉表的功能,其它的报表构件提供的交叉表功能一般也比较死板和功能有限。利用 Grid++Report 的编程接口可以做出灵活多变,功能丰富的交叉表。示例程序 CrossTab 就是一个实现交叉表的例子程序,认真领会此例子程序,你就可以做出自己想要各种交叉表,并能提取一些共用代码,便于重复使用。 问:怎样设置整个报表的缺省字体? 答:设置报表主对象的字体属性,也就是设置了整个报表的缺省字体。如果改变报表主对象的字体属性,则没有专门的设置字体属性的子对象的字体属性也跟随改变。同样每个报表节与明细网格也有字体属性,他们的字体属性也就是其拥有的子对象的缺省字体。 问:怎样在打印时限制一页的输出行数? 答:设定明细网格的内容行的‘每页行数(RowsPerPage)’属性即可。另外要注意‘调节行高(AdjustRowHeight)’属性值:为真时根据页面的输出高度自动调整行的高度,使整个页面的输出区域充满。为假时按设计时的高度输出行。 问:怎样显示中文大写金额? 答:将对象的“格式(Format)”属性设为 “$$” 及可,可以设置格式的对象有:字段(IGRField)、参数(IGRParameter)、系统变量(IGRSystemVarBox)与综合文字框(IGRMemoBox),其中综合文字框是在报表式上设格式。 问:能否实现自定义纸张与票据打印? 答:Grid++Report 完全支持自定义纸张的打印,只要在报表设定时在页面设置中选定自定义纸张,并指定准确的纸张尺寸。当然要在最终输出时得道合适的打印结果,输出打印机必须支持自定义纸张打印。Windows2000/XP/2003 操作系统上可以在打印机上定义自定义纸张,也可以采用这种方式实现自定义纸张打印。 问:怎样实现 0 值不打印? 答:直接设置格式串就可以,在“数字格式”设置对话框中选定“0 不显示”,就会得到合适的格式串。也可以通过直接录入格式串来指定 0 不显示,但格式串必须符合 Grid++Report 的规定格式。另一种实现办法是在报表获取明细记录数据时,在 BeforePostRecord 事件中将值为零的字段设为空,调用字段的 Clear 方法将字段置为空。 问:怎样实现多栏报表? 答:在明细网格上设‘页栏数(PageColumnCount)’属性值大于 1 即可。通过 Grid++Report 的“页栏输出顺序”还可以指定多栏报表的输出顺序是“先从上到下”还是“先从左到右”。 问:如何实现票据套打? 答:Grid++Report 为实现票据套打做了很多专门的安排:报表设计器提供了页面设计模式,按照设定的纸张尺寸显示设计面板,如果将空白票据的扫描图设为设计背景图,在定位报表内容的输出位置会非常方便。报表部件可以设定打印类别,非套打输出的内容在套打打印模式下就不会输出。 问:Grid++Report 有没有横向分页功能? 答:回答是肯定的,在列的总宽度超过打印页面的输出宽度时,Grid++Report 可以另起新页输出剩余的列,如果左边存在锁定列,锁定列可以在后面的新页中重复输出,这样可以保证关键数据列在每一页都有输出。仔细体会 Grid++Report 提供的多种打印适应策略,选用最合适的方式。Grid++Report 的多种打印适应策略为开发动态报表提供了很好的支持。 问:怎样实现报表本页小计功能? 答:定义一个报表分组,将本分组定义为页分组,在本分组的分组头与分组尾上定义统计。页分组就是在每页产生一个分组项,在每页的上端与下端都会分别显示页分组的分组头与分组尾,页分组不用定义分组依据字段。 报表运行 问:怎样与数据库建立连接? 答:如果在设计报表时指定了数据集的数据源连接串与查询 SQL 语句,Grid++Report 采用拉模式直接从数据源取得报表数据,Grid++Report 利用 OLE DB 从数据源取数,OLE DB 提供了广泛的数据源操作能力。如果 Grid++Report 的数据来源采用推模式,即 Grid++Report 不直接与数据库建立连接,各种编程语言/平台都提供了很好的数据库连接方式,并且易于操作,应用程序在报表主对象(IGridppReport)的 FetchRecord 事件中将数据传入,例子程序提供了各种编程语言填入数据的通用方法,对C++Builder 和 Delphi 还进行了专门的包装,直接关联 TDataSet 对象也可以将 TDataSet 对象中的数据传给报表。 问:打印时能否对打印纸张进行自适应?支持表格的折行打印吗? 答:Grid++Report 在打印时采用多种适应策略,通过设置明细网格(IGRDetailGrid)的‘打印策略(PrintAdaptMethod)’属性指定打印策略。(1)丢弃:按设计时列的宽度输出,超出范围的内容不显示。(2)绕行:按设计时列的宽度输出,如果在当前行不能完整输出,则另起新行进行输出。(3)缩放适应:对所有列的输出宽度进行按比例地缩放,使总宽度等于页面的输出宽度。(4)缩小适应:如果列的总宽度小于页面的输出宽度,对所有列的输出宽度进行按比例地缩小,使总宽度等于页面的输出宽度。(5)横向分页:超范围的列在新页中输出。(6)横向分页并重复锁定列。 问:如何改变缺省打印预览窗口的窗口标题? 答:改变报表主对象的‘标题(Title)’属性即可。 问:利用集合对象的编程接口取子对象的接口引用,但不是自己期望的结果。 答:Grid++Report中所有集合对象的下标索引都是从 1 开始,另按对象的名称查找对象的接口引用时,名称字符是不区分大小写的。 问:怎样在运行时控制报表中各个对象的可见性?即怎样在运行时显示或隐藏对象? 答:在报表主对象(GridppReport)的 SectionFormat 事件中设定相应报表子对象的可见(Visible)属性即可。 问:报表主对象重新载入数据,设计器中为什么没有反映新载入的数据? 答:应调用 IGRDesigner 的 Reload 方法。 问:怎样实现不进入打印预览界面,直接将报表打印出来?