跳到主要内容

分治

分治算法​

基本思路​

  • 分: 递归将原问题分为多个子问题, 直至达到最小子问题;
  • 治: 从最小子问题, 从下而上合并, 构建原问题解;

分治前提​

  • 问题可以分解;
  • 子问题独立;
  • 子问题解可以合并;

分治和递归​

  • 分治根据实现方式的不同;
  • 分为递归和迭代;

常见应用​

  • 大数乘法;
  • 矩阵乘法;
  • 汉诺塔问题;
  • 二分查找;
  • 归并/快速/桶排序;
  • dfs;

基本模板​

def divide_and_conquer(problems_n):             # problems_n 为问题规模
    if problems_n < d:                          # 当问题规模足够小时, 直接解决该问题
        return solove()                         # 直接求解

    problems_k = divide(problems_n)             # 将问题分解为 k 个相同形式的子问题

    res = [0 for _ in range(k)]                 # res 用来保存 k 个子问题的解
    for problem_k in problems_k:
        res[i] = divide_and_conquer(problem_k)  # 递归的求解 k 个子问题

    ans = merge(res)                            # 合并 k 个子问题的解
    return ans                                  # 返回原问题的解

分治题目​

汉诺塔问题​

题目​
思路​
  • 假设 n 个圆盘;
  • 将顶部 n - 1 个圆盘看作一个整体;
  • 分治步骤;
    • C 为缓冲柱, 将 n-1 从 A 移至 B;
    • 将 A 剩余的 1 从 A 移至 C;
    • A 为缓冲柱, 将 n-1 从 B 移至 C;
  • 终止条件;
    • 当 A 只剩 1 个时, 直接从 A 移至 C;
  • 将 f(n) 问题转换为 2 个 f(n-1) 和 1 个 f(1);
/**
 * @param {number[]} A
 * @param {number[]} B
 * @param {number[]} C
 * @return {void} Do not return anything, modify C in-place instead.
 */
var hanota = function (A, B, C) {
  const dfs = (n, A, B, C) => {
    if (n === 1) {
      C.push(A.pop());
      return;
    }
    dfs(n - 1, A, C, B);
    C.push(A.pop());
    dfs(n - 1, B, A, C);
  };

  dfs(A.length, A, B, C);
};

合并 k 个链表​

题目​
思路​
  • 等同于链表的归并排序;
  • 将单一链表中点的划分, 替换为链表数组的划分;
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  const merge = (l1, l2) => {
    const dummy = new ListNode(-1);
    let cur = dummy;
    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        cur.next = l1;
        l1 = l1.next;
      } else {
        cur.next = l2;
        l2 = l2.next;
      }
      cur = cur.next;
    }
    if (l1) cur.next = l1;
    if (l2) cur.next = l2;

    return dummy.next;
  };

  const mergeK = (lists, left, right) => {
    if (left >= right) return lists[left];
    const mid = Math.floor(left + (right - left) / 2);
    const l1 = mergeK(lists, left, mid);
    const l2 = mergeK(lists, mid + 1, right);
    return merge(l1, l2);
  };

  if (lists.length === 0) return null;
  return mergeK(lists, 0, lists.length - 1);
};
复杂度​
  • 时间: ;
  • 空间: ;

寻找两个正序数组的中位数​

题目​
思路​
  • 当数组长度之和为奇数时, 中位数为数组第 Math.floor((m + n)/2) + 1 个元素;
  • 反之为数组第 Math.floor((m + n)/2) 个元素和数组第 Math.floor((m + n)/2) + 1 个元素的平均数;
  • 所以包含中位数的数组一侧个数恒为 Math.floor((m + n + 1)/2), 记作 k;
  • 此时问题变为如何在两数组中取前 k 小的元素位置;
    • nums1 取 a 个, nums2 取 k - a 个;
    • 取较短元素设置为 nums1;
    • 设置两端指针 left, right 指向 nums1 两端;
    • 取中间位置 mid, 作为 a;
    • 比较 nums1[a] 和 nums2[k-a-1];
      • 如果 nums1[a] < nums2[k-a-1];
        • 说明最多有 a + k - a - 1 = k - 1 个元素比 nums1[a] 小;
        • 故 nums1[a-1] 不可能是第 k 个元素;
        • left = mid + 1;
      • 反之, right = mid;
  • 此时, 可能存在的中位数对应 num1[left-1] 和 nums[k-left-1], 需要判断两者是否存在;
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  if (nums1.length > nums2.length) {
    return findMedianSortedArrays(nums2, nums1);
  }
  const k = Math.floor((nums1.length + nums2.length + 1) / 2);
  let left = 0;
  let right = nums1.length;
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums1[mid] < nums2[k - mid - 1]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  const n = left;
  const m = k - left;
  const v1 = Math.max(
    n <= 0 ? -Infinity : nums1[n - 1],
    m <= 0 ? -Infinity : nums2[m - 1]
  );
  if ((nums1.length + nums2.length) % 2 === 1) return v1;
  const v2 = Math.min(
    n >= nums1.length ? Infinity : nums1[n],
    m >= nums2.length ? Infinity : nums2[m]
  );
  return (v1 + v2) / 2;
};
复杂度​
  • 时间: log(m+n);
  • 空间: 1;

Pow(x,n)​

题目​
思路​
  • 快速幂算法;
    • 如果 n 为偶数, xn=(x2)n//2x^n=(x^2)^{n//2};
    • 反之, xn=x(x2)n//2x^n=x(x^2)^{n//2};
  • 基于分治的思想, 复杂度降低为 logn;
/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  if (n < 0) return myPow(1 / x, -n);
  if (n === 0) return 1;
  if (n % 2 !== 1) return myPow(x * x, Math.floor(n / 2));
  else return x * myPow(x * x, Math.floor(n / 2));
};
复杂度​
  • 时间: logn;
  • 空间: 1;

验证二叉搜索树的后序遍历序列​

题目​
思路​
  • 后序遍历顺序为 "左右根";
  • 将数组最右侧元素左右根节点值, 判断数组左右两者是否符合左侧都小于, 右侧都大于;
    • 若满足, 找到左右分界线位置, 递归子数组;
    • 若不满足, 说明不是二叉搜索树的后序遍历结果;
  • 终止条件: left>=right, 说明当前只有一个节点;
/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyTreeOrder = function (postorder) {
  const dfs = (left, right) => {
    if (left >= right) return true;
    let index = left;
    while (postorder[index] < postorder[right]) index++;
    const mid = index;
    while (postorder[index] > postorder[right]) index++;

    return index === right && dfs(left, mid - 1) && dfs(mid, right - 1);
  };

  return dfs(0, postorder.length - 1);
};
复杂度​
  • 时间: n^2;
  • 空间: n;

回溯算法​

基本思想​
  • 基于穷举和深度优先遍历解决问题;
  • 从某个初始状态出发, 穷举所有可能, 直至找到解或无解;
尝试和回退​
  • 当搜索过程中, 状态无法继续前进;
  • 撤销上一步选择, 回退到之前状态, 尝试其他可能;
剪枝​
  • 根据回溯问题的约束条件;
  • 避免无意义的搜索路径;
模板代码​
  • 定义决策树;
  • 明确终止条件;
  • 翻译代码;
    • 定义回溯函数;
    • 回溯函数主体;
      • 剪枝;
      • 选择元素;
      • 递归搜索;
      • 回退;
    • 明确终止条件;
/* 回溯算法框架 */
function backtrack(state, choices, res) {
  // 判断是否为解
  if (isSolution(state)) {
    // 记录解
    recordSolution(state, res);
    // 不再继续搜索
    return;
  }
  // 遍历所有选择
  for (let choice of choices) {
    // 剪枝: 判断选择是否合法
    if (isValid(state, choice)) {
      // 尝试: 做出选择, 更新状态
      makeChoice(state, choice);
      // 递归搜索
      backtrack(state, choices, res);
      // 回退: 撤销选择, 恢复到之前的状态
      undoChoice(state, choice);
    }
  }
}

回溯算法题目​

子集​

题目​
思路​
  • 对于每个元素, 都有选与不选两个选择;
  • 遍历数组;
    • 当前元素索引为 cur, 遍历 nums[cur+1: -1], 避免选取重复元素;
    • 添加当前路径到 res;
    • 逐个假设其被选择, 递归选择元素, 其为下一次递归的当前元素;
    • 直至到达数组末尾;
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  const backtrack = (res, state, index, nums) => {
    res.push([...state]);
    if (index === nums.length) {
      return;
    }
    for (let i = index; i < nums.length; i++) {
      state.push(nums[i]);
      backtrack(res, state, i + 1, nums);
      state.pop();
    }
  };

  const res = [];
  backtrack(res, [], 0, nums);

  return res;
};
复杂度​
  • 时间: n*2^n;
  • 空间: n;

n 皇后​

题目​
思路​
  • 每一行只能放置一个皇后;
    • 遍历数组一维索引, 逐索引放置;
  • 约束条件;
    • 每一列只能放置一个皇后;
      • 定义长度为 n 的布尔数组 cols, 记录每一列是否有皇后;
    • 同一对角线只能放置一个皇后;
      • 主对角线上的格子 row - col 为恒定值, 范围为 [-n+1, n-1];
      • 次对角线上的格子 row + col 为恒定值, 范围为 [0, 2n-2];
      • 定义 diags 数组, 记录对角线上是否有皇后;
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  const dfs = (row, n, state, res, cols, diags1, diags2) => {
    if (row >= n) {
      res.push(state.map((row) => row.join("")));
      return;
    }
    for (let col = 0; col < n; col++) {
      const diag1 = row - col + n - 1;
      const diag2 = row + col;
      if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
        state[row][col] = "Q";
        cols[col] = diags1[diag1] = diags2[diag2] = true;
        dfs(row + 1, n, state, res, cols, diags1, diags2);
        state[row][col] = ".";
        cols[col] = diags1[diag1] = diags2[diag2] = false;
      }
    }
  };

  const state = Array.from({ length: n }, () => Array(n).fill("."));
  const cols = Array(n).fill(false);
  const diags1 = Array(2 * n - 1).fill(false);
  const diags2 = Array(2 * n - 1).fill(false);
  const res = [];

  dfs(0, n, state, res, cols, diags1, diags2);
  return res;
};
复杂度​
  • 空间: n!;
  • 时间: n^2;

全排列 1​

题目​
思路​
  • 引入布尔数组 selected, selected[i] 记录 nums[i] 是否被选择;
  • 作出选择后, 将对应 selected[i] 赋值为 True;
  • 遍历选择时, 跳过所有为 True 的 selected, 即剪枝;
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const backtrack = (res, state, selected, nums) => {
    if (state.length === nums.length) {
      res.push([...state]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (selected[i]) continue;
      selected[i] = true;
      state.push(nums[i]);
      backtrack(res, state, selected, nums);
      selected[i] = false;
      state.pop();
    }
  };

  const res = [];
  const selected = new Array(nums.length).fill(false);
  backtrack(res, [], selected, nums);

  return res;
};
复杂度​
  • 时间: n*n!;
  • 空间: n;

全排列 2​

题目​
思路​
  • 在全排列的基础上;
  • 判断其上一个元素是否相等且是否访问;
    • 如果相等且未被访问, 跳过;
    • 若存在相邻的两个重复元素;
      • 存在 AB 和 BA 两种顺序, 两者相同;
      • 所以使用 !selected[i - 1] 筛选出其中一种情况, 加不加 ! 都可以;
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  const backtrack = (res, state, selected, nums) => {
    if (state.length >= nums.length) {
      res.push([...state]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (i >= 1 && nums[i] === nums[i - 1] && !selected[i - 1]) continue;
      if (selected[i]) continue;
      state.push(nums[i]);
      selected[i] = true;
      backtrack(res, state, selected, nums);
      state.pop();
      selected[i] = false;
    }
  };

  const res = [];
  const selected = new Array(nums.length).fill(false);
  backtrack(
    res,
    [],
    selected,
    nums.sort((a, b) => a - b)
  );

  return res;
};
复杂度​
  • 时间: n*n!;
  • 空间: n;

组合总和 1​

题目​
思路​
  • 通过 target-=nums[i], 少定义 sum, 也可是不使用, 看你心情;
  • 首先对 nums 进行排序, 当 target < 0 或 target > sum 直接结束循环;
  • 明确所有选择: 对剩余元素进行遍历;
  • 明确终止条件: target === 0/sum 或到达数组末端;
  • 定义回溯函数: backtrack(res, state, index, target, nums);
    • 遍历 [index, -1], 避免重复组合的生成, 实现同一元素的重复选取;
    • target < 0 为剪枝条件;
  • 终止条件;
    • 终止条件: sum > target;
    • 更新结果: target === 0/sum;
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
  const backtrack = (res, state, index, sum, target, nums) => {
    if (sum > target) return;
    if (sum === target) {
      res.push([...state]);
      return;
    }

    for (let i = index; i < nums.length; i++) {
      sum += nums[i];
      if (sum > target) break;
      state.push(nums[i]);
      backtrack(res, state, i, sum, target, nums);
      state.pop();
      sum -= nums[i];
    }
  };

  const res = [];
  candidates.sort((a, b) => a - b);
  backtrack(res, [], 0, 0, target, candidates);

  return res;
};
复杂度​
  • 时间: n * 2^n;
  • 空间: n;

组合总和 2​

题目​
思路​
  • 在组合总和 1 的基础上, 增加剪枝条件;
    • 索引从 i+1 开始, 避免同一元素的重复选取;
    • 遍历 index 时, 判断与上一个元素是否相同, 相同则跳过, 避免重复组合的生成;
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  const backtrack = (res, state, index, sum, target, nums) => {
    if (sum > target) return;
    if (sum === target) {
      res.push([...state]);
      return;
    }

    for (let i = index; i < nums.length; i++) {
      if (sum + nums[i] > target) break;
      if (i > index && nums[i - 1] === nums[i]) continue;
      state.push(nums[i]);
      sum += nums[i];
      backtrack(res, state, i + 1, sum, target, nums);
      state.pop();
      sum -= nums[i];
    }
  };

  const res = [];
  candidates.sort((a, b) => a - b);
  backtrack(res, [], 0, 0, target, candidates);

  return res;
};
复杂度​
  • 时间: n * 2^n;
  • 空间: n;

括号生成​

题目​
思路​
  • 一共 2 * n 个括号;
  • 明确所有选择: 添加 ( 或 );
  • 明确终止条件: 添加 2 * n 个括号;
  • 定义回溯函数: backtrack(state, res, n, symbol);
    • 剪枝;
      • 使用 symbol 表示当前组合是否成对匹配;
        • 添加 (, symbol+=1;
        • 添加 ), symbol-=1;
        • 只有 symbol < n, 才可添加 (;
        • 只有 symbol > 0, 才可添加 );
  • 终止条件;
    • 终止条件: state.length === 2 * n;
    • 添加结果: 终止条件且 symbol === 0;
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const backtrack = (res, state, tag, n) => {
    if (state.length === 2 * n) {
      if (tag === 0) res.push(state.join(""));
      return;
    }
    if (tag > 0) {
      state.push(")");
      backtrack(res, state, tag - 1, n);
      state.pop();
    }
    if (tag < n) {
      state.push("(");
      backtrack(res, state, tag + 1, n);
      state.pop();
    }
  };

  const res = [];
  backtrack(res, [], 0, n);
  return res;
};
复杂度​
  • 时间: 22×nn\frac{2^{2 \times n}}{\sqrt{n}};
  • 空间: n;

复原 ip 地址​

题目​
思路​
  • 通过在字符串种添加三个点生成不同 IP 地址;
  • 明确所有选择: 每个部分有剩余全部元素给出;
  • 终止条件: 分割为 4 部分;
  • 定义回溯函数 trackback(res, state, index, s);
    • index 为剩余元素的起始索引;
  • 书写回溯函数主体;
    • 剪枝;
      • 从剩余元素选择, 即 i in [index: -1];
      • 判断 s[index: i-1] 的值;
        • > 255: 跳过;
        • 存在前导 0, 但并非单个零: 跳过;
  • 终止条件;
    • 终止条件: 路径长度大于 4;
    • 更新状态: 路径长度等于 4, 且位置处于字符串末端;
/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
  const dfs = (res, state, index, s) => {
    if (index >= s.length) {
      if (state.length === 4) res.push(state.join("."));
      return;
    }

    for (let i = index; i < s.length; i++) {
      const sub = s.slice(index, i + 1);
      if (sub[0] === "0" && i !== index) break;
      const num = Number(sub);
      if (sub > 255) break;
      state.push(num);
      dfs(res, state, i + 1, s);
      state.pop();
    }
  };

  const res = [];
  dfs(res, [], 0, s);

  return res;
};
复杂度​
  • 时间: 3^4 * |s|;
  • 空间: |s|;

解数独​

题目​
思路​
  • 原理类似 n 皇后;
  • 遍历棋盘格子, 对于每个格子, 遍历 1- 9, 判断同行, 同列, 9 宫格是否重复;
    • 如果 val 有效, 立刻返回 true, 如果遍历 1 - 9 均无效, 返回 false;
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
  const isValid = (row, col, val, board) => {
    for (let i = 0; i < 9; i++) {
      if (val === board[row][i] || val === board[i][col]) return false;
    }

    const startRow = Math.floor(row / 3) * 3;
    const startCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (val === board[startRow + i][startCol + j]) return false;
      }
    }
    return true;
  };

  const backtrack = (board) => {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] !== ".") continue;
        for (let k = 1; k < 10; k++) {
          if (!isValid(i, j, String(k), board)) continue;
          board[i][j] = String(k);
          const res = backtrack(board);
          if (res === true) return true;
          board[i][j] = ".";
        }
        return false;
      }
    }
    return true;
  };

  backtrack(board);
};
复杂度​
  • 时间: 9^m;
  • 空间: 9^2;

单词搜索​

题目​
思路​
  • 明确所有选择: 向四个方向移动;
  • 确定终止条件: 单词不匹配或者遍历完单词;
  • 确定递归函数: backtrack(col, row, visited, wordIndex, word);
    • 判断当前矩阵元素是否匹配单词当前字符;
    • 定义已访问节点 visited;
    • 遍历四个方向;
    • 剪枝;
      • 超过矩阵索引范围;
      • 当前节点已经被访问;
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  const dirctionList = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  const rows = board.length;
  const cols = board[0].length;

  const backtrack = (row, col, visited, index, word, board) => {
    if (index === word.length - 1) return word[index] === board[row][col];

    if (word[index] === board[row][col]) {
      visited[row][col] = true;
      for (const [dx, dy] of dirctionList) {
        const curCol = col + dx;
        const curRow = row + dy;
        if (
          curCol < 0 ||
          curCol >= cols ||
          curRow < 0 ||
          curRow >= rows ||
          visited[curRow][curCol]
        )
          continue;
        const res = backtrack(curRow, curCol, visited, index + 1, word, board);
        if (res) return true;
      }
      visited[row][col] = false;
    }

    return false;
  };

  const visited = Array.from(
    {
      length: rows,
    },
    () => new Array(cols).fill(false)
  );
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      const res = backtrack(i, j, visited, 0, word, board);
      if (res) return true;
    }
  }

  return false;
};
复杂度​
  • 时间: mn*2^l;
  • 空间: mn;

贪心算法​

概述​

  • 分步解决算法;
  • 解决问题的每个决策阶段, 选择当前的最优解;
  • 贪心作出局部最优, 期望获得全局最优;

特征​

  • 贪心选择性质: 全局最优解可通过局部最优解得到;
  • 最优子结构: 问题最优解包括子问题最优解;

解题思路​

  • 转换为贪心问题: 作出当前选择, 再解决剩余子问题; ;
  • 贪心选择性质: 选择当前最优解;
  • 最优子结构性质: 根据局部最优解构造全局最优解;

贪心题目​

买卖股票的最佳时机 1​

题目​
思路​
  • 贪心问题: 递推得到当天的最低成本和最大利润;
  • 贪心选择性质;
    • 对当天价格进行比较, 更新最低成本;
    • 计算当天的最大理论
  • 最优子结构: 全局最大利润;
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let min = prices[0];
  let max = 0;

  for (let i = 1; i < prices.length; i++) {
    min = Math.min(min, prices[i]);
    max = Math.max(max, prices[i] - min);
  }

  return max;
};
复杂度​
  • 时间: n;
  • 空间: 1;

买卖股票的最佳时机 2​

题目​
思路​
  • 贪心问题: 决定当天是否买卖股票, 然后进行下一次选择;
  • 贪心选择性质;
    • 赚钱就买卖, 反之不买卖;
    • 即判断当天和前一天的差值;
  • 最优子结构;
    • 利润累加;
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let res = 0;
  for (let i = 1; i < prices.length; i++) {
    res += Math.max(0, prices[i] - prices[i - 1]);
  }
  return res;
};
复杂度​
  • 时间: n;
  • 空间: 1;

跳跃游戏 2​

题目​
思路​
  • 贪心问题: 根据当前可以到达的最大位置, 判断当前位置, 是否更新最小方案数 res 和最大位置 pos;
  • 贪心选择性质;
    • 遍历当前位置;
    • 实时维护最大距离 dis;
    • 如果当前位置为最大位置 pos, 更新 res 和 pos;
  • 最优子结构;
    • 返回 res;
/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
  let res = 0;
  let pos = 0;
  let dis = 0;
  for (let i = 0; i < nums.length; i++) {
    if (pos >= nums.length - 1) break;
    dis = Math.max(dis, i + nums[i]);
    if (pos === i) {
      pos = dis;
      res++;
    }
  }

  return res;
};
复杂度​
  • 时间: n;
  • 空间: 1;

移掉 k 位数字​

题目​
思路​
  • 基于单调栈和贪心;
  • 贪心问题: 结果更有 n-k 位, 希望高位数字越小越好;
  • 贪心选择性质;
    • 使用最小栈遍历数组, 保证高位数字最小;
    • 如果遍历数组后, 仍未移除 k 个, 手动移除栈顶元素至 k 个;
    • 注意处理前导 0;
  • 最优子结构;
    • 返回 stack, 如果栈为空返回 0;
/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function (num, k) {
  const minStack = [];
  for (const ch of num) {
    while (
      k > 0 &&
      minStack.length !== 0 &&
      ch < minStack[minStack.length - 1]
    ) {
      minStack.pop();
      k--;
    }
    if (ch !== "0" || minStack.length !== 0) minStack.push(ch);
  }

  while (k > 0) {
    minStack.pop();
    k--;
  }

  return minStack.length === 0 ? "0" : minStack.join("");
};
复杂度​
  • 时间: n;
  • 空间: n;

分发糖果​

题目​
思路​
  • 贪心问题;
    • 每个孩子至少有一个, 即糖果数目至少为 n;
    • 分高孩子比两侧孩子糖果多;
      • ratings[i-1] < ratings[i], res[i-1] < res[i];
      • ratings[i] > ratings[i+1], res[i] > res[i+1];
  • 贪心选择性质;
    • 定义长度为 n 的数组, 初始化为 1;
    • 遍历两次数组, 分别满足两侧大小的对应条件;
      • 正序遍历, 满足左规则: ratings[i-1] < ratings[i], res[i]=res[i-1]+1;
      • 倒序遍历, 满足右规则: ratings[i] > ratings[i+1], res[i]=max(res[i], res[i+1]+1);
        • 和右侧进行比较, 所有优先计算右侧, 故倒序遍历;
  • 最优子结构;
    • 返回 res 的总和;
/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function (ratings) {
  const n = ratings.length;
  const res = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) res[i] = res[i - 1] + 1;
  }
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) res[i] = Math.max(res[i], res[i + 1] + 1);
  }

  return res.reduce((a, b) => a + b, 0);
};
复杂度​
  • 时间: n;
  • 空间: n;

加油站​

题目​
思路​
  • 计算所有加油站能够提供的油量和汽车消耗量;
    • 如果油量大于消耗量, 必能行驶一周;
      • 可以将加油和消耗看作 [+, -, ..., +, +] 的数组;
      • 如果 + 对应数值总和大于 - 对应数值总和;
      • 总能找到多个子数组的组合, 使得每个子数组总和都大于 0;
  • 不考虑油量为负的情况, 从 start 出发, 计算两者差值 diff 和汽车剩余油量 min;
  • 如果 min<0, 则说明不能 start 在出发环行一周, start = i+1, min = 0;
  • 如果 diff < 0 必不能环形一周;
  • 反之返回 start;
/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function (gas, cost) {
  let diff = 0;
  let min = 0;
  let start = 0;
  for (let i = 0; i < gas.length; i++) {
    diff += gas[i] - cost[i];
    min += gas[i] - cost[i];
    if (min < 0) {
      start = i + 1;
      min = 0;
    }
  }
  if (diff < 0) return -1;
  return start;
};
复杂度​
  • 时间: ;
  • 空间: ;