一些经典算法

    /*
     * 翻转二叉树 226
     *      4              4
     *    /   \          /   \
     *   2     7        7     2
     *  / \   / \      / \   / \
     * 9   6 3   1    1   3 6   9
     * 先翻转左右子树，再将子树换个位置
     * 符合“分、解、合”的步骤
     * 分：获取左右子树
     * 解：递归地翻转左右子树
     * 合：将反转后的左右子树换个位置放到根结点上
     * 时间复杂度为 O(N) N 为树的节点数量
     * 空间复杂度为 O(N) N 最小为树的高度，最大为树的节点数量
     */
    var invertTree = function(root) {
        if (!root) return null
        return {
            val: root.val
            left: invertTree(root.right),
            right: invertTree(root.left)
        }
    }

/*
 * 相同的树 100
 * 给定两个二叉树，编写一个函数来检验是它们是否相同
 * 两棵树：根结点的值相同，左子树相同，右子树相同
 * 分：分别获取两棵树的左子树和右子树
 * 解：递归地判断两个树的左子树是否相同，右子树是否相同
 * 合：将上述结果合并，如果根结点的值也相同，树就相同
 * 时间复杂度为 O(N) N 为树的节点数
 * 空间复杂度为 O(N) N 在最复杂的情况下为树的节点数，最好的情况下为 O(logN)
 */
var isSameTree = function (p, q) {
  if (!p && !q) return true;
  if (
    p &&
    q &&
    p.val === q.val &&
    isSameTree(p.left, q.left) &&
    isSameTree(p.right, q.right)
  ) {
    return true;
  }
  return false;
};

/*
 * 对称二叉树 101
 * 给定一个二叉树，检查它是否是镜像对称的
 * 转化为：左右子树是否镜像
 * 分解为：树1的左子树和树2的右子树是否镜像，树1的右子树和树2的左子树是否镜像
 */
var isSymetric = function (root) {
  if (!root) return true;
  const isMirror = (l, r) => {
    if (!l && !r) return true;
    if (
      l &&
      r &&
      l.val === r.val &&
      isMirror(l.left, r.right) &&
      isMirror(l.right, r.left)
    ) {
      return true;
    } else {
      return false;
    }
  };
};

/*
 * 爬楼梯 70
 * 假设你正在爬楼梯，需要 n 阶你才能到达楼顶
 * 每次可以爬 1 或 2 个台阶。你有多少种不同的方法爬到楼顶，n 是一个正整数
 * 爬到第 n 阶可以在第 n - 1 阶爬 1 个台阶，或在第 n - 2 阶爬 2 个台阶
 * F(n) = F(n - 1) + F(n - 2)
 * 定义子问题：F(n) = F(n - 1) + F(n - 2)
 * 反复执行：从 2 循环到 n，执行上述公式
 */
var climbStairs = function (n) {
  if (n < 2) return 1;
  const dp = [1, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};
// 或是一种空间复杂度更小的
var climbStairs = function (n) {
  if (n < 2) return 1;
  let dp0 = 1;
  let dp1 = 1;
  for (let i = 2; i <= n; i++) {
    const temp = dp0;
    dp0 = dp1;
    dp1 = dp1 + temp;
  }
  return dp1;
};

/*
 * 打家劫舍 198
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都有一定的现金，
 * 影响你偷窃的唯一制约因素就是相邻的房屋装有互相连通的防盗系统，
 * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
 * 给定一个代表每个存放金额的非负整数数组，计算你在不触动警报装置的情况下，
 * 能够偷窃到的最高金额
 * 输入：[1, 2, 3, 1]
 * 输出：4
 * 解释：偷窃 1 号房屋，然后偷窃 3 号房屋，最高金额 1 + 3 = 4
 * f(k) = 从前 k 个房屋中能偷窃到的最大数额
 * Ak = 第 k 个房屋的钱数
 * f(k) = max(f(k - 2) + Ak, f(k - 1))
 * 反复执行，从 2 到 n
 * 考虑使用动态规划
 * 时间复杂度 o(n) n 为数组长度
 * 空间复杂度 O(n) n 有一个数组
 * 第二种方法为 O(1)
 */
var rob = function (nums) {
  if (nums.length === 0) return 0;
  const dp = [0, nums[0]];
  for (let i = 2; i <= nums.length; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
  }
  return dp[dp.length - 1];
};

var rob = function (nums) {
  if (nums.length === 0) return 0;
  let dp0 = 0;
  let dp1 = nums[0];
  for (let i = 2; i <= nums.length; i++) {
    const dp2 = Math.max(dp0 + nums[i - 1], dp1);
    dp0 = dp1;
    dp1 = dp2;
  }
  return dp1;
};

/*
 * 分饼干 455
 * 想给你的孩子一些饼干，但是每个孩子只能给一个，
 * 每个孩子 i，都有一个胃口值 gi，
 * 这是能让孩子们满足胃口的饼干的最小尺寸
 * 并且每块饼干 j，都有一个最小尺寸 sj
 * 如果 sj >= gj，我们可以将这个饼干 j 分配给孩子 i
 * 这个孩子会得到满足，你的目标是尽可能满足越多数量的孩子，并输出这个最大数值
 * 输入 [1, 2, 3], [1, 1]，有三个孩子和两个小饼干
 * 输出 1
 * 局部最优：既能满足孩子，还消耗最少
 * 先将“较小的饼干”分给“胃口最小”的孩子
 * 对饼干数组和胃口数组升序排序
 * 遍历饼干数组，找到能满足第一个孩子的饼干
 * 然后继续遍历饼干数组，找到满足第二、三、...、n 个孩子的饼干
 * 时间复杂度为 O(n) 排序消耗 O(n * logn)，后面循环为 O(n)，取最大值为 O(n * logn)
 * 空间复杂度为 O(1)
 */
const findContentChildren = function (g, s) {
  const sortFunc = function (a, b) {
    return a - b;
  };
  g.sort(sortFunc);
  s.sort(sortFunc);
  let i = 0;
  s.forEach((v) => {
    if (v >= g[i]) {
      i += 1;
    }
  });
  return i;
};

/*
 * 买卖股票的最佳时机|| 122
 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格
 * 设计一个算法来计算你能获得的最大利润，你可以尽可能地完成更多的交易（多次买卖一支股票）
 * 你不能同时参与多笔交易
 * 输入：[7, 1, 5, 3, 6, 4]
 * 输出：7
 * 在第 2 天地时候买入，在第三天的时候卖出，这笔交易所能获得的利润为 5 - 1 = 4
 * 随后，在第 4 天的时候买入，在第 5 天的时候卖出，这笔交易所能获得的利润为 6 - 3 = 3
 * 我们是知道未来的价格的，还能回退回去觉得买或不买
 * 见好就收，见差就不动，不做任何长远打算
 * 新建一个变量，用来统计总利润
 * 遍历价格数组，如果当前价格比昨天高，在昨天买，今天买，否则不交易
 * 时间复杂度 O(n) 有一个 for 循环
 * 空间复杂度 O(1) 有一个变量
 */
const maxProfit = function (prices) {
  let profit = 0;
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }
  return profit;
};

/*
 * 全排列 46
 * 给定一个没有重复数字的序列，返回其所有可能的全排列
 * 要求：1、所有排列情况；2、没有重复元素
 * 有出路、有死路
 * 使用回溯算法
 * 用递归模拟出所有情况
 * 输入 [1, 2, 3]
 * 输出 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
 * 遇到包含重复元素的情况，就回溯
 * 收集所有到达递归终点的情况，并返回
 * 时间复杂度为 O(n!) 有两个迭代，因为没有不能有重复元素
 * 空间复杂度为 O(n) 递归的深度为输入序列的长度
 */
var persute = function (nums) {
  const res = [];
  const backtrack = (path) => {
    if (path.length === nums.length) {
      res.push(path);
      return;
    }
    nums.forEach((n) => {
      if (path.includes(n)) return;
      backtrack(path.concat(n));
    });
  };
  backtrack([]);
  return res;
};

/*
 * 子集 78
 * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）
 * 输入：nums = [1, 2, 3]
 * 输出：[[3], [1], [2], [1, 2, 3], [1, 3], [2, 3], [1, 2], []]
 * 用递归模拟出所有情况
 * 保证接的数字都是后面的数字
 * 收集所有到达递归终点的情况，并返回
 * 时间复杂度为 O(2 ^ n)
 */
var subsets = function (nums) {
  const res = [];
  const backtrack = (path, l, start) => {
    if (path.length === l) {
      res.push(path);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      backtrack(path.concat(nums[i]), l, i++);
    }
  };
  for (let i = 0; i <= nums.length; i++) {
    backtrack([], i, 0);
  }

  return res;
};