leetCode题目

1. leetcode hot100 (opens new window)
2. 剑指offer (opens new window)

1、最长回文子串

题目：给你一个字符串 s，找到 s 中最长的回文子串，相关示例如下：

//示例1
输入：s = "babad"
输出："bab"
//示例2
输入：s = "cbbd"
输出："bb"
//示例3
输入：s = "a"
输出："a"
//示例4
输入：s = "ac"
输出："a"

解法：

• 暴力枚举：时间复杂度：O(n^3)，空间复杂度：O(1)
• 中心扩散法：时间复杂度：O(n^2)，空间复杂度：O(1)
• 动态规划：时间复杂度：O(n^2)，空间复杂度：O(n^2)
• Manacher算法：动态规划 + 中心扩散，时间复杂度：O(n)，空间复杂度：O(n)

1、暴力枚举

• 根据回文子串的定义，枚举所有长度大于等于 2 的子串，依次判断它们是否是回文；
• 可以只针对大于「当前得到的最长回文子串长度」的子串进行回文验证；
• 当得到了一个更长的回文时，不需要真的做截取。只需要记录「当前子串的起始位置」和「子串长度」。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    const length = s.length;
    if(length < 2){
        return s;
    }
    let maxNum = 1;
    let startNum = 0;
    for(let i=0; i<length-1; i++){
        for(let j=i+1; j<length; j++){
            if(isPlalindrome(s, i, j) && (j- i + 1 > maxNum)){
                startNum = i;
                maxNum = j - i + 1;
            }
        }
    }
    return s.substr(startNum, maxNum);

};

function isPlalindrome(s, start, end){
    while(start < end){
        if(s[start] !== s[end]){
            return false;
        }else{
            start++;
            end--;
        }
    }
    return true;
}

2、中心扩散法

遍历每一个下标，以这个下标为中心，利用「回文串」中心对称的特点，往两边扩散，看最多能扩散多远。

设计一个方法，兼容以上两种情况：

• 如果传入重合的下标，进行中心扩散，此时得到的回文子串的长度是奇数；
• 如果传入相邻的下标，进行中心扩散，此时得到的回文子串的长度是偶数。

var longestPalindrome = function(s) {
    const length = s.length;
    if(length < 2){
        return s;
    }
    let maxNum = 1;
    let startNum = 0;
    for(let i=0; i<length; i++){
        const n1 = expandAroundCenter(s, i, i);
        const n2 = expandAroundCenter(s, i, i+1);
        const maxN = Math.max(n1, n2);
        if(maxN > maxNum){
            maxNum = maxN;
            startNum = n1 > n2 ? i - Math.floor(maxN/2) : i - Math.floor(maxN/2) + 1;
        }
    }
    return s.substr(startNum, maxNum);
}

function expandAroundCenter(s, start, end){
    const length = s.length;
    while(start >= 0 && end < length){
        if(s[start] === s[end]){
            start--;
            end++;
        }else{
            break;
        }
    }
    return (end -1) - (start + 1) + 1;
}

3、动态规范

回文天然具有「状态转移」性质：一个长度严格大于 22 的回文去掉头尾字符以后，剩下的部分依然是回文。反之，如果一个字符串头尾两个字符都不相等，那么这个字符串一定不是回文。「动态规划」的方法根据这样的性质得到。

1、定义状态

dp[i][j] 表示：子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，即可以取到 s[i] 和 s[j]。

2、状态转移方程

dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

• 「动态规划」的「自底向上」求解问题的思路，很多时候是在填写一张二维表格。由于 s[i..j] 表示 s 的一个子串，因此 i 和 j 的关系是 i <= j，只需要填这张表格对角线以上的部分；
• 看到 dp[i + 1][j - 1] 就需要考虑特殊情况：如果去掉 s[i..j] 头尾两个字符子串 s[i + 1..j - 1] 的长度严格小于 2（不构成区间），即 j - 1 - (i + 1) + 1 < 2时，整理得 j - i < 3，此时 s[i..j] 是否是回文只取决于 s[i] 与 s[j] 是否相等。结论也比较直观：j - i < 3等价于 j - i + 1 < 4，即当子串 s[i..j]s[i..j] 的长度等于 2 或者等于 3的时候，s[i..j] 是否是回文由 s[i] 与 s[j] 是否相等决定。

3、初始化

单个字符一定是回文串，因此把对角线先初始化为 true，即 dp[i][i] = true。根据第 2 步的说明：当 s[i..j] 的长度为 22时，只需要判断 s[i] 是否等于 s[j]，所以二维表格对角线上的数值不会被参考。所以不设置 dp[i][i] = true 也能得到正确结论。

4、优化空间

• 一旦得到 dp[i][j] = true，就记录子串的「长度」和「起始位置」。没有必要截取，这是因为截取字符串也有性能消耗。

• 填表应该遵守这样的原则：总是先得到小子串是否是回文的结果，然后大子串才能参考小子串的判断结果，所以填表顺序很重要；

var longestPalindrome = function(s) {
    const length = s.length;
    if(length < 2){
        return s;
    }
    let maxNum = 1;
    let startNum = 0;
    const dp = Array.from(new Array(length), ()=> new Array(length));
    for(let i=0; i< length; i++){
        dp[i][i] = true;
    }
    for(let j=1; j<length; j++){
        for(let i=0; i<j; i++){
            if(s[j] !== s[i]){
                dp[i][j] = false;
            }else{
                if(j-i < 3){
                    dp[i][j] = true;
                }else{
                    dp[i][j] = dp[i+1][j-1];
                }
            }
            if(dp[i][j] && j - i + 1 > maxNum){
                maxNum = j - i + 1;
                startNum = i;
            }
        }
    }

    return s.substr(startNum, maxNum);
}

2、最长连续序列

题目：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    if(nums == null || !Array.isArray(nums) || nums.length < 1){
        return 0
    }
    const length = nums.length;
    let longetStreak = 0;
    let nSets = new Set();
    for(let i=0; i<length; i++){
        nSets.add(nums[i])
    }
    for(const num of nSets){
        if(!nSets.has(num -1)){
            let cNum = num;
            let currentStreak = 1;
            while(nSets.has(cNum + 1)){
                cNum = cNum + 1;
                currentStreak += 1;
            }
            longetStreak = Math.max(longetStreak, currentStreak);
        }
    }
    return longetStreak;
};

3、最长上升子序列

题目：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    if(nums == null || nums.length < 1){
        return 0;
    }
    const length = nums.length;
    let maxLength = 1;
    let dp = new Array();
    dp[0] = 1;
    for(let i=1; i< length; i++){
        dp[i] = 1;
        for(let j=0; j<i; j++){
            if(nums[i] > nums[j]){
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLength = Math.max(maxLength, dp[i]);
    }
    return maxLength;
};