• 数据结构
  • 图论
    • 最短路径
      • 🟡 2385. 感染二叉树需要的总时间
  • 二叉树
    • 前序遍历
      • 递归
      • 迭代
    • 中序遍历
      • 递归
      • 迭代
    • 后序遍历
      • 递归
      • 迭代
    • 层序遍历
      • 迭代
      • 相关的一些题目
    • 二叉搜索树
    • 二叉平衡树
      • 🟢 LCR 176. 判断是否为平衡二叉树
      • 1382. 将二叉搜索树变平衡
  • 树
  • 链表
    • 双链表
• 算法
  • 双指针
    • 🟢 88. 合并两个有序数组
    • 🟡 15. 三数之和
    • 🟡 19. 删除链表的倒数第 N 个结点
  • 二分查找
    • 🟡 33.搜索旋转排序数组
  • 哈希表
  • 回溯
    • 🟡 22. 括号生成
  • 单调栈
  • djb2 算法
    • 参数 33 的选择
  • 动态规划
    • 🟡 198. 打家劫舍
    • 🟡 300. 最长递增子序列
    • 🟡 221. 最大正方形
    • 🟡 53. 最大子数组和
    • 🟡 309. 买卖股票的最佳时机含冷冻期
    • 🟡 337. 打家劫舍 III
    • 🟡 - 2944. 购买水果需要的最少金币数
  • BFS
    • 🟡 200. 岛屿数量
  • 前缀和
    • 🟡 238. 除自身以外数组的乘积

数据结构

图论

最短路径

🟡 2385. 感染二叉树需要的总时间

先走 深搜 构造无向图 然后从 start 节点开始走 广搜 寻找最短路径

二叉树

前序遍历

🟢 144. 二叉树的前序遍历

前序遍历是一种深度优先搜索的遍历方式, 遍历顺序为 根结点 -> 左子树 -> 右子树 的顺序

示例 1:

example 1

        1
      /   \
    2       3
  /  \     /  \
 4    5   6    7


遍历输出为 [1,2,4,5,3,6,7]

示例 2:

example 2

        1
      /   \
    2       3
   / \
  4   5
 / \
6   7

遍历输出为 [1,2,4,6,7,5,3]

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
function preOrder(root, queue=[]){
  if(!root)return queue;
  queue.push(root.val)
  preOrder(root.left,queue);
  preOrder(root.right,queue);
  return queue;
}

迭代

利用栈先进后出的性质 实现迭代方式遍历

先入栈右子树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
function preOrder(root){
  if(!root)return [];

  const ans = [];
  const stack = [root];
  while (stack.length) {
      const top = stack.pop();
      ans.push(top.val);
      if (top.right) stack.push(top.right);
      if (top.left) stack.push(top.left);
  }

  return ans;
}

中序遍历

🟢 94. 二叉树的中序遍历

中序遍历是一种深度优先搜索的遍历方式, 遍历顺序为 左子树 -> 根结点 -> 右子树

示例 1:

example 1

        1
      /   \
    2       3
  /  \     /  \
 4    5   6    7


遍历输出为 [4,2,5,1,6,3,7]

示例 2:

example 2

        1
      /   \
    2       3
   / \
  4   5
 / \
6   7

遍历输出为 [6,4,7,2,5,1,3]

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root, ans = []) {
    if (!root) return ans;

    inorderTraversal(root.left, ans);
    ans.push(root.val);
    inorderTraversal(root.right, ans);
    return ans;
};

迭代

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
    if (!root) return [];

    const ans = [];
    const stack = [];
    let current = root;

    while (current || stack.length) {
        while (current) {
            stack.push(current);
            current = current.left;
        }

        const top = stack.pop();
        ans.push(top.val);
        current = top.right;
    }

    return ans;
};

后序遍历

🟢 145. 二叉树的后序遍历

后序遍历是一种深度优先搜索的遍历方式, 遍历顺序为 左子树 -> 右子树 -> 根结点

示例 1:

example 1

        1
      /   \
    2       3
  /  \     /  \
 4    5   6    7


遍历输出为 [4,5,2,6,7,3,1]

示例 2:

example 2

        1
      /   \
    2       3
   / \
  4   5
 / \
6   7

遍历输出为 [6,7,4,5,2,3,1]

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root, ans = []) {
    if (!root) return ans;

    postorderTraversal(root.left, ans);
    postorderTraversal(root.right, ans);
    ans.push(root.val);
    return ans;
};

迭代

先按 根节点 -> 右子树 -> 左子树 顺序遍历

然后将结果 逆转

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
    if (!root) return [];

    const stack = [root];
    const ans = [];

    while (stack.length) {
        const top = stack.pop();
        ans.push(top.val);

        if (top.left) stack.push(top.left);
        if (top.right) stack.push(top.right);
    }

    return ans.reverse();
};

层序遍历

🟡 102. 二叉树的层序遍历

层序遍历是一种广度优先搜索的遍历方式, 从根节点开始, 按层访问树的节点

示例 1:

example 1

        1
      /   \
    2       3
  /  \     /  \
 4    5   6    7


遍历输出为 [[1],[2,3],[4,5,6,7]]

示例 2:

example 2

        1
      /   \
    2       3
   / \
  4   5
 / \
6   7

遍历输出为 [[1],[2,3],[4,5],[6,7]]

迭代

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
    if (!root) return [];
    let q = [root];
    const ans = [];
    while (q.length) {
        const size = q.length;
        let current = [];
        ans.push([]);
        for (let i = 0; i < size; i++) {
            const head = q[i];
            ans[ans.length-1].push(head.val);
            if (head.left) current.push(head.left);
            if (head.right) current.push(head.right);
        }
        q = current;
    }
    return ans;
};

相关的一些题目

🟡 1302. 层数最深叶子节点的和

使用 BFS 找出最深一层的节点集合, 然后求和

🟡 2583. 二叉树中的第 K 大层和

使用 BFS 计算每一层的和, 然后排序

二叉搜索树

二叉搜索树（Binary Search Tree, BST）具有以下特性

• 节点左子树中所有节点都小于该节点的值
• 节点右子树中所有节点都大于该节点的值
• 左子树和右子树也分别是二叉搜索树

二叉搜索树 支持高效搜索、插入、删除操作

搜索操作的时间复杂度为 O(log n), n 是树中节点数量

示例 1:

example 1

        8
      /   \
    6       10
  /  \     /  \
 5    7   9    11

🟢 700. 二叉搜索树中的搜索

🟡 95. 不同的二叉搜索树 II

DFS

二叉平衡树

二叉平衡树是一种特殊的二叉搜索树, 在最坏的情况下搜索时间复杂度也是 O(log n)

• 树中每个节点左子树跟右子树高度差不超过 1
• 左子树与右子树也分别是二叉平衡树

示例 1

example 1

        8
      /   \
    6       10
  /  \
 5    7

🟢 LCR 176. 判断是否为平衡二叉树

递归获取左右子树高度差做计算, 同时递归判断左右子树是否也是平衡树

/**
 * Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
 * @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function (root) {
    if (!root) return true;
    return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right)
};

function height(root) {
    if (!root) return 0;

    return Math.max(height(root.left) + 1, height(root.right) + 1);
}

1382. 将二叉搜索树变平衡

通过中序遍历获取升序数组, 然后以中间点为 根 递归生成树

/**
 * Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
 * @param {TreeNode} root
* @return {TreeNode}
*/
var balanceBST = function (root) {
    const arr = [];
    const stack = [];
    let current = root;

    while (current || stack.length) {
        while (current) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        arr.push(current.val);
        current = current.right;
    }

    function build(start, end) {
        if (start > end) return null;
        const mid = start + Math.floor((end - start) / 2);

        const node = new TreeNode(arr[mid]);

        node.left = build(start, mid - 1);
        node.right = build(mid + 1, end);
        return node;
    }

    return build(0, arr.length - 1);
};

树

链表

双链表

• 146. LRU 缓存

构造双链表存储节点, 每新增一个新数添加到头部, 已存在则更新 value 以及移动到头部 构造 map 存储每个链表节点, 方便在 get 时直接取到对应链表节点, 然后做移动到头节点动作

算法

双指针

双指针通过两个指针在数组或链表中移动, 以解决一些特定类型的问题

• 快慢指针: 快指针移动速度快, 慢指针移动速度慢, 常用于解决链表成环检测、链表中点、链表是否相交等问题
• 左右指针: 左右指针分别位于数组两端, 移动左指针、右指针或同时移动, 常用于解决数组或字符串的搜索、反转、滑动窗口等问题
• 对撞指针: 对撞指针指向数组两端, 并向中间移动, 常用于解决需要同时考虑两端情况的问题, 例如有序数组的两数之和、反转数组等

双指针在 优化时间复杂度的问题时非常有用, 通常能在 O(n) 时间复杂度内解决问题, 例如将 O(n²) 降低到 O(n)

🟢 88. 合并两个有序数组

这里因为是原地操作, 通过逆序遍历省去临时数组的使用, 从尾部逐个对比移动 i, j 指针, 实时将对比中较大的数覆盖到 nums1 中

/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function (nums1, m, nums2, n) {
    let i = m - 1, j = n - 1;

    while (i >= 0 || j >= 0) {
        if (i === -1) {
            nums1[i + j + 1] = nums2[j--];
        } else if (j === -1) {
            i--;
        } else if (nums1[i] >= nums2[j]) {
            nums1[i+j+1] = nums1[i--];
        }else {
            nums1[i+j+1] = nums2[j--];
        }
    }
};

🟡 15. 三数之和

暴力解法三重循环 O(n^3) 会超时, 通过排序 + 双指针 优化第二第三重循环, 左指针右指针向中间收拢, 找出和为 0 的组合, 同时去除重复组合

/**
 * @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
    nums = nums.sort((a, b) => a - b);
    const ans = [];

    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let l = i + 1, r = nums.length - 1;
        while (l < r) {
            const sum = nums[l] + nums[r] + nums[i];
            if (sum < 0) {
                while (l < r && nums[l] === nums[++l]);
            } else if (sum > 0) {
                while (l < r && nums[r] === nums[--r]);
            } else {
                ans.push([nums[i], nums[l], nums[r]]);
                while (l < r && nums[l] === nums[++l]);
                while (l < r && nums[r] === nums[--r]);
            }
        }

    }
    return ans;
};

🟡 19. 删除链表的倒数第 N 个结点

设立快慢指针, 让快指针先走 n 步, 然后移动慢指针找到要移除节点的位置, 这里我使用虚拟头节点, 找到要移除节点的前一个节点

/**
 * Definition for singly-linked list.
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function (head, n) {
  let front = (end = res = new ListNode());

  front.next = end.next = head;
  while (n--) {
    front = front.next;
  }

  while (front && front.next) {
    front = front.next;
    end = end.next;
  }

  end.next = end.next.next;
  return res.next;
};

二分查找

🟡 33.搜索旋转排序数组

逻辑梳理有点复杂, 条件判断较多, 核心是利用单调性, 来判断二分继续往左还是往右找, 例如: 如果当前 mid 偏大, 左边是单调递增 则判断左端点是否也偏大, 偏大则向右查找, 否则向左, 其他情况略...

/**
 * @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
    let i = 0, j = nums.length - 1
    let mid
    while (i <= j) {
        mid = Math.floor((j - i) / 2) + i
        if (nums[mid] === target) {
            return mid
        }
        if (nums[mid] > nums[i]) {
            if (nums[mid] > target) {
                if (nums[i] > target) {
                    i = mid + 1
                } else {
                    j = mid - 1
                }
            } else {
                i = mid + 1
            }
        } else if (nums[mid] < nums[i]) {
            if (nums[mid] > target) {
                j = mid - 1
            } else {
                if (nums[j] < target) {
                    j = mid - 1
                } else {
                    i = mid + 1
                }
            }
        } else {
            i = mid + 1
        }
    }
    return -1
};

哈希表

n 数之和

回溯

🟡 22. 括号生成

回溯过程中限制左括号数量小于右括号数量即可

/**
 * @param {number} n
* @return {string[]}
*/
var generateParenthesis = function (n) {
  const ans = [];

  const store = [n, n];

  const dfs = (tmp) => {
    if (!store[0] && !store[1]) {
      ans.push(tmp);
      return;
    }

    if (store[0]) {
      store[0]--;
      dfs(tmp + '(');
      store[0]++;
    }

    if (store[0] < store[1]) {
      store[1]--;
      dfs(tmp + ')');
      store[1]++;
    }
  };
  dfs('');
  return ans;
};

单调栈

djb2 算法

djb2 是一个产生随机分布的的哈希函数

参数 33 的选择

在 DJB2 哈希算法中, 使用乘数 33 作为哈希算法的参数, 是为了利用位运算的性质, 避免乘法运算, 从而提高计算速度和效率

使用乘数 33 的主要原理是：将一个数左移一位, 相当于将这个数乘以 2, 左移 n 位相当于将这个数乘以 2 的 n 次方。而使用位运算的速度远远快于乘法运算, 因此在哈希算法中使用位运算可以显著提高计算速度和效率

同时, 33 作为乘数的选择也是有一定道理的。首先, 33 是一个奇数, 这可以确保在哈希过程中使用的乘数不会与偶数相关的信息发生冲突。其次, 33 可以写成 2 的五次方再加上 1, 即 33=2^5+1。这意味着在哈希过程中, 可以将原始哈希值左移 5 位, 再加上原始哈希值, 相当于将原始哈希值乘以 33, 从而得到更好的哈希值

动态规划

动态规划（英语：Dynamic programming, 简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的, 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法

动态规划适用于有重叠子问题和最优子结构性质的问题, 动态规划方法耗时远少于朴素解法

🟡 198. 打家劫舍

找到 状态转移方程, 打劫第 i 家的收益最大化, 根据条件限制应该为 打劫第 i-2 家的收益加上 第 i 家 跟 打劫第 i-1 家的最大收益做比较, 最后结果返回 dp 的最后一项即可

也就是 dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1])

/**
 * @param {number[]} nums
* @return {number}
*/
var rob = function (nums) {
    const dp = new Array(nums.length + 10).fill(0)
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])

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

    return dp[nums.length - 1]
};

🟡 300. 最长递增子序列

动态规划解法: 状态转移方程 dp[j] = max(dp[i] + 1, dp[j])

/**
 * @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function (nums) {
    const n = nums.length
    const dp = new Array(n).fill(1)

    let ans = 1

    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[j] > nums[i]) {
                dp[j] = Math.max(dp[i] + 1, dp[j])
                if (dp[j] > ans) ans = dp[j]
            }
        }
    }

    return ans
};

二分查找解法: 我们维护一个单调递增的序列 arr, 存储当前最长子序列, 遍历数组元素, 大于 arr 元素则扩充 arr 小于则用二分找到该元素插入点 更新序列 arr, 最终最大长度则是 arr 序列长度

/**
 * @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function (nums) {
    const n = nums.length
    const arr = new Array(n)

    arr[0] = nums[0]

    let len = 0

    for (let i = 1; i < n; i++) {
        if (nums[i] > arr[len]) {
            arr[++len] = nums[i]
        } else {
            let l = 0, r = len, pos = 0

            while (l <= r) {
                let mid = l + Math.floor((r - l) / 2)
                if (arr[mid] >= nums[i]) {
                    r = mid - 1
                    pos = mid
                } else {
                    pos = mid + 1
                    l = mid + 1
                }
            }
            arr[pos] = nums[i]

        }
    }

    return len + 1
};

🟡 221. 最大正方形

dp[i][j] 代表 以 i,j 索引的二维矩阵为右下角的最大边长, 状态转移方程 dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1

当前元素 为 '1' 可根据靠左上角的三个邻近元素去推断当前元素能组成多大的正方形

/**
 * @param {character[][]} matrix
* @return {number}
*/
var maximalSquare = function (matrix) {
    const m = matrix.length
    const n = matrix[0].length

    let edge = 0;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === '1') {
                if (i !== 0 && j !== 0) {
                    matrix[i][j] = Math.min(Math.min(matrix[i - 1][j], matrix[i][j - 1]), matrix[i - 1][j - 1]) + 1
                }
                if (matrix[i][j] > edge) {
                    edge = matrix[i][j]
                }
            }
        }
    }

    return edge * edge
};

🟡 53. 最大子数组和

状态转移方程: dp[i] = max(dp[i-1]+nums[i], nums[i]), 如果 i 之前的最大值 dp[i-1] 加上当前元素还没有 nums[i] 大 那更新 dp[i] 为 nums[i], 也就是抛弃 i 之前的数字, 因为加上它们 结果反而更小了

/**
 * @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(0);
    dp[0] = nums[0];

    let ans = dp[0];

    for(let i=1;i<n;i++){
        dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
        ans = Math.max(ans, dp[i]);
    }

    return ans
};

🟡 309. 买卖股票的最佳时机含冷冻期

含冷冻期的状态稍微复杂些, 在每个索引下有 持有、非持有冷冻期、非持有非冷冻期三种状态, 用 dp[i][0]、dp[i][1]、dp[i][2] 来表示

状态转移方程:

持有状态更新: dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]) 非持有冷冻期状态更新: dp[i][1] = dp[i-1][0] + prices[i] 非持有非冷冻期状态更新: dp[i][2] = max(dp[i-1][1], dp[i-1][2])

/**
 * @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
    const n = prices.length

    const dp = new Array(n)
    for (let i = 0; i < n; i++) {
        dp[i] = new Array(3).fill(0)
    }

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

    return Math.max(dp[n - 1][1], dp[n - 1][2])

🟡 337. 打家劫舍 III

树形 dp, 问题求解最大收益, 分析状态转移方程, 从根节点出发, 每个节点能获取到的最大收益, 分为偷当前节点 checked 和不偷当前节点 unchecked 两种状态

当前 unchecked1 第一种情况为 两个叶子节点 left 和 right checked 最大值之和, unchecked1 = left.checked + right.checked

unchecked2 第二种情况为 两个叶子节点 left 和 right unchecked 最大值之和, unchecked2 = left.unchecked + right.unchecked

最终 unchecked = max(unchecked1, unchecked2)

当前 checked 为 当前节点值与两个叶子节点 left 和 right 的 unchecked 值之和, checked = left.unchecked + right.unchecked + val

另外还需要 使用 贪心 与 unchecked 对比取最大值, 保证当前状态为最优

/**
 * Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
 * @param {TreeNode} root
* @return {number}
*/
var rob = function (root) {
    const dfs = (node) => {
        if (!node) return [0, 0]

        const l = dfs(node.left)
        const r = dfs(node.right)

        const unchecked = Math.max(l[0] + r[0], l[1] + r[1])
        const checked = Math.max(node.val + r[0] + l[0], unchecked)
        return [unchecked, checked]
    }

    const result = dfs(root)

    return Math.max(result[0], result[1])
};

🟡 - 2944. 购买水果需要的最少金币数

动态规划问题, 获取所有水果需要的最少金币可以转化为 获取到 第 i 个水果所需要的最少金币, 用 dp[i]来表示, 这里因为题目条件从 索引 1 开始的

所以我们 dp[1] = prices[0] 起步, dp[2] 在 第一个购买后就能自动获取 dp[2] = dp[1]

分析状态转移方程, 根据题中条件, 获取 第 i 个 所用的最少金币 可以推断的状态转移方程为 可以往前推导

从 i/2 到 i 位置 取索引 j, dp[i] = min(dp[i], prices[j] + dp[j - 1])

比如第 6 个水果, i/2==3, 买第 3, 4, 5 个就可以免费获得 第 6 个, 那我们比较 (prices[3] + d[3]), (prices[4] + d[4]), (prices[5] + d[5]), ((prices[6] + dp[6])) (这里因为 dp 是从 1 开始的, 所以索引跟 prices 索引一致), 得到 dp[7] 的值

最终我们从 2 到 n 依次更新 dp 状态

```Js
/**
 * @param {number[]} prices
 * @return {number}
 */
var minimumCoins = function (prices) {
    const n = prices.length
    const dp = new Array(n + 1).fill(Number.MAX_SAFE_INTEGER)

    dp[1] = prices[0]
    dp[2] = dp[1]

    let ans = Number.MAX_SAFE_INTEGER

    for (let i = 2; i < n; i++) {
        let k = i + 1
        for (let j = Math.ceil(k / 2); j <= k; j++) {
            dp[k] = Math.min(dp[k], prices[j-1] + dp[j - 1])
        }
    }

    return dp[n]
};
```

BFS

广度优先搜索

🟡 200. 岛屿数量

/**
 * @param {character[][]} grid
* @return {number}
*/
var numIslands = function (grid) {
    const m = grid.length, n = grid[0].length

    let ans = 0

    const rects = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    const bfs = (i, j) => {
        grid[i][j] = '0'
        rects.forEach((rect) => {
            i += rect[0]
            j += rect[1]
            if (i >= 0 && j >= 0 && i < m && j < n && grid[i][j] === '1') {
                grid[i][j] = '0'
                bfs(i, j)
            }
            i -= rect[0]
            j -= rect[1]
        })

    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === '0') {
                continue
            }

            ans++
            bfs(i, j)
        }
    }

    return ans
};

前缀和

🟡 238. 除自身以外数组的乘积

预先计算 左、右前缀和, l[i] 代表 i 左边所有数字的乘积, r[i] 代表 i 右边所有数字的乘积

遍历修改 nums[i] = l[i] * r[i], 这里 0 索引和 n-1 索引需要特殊处理, 因为没有 l[0] 和 r[n-1]

/**
 * @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function (nums) {
    const n = nums.length
    const l = new Array(n).fill(1)
    const r = new Array(n).fill(1)

    l[1] = nums[0]
    r[n - 2] = nums[n - 1]
    for (let i = 1; i < n; i++) {
        l[i] = nums[i - 1] * l[i - 1]
    }
    for (let i = n - 2; i >= 0; i--) {
        r[i] = nums[i + 1] * r[i + 1]
    }

    for (let i = 0; i < n; i++) {
        if (i === 0) {
            nums[i] = r[i]
        } else if (i === n - 1) {
            nums[i] = l[i]
        } else {
            nums[i] = l[i] * r[i]
        }
    }

    return nums
};