Leetcode Day2

• leetcode -4 尋找兩個正序數組的中位數
• leetcode -5 最長回文子串
• leetcode -6 Z字型變換

leetcode -4 尋找兩個正序數組的中位數

• 題目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数。

• 解 :

解題思路: 把兩數組合併，排序，然後直接求中位數就可以了。唯一要注意的是，js 中的 sort 函數是默認以字符串字典順序排序的，所以會導致在排序數字時會發生 -1 排在 -2 前面的錯誤，在 sort 方法中傳入比較函數就可以了。

不過解一有缺點，解一的空間複雜度為 O(m+n)，而如果不允許使用 sort 以及 concat 函數，要自己合併兩數組，時間複雜度將為 O(m+n)，複雜度不太好。

降低複雜度的辦法，看解二。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */

 let findMedianSortedArrays = function(nums1, nums2) {
    if(nums1 == [] && nums2 != [])
        return num1;
    if(nums1 != [] && nums2 == [])
        return num2;

    let join = nums1.concat(nums2).sort(function(a, b) { return a-b });
    const len = join.length;
    if(len % 2 != 0) {
        return join[Math.floor(len/2)];
    }else {
        const right = len/2;
        const left = right-1;
        return (join[left] + join[right])/2;
    }
}

leetcode -5 最長回文子串

• 題目描述

给你一个字符串 s，找到 s 中最长的回文子串。譬如說給定 babad，要求返回 bab 或 aba。

• 解 : 動態規劃

具體的核心思想如下:

• 如果一個字符串是回文串，那麼在它的左右加上相同字符它還是個回文串。

• 如果在一個不是回文串的字符串的兩端加上任何字符，或者在一個回文串兩端加上不同字符，得到的一定不是個回文串。

基於上面的規則，我們建立一個動態規劃模型。

我們用 dp[i][j] 來表示整個字符串從 i 到 j (包括 i,j) 能不能形成一個回文串，動態規劃模型可以表示為如下代碼表述:

if(s[i] === s[j] && dp[i+1][j-1]) {
    dp[i][j] = true;
}

而最基本的回文串就是一個字符，或是兩個相同的字符。

/**
 * @param {string} s
 * @return {string}
 */

let longestPalindrome = function(s) {
    if(!s || s.length == 0)
        return "";
    
    let res = s[0];
    let dp = [];

    for(let i=s.length-1; i>=0; i--) {
        dp[i] = [];
        for(let j=i; j<s.length; j++) {
            if(j - i == 0) {
                dp[j][i] = true;
            }
            else if(j - i == 1 && s[i] == s[j]) {
                dp[i][j] = true;
            }
            else if(s[i] == s[j] && dp[i+1][j-1]) {
                dp[i][j] = true;
            }

            if(dp[i][j] && j-i+1 > res.length) {
                res = s.slice(i, j+1);
            }
        }
    }

    return res;
}

leetcode -6 Z字型變換

• 題目描述

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

• 解 :

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */

let convert = function(s, numRows) {
    if(numRows == 1)
        return s;
    
    let arr = new Array(numRows).fill("");
    let group = 2*numRows -2;
    for(let i=0; i<s.length; i++) {
        arr[Math.min(i%group, group-i%group)] += s.charAt(i);
    }

    return arr.join("");
}