zigzag
https://leetcode-cn.com/problems/zigzag-conversion/
思路一：
建一个二维数组，存zigzag图形（char初始值为0）
把字符换成下标来排列，更容易发现规律
找到循环一次需要的字符数 ： int circle = 2*(numRows-1);
一个circle分成两部分：从上到下 和 斜着的从下到上
- 从上到下的是竖直的：行等于它在circle中的位置，列是每个circle的第一列。每个circle占numRows-1列。所以列下标 = i/circle*(numRows-1)
- 从下到上是斜的：这样的斜对角线一般满足 横坐标+纵坐标 = 每个常数
而由于可能有多个circle，所以实际情况是 横坐标 + （纵坐标-之前的circle所占列数）= numRows-1。横坐标是倒着的，表示差多少到1个circle，横坐标 = circle-mod；纵坐标 = numRows-1-横坐标 + 之前的circle所占列数 = mod - (numRows-1) + i/circle*(numRows-1)
易错点：
char初始值判断：0
s为空和numRows=1的情况
class Solution {
public String convert(String s, int numRows) {
if(s==null||s.length()==0||numRows==1)return s;
int n = s.length();
int circle = 2*(numRows-1);
int col = ((n-1)/circle+1)*(numRows-1);
char[][] result = new char[numRows][col];
for(int i=0;i<n;i++){
int mod = i%circle;
int devide = i/circle;
if(mod<numRows-1){
result[mod][devide*(numRows-1)] = s.charAt(i);
}else{
result[circle-mod][devide*(numRows-1)+(mod-(numRows-1))] = s.charAt(i);
}
}
char[] resultArray = new char[n];
int index = 0;
for(int i=0;i<result.length;i++){
for(int j=0;j<result[0].length;j++){
if(result[i][j]!=0){
resultArray[index++] = result[i][j];
}
}
}
return new String(resultArray);
}
}
思路2：
不借助额外的空间要怎么做呢？
一定是需要寻找规律了。
如果有0-21个字符。
row 0: 0,circle,circle*2....
row i:0*circle+i,1*circle-i,1*circle+i,2*cirlce-i,...
row numRows-1: numRows-1，1*circle+numRows-1,2*circle+numRows-1
所以我们发现规律，除了第1行和最后一行，中间的i行都符合上述规律。而第1行和最后一行，特殊在只算了+i的，没有-i。
那么，我们可以顺序地填充结果数组。每次判断应有的下标是否超限，按照+i,(index++),-i的顺序依次循环，一旦发现当前下标不满足了，就跳到下一行，并且重新循环判断。
指的注意的是，在第一行和最后一行时，不执行-i的步骤。
class Solution {
public String convert(String s, int numRows) {
if(s==null||s.length()==0||numRows==1)return s;
int n = s.length();
char[] result = new char[n];
int row = 0;
int index = 0;
int circle = 2*(numRows-1);
for(int i=0;i<n;){
if((index*circle+row)<n){
result[i++] = s.charAt(index*circle+row);
}else{
row++;
index =0;
continue;
}
index++;
if(row==0 || row==numRows-1){
continue;
}else if((index*circle-row)<n){
result[i++] = s.charAt(index*circle-row);
}else{
row++;
index =0;
continue;
}
}
return new String(result);
}
}
516.Longest Palindromic Subsequence(最长回文子序列)
子序列有顺序，可以不连续
bbbab的最长回文子序列长度为4
思路:
- 动态规划。n=s.length(),设立一个n行，n列的dp数组。
d[i][j]代表s中下标i到j的子串中，最长回文子序列的长度。我们最后需要返回的是d[0][n-1]的值 - 易得 d[i][i]=1边界条件。
- dp数组这样更新，有两个指针i和j。指针i从尾部一直向前遍历到头，j从i的下一个元素一直遍历到尾部。
- 如果i,j指向的字符相等，说明能够添加到i~j的回文串的长度中，即d[i][j]=d[i+1][j-1]+2;
- 如果不相等，说明i ,j所指的两个元素对回文串长度无贡献，则dp[i][j]就是从dp[i+1][j]和dp[i][j-1]中选取较大的一个值即可
注意
1.状态转移方程要求d[i+1][j-1]，dp[i+1][j]，dp[i][j-1]都在d[i][j]之前就计算出来，也即开头更靠后的要先计算。所以i从末尾向前遍历。
2.d[i][i+1]的情况也符合递推式。因为d[i+1][i]的初始值为0
class Solution {
public int longestPalindromeSubseq(String s) {
if(s==null||s.length()==0)return 0;
int n = s.length();
int[][] d = new int[n][n];
for(int i=n-1;i>=0;i--){
d[i][i]=1;
for(int j=i+1;j<n;j++){
if(s.charAt(i)==s.charAt(j)){
d[i][j] = d[i+1][j-1] + 2;
}else{
d[i][j] = Math.max(d[i+1][j],d[i][j-1]);
}
}
}
return d[0][n-1];
}
}
最长回文子串
回文子串的判断，两个指针从两头到中间指向的字符都相等，就是回文字符串；或者反转字符串，和原字符串一样，也说明是回文字符串。
思路一：
动态规划。
//dp[i][i]=1
//如果s[i]==s[j]&&dp[i+1][j-1]==1则dp[i][j]=1;否则dp[i][j]=0
//dp[i][j]代表i~j的子串是不是回文字符串
//初始化：dp[i][<i]认为是空字符串，空的也算是回文。不然aa这里计算会出错
class Solution {
public String longestPalindrome(String s) {
if(s==null||s.length()==0)return s;
int start=0;
int end = 0;
int n=s.length();
int[][] dp = new int[n][n];
int max = 0;
//初始化：dp[i][<i]认为是空字符串，空的也算是回文。不然aa这里计算会出错
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
dp[i][j]=1;
}
}
//dp[i][i]=1
//如果s[i]==s[j]&&dp[i+1][j-1]==1则dp[i][j]=1;否则dp[i][j]=0
//dp[i][j]代表i~j的子串是不是回文字符串
for(int i=n-1;i>=0;i--){
dp[i][i]=1;
for(int j=i+1;j<n;j++){
if(s.charAt(i)==s.charAt(j)&&dp[i+1][j-1]==1){
dp[i][j]=1;
if(max<(j-i+1)){
max = j-i+1;
start =i;
end = j;
}
}else{
dp[i][j]=0;
}
}
}
return s.substring(start,end+1);
}
}
思路2：
反转字符串（n），求和原字符串的公共子串，如果公共子串是回文字符串且最长，就是原字符串的最长回文子字符串。
思路3
从头到尾，每个当做是mid,向两头扩展，如果两头指针指向的字符不相等了，就停止。记录最长长度。
如果遇到 baab这种情况，把它当做bab来看，也即right++直到不和mid相等。是O(n^2)的解法。
