【JavaScript】LeetCode：21-25

21 最大子数组和

• 贪心 / 动态规划
• 贪心：连续和（count）< 0时，放弃当前起点的连续和，将下一个数作为新起点，这里提供使用贪心算法解决本题的代码。
• 动态规划：dp[i]：以nums[i]为结尾的最长连续子序列（子数组）和。
  dp[i] = max(dp[i - 1] + nums[i], nums[i])。
  初始化：dp[0] = nums[0]。
  结果：dp中的最大值。

/*** @param {number[]} nums* @return {number}*/
var maxSubArray = function(nums) {var res = -Number.MAX_VALUE;var count = 0;for(var i of nums){count += i;if(count > res){res = count;}if(count < 0){count = 0continue;}}return res;
};

22 合并区间

• 贪心
• 将intervals数组的元素按照左端点进行升序排序。
• intervals[i][0]：左边界，intervals[i][0]：右边界。
• 如果intervals[i][0] < intervals[i - 1][1]，当前区间与上一个区间有重叠，此时合并区间，更新右边界 = max(intervals[i - 1][1], intervals[i][1])。否则将当前区间加入结果数组res中。
• 直接在结果数组res中进行更新区间，即intervals[i - 1][1]为res的最后一个元素。

/*** @param {number[][]} intervals* @return {number[][]}*/
var merge = function(intervals) {if(intervals.length == 0){return [];}intervals.sort((a, b) => a[0] - b[0]);var res = [];res.push(intervals[0]);for(var i = 1; i < intervals.length; i++){if(intervals[i][0] <= res[res.length - 1][1]){res[res.length - 1][1] = Math.max(res[res.length - 1][1], intervals[i][1]);}else{res.push(intervals[i]);}}return res;
};

23 轮转数组

• 数组
• 数组切片：nums[-k: ] + nums[: -k]

/*** @param {number[]} nums* @param {number} k* @return {void} Do not return anything, modify nums in-place instead.*/
var rotate = function(nums, k) {var lens = nums.length;var n = new Array(lens);k = k % lens;n = nums.slice(-k, lens).concat(nums.slice(0, -k));for(var i = 0; i < lens; i++){nums[i] = n[i]}
};

24 除自身以外数组的乘积

• 前后缀分解
• 前缀积pre[i]：从nums[0]~nums[i - 1]的乘积，pre[i] = pre[i - 1] * nums[i - 1]。
• 后缀积suf[i]：从nums[i + 1]~nums[lens - 1]的乘积，suf[i] = suf[i + 1] * nums[i + 1]。
• 初始化：pre[0] = suf[lens - 1] = 0。
• 结果：除元素nums[i]外的乘积 = 元素前面所有元素的乘积 * 元素后所有元素的乘积。ans[i] = pre[i] * suf[i]。

/*** @param {number[]} nums* @return {number[]}*/
var productExceptSelf = function(nums) {var lens = nums.length;var pre = new Array(lens);var suf = new Array(lens);pre[0] = 1;suf[lens - 1] = 1;for(var i = 1; i < lens; i++){pre[i] = pre[i - 1] * nums[i - 1];}for(var j = lens - 2; j >= 0; j--){suf[j] = suf[j + 1] * nums[j + 1]}for(var k = 0; k < lens; k++){suf[k] = pre[k] * suf[k];}return suf;
};

25 缺失的第一个正数

• 原地哈希
• 将数组视作哈希表，把1放到下标为0的位置，把2放到下标为1的位置，…，把n（数组长度）放到下标为n - 1的位置，实现数组元素的映射。
• 缺失的数一定为[1, n + 1]之间的数。
• 如果元素i在1~n，判断元素i是否在索引i - 1上，如果不在，则将两数（元素i，在索引i - 1上的元素）进行交换。
• 遍历数组，找到元素i的值不是i + 1的位置，返回i + 1。
• 极端情况：1~n都存在，返回n + 1。

/*** @param {number[]} nums* @return {number}*/
var firstMissingPositive = function(nums) {var lens = nums.length;for(var i = 0; i < lens; i++){while(nums[i] >= 1 && nums[i] <= lens && nums[i] != nums[nums[i] - 1]){var temp = nums[nums[i] - 1];nums[nums[i] - 1] = nums[i];nums[i] = temp;}}for(var j = 0; j < lens; j++){if(nums[j] != j + 1){return j + 1;}}return lens + 1;
};