leetcode 4_5_6_8

algorithm

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
大意：求两个有序数组的中位数(中位数：奇数个即为中间数，偶数个为中间2个数均值)

解法1:(不考虑time complexity)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
   public double findMedianSortedArrays2(int[] a, int[] b) {
	int alen=a.length;
	int blen=b.length;
	int[] result=new int[alen+blen];
	System.arraycopy(a, 0, result, 0, alen);
	System.arraycopy(b, 0, result, alen, blen);
	Arrays.sort(result);
	>>Arrays.parallelSort(result);并行排序在数量大于10K时，将明显体现<<
	int mid=result.length/2;
	if ((result.length)%2!=0) {
		return (double)result[mid];
	}
	else {
		return ((double)result[mid]+(double)result[mid-1])/2;
	}
}

解法2：(考虑time complexity)
思路：
扩展为2个有序数组，求第K小的数，median是此情况特例。
寻找第K小的数(Kth)，假如数组均是升序排列，中位数(奇数个即中间的数，偶数个是中间2个数的平均值)
几个步骤，暂不考虑b[index]的游标index如何更合适：

  1. 将2个数组按长短分为a[0,1,…,m-1],b[0,1,….,n-1],其中n>=m
  2. 分治法，将K/2，比较a[k/2-1]和b[k/2-1],第k小，即合并并后数组ab[k-1]!
  3. 三种情况，

一： a[k/2-1]==b[k/2-1]，则a[k/2-1]==b[k/2-1]==第k小的数

二： a[k/2-1]< b[k/2-1],则a[0,…,k/2-1]中Kth必然不在此，因为a[0,…,k/2-1]加上b[0,…,k/2-1]总共才k个数，而a[k/2-1]<b[k/2-1]，也就是Kth只可能存在a[k/2,..,m-1]和b[0,…,n-1]中

三： a[k/2-1]> b[k/2-1],则b[0,…,k/2-1]中Kth必然不在此，因为a[0,…,k/2-1]加上b[0,…,k/2-1]总共才k个数，而a[k/2-1]>b[k/2-1]，也就是Kth只可能存在a[0,..,m-1]和b[k/2,…,n-1]中

Edge case：

  1. m==0;return b[k-1];
  2. k/2>m,此时，A[index]index直接取m-1,使用a[m-1];
  3. 递归过程中，k每次减去从两个数组中剔除数字的个数，所以k在自减，然后k/2分治在2个数组中，终止条件k<=1,Kth等于此时两个数组的首个的最小值
  4. a[min(k/2,m)-1],b[index],index如果取值k/2-1会使分治的区域中无法包含Kth，因为采用k-min(k/2,m),此处代码中有详解
1
2
3
4
5
6
7
8
9
10
11
12
13
   public double findMedianSortedArrays(int[] nums1, int[] nums2) {
	int k=nums1.length+nums2.length;
	int m=nums1.length;
	int n=nums1.length;
	if(k%2!=0)
	{
		return findKth(nums1, m, nums2, n,k/2+1);
	}
	else
	{	
		return (findKth(nums1, m, nums2, n, k/2)+findKth(nums1, m, nums2, n, k/2+1));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
   public  double findKth(int[] a,int alen, int[] b,int blen,  int k)
{
	if(alen>blen)
	{
		return findKth(b, blen, a, alen, k);
	}
	if(alen==0)
	{
		return b[k-1];
	}
	if(k==1)
		return Math.min(a[0],b[0]);
	//>>游标pa,pb表示a,b的前pa,pb个数,将k进行分治，舍得pa+pb=k<<
	int pa=Math.min(k/2, alen);
	//>>当k为奇数时，若pb=k/2，则pa和pb两个游标不能涵盖kth:(k=3,pa=1,pb=1,pa+pb<k)<<
	int pb=k-pa;
	if (a[pa-1]<b[pb-1]) {
		return findKth(Arrays.copyOfRange(a, pa, alen), alen-pa, b, blen, k-pa);			
	}
	else if (a[pa-1]>b[pb-1]) {
		return findKth(a, alen, Arrays.copyOfRange(b, pb, blen), blen-pb, k-pb);
	}
	else {
		return a[pa-1];
	}
}

补充：关于copyOfRange()方法
public static long[] copyOfRange(long[] original, int from, int to)
参数：
original - 将要从其复制一个范围的数组
from - 要复制的范围的初始索引（包括）!!!!!!
to - 要复制的范围的最后索引（不包括）!!!!!!要复制全部的话，必须大于（不能等于最后索引）（此索引可以位于数组范围之外）

EOF 4

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
最长回文子串

思路：
单字符即是回文，有初始条件，可以联想到用DP
用个boolean flag[i][j]二维数组，表示从i到j是不是回文

  1. i=j,是回文(a)
  2. j=i+1，如果字符相当，是回文(aa)
  3. j>i+1, 判断string[j]=?string[i],相等的话，递归求flag[i+1][j-1]=?true,全部满足，则flag[i][j]=true(abba)

注意，TLE问题，substring()时间消耗挺大，避免循环中使用

public String substring(int beginIndex, int endIndex)
参数：
beginIndex - 起始索引（包括）
endIndex - 结束索引（不包括）又是不包括，注意+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
   public String longestPalindrome(String s) {
   if(s == null || s.length() <= 1) {
       return s;
   }
   int len = s.length();
   int start = 0, end = 0;
   boolean[][] flag = new flag[len][len];
   // 间距0
   for(int i=0;i<len;i++) {
       flag[i][i] = true;
   }
   // 间距1
   for(int i=1;i<len;i++) {
       if(s.charAt(i-1) == s.charAt(i)) {
           flag[i-1][i] = true;
           start = i-1; end = i;
       }
   }
   >>间距>=2！用k表示j和i的间距，进行递增。每次从i=0开始寻找i+k后的j，<<
   >>判断flag[i][j]值，最终完成最大间距的flag[i][j]，其中j-i is max！<<
   for(int k=2;k<len;k++) {
       for(int i=0;i+k<len;i++) {
           int j = i+k;
           if(s.charAt(i) == s.charAt(j) && flag[i+1][j-1]) {
               flag[i][j] = true;
               start = i; end = j;
           }
       }
   }
return s.substring(start,end);
   }

EOF 5

ZigZag Conversion

ZigZag，直接上个表格，就明了了，以string=“abcdefghij”为例：

a g
b f h l
c e i k
d j

思路：

  • 题目要求较简单，仅仅是返回一个经过Zigzag转化的字符串，所以考虑用StringBuilder
  • zigzag特点是，斜着的部分的个数是row-2,首行和末行是没有斜位的
  • StringBuilder一定要先初始化再用，否则报错，老是忘….
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
           public String convert(String s, int nRows) {
    	char[] c=s.toCharArray();
    	int len=c.length;
    	StringBuilder[] StringBuilders=new StringBuilder[nRows];
    	for (int i = 0; i < nRows; i++) {
    		StringBuilders[i]=new StringBuilder();
    	}
    	int i=0;
    	while(i<len)
    	{
    		for (int j = 0; j < nRows&&i<len; j++) {
    			StringBuilders[j].append(c[i++]);
    		}
    		for (int j = nRows-2; j >=1&&i<len; j--) {
    			StringBuilders[j].append(c[i++]);
    		}
    	}
    	for (int j = 1; j < StringBuilders.length; j++) {
    		StringBuilders[0].append(StringBuilders[j]);
    	}
    	return StringBuilders[0].toString();
    }