date: 2015-09-13 16:32:49
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)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如何更合适:- 将2个数组按长短分为a[0,1,...,m-1],b[0,1,....,n-1],其中n>=m
- 分治法,将K/2,比较a[k/2-1]和b[k/2-1],第k小,即合并并后数组ab[k-1]!
- 三种情况,
一: 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:
- m==0;return b[k-1];
- k/2>m,此时,A[index]index直接取m-1,使用a[m-1];
- 递归过程中,k每次减去从两个数组中剔除数字的个数,所以k在自减,然后k/2分治在2个数组中,终止条件k<=1,Kth等于此时两个数组的首个的最小值
- a[min(k/2,m)-1],b[index],index如果取值k/2-1会使分治的区域中无法包含Kth,因为采用k-min(k/2,m),此处代码中有详解
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)); } }
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<< int pb=k-pa; 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是不是回文- i=j,是回文(a)
- j=i+1,如果字符相当,是回文(aa)
- 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
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>间距>=2!用k表示j和i的间距,进行递增。每次从i=0开始寻找i+k后的j,<< >>判断flag[i][j]值,最终完成最大间距的flag[i][j],其中j-i is max!<< for(int k=2;k
EOF 5
ZigZag Conversion
ZigZag,直接上个表格,就明了了,以string=“abcdefghij”
为例:
a | g | |||
---|---|---|---|---|
b | f | h | ||
c | e | i | k | |
d | j |
思路:
- 题目要求较简单,仅仅是返回一个经过Zigzag转化的字符串,所以考虑用StringBuilder
- zigzag特点是,斜着的部分的个数是row-2,首行和末行是没有斜位的
- StringBuilder一定要先初始化再用,否则报错,老是忘....
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=1&&i