LeetCode(4-寻找两个正序数组的中位数&&5-最长回文子串&&6-Z形变换)

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();
		}
    }
}