top5
给定一个字符串，输出最长的回文子串。回文串指的是正的读和反的读是一样的字符串，例如 "aba"，"ccbbcc"。
解法一 暴力破解
暴力求解，列举所有的子串，判断是否为回文串，保存最长的回文串。
publicbooleanisPalindromic(Strings) { intlen=s.length(); for (inti=0; i<len/2; i++) { if (s.charAt(i) !=s.charAt(len-i-1)) { returnfalse; } } returntrue; } // 暴力解法publicStringlongestPalindrome(Strings) { Stringans=""; intmax=0; intlen=s.length(); for (inti=0; i<len; i++) for (intj=i+1; j<=len; j++) { Stringtest=s.substring(i, j); if (isPalindromic(test) &&test.length() >max) { ans=s.substring(i, j); max=Math.max(max, ans.length()); } } returnans; }
时间复杂度：两层 for 循环 O（n²），for 循环里边判断是否为回文，O（n），所以时间复杂度为 O（n³）。
空间复杂度：O（1），常数个变量。
解法二 最长公共子串
根据回文串的定义，正着和反着读一样，那我们是不是把原来的字符串倒置了，然后找最长的公共子串就可以了。例如，S = " caba"，S' = " abac"，最长公共子串是 "aba"，所以原字符串的最长回文串就是 "aba"。
关于求最长公共子串（不是公共子序列），有很多方法，这里用动态规划的方法，可以先阅读下边的链接。
https://blog.csdn.net/u010397369/article/details/38979077
https://www.kancloud.cn/digest/pieces-algorithm/163624
整体思想就是，申请一个二维的数组初始化为 0，然后判断对应的字符是否相等，相等的话
arr [ i ][ j ] = arr [ i - 1 ][ j - 1] + 1 。
当 i = 0 或者 j = 0 的时候单独分析，字符相等的话 arr [ i ][ j ] 就赋为 1 。
arr [ i ][ j ] 保存的就是公共子串的长度。
publicStringlongestPalindrome(Strings) { if (s.equals("")) return""; Stringorigin=s; Stringreverse=newStringBuffer(s).reverse().toString(); //字符串倒置intlength=s.length(); int[][] arr=newint[length][length]; intmaxLen=0; intmaxEnd=0; for (inti=0; i<length; i++) for (intj=0; j<length; j++) { if (origin.charAt(i) ==reverse.charAt(j)) { if (i==0||j==0) { arr[i][j] =1; } else { arr[i][j] =arr[i-1][j-1] +1; } } if (arr[i][j] >maxLen) { maxLen=arr[i][j]; maxEnd=i; //以 i 位置结尾的字符 } } } returns.substring(maxEnd-maxLen+1, maxEnd+1); }
再看一个例子，S = "abc435cba"，S’ = "abc534cba" ，最长公共子串是 "abc" 和 "cba" ，但很明显这两个字符串都不是回文串。
所以我们求出最长公共子串后，并不一定是回文串，我们还需要判断该字符串倒置前的下标和当前的字符串下标是不是匹配。
比如 S = " caba "，S' = " abac " ，S’ 中 aba 的下标是 0 1 2 ，倒置前是 3 2 1，和 S 中 aba 的下标符合，所以 aba 就是我们需要找的。当然我们不需要每个字符都判断，我们只需要判断末尾字符就可以。
首先 i ，j 始终指向子串的末尾字符。所以 j 指向的红色的 a 倒置前的下标是 beforeRev = length - 1 - j = 4 - 1 - 2 = 1，对应的是字符串首位的下标，我们还需要加上字符串的长度才是末尾字符的下标，也就是 beforeRev + arr[ i ] [ j ] - 1 = 1 + 3 - 1 = 3，因为 arr[ i ] [ j ] 保存的就是当前子串的长度，也就是图中的数字 3 。此时再和它与 i 比较，如果相等，则说明它是我们要找的回文串。
之前的 S = "abc435cba"，S' = "abc534cba" ，可以看一下图示，为什么不符合。
当前 j 指向的 c ，倒置前的下标是 beforeRev = length - 1 - j = 9 - 1 - 2 = 6，对应的末尾下标是 beforeRev + arr[ i ] [ j ] - 1 = 6 + 3 - 1 = 8 ，而此时 i = 2 ，所以当前的子串不是回文串。
代码的话，在上边的基础上，保存 maxLen 前判断一下下标匹不匹配就可以了。
publicStringlongestPalindrome(Strings) { if (s.equals("")) return""; Stringorigin=s; Stringreverse=newStringBuffer(s).reverse().toString(); intlength=s.length(); int[][] arr=newint[length][length]; intmaxLen=0; intmaxEnd=0; for (inti=0; i<length; i++) for (intj=0; j<length; j++) { if (origin.charAt(i) ==reverse.charAt(j)) { if (i==0||j==0) { arr[i][j] =1; } else { arr[i][j] =arr[i-1][j-1] +1; } } /**********修改的地方*******************/if (arr[i][j] >maxLen) { intbeforeRev=length-1-j; if (beforeRev+arr[i][j] -1==i) { //判断下标是否对应maxLen=arr[i][j]; maxEnd=i; } /*************************************/ } } returns.substring(maxEnd-maxLen+1, maxEnd+1); }
时间复杂度：两层循环，O（n²）。
空间复杂度：一个二维数组，O（n²）。
top6
就是给定一个字符串，然后按写竖着的 「z」的方式排列字符，就是下边的样子。
然后按行的方式输出每个字符，第 0 行，第 1 行，第 2 行 ....
解法一
按照写 Z 的过程，遍历每个字符，然后将字符存到对应的行中。用 goingDown 保存当前的遍历方向，如果遍历到两端，就改变方向。
publicStringconvert(Strings, intnumRows) { if (numRows==1) returns; List<StringBuilder>rows=newArrayList<>(); for (inti=0; i<Math.min(numRows, s.length()); i++) rows.add(newStringBuilder()); intcurRow=0; booleangoingDown=false; for (charc : s.toCharArray()) { rows.get(curRow).append(c); if (curRow==0||curRow==numRows-1) goingDown=!goingDown; //遍历到两端，改变方向curRow+=goingDown?1 : -1; } StringBuilderret=newStringBuilder(); for (StringBuilderrow : rows) ret.append(row); returnret.toString(); }
时间复杂度：O（n），n 是字符串的长度。
空间复杂度：O（n），保存每个字符需要的空间。
解法二
找出按 Z 形排列后字符的规律，然后直接保存起来。
我们可以看到，图形其实是有周期的，0，1，2 ... 7 总过 8 个，然后就又开始重复相同的路径。周期的计算就是 cycleLen = 2 × numRows - 2 = 2 × 5 - 2 = 8 个。
我们发现第 0 行和最后一行一个周期内有一个字符，所以第一个字符下标是 0 ，第二个字符下标是 0 + cycleLen = 8，第三个字符下标是 8 + cycleLen = 16 。
其他行都是两个字符。
第 1 个字符和第 0 行的规律是一样的。
第 2 个字符其实就是下一个周期的第 0 行的下标减去当前行。什么意思呢？
我们求一下第 1 行第 1 个周期内的第 2 个字符，下一个周期的第 0 行的下标是 8 ，减去当前行 1 ，就是 7 了。
我们求一下第 1 行第 2 个而周期内的第 2 个字符，下一个周期的第 0 行的下标是 16 ，减去当前行 1 ，就是 15 了。
我们求一下第 2 行第 1 个周期内的第 2 个字符，下一个周期的第 0 行的下标是 8 ，减去当前行 2 ，就是 6 了。
当然期间一定要保证下标小于 n ，防止越界。
可以写代码了。
publicStringconvert(Strings, intnumRows) { if (numRows==1) returns; StringBuilderret=newStringBuilder(); intn=s.length(); intcycleLen=2*numRows-2; for (inti=0; i<numRows; i++) { for (intj=0; j+i<n; j+=cycleLen) { //每次加一个周期ret.append(s.charAt(j+i)); if (i!=0&&i!=numRows-1&&j+cycleLen-i<n) //除去第 0 行和最后一行ret.append(s.charAt(j+cycleLen-i)); } } returnret.toString(); }
时间复杂度：O（n），虽然是两层循环，但第二次循环每次加的是 cycleLen ，无非是把每个字符遍历了 1 次，所以两层循环内执行的次数肯定是字符串的长度。
空间复杂度：O（n），保存字符串。
