LeetCode(力扣)答案解析（三）

[Checkson]

9. 回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例1：

输入: 121
输出: true

示例2：

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例3：

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

你能不将整数转为字符串来解决这个问题吗？

解法一

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function (x) {
    if (x < 0) return false;
    var t = x, y = 0;
    do {
        y = y * 10 + t % 10;
        t = Math.floor(t / 10);
    } while (t != 0);
    return y === x;
};

这种解法的思路很简单，就是存粹反转数字，看最后反转的结果和原数字对比，是否相等。细心的同学可以看出，这个算法是有优化的空间的：我们只需将数字按中间划分，只要左右反转相等就证明是回文数了，时间复杂度将减半。

解法二（优化）

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function (x) {
    if (x < 0 || (x && x % 10 === 0)) return false;
    var num = 0;
    while (x > num) {
        num = num * 10 + x % 10;
        x = Math.floor(x / 10);
    }
    return x === num || x === Math.floor(num / 10);
};

这个算法的优化，注意点在于在10的倍数的时候需要特殊处理，直接返回false。

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例1：

输入: ["flower","flow","flight"]
输出: "fl"

示例2：

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明：

所有输入只包含小写字母 a-z 。

解法一（暴力法）

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    var ans = '';
    if (strs.length) {
        var str = strs[0], isBreak = false;
        for (var i = 0, len = str.length; i < len; i++) {
           for (var j = 1, len2 = strs.length; j < len2; j++) {
               if (i < strs[j].length && str[i] === strs[j][i]) continue;
               isBreak = true;
               break;
           }
           if (!isBreak) {
               ans += str[i];
               continue;
           }
           break;
        }
    }
    return ans;
};

这里解题思路大致是：以数组strs第一个元素作为字符串模板，然后将它和数组后面字符串进行逐个字符从左到右进行遍历对比，若找到不相同，直接跳出循环；若相同，则记录在ans，直到超出最短的字符串长度或者找到不同的字符。这个算法时间复杂度为O(n*m)，n是strs数组的长度，m是最短字符串的长度。

另外，需要注意的两点是：

• 当传入的strs数组为空时，默认返回""，在这里我们并没有处理，因为ans默认为""。
• 每次字符串间的字符对比，都需要检测遍历的下标是否越界了。若是，直接跳出循环。

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶：

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解法一（暴力法）

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    var front = 0, rear = nums.length - 1;
    var ans = front <= rear ? nums[0] : 0;
    while (front <= rear) {
        var max = rear;
        while (max >= front) {
            var sum = 0;
            for (var i = max; i >= front; i--) {
                sum += nums[i];
            }
            (sum > ans) && (ans = sum);
            max--;
        }
        front++;
    }
    return ans;
};

看完题目后，二话不说，一上来就是用暴力法，头就是铁！然而，提交答案的时候，报超时...... 暴力法的时间复杂度足足是O(n³)，非常恐怖。那么，如果我们换种思路，头不那么铁，动动脑筋，能不能降低时间复杂度呢？

解法二（动态规划）

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    var ans = 0, len = nums.length;
    if (len > 0) {
         ans = nums[0];
         for (var i = 1; i < len; i++) {
             if (nums[i - 1] > 0) nums[i] += nums[i - 1];
             if (ans < nums[i]) ans = nums[i];
         }
    }
    return ans;
};

这个解法运用了动态规划。动态规划是求解最优解的能手。简单来说，我们这里将数组nums中第i个数，记录着这i个数之前的最大子序列和，只要前i-1个数的最大子序列和出现负数，则不相加，因为任何数加上负数，都会越加越小。而这个解法的时间复杂度只为O(n)，性能明显提升了很多。具体请看以下图例：

另外，题目竟然提示了还有更精妙的分治方法。不过我本人认为动态规划的解法才是最精妙的！题目既然明示了分治方法，那么这里我也相应地给出这种解题思路：

解法三（分治算法）

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    return maxSubArrayHelper(nums, 0, nums.length - 1);
};
function maxSubArrayHelper(nums, left, right) {
    if (left >= right) {
        return nums[left];
    }
    var center = parseInt((left + right) / 2);
    var maxLeftSubArray = maxSubArrayHelper(nums, left, center);
    var maxRightSubArray = maxSubArrayHelper(nums, center + 1, right);
    // 求左边界最大子序列和
    var leftSum = 0, maxLeftSum = nums[center];
    for (var i = center; i >= left; i--) {
        leftSum += nums[i];
        leftSum > maxLeftSum && (maxLeftSum = leftSum);
    }
    // 求右边界最大子序列和
    let rightSum = 0, maxRightSum = nums[center + 1];
    for (var i = center + 1; i <= right; i++) {
        rightSum += nums[i];
        rightSum > maxRightSum && (maxRightSum = rightSum);
    }
    // 返回结果
    return Math.max(maxLeftSubArray, maxRightSubArray, maxLeftSum + maxRightSum);
}

分治算法的思想不难理解，就是分而治之，将较复杂的问题，一分为二求解，以此类推。那么这里需要注意的是：

• JavaScript中整数间非整除的运算，最后得到的结果将会是小数，float类型，有一个隐式转换的过程。我们需要借助parseInt方法来将结果强制转化为整数。
• 分治能分别求出左右子序列的最优解，但忽略了中间组合的最优解，这里我们需要利用左右边界较中间位置，额外计算中间部分的最优解。