【JavaScript】LeetCode：6-10

文章目录

• 6 轮转数组
• 7 买卖股票的最佳时机Ⅰ
• 8 买卖股票的最佳时机Ⅱ
• 9 两数之和
• 10 字母异位词分组

6 轮转数组

• 数组
• 题目要求最终结果返回nums。
• 方法1：拼接数组，n = nums.concat(nums);。
• 方法2：数组直接截取，这里提供方法2的代码。

/**
 * @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]
    }
};

7 买卖股票的最佳时机Ⅰ

• 动态规划
• dp[i][0]：第i天持有股票的最大利润，dp[i][1]：第i天不持有股票的最大利润。
• dp[i][0] = max(dp[i - 1][0], -prices[i])
  dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
• 初始化
  dp[0][0] = -prices[0]，第0天持有股票的最大利润。
  dp[0][1] =0，第0天不持有股票的最大利润。
• 结果：max(dp[len - 1][0], dp[len - 1][1])

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    const len = prices.length;
    const dp = new Array(len).fill([0, 0]);
    dp[0] = [-prices[0], 0];
    for(var i = 1; i < len; i++){
        dp[i] = [
            Math.max(dp[i - 1][0], -prices[i]),
            Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i])
        ];
    }
    return Math.max(dp[len - 1][0], dp[len - 1][1]);
};

8 买卖股票的最佳时机Ⅱ

• 动态规划
• 可买卖多次。
• dp[i][0]：第i天持有股票的最大利润，dp[i][1]：第i天不持有股票的最大利润。
• dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])（与Ⅰ不同）
  dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])（与Ⅰ相同）
• 初始化和结果同Ⅰ。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    const len = prices.length;
    const dp = new Array(len).fill([0, 0]);
    dp[0] = [-prices[0], 0];
    for(var i = 1; i < len; i++){
        dp[i] = [
            Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]),
            Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i])
        ];
    }
    return Math.max(dp[len - 1][0], dp[len - 1][1]);
};

9 两数之和

• Map
• Map(遍历的元素，对应的索引)。
• 遍历数组中的元素x，在Map中查询target - x，若存在则返回，不存在则继续遍历。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var map = new Map();
    for(var i = 0; i < nums.length; i++){
        var x = target - nums[i];
        if(map.has(x)){
            return [map.get(x), i];
        }else{
            map.set(nums[i], i);
        }
    }
};

10 字母异位词分组

• Map
• 字母相同，但排列不同的字符串，排序后一定是相同的。
• 将排序之后的字符串作为Map的键。

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    var map = new Map();
    for(var str of strs){
        var str_arr = Array.from(str);
        var key = str_arr.sort();
        key = key.toString();
        var list = map.get(key);
        if(list){
            list.push(str);
        }else{
            list = [];
            list.push(str);
        }
        map.set(key, list);
    }
    return Array.from(map.values());
};