题目4

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution  //combine the arrays
{
    public double findMedianSortedArrays(int[] nums1, int[] nums2) 
    {
        int[] nums;
        int length1 = nums1.length;
        int length2 = nums2.length;
        nums = new int[length1 + length2];
        if(length1 == 0)
        {
            if(length2 % 2 == 0)
            {
                return (nums2[length2/2] + nums2[length2/2 - 1])/2.0;
            }
            else
            {
                return nums2[length2/2];
            }
        }

        if(length2 == 0)
        {
            if(length1 % 2 == 0)
            {
                return (nums1[length1/2] + nums1[length1/2 - 1])/2.0;
            }
            else
            {
                return nums1[length1/2];
            }
        }

        int flag = 0;
        int i = 0,j = 0;
        while(flag != (length1+length2))
        {
            if(i == length1)
            {
                while(j != length2)
                {
                    nums[flag++] = nums2[j++];
                }
                break;
            }

            if(j == length2)
            {
                while(i != length1)
                {
                    nums[flag++] = nums1[i++];
                }
                break;
            }

            if(nums1[i] < nums2[j])
            {
                nums[flag++] = nums1[i++];
            }
            else
            {
                nums[flag++] = nums2[j++];
            }
        }
        
        if (flag % 2 == 0)
        {
            return (nums[flag/2] + nums[flag/2 - 1])/2.0;
        }
        else
        {
            return nums[flag/2];
        }
    }
}

题目5

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：
输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution  //brute force
{
    public String longestPalindrome(String s) 
    {
        int max = 0;
        String ans = "";
        int n = s.length();
        for(int i = 0;i < n;i++)
        {
            for(int j = i+1;j <= n;j++)
            {
                String tempString = s.substring(i, j);
                if(isPalindRomic(tempString) && tempString.length()>max)
                {
                    max = tempString.length();
                    ans = s.substring(i, j);
                }
            }
        }
        return ans;
    }

    public boolean isPalindRomic(String s)
    {
        int n = s.length();
        for(int i = 0;i < n/2; i++)
        {
            if(s.charAt(i) != s.charAt(n-i-1)) return false;
        }
        return true;
    }
}

class Solution  //DP
{
    public String longestPalindrome(String s)
    {
        int len = s.length();
        if(len < 2)
        {
            return s;
        }

        boolean[][] dp = new boolean[len][len];

        for(int i = 0;i < len; i++)
        {
            dp[i][i] = true;
        }

        int maxLen = 1;
        int start = 0;
        for(int j = 1;j < len;j++)
        {
            for(int i = 0;i < j;i++)
            {
                if(s.charAt(i) == s.charAt(j))
                {
                    if((j - i) < 3)
                    {
                        dp[i][j] = true;
                    }
                    else
                    {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                else
                {
                    dp[i][j] = false;
                }

                if(dp[i][j])
                {
                    int curLen = j -i + 1;
                    if(curLen > maxLen)
                    {
                        maxLen = curLen;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start,start + maxLen);
    }
}