class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    List<Integer>list=new ArrayList<Integer>();
    int i=0;
    int j=0;
    //重新组合序列
    while(i<nums1.length&&j<nums2.length) {
        if(nums1[i]<=nums2[j]) {
          list.add(nums1[i++]);
        }
        else {
          list.add(nums2[j++]);
                }
      }
        //如果跳出上面的循环,那么显然至少有一个数组已经遍历结束了
      //那么很显然我们就只需要再吧最后剩下的数组遍历结束即可
        while(j<nums2.length) {
            list.add(nums2[j++]);
        }
        //这里理由同上
        while(i<nums1.length) {
            list.add(nums1[i++]);
        }
        //分情况返回或者中位数
    if(list.size()%2==0) {
      double result=(double)(list.get(list.size()/2-1)+list.get(list.size()/2))/2;
      return result;
    }
    else {
      return list.get(list.size()/2);
    }
    }
}

class Solution {
   public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int sum=nums1.length+nums2.length;
    //这里我们将数组的长度定义为+1,是为了包容两种情况
    //否则又得分情况讨论
    int nums3[]=new int [sum/2+1];
    int i=0,j=0,k=0;
    //重新组合序列
    while (i<nums3.length) {
      if(j<nums1.length&&k<nums2.length) {
        if(nums1[j]<nums2[k]) {
          nums3[i++]=nums1[j++];
        }
        else {
          nums3[i++]=nums2[k++];
        }
      }
            else 
        break;
    }
    //这里和第一版的代码差不多,只不过多了一步判断是否越过重新组合序列长度
        while(i<nums3.length&&j<nums1.length) {
      nums3[i++]=nums1[j++];
    }
        while(i<nums3.length&&k<nums2.length) {
            nums3[i++]=nums2[k++];
        }
        //分情况返回或者中位数
    if(sum%2==0)
      return (double)(nums3[nums3.length-2]+nums3[nums3.length-1])/2;
    else 
      return nums3[nums3.length-1];
    }
}

class Solution {
    //判断是不是回文串
    public boolean panduan(String string1) {
    char[]ch=string1.toCharArray();
    for(int i=0;i<ch.length/2;i++) {
      if(ch[i]!=ch[ch.length-i-1])
        return false;
    }
    return true;
  }
  //暴力求解
  public String longestPalindrome(String s) {
    for(int i=s.length();i>0;i--) {
      for(int j=0;j<s.length()-i+1;j++) {
        if(panduan(s.substring(j, j+i))) {
          return s.substring(j, j+i);
        }
      }
    }
    return "";
   }
}

class Solution {
 public String longestPalindrome(String s) {
    boolean [][]dp=new boolean[s.length()][s.length()];
    char []schar=s.toCharArray();
    int max=Integer.MIN_VALUE;
    int begin=0;
    int end=0;
    for(int i=0;i<schar.length;i++) {
      dp[i][i]=true;
    }
    //k为步长,i为起点,j为终点
    for(int k=1;k<schar.length;k++) {
      for(int i=0;i<schar.length-k;i++) {
        int j=i+k;
        //处理回文串长度为偶数的情况
        if(j-i==1) {
          if(schar[i]==schar[j]) {
            dp[i][j]=true;
            //记录最大的回文串索引
            if(j-i+1>max) {
              max=j-i+1;
              begin=i;
              end=j;
            }
          }
          else 
            dp[i][j]=false;
        }
        //防止数组越界
        else if(i+1<=j-1) {
          if(schar[i]==schar[j]&&dp[i+1][j-1]) {
            dp[i][j]=true;
            //记录最大的回文串索引
            if(j-i+1>max) {
              max=j-i+1;
              begin=i;
              end=j;
            }
          }
          else 
            dp[i][j]=false;
        } 
      }
    }
    return s.substring(begin, end+1);
    }
}

class Solution {
//中心扩散法
  public String longestPalindrome(String s) {
    int max=1;
    String result=s.substring(0,1);
    for(int i=0;i<s.length()-1;i++) {
        //长度为奇数的最大回文串
      String oddString=diffusion(s, i, i);
      //长度为偶数的最大回文串
      String evenString=diffusion(s, i, i+1);
      String maxString=oddString.length()>evenString.length()?oddString:evenString;
      if(maxString.length()>max) {
        max=maxString.length();
        result=maxString;
      }
    }
    return result;
    }
  //扩散函数,找到以当前位置为中间点的最大回文串
  public String diffusion(String s,int left,int right) {
    int i=left;
    int j=right;
    while(i>=0&&j<s.length()) {
      if(s.charAt(i)==s.charAt(j)) {
        i--;
        j++;
      }
      else {
        break;
      }
    }
    return s.substring(i+1, j);
  }
}

class Solution {
   //判断每个字符应该添加在哪一行
   public int row(int index,int numRows) {
    if(index%(numRows*2-2)<numRows)
      return index%(numRows*2-2);
    else 
      return 2*numRows-2-index%(numRows*2-2);
  }
  public String convert(String s, int numRows) {
    if(numRows==1) {
      return s;
    }else {
        //创建numRows个字符串用来存储我们的元素
      StringBuffer []stringBuffers=new StringBuffer[numRows];
      for(int i=0;i<numRows;i++) {
        stringBuffers[i]=new StringBuffer();
      }
      //根据计算出来的行号,将元素添加到对应行号的字符串中
      for(int i=0;i<s.length();i++) {
        stringBuffers[row(i, numRows)].append(s.charAt(i));
      }
      //将之前我们已经分配好元素的字符串按照顺序进行拼接
      StringBuffer stringBuffer=new StringBuffer();
      for(int i=0;i<numRows;i++) {
        stringBuffer.append(stringBuffers[i]);
      }
      return stringBuffer.toString();
    }
    }
}