# LeetCode日常刷题（2）

xiaoxiao2021-02-28  8

# 4. 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)).

Example 1:

nums1 = [1, 3] nums2 = [2] The median is 2.0

Example 2:

nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5

## 解法

#### Approach #1 Recursive Approach [Accepted]

To solve this problem, we need to understand “What is the use of median”. In statistics, the median is used for:

Dividing a set into two equal length subsets, that one subset is always greater than the other.

If we understand the use of median for dividing, we are very close to the answer.

First let’s cut \text{A}A into two parts at a random position ii:

left_A | right_A A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]

Since A has m elements, so there are m 1 kinds of cutting ( i=0m ).

And we know:

len(left_A)=i,len(right_A)=m−i. Note: when i = 0; left_A is empity, and when i = m, right_A is empty.

With the same way, cut B into two parts at a random position j :

left_B | right_B B[0], B[1], ..., B[j-1] | B[j], B[j 1], ..., B[n-1]

Put left_A and left_B into one set, and put right_A and right_B into another set. Let’s name them left_part and right_part:

left_part | right_part A[0], A[1], ..., A[i-1] | A[i], A[i 1], ..., A[m-1] B[0], B[1], ..., B[j-1] | B[j], B[j 1], ..., B[n-1]

If we can ensure:

len(left_part) = len(right_part) max(left_part) <= min(right_part)

then we divide all elements in {A,B} into two parts with equal length, and one part is always greater than the other. Then

median=max(left_part) min(right_part)2

To ensure these two conditions, we just need to ensure:

i + j = m - i + n - j (or: m - i + n - j + 1) if nm , we just need to set: [Math Processing Error] B[j1]A[i]andA[i1]B[j]

ps.1 For simplicity, I presume A[i−1],B[j−1],A[i],B[j] are always valid even if i = 0, i = m, j = 0, j = m. I will talk about how to deal with these edge values at last.

ps.2 Why nm ? Because I have to make sure j is non-negative since 0≤i≤m and j=m+n+12i . If n < m, then j may be negative, that will lead to wrong result.

So, all we need to do is:

Searching i in [0,m] , to find an object i such that:

B[j1]A[i] and  A[i1]B[j] , where j=m+n+12i

B[j1]A[i]andA[i1]B[j]

B[j1]>A[i]

​ 当然，因为当i增大的时候，j会相应的减小，所以B[j - 1]会减小, A[i]会增 大，最后B[j1]A[i]

A[i1]>B[j]

When the object i is found, the median is:

max(A[i1],B[j1]), when m+n is odd 当m+n是奇数

max(A[i1],B[j1])+min(A[i],B[j])2 , when m+n is even 当m+n是偶数

[0,m] 的区间中搜索 i

(j==0 or i==m or B[j1]A[i]) and(i==0 orj==n orA[i1]B[j]) j=m+n+12i

(j==0 or i==m or B[j1]A[i]) and

(i==0 orj==n orA[i1]B[j])

j>0 andi<m and B[j1]>A[i]

i>0 j<n and A[i1]>B[j]

## 代码：

class Solution { public static double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1 == null && nums2 == null) { return 0; } if ((nums1 == null || nums1.length == 0) && (nums2 != null && nums2.length != 0)) { return nums2.length % 2 == 0 ? (nums2[nums2.length / 2] nums2[nums2.length / 2 - 1]) / 2.0f : (nums2[nums2.length / 2]); } if ((nums2 == null || nums2.length == 0) && (nums1 != null && nums1.length != 0)) { return nums1.length % 2 == 0 ? (nums1[nums1.length / 2] nums1[nums1.length / 2 - 1]) / 2.0f : (nums1[nums1.length / 2]); } assert nums1 != null; assert nums2 != null; int[] arrA; int[] arrB; if (nums1.length > nums2.length){ arrA = nums2; arrB = nums1; }else{ arrA = nums1; arrB = nums2; } int iMin = 0; int iMax = arrA.length; int m = arrA.length; int n = arrB.length; assert n >= m; int halfLen = (m n 1) / 2; while (iMin <= iMax){ int i = (iMin iMax) / 2; int j = halfLen - i; if (i < iMax && arrB[j - 1] > arrA[i]){ iMin ; }else if (i > iMin && arrA[i - 1] > arrB[j]){ iMax --; }else { int maxLeft = 0; if (i == 0){ maxLeft = arrB[j - 1]; }else if (j == 0){ maxLeft = arrA[i - 1]; }else{ maxLeft = max(arrA[i - 1], arrB[j - 1]); } if ((m n) % 2 != 0){ return maxLeft; } int minRight = 0; if (i == m){ minRight = arrB[j]; }else if (j == n){ minRight = arrA[i]; }else{ minRight = min(arrA[i], arrB[j]); } return (maxLeft minRight) / 2.0; } } return 0.0; } public static int max(int a, int b) { return a > b ? a : b; } public static int min(int a, int b) { return a > b ? b : a; } }

# 5. 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.

Example:

Example:

Input: "cbbd" Output: "bb"

## 解法：

### 2.动态规划

map[i][i]=true

map[i][i+1]=(si==sj)

map[i,j]=(map[i+1][j1] and Si==Sj)

public String longestPalindrome(String s) { int n = s.length(); String res = null; boolean[][] dp = new boolean[n][n]; for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]); if (dp[i][j] && (res == null || j - i + 1 > res.length())) { res = s.substring(i, j + 1); } } } return res; }

### 3. 中心延展法

public String longestPalindrome(String s) { int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } private int expandAroundCenter(String s, int left, int right) { int L = left, R = right; while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) { L--; R++; } return R - L - 1; }

# 6. ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P L I A A I R N Y P S I G P H

And then read line by line:

"PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert(“PAYPALISHIRING”, 4) should return “PLIAAIRNYPSIGPH”

public String convert(String s, int numRows) { if (numRows <= 1) return s; StringBuilder[] stringMap = new StringBuilder[numRows]; for (int i = 0; i < stringMap.length; i++) { stringMap[i] = new StringBuilder(""); } int increase = 1; int index = 0; for (int i = 0; i < s.length(); i++) { stringMap[index].append(s.charAt(i)); if (index == 0) { increase = 1; } if (index == numRows - 1) { increase = -1; } index += increase; } StringBuilder builder = new StringBuilder(); for (StringBuilder aStringMap : stringMap) { builder.append(aStringMap); } return builder.toString(); }

.