Leetcode-4-5

LeetCode 4 Median of Two Sorted Arrays

Problem : 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)).

Example1 :

nums1 = [1, 3] nums2 = [2]

The median is 2.0

Example1 :

nums1 = [1, 2] nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution : 刚看到这道题目其实觉得并不是一道难题，上手写发现还真是那么一回事，完全不像是hard这个难度的题目，其实解法也很简单，就是将两个数组合并获得最终数组再判断最终数组长度的基偶情况，最后再获得其最终结果（合并的算法就是归并算法的其中一部分）。

当然其中的小坑就是没有将int类型转换为double类型而导致输出错误，就是对java的学习还不够深入。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int i = 0, j = 0, k = 0;
        int length = nums1.length + nums2.length;
        int []nums = new int[length];
        double result;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j])
                nums[k++] = nums1[i++];
            else
                nums[k++] = nums2[j++];
        }

        while (i < nums1.length) {
            nums[k++] = nums1[i++];
        }

        while (j < nums2.length) {
            nums[k++] = nums2[j++];
        }

        int median = length / 2;
        result = nums[median];
        if(length % 2 == 0) {
            // 最后这里没加入(double)导致输出的结果是int形式的
            result = (double)(nums[median] + nums[median - 1]) / 2;
        }
        return result;
    }
}

LeetCode 5 Longest Palindromic Substring

Problem : Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example1 :

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.

Example2 :

Input: “cbbd”

Output: “bb”

Solution : 这道题作为一道medium的题目，刚看到还真的是难倒我了，题目是要 找到最长的回文并且打印出来。刚开始以为是需要使用某种数据结构（比如stack或者hashmap）来解决问题的，但是都不能解决问题，看了答案发现是遍历所有点来判断点是否为回文的中点。

class Solution {
    public String longestPalindrome(String s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            // 判断是否是aba这种形式
            int len1 = findPalindrome(s, i, i);
            // 判断是否是abba这种形式
            int len2 = findPalindrome(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 findPalindrome(String s, int left, int right) {
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

刚开始记录的都是leetcode的刷题心得，但是后面会慢慢的写对数据结构和计算机网络的理解以及容易遇到的问题。

LeetCode 4 Median of Two Sorted Arrays

LeetCode 5 Longest Palindromic Substring

CATALOG

FEATURED TAGS

FRIENDS