Leetcode Day2

Leetcode Day2

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,要求返回 bababa

  • 解 : 動態規劃

Leetcode Day2
具體的核心思想如下:

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

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

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

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

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

Leetcode Day2

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

/**
 * @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 字形排列。
Leetcode Day2

  • 解 :
/**
 * @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("");
}
上一篇:学习redis_day2常用小命令


下一篇:《Linux系统编程》----DAY2