geekhyt / javascript-leetcode Goto Github PK

const threeSum = function(nums) {
    const result = []
    const len = nums.length
    if (len < 3) {
        return result
    }
    nums.sort((a, b) => a - b)
    for (let i = 0; i < len - 2; i++) {
        if (nums[i] > 0) {
            break
        }
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue
        }
        let L = i + 1
        let R = len - 1
        while (L < R) {
            let sum = nums[i] + nums[L] + nums[R]
            if (sum === 0) {
                result.push([nums[i], nums[L], nums[R]])
                while(nums[L] === nums[L + 1]){
                    L++
                }
                while(nums[R] === nums[R - 1]){
                    R--
                }
                L++
                R--
            } else if (sum < 0) {
                L++
            } else {
                R--
            }
        }
    }
    return result
}

const isValid = function(s) {
    // 奇数个括号或右括号开头的情况无效
    if (s.length % 2 !== 0 || [')', ']', '}'].indexOf(s[0]) !== -1) return false
    const map = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    const stack = []
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(' || s[i] === '{' || s[i] === '[') {
            stack.push(s[i])
        } else if(s[i] !== map[stack.pop()]){
            return false
        }
    }
    return stack.length === 0
}

const heapSort = function(arr) {
    buildHeap(arr, arr.length - 1)
    let heapSize = arr.length - 1 // 初始化堆的有效序列长度
    for (let i = arr.length - 1; i > 1; i--) {
        swap(arr, 1, i) // 交换堆顶元素与最后一个有效子元素
        heapSize-- // 有效序列长度减 1
        heapify(arr, heapSize, 1) // 堆化有效序列
    }
    return arr
}

// 构建大顶堆
const buildHeap = function(items, heapSize) {
    // 从后往前并不是从序列的最后一个元素开始，而是从最后一个非叶子节点开始，这是因为，叶子节点没有子节点，不需要自上而下式堆化。
    // 最后一个子节点的父节点为 n/2 ，所以从 n/2 位置节点开始堆化
    for (let i = Math.floor(heapSize / 2); i >= 1; i--) {
        heapify(items, heapSize, i)
    }
}
// 堆化
const heapify = function(arr, heapSize, i) {
    while (true) {
        let maxIndex = i
        if (2 * i <= heapSize && arr[i] < arr[i * 2]) {
            maxIndex = i * 2
        }
        if (2 * i + 1 <= heapSize && arr[maxIndex] < arr[i * 2 + 1]) {
            maxIndex = i * 2 + 1
        }
        if (maxIndex === i) break
        swap(arr, i, maxIndex)
        i = maxIndex
    }
}

// 交换工具函数
const swap = function(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

const climbStairs = function(n) {
    const dp = []
    dp[0] = 1
    dp[1] = 1
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

const climbStairs = function(n) {
    let a1 = 1
    let a2 = 1
    for (let i = 2; i <= n; i++) {
        [a1, a2] = [a2, a1 + a2]
    }
    return a2
}

const selectSort = function(arr) {
    const len = arr.length
    let temp, minIndex
    for (let i = 0; i < len - 1; i++) {
        minIndex = i
        for (let j = i + 1; j < len; j++) {
            if (arr[j] <= arr[minIndex]) {
                minIndex = j
            }
        }
        temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    }
    return arr
}

const longestValidParentheses = function(s) {
  let res = 0
  const len = s.length
  const dp = new Array(len).fill(0)
  for (let i = 1; i < len; i++) {
    if (s[i] == ')') {
      if (s[i - 1] == '(') {
        if (i - 2 >= 0) {
          dp[i] = dp[i - 2] + 2
        } else {
          dp[i] = 2
        }
      } else if (s[i - dp[i - 1] - 1] == '(') {
        if (i - dp[i - 1] - 2 >= 0) {
          dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
        } else {
          dp[i] = dp[i - 1] + 2
        }
      }
    }
    res = Math.max(res, dp[i])
  }
  return res
}

const rob = function(nums) {
    const n = nums.length
    if (n === 0) return 0
    const dp = new Array(n)
    dp[0] = 0
    dp[1] = nums[0]
    for (let i = 2; i <= n; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1])
    }
    return dp[n]
}

const rob = function(nums) {
    const n = nums.length
    if (n === 0) return 0
    let prev = 0
    let curr = 0
    for (let i = 0; i < n; i++) {
        let tmp = curr
        curr = Math.max(curr, prev + nums[i])
        prev = tmp
    }
    return curr
}

const inorderTraversal = function(root) {
    const result = [];
    function pushRoot(root) {
        if (root !== null) {
            if (root.left !== null) {
                pushRoot(root.left);
            }
            result.push(root.val);
            if (root.right !== null) { 
                pushRoot(root.right);
            }
        }
    }
    pushRoot(root);
    return result;
};

const removeDuplicates = function(nums) {
    const n = nums.length
    let i = 0
    if (n === 0) return 0
    for (let j = 1; j < n; j++) {
        if (nums[j] !== nums[j - 1]) {
            i++
            nums[i] = nums[j]
        }
    }
    return i + 1
}

const lemonadeChange = function(bills) {
    let five = 0, ten = 0
    const len = bills.length
    for (let i = 0; i < len; i++) {
        if (bills[i] == 5) {
            five++
        } else if (bills[i] == 10) {
            if (five == 0) {
                return false
            }
            five--
            ten++
        } else if (bills[i] == 20) {
            if (ten > 0 && five > 0) {
                ten--
                five--
            } else if (five >= 3) {
                five -= 3
            } else {
                return false
            }
        }
    }
    return true
}

const combinationSum = (candidates, target) => {
    const res = []
    // start: 起点索引 arr: 当前集合 cur: 当前所求之和
    const dfs = (start, arr, cur) => {
        if (cur > target) return
        if (cur === target) {
            res.push(arr.slice())
            return
        }
        for (let i = start; i < candidates.length; i++) {
            arr.push(candidates[i])
            dfs(i, arr, cur + candidates[i])
            arr.pop()
        }
    }
    dfs(0, [], 0)
    return res
}

const twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === target - nums[j]) {
                return [i, j]
            }
        }
    }
}

const twoSum = function(nums, target) {
    const map = new Map()
    for (let i = 0; i < nums.length; i++) {
        const diff = target - nums[i]
        if (map.has(diff)) {
            return [map.get(diff), i]
        }
        map.set(nums[i], i)
    }
}

const MinStack = function() {
    this.stack = [];
    this.resStack = [Infinity];
};

MinStack.prototype.push = function(x) {
    this.stack.push(x);
    this.resStack.push(Math.min(this.resStack[this.resStack.length - 1], x));
};

MinStack.prototype.pop = function() {
    this.stack.pop();
    this.resStack.pop();
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

MinStack.prototype.getMin = function() {
    return this.resStack[this.resStack.length - 1];
};

const maxArea = function(height) {
    let max = 0 // 最大容纳水量
    for (let i = 0; i < height.length; i++) {
        for (let j = i + 1; j < height.length; j++) {
            // 当前容纳水量
            let cur = (j - i) * Math.min(height[i], height[j])
            if (cur > max) {
                max = cur
            }
        }
    }
    return max
}

const maxArea = function(height) {
    let max = 0 // 最大容纳水量
    let left = 0 // 左指针
    let right = height.length - 1 // 右指针
    
    while (left < right) {
        // 当前容纳水量
        let cur = (right - left) * Math.min(height[left], height[right]);
        max = Math.max(cur, max)
        height[left] < height[right] ? left ++ : right --
    }

    return max
};

const largestRectangleArea = function(heights) {
  let maxArea = 0
  let len = heights.length
  for (let i = 0; i < len; i++) {
    let minHeight = heights[i]
    for (let j = i; j < len; j++) {
      minHeight = Math.min(minHeight, heights[j])
      maxArea = Math.max(maxArea, minHeight * (j - i + 1))
    }
  }
}

const largestRectangleArea = function(heights) {
  let maxArea = 0
  let len = heights.length
  for (let i = 0; i < len; i++) {
    let left = i
    let right = i
    while (left >= 0 && heights[left] >= heights[i]) {
      left--
    }
    while (right < len && heights[right] >= heights[i]) {
      right++
    }
    maxArea = Math.max(maxArea, (right - left - 1) * heights[i])
  }
  return maxArea
}

const largestRectangleArea = function(heights) {
  let maxArea = 0
  let stack = []
  heights.push(0)
  heights.unshift(0)
  // heights = [0, ...heights, 0] 你也可以这样写
  for (let i = 0; i < heights.length; i++) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {
      maxArea = Math.max(maxArea, heights[stack.pop()] * (i - stack[stack.length - 1] - 1))
    }
    stack.push(i)
  }
  return maxArea
}

const mergeSort = function(arr) {
    const merge = (right, left) => {
    const result = []
    let i = 0, j = 0
    while (i < left.length && j < right.length) {
      if (left[i] < right[j]) {
        result.push(left[i++])
      } else {
        result.push(right[j++])
      }
    }
    while (i < left.length) {
      result.push(left[i++])
    }
    while (j < right.length) {
      result.push(right[j++])
    }
    return result
    }
    const sort = (arr) => {
        if (arr.length === 1) { return arr }
        const mid = Math.floor(arr.length / 2)
        const left = arr.slice(0, mid)
        const right = arr.slice(mid, arr.length)
        return merge(mergeSort(left), mergeSort(right))
    }
    return sort(arr)
}

const letterCombinations = function (digits) {
    if (!digits) {
        return []
    }
    const len = digits.length
    const map = new Map()
    map.set('2', 'abc')
    map.set('3', 'def')
    map.set('4', 'ghi')
    map.set('5', 'jkl')
    map.set('6', 'mno')
    map.set('7', 'pqrs')
    map.set('8', 'tuv')
    map.set('9', 'wxyz')
    const result = []

    function generate(i, str) {
        if (i === len) {
            result.push(str)
            return
        }
        const tmp = map.get(digits[i])
        for (let r = 0; r < tmp.length; r++) {
            generate(i + 1, str + tmp[r])
        }
    }
    generate(0, '')
    return result
}

const insertSort = function(arr) {
    const len = arr.length
    let curr, prev
    for (let i = 1; i < len; i++) {
        curr = arr[i]
        prev = i - 1
        while (prev >= 0 && arr[prev] > curr) {
            arr[prev + 1] = arr[prev]
            prev--
        }
        arr[prev + 1] = curr
    }
    return arr
}

const longestPalindrome = function (s) {
    const len = s.length
    const dp = Array.from(new Array(len), () => new Array(len).fill(0))
    let res = ''
    for (let i = len - 1; i >= 0; i--) {
        for (let j = i; j < len; j++) {
            dp[i][j] = s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1])
            if (dp[i][j] && j - i + 1 > res.length) { // 符合条件时截取得到最长的回文串
                res = s.slice(i, j + 1)
            }
        }
    }
    return res
}

const reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr !== null) {
        // 记录 next 节点
        let next = curr.next;
        // 反转指针
        curr.next = prev;
        // 推进指针
        prev = curr;
        curr = next;
    }
    // 返回翻转后的头节点
    return prev;
};

const reverseList = function(head) {
    if (!head || !head.next) return head;
    // 记录当前节点的下一个节点
    let next = head.next;
    let reverseHead = reverseList(next);
    // 操作指针进行反转
    head.next = null;
    next.next = head;
    return reverseHead;
};

const mergeTwoLists = function (l1, l2) {
    if (l1 === null) {
        return l2
    }
    if (l2 === null) {
        return l1
    }
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    } else {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    }
}

const invertTree = function(root) {
    if (root === null) return null // 递归终止条件
    invertTree(root.left)
    invertTree(root.right)
    const temp = root.left
    root.left = root.right
    root.right = temp
    return root
}

const invertTree = function(root) {
    if (root === null) return null // 递归终止条件
    const temp = root.left
    root.left = root.right
    root.right = temp
    invertTree(root.left)
    invertTree(root.right)
    return root
}

const invertTree = (root) => {
  if (root === null) return null;
  const queue = [root];
  while (queue.length) {
    const cur = queue.shift();
    [cur.left, cur.right] = [cur.right, cur.left];
    if (cur.left) queue.push(cur.left);
    if (cur.right) queue.push(cur.right);
  }
  return root;
}

const plusOne = function(digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
        if (digits[i] === 9) {
            digits[i] = 0
        } else {
            digits[i]++
            return digits
        }
    }
    digits.unshift(1)
    return digits
};

const reverseString = function(s) {
    s.reverse()
}

const reverseString = function (s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        [s[left], s[right]] = [s[right], s[left]]
        left++
        right--
    }
}

const moveZeroes = function (nums) {
    let i = 0, j = 0;
    while (i < nums.length) {
        if (nums[i] != 0) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
            j++;
        } else {
            i++;
        }
    }
}

dp[i][k][0]
dp[i][k][1]

// 举个🌰
dp[2][2][1] // 今天是第 2 天，手中持有股票，最多还可以进行 2 次交易

// 今天手中没有持有股票，有两种可能：
// 1. 昨天没有持有，今天选择不操作。 对应: dp[i - 1][k][0]
// 2. 昨天持有，今天卖出了，所以今天没有股票了。对应: dp[i - 1][k][1] + prices[i]
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])


// 今天手中持有股票，有两种可能：
// 1. 昨天手中持有股票，今天选择不操作。对应: dp[i - 1][k][1]
// 2. 昨天没有持有股票，今天买入了。对应: dp[i - 1][k - 1][0] - prices[i]
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
            = Math.max(dp[i - 1][1][1], -prices[i])
// k = 0 时，dp[i - 1][0][0] = 0

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], -prices[i])

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        dp[i][1] = Math.max(dp[i - 1][1], -prices[i])
    }
    return dp[n - 1][0]
}

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {
        dp[0] = Math.max(dp[0], dp[1] + prices[i])
        dp[1] = Math.max(dp[1], -prices[i])
    }
    return dp[0]
}

const maxProfit = function(prices) {
    let n = prices.length
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < n; i++) {
        profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in,  -prices[i])
    }
    return profit_out
}

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
            = Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0][0] = 0 
    dp[0][1] = -prices[0]
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
    }
    return dp[n - 1][0]
}

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {
        let tmp = dp[0] // 中间变量可省略，因为当天买入卖出不影响结果
        dp[0] = Math.max(dp[0], dp[1] + prices[i])
        dp[1] = Math.max(dp[1], tmp - prices[i])
    }
    return dp[0]
}

const maxProfit = function(prices) {
    let n = prices.length
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < n; i++) {
        profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in, profit_out - prices[i])
    }
    return profit_out
}

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

for (let i = 0; i < n; i++) {
    for (let k = maxK; k >= 1; k--) {
        dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
        dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
    }
}

dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])
dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
            = Math.max(dp[i - 1][1][1], -prices[i])

const maxProfit = function(prices) {
    let n = prices.length
    let dp_i10 = 0
    let dp_i11 = -prices[0]
    let dp_i20 = 0
    let dp_i21 = -prices[0]
    for (let i = 1; i < n; i++) {
        dp_i20 = Math.max(dp_i20, dp_i21 + prices[i])
        dp_i21 = Math.max(dp_i21, dp_i10 - prices[i])
        dp_i10 = Math.max(dp_i10, dp_i11 + prices[i])
        dp_i11 = Math.max(dp_i11, -prices[i])
    }
    return dp_i20
}

const maxProfit = function(prices) {
    let profit_1_in = -prices[0], profit_1_out = 0
    let profit_2_in = -prices[0], profit_2_out = 0
    let n = prices.length
    for (let i = 1; i < n; i++) {
        profit_2_out = Math.max(profit_2_out, profit_2_in + prices[i])
        profit_2_in = Math.max(profit_2_in, profit_1_out - prices[i])
        profit_1_out = Math.max(profit_1_out, profit_1_in + prices[i])
        profit_1_in = Math.max(profit_1_in, -prices[i])
    }
    return profit_2_out
}

const maxProfit = function(k, prices) {
    let n = prices.length
    const maxProfit2 = function(prices) {
        let profit_out = 0
        let profit_in = -prices[0]
        for (let i = 1; i < n; i++) {
            profit_out = Math.max(profit_out, profit_in + prices[i])
            profit_in = Math.max(profit_in, profit_out - prices[i])
        }
        return profit_out
    }
    if (k > n / 2) {
        return maxProfit2(prices)
    }
    let profit = new Array(k)
    // 初始化买入卖出时的利润，将每次交易买入、卖出时的利润放在一个对象中，实现降维
    for (let j = 0; j <= k; j++) {
        profit[j] = {
            profit_in: -prices[0],
            profit_out: 0
        }
    }
    for (let i = 0; i < n; i++) {
        for (let j = 1; j <= k; j++) {
            profit[j] = {
                profit_out: Math.max(profit[j].profit_out, profit[j].profit_in + prices[i]), 
                profit_in: Math.max(profit[j].profit_in, profit[j-1].profit_out - prices[i])
            }
        }
    }
    return profit[k].profit_out
}

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - prices[i])
            = Math.max(dp[i - 1][k][1], dp[i - 2][k][0] - prices[i])

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i])

const maxProfit = function(prices) {
    let n = prices.length
    let dp_i0 = 0
    let dp_i1 = -prices[0];
    let dp_pre = 0 // 代表 dp[i-2][0]
    for (let i = 0; i < n; i++) {
        let tmp = dp_i0
        dp_i0 = Math.max(dp_i0, dp_i1 + prices[i])
        dp_i1 = Math.max(dp_i1, dp_pre - prices[i])
        dp_pre = tmp
    }
    return dp_i0
}

const maxProfit = function(prices) {
    let n = prices.length
    let profit_in = -prices[0]
    let profit_out = 0
    let profit_freeze = 0
    for (let i = 1; i < n; i++) {
        let temp = profit_out
        profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in, profit_freeze - prices[i])
        profit_freeze = temp
    }
    return profit_out
}

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] - fee)

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

const maxProfit = function(prices, fee) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {
        let tmp = dp[0]
        dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee)
        dp[1] = Math.max(dp[1], tmp - prices[i])
    }
    return dp[0]
}

const maxProfit = function(prices, fee) {
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < prices.length; i++) {
        profit_out = Math.max(profit_out, profit_in + prices[i] - fee)
        profit_in = Math.max(profit_in, profit_out - prices[i])
    }
    return profit_out
}

const middleNode = function(head) {
    let fast = head, slow = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

const camJump = function(nums) {
    let canJumpMax = 0
    let len = nums.length
    for (let i = 0; i < len; i++) {
        if (i > canJumpMax) {
            return false
        }
        canJumpMax = Math.max(canJumpMax, i + nums[i])
    }
    return true
}