转载请注明出处：
4.Median ofTwo Numbers
https://leetcode.com/problems/median-of-two-sorted-arrays/
思路：
参考链接：
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));elsereturn (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);elsereturn 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;elsereturn (double) findKth(A, B, mid + 1);}
5.LongestPalindromic Substring
https://leetcode.com/problems/longest-palindromic-substring/
给定一个字符串，求出其最长回文子串。
思路：
参考链接：
dp[i][i]= true，dp[i][i+1] = (s[i] == s[i+1])
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 palindromefor (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;}JAVA:
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/
P A H NA P L S I I GY I R
打印出来即为："PAHNAPLSIIGYIR"
思路：
见参考链接：
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或3else{if (k & 0x1) //奇数位indx += 2 * (nRows – 1 – i);else indx += 2 * i;}//判断indx合法性if (indx < len){res += s[indx];}}}return res;}JAVA:
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();}
，放弃等于又一次可以选择的机会。
