一天三题LeetCode(C++&JAVA)-4~6

转载请注明出处：

http://blog.csdn.net/miaoyunzexiaobao

4.     Median ofTwo Numbers

https://leetcode.com/problems/median-of-two-sorted-arrays/

给定两个有序数组A（长度为m）和B（长度为n），找到两个数组的中位数。若两个数组长度和为偶数，则返回中间两个数的平均值。例：A={1,5,14}，B={3,7,30}，则返回(5+7)/2=6.A={1,5,14}，B={3,7}，返回5。要求时间复杂度为log(m+n)

思路：

参考链接：http://blog.csdn.net/yutianzuijin/article/details/11499917/

简单的方法是将两个有序数组合并成一个，然后返回该数组的中间值。但在LeetCode中测试时会出现超时的问题。

这里将问题转化为更一般的情况：求两个有序数组合并起来，按序排列后的第k个值。然后利用A和B是有序数组的特性，首先假设数组A和B的元素个数都大于k/2，我们比较A[k/2-1]和B[k/2-1]两个元素，这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种情况：>、<和=。

1.   A[k/2-1]<B[k/2-1]，这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。

2.   当A[k/2-1]>B[k/2-1]时存在类似的结论。

3.   当A[k/2-1]=B[k/2-1]时，我们已经找到了第k小的数，也即这个相等的元素，我们将其记为m。由于在A和B中分别有k/2-1个元素小于m，所以m即是第k小的数。

这里如果k为奇数，则m不是中位数。在实际代码中是先求k/2，然后利用k-k/2获得另一个数

通过上面的分析，我们即可以采用递归的方式实现寻找第k小的数。此外我们还需要考虑几个边界条件：

• 如果A或者B为空，则直接返回B[k-1]或者A[k-1]；
• 如果k为1，我们只需要返回A[0]和B[0]中的较小值；
• 如果A[k/2-1]=B[k/2-1]，返回其中一个；

C++:

int findKth(int A[],int B[],int k,int m,int n){
	if(m>n)
		return findKth(B,A,k,n,m);
	if(m == 0)
		return B[k-1];
	if(k == 1)
		return (A[k-1]<B[k-1]?A[k-1]:B[k-1]);

	int pa = (k/2 < m ? k/2 : m);
	int pb = k - pa;

	if(A[pa - 1] < B[pb - 1])
		return findKth(A+pa,B,k-pa,m-pa,n);
	else if(A[pa - 1] > B[pb - 1])
		return findKth(A,B+pb,k-pb,m,n-pb);
	else 
		return A[pa - 1];
}
double findMedianSortedArrays(int A[], int m, int B[], int n)
{
	int total = m + n;
	if(total % 2 !=0)
		return (double)(findKth(A,B,total/2+1,m,n));
	else
		return (findKth(A,B,total/2,m,n)+findKth(A,B,total/2+1,m,n))/2.0 ;

}

JAVA:

public static int findKth(int A[], int B[], int k) {
		int aLen = A.length;
		int bLen = B.length;

		if (aLen > bLen)
			return findKth(B, A, k);
		if (aLen == 0)
			return B[k - 1];
		if (k == 1)
			return Math.min(A[0], B[0]);

		int pa = Math.min(k / 2, aLen);
		int pb = k - pa;

		if (A[pa - 1] < B[pb - 1])
			return findKth(Arrays.copyOfRange(A, pa, aLen), B, k - pa);
		else
			return findKth(A, Arrays.copyOfRange(B, pb, bLen), k - pb);
	}

	public static double findMedianSortedArrays(int A[], int B[]) {
		int m = A.length;
		int n = B.length;
		int mid = (m + n) / 2;

		if ((m + n) % 2 == 0)
			return (double) (findKth(A, B, mid) + findKth(A, B, mid + 1)) / 2.0;
		else
			return (double) findKth(A, B, mid + 1);
	}

5.      LongestPalindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

给定一个字符串，求出其最长回文子串。

思路：

参考链接：

http://blog.csdn.net/zhouworld16/article/details/16842467

解法1：逆转该字符串，则问题转换为求两个字符串的最长公共子字符串

解法2：动态规划。用booldp[i][j]表示子串从第i个字符到第j个字符是否为回文子串。易知：

初始条件可设置长度为1和为2的dp。即可确定dp[i][i]= true，dp[i][i+1] = (s[i] == s[i+1])

判断条件为：dp[i ][ j ] = dp[ i + 1][ j - 1] && s[ i ] == s[ j ]。

解法3：中心扩展法。利用回文是中心对称的特性，从下标i出发，用两个指针分别向i的左右两边移动，判断是否相等。需要注意的是回文有奇偶数之分。如abc和abba两种类型。

C++:

static string expandAroundCenter(string s, int c1, int c2) {
		int l = c1, r = c2;
		int n = s.length();
		while (l >= 0 && r <= n-1 && s[l] == s[r]) {
			l--;
			r++;
		}
		return s.substr(l+1, r-l-1);
	}

	static string longestPalindrome(string s) {
		int n = s.length();
		if (n == 0) return "";
		string longest = s.substr(0, 1);  // a single char itself is a palindrome
		for (int i = 0; i < n-1; i++) {
			string p1 = expandAroundCenter(s, i, i);
			if (p1.length() > longest.length())
				longest = p1;

			string p2 = expandAroundCenter(s, i, i+1);
			if (p2.length() > longest.length())
				longest = p2;
		}
		return longest;
	}

public static String longestPalindrome(String s) {
		if (s.isEmpty()) {
			return null;
		}
		if (s.length() == 1) {
			return s;
		}
		String longest = s.substring(0, 1);
		for (int i = 0; i < s.length(); i++) {
			String tmp = helper(s, i, i);
			if (tmp.length() > longest.length()) {
				longest = tmp;
			}
			tmp = helper(s, i, i + 1);
			if (tmp.length() > longest.length()) {
				longest = tmp;
			}
		}

		return longest;
	}
	public static String helper(String s, int begin, int end) {
		while (begin >= 0 && end <= s.length() - 1
				&& s.charAt(begin) == s.charAt(end)) {
			begin--;
			end++;
		}
		return s.substring(begin + 1, end);
	}

6.      ZigZagConversion

https://leetcode.com/problems/zigzag-conversion/

把一个字符串用ZigZag的形式表示并打印出来。比如"PAYPALISHIRING"按照ZIgZag的形式为：

P   A   H   N

A P L S I I G

Y   I   R

打印出来即为："PAHNAPLSIIGYIR"

思路：

见参考链接：

http://blog.csdn.net/zhouworld16/article/details/14121477

C++:

string convert(string s, int nRows) {
          if (nRows <= 1 || s.length() == 0)  
           return s;  
  
        string res = "";  
        int len = s.length();  
        for (int i = 0; i < len && i < nRows; ++i)  
        {  
            int indx = i;  
            res += s[indx];  
  
            for (int k = 1; indx < len; ++k)  
            {  
                //第一行或最后一行，使用公式1：  
                if (i == 0 || i == nRows - 1)  
                {  
                    indx += 2 * nRows - 2;  
                }  
                //中间行，判断奇偶，使用公式2或3  
                else  
                {  
                    if (k & 0x1)  //奇数位  
                        indx += 2 * (nRows - 1 - i);  
                    else indx += 2 * i;  
                }
                //判断indx合法性  
                if (indx < len)  
                {  
                    res += s[indx];  
                }     
            }  
        }  
        return res;  
    }

public static String convert(String s, int nRows) {
		if (s == null || s.length() <= nRows || nRows <= 1)
			return s;
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < s.length(); i += 2 * (nRows - 1))
			sb.append(s.charAt(i));

		for (int i = 1; i < nRows - 1; ++i)
			for (int j = i; j < s.length(); j += 2 * (nRows - 1)) {
				sb.append(s.charAt(j));
				if (j + 2 * (nRows - i - 1) < s.length())
					sb.append(s.charAt(j + 2 * (nRows - i - 1)));
			}

		for (int i = nRows - 1; i < s.length(); i += 2 * (nRows - 1))
			sb.append(s.charAt(i));

		return sb.toString();
	}