function binarySearch(arr, target) {
  let l = 0;
  let r = arr.length - 1;
  while (l <= r) {
    let mid = Math.floor((l + r) / 2);
    if (arr[mid] == target) {
      return mid;
    }
    if (arr[mid] < target) {
      l = mid + 1;
    }
    if (arr[mid] > target) {
      r = mid - 1;
    }
  }
  return -1;
}
console.log(binarySearch([0, 1, 2, 3, 4, 5], 4));

var map = {
  距离: '频次',
  长度10: '20次',
};
// 拿掉一个点后，其实就是取这个点后还剩一个点，总次数就是 20*19

// 迭代-视频解法
var swapPairs = function (head) {
  const dummyHead = new ListNode(0);
  dummyHead.next = head;
  let temp = dummyHead;
  while (temp.next !== null && temp.next.next !== null) {
    const node1 = temp.next;
    const node2 = temp.next.next;
    // 下边的顺序背下来就行
    temp.next = node2;
    node1.next = node2.next;
    node2.next = node1;
    temp = node1; // 如果只是反转链表这里改成node2就对了，因为node2现在已经变到第一位了，temp指向这里往下
  }
  return dummyHead.next;  // 这里一定是dummyHead
};

// 递归
var swapPairs = function (head) {
  if (head === null || head.next === null) {
    return head;
  }
  const newHead = head.next;
  head.next = swapPairs(newHead.next);
  newHead.next = head;
  return newHead;
};

// 就地反转-迭代
var reverseList = function (head) {
  let [prev, curr] = [null, head];
  while (curr) {
    let tmp = curr.next; // 1. 临时存储当前指针后续内容
    curr.next = prev; // 2. 反转链表
    prev = curr; // 3. 接收反转结果
    curr = tmp; // 4. 接回临时存储的后续内容
  }
  return prev;
};
// 上边的更容易理解-下边这个只是把第一项移到了最后
var swapPairs = function (head) {
  const dummyHead = new ListNode(0);
  dummyHead.next = head;
  let temp = dummyHead;
  while (temp.next !== null && temp.next.next !== null) {
    const node1 = temp.next;
    const node2 = temp.next.next;
    temp.next = node2;
    node1.next = node2.next;
    node2.next = node1;
    temp = node2; // 这里改成node2就对了，因为node2现在已经变到第一位了，temp指向这里往下
  }
  return dummyHead.next;
};

function flatten(arr, result = []) {
  for (let item of arr) {
    if (Array.isArray(item)) flatten(item, result);
    else result.push(item);
  }
  return result;
}

var numSquares = function (n) {
  const list = [];
  list.push({ num: n, step: 0 });

  while (list.length > 0) {
    const { num, step } = list.shift();
    if (num === 0) return step;
    for (let i = 1; num - i * i >= 0; i++) {
      list.push({ num: num - i * i, step: step + 1 });
    }
  }
};

// 注意优化点
// 因为这个是个图而不是单纯的树，所以num的值num-i*i 会出现大量的重复，所以需要存储
var numSquares = function (n) {
  const list = [];
  list.push({ num: n, step: 0 });
  const visitedObj = { [n]: true };
  while (list.length > 0) {
    const { num, step, visited } = list.shift();
    for (let i = 1; ; i++) {
      const extraNum = num - i * i;
      if (extraNum < 0) break;
      // this line return the result in advance, it reduces perform time very much.
      if (extraNum === 0) return step + 1;
      if (!visitedObj[extraNum]) {
        visitedObj[extraNum] = true;
        list.push({ num: num - i * i, step: step + 1 });
      }
    }
  }
};

var maxDepth = function (root) {
  if (root == null) return 0;
  const left = maxDepth(root.left);
  const right = maxDepth(root.right);
  return Math.max(left, right) + 1;
};

var invertTree = function (root) {
  if (root === null) {
    return null;
  }
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
};

const hasPathSum = (root, sum) => {
  if (root == null) return sum == 0;
  return (
    hasPathSum(root.left, sum - root.val) ||
    hasPathSum(root.right, sum - root.val)
  );
};
// 修复bug-当直接传入null的时候，当第一个节点就等于sum值时
const hasPathSum = (root, sum) => {
  if (root == null) return false; // 遍历到null节点, 只有首次传入null才会到这里
  if (root.left == null && root.right == null) {
    // 遍历到叶子节点，解决首个节点的值就和sum相等且其中一个子节点为null的情况
    return sum - root.val == 0; // 如果满足这个就返回true
  }
  return (
    hasPathSum(root.left, sum - root.val) ||
    hasPathSum(root.right, sum - root.val)
  ); // 大问题转成两个子树的问题
};

if (root == null) return res; // 遍历到null节点, 只有首次传入null才会到这里
 if (root.left == null && root.right == null) {
   return ?
 }

var binaryTreePaths = function (root) {
  const paths = [];
  const construct_paths = (root, path) => {
    if (root) {
      path += root.val.toString();
      if (root.left === null && root.right === null) {
        // 当前节点是叶子节点（叶子节点其实就是最底层的节点）
        paths.push(path); // 把路径加入到答案中
      } else {
        path += '->'; // 当前节点不是叶子节点，继续递归遍历
        construct_paths(root.left, path);
        construct_paths(root.right, path);
      }
    }
  };
  construct_paths(root, '');
  return paths;
};

var pathSum = function (root, sum) {
  //root为根节点， sum为规定的路径权值和
  if (!root) return 0; //若节点为空，返回0
  let page = findDown(root, sum); //从根节点开始有多少满足条件的路径数，findDown函数是求从单个节点开始满足条件的路径数
  let sum1 = pathSum(root.left, sum); //遍历左子树求符合条件的路径数，
  let sum2 = pathSum(root.right, sum); //遍历右子树求符合条件的路径数
  return page + sum1 + sum2; //得出总路径数
};

function findDown(tNode, sum) {
  // 求从单个节点开始满足条件的路径数，tNode为当前节点，sum为规定的路径权值和
  if (!tNode) return 0; //若节点为空，返回0
  let flag = tNode.val === sum ? 1 : 0; // 当前节点权值刚好等于sum则算为1，否则为0
  let leftSum = findDown(tNode.left, sum - tNode.val); //剩下的权值要子树来凑，先看左子树能不能凑出来
  let rightSum = findDown(tNode.right, sum - tNode.val); //再看右子树是否能凑出来
  return flag + leftSum + rightSum; // 返回符合条件的路径数
}

const lowestCommonAncestor = (root, p, q) => {
  if (p.val < root.val && q.val < root.val) {
    return lowestCommonAncestor(root.left, p, q);
  }
  if (p.val > root.val && q.val > root.val) {
    return lowestCommonAncestor(root.right, p, q);
  }
  return root;
};

//回溯
const letterCombinations = (digits) => {
  if (digits.length == 0) return [];
  const res = [];
  const map = {
    2: 'abc',
    3: 'def',
    4: 'ghi',
    5: 'jkl',
    6: 'mno',
    7: 'pqrs',
    8: 'tuv',
    9: 'wxyz',
  };

  const dfs = (curStr, i) => {
    // curStr是当前字符串，i是扫描的指针
    if (i > digits.length - 1) {
      // 指针越界，递归的出口
      res.push(curStr); // 将解推入res
      return; // 结束当前递归分支，进入另一个递归分支
    }
    const letters = map[digits[i]]; // 当前数字对应有哪些字母
    for (const l of letters) {
      // 不同的字母选择代表不同的递归分支
      dfs(curStr + l, i + 1); // 生成新字符串，i指针右移，递归
    }
  };
  dfs('', 0); // 递归的入口，初始字符串为''，指针为0
  return res;
};

// dfs
var letterCombinations = function (digits) {
  if (digits.length === 0) {
    return [];
  }

  const dictionary = {
    2: 'abc',
    3: 'def',
    4: 'ghi',
    5: 'jkl',
    6: 'mno',
    7: 'pqrs',
    8: 'tuv',
    9: 'wxyz',
  };

  let result = [];

  const dfs = (str, index) => {
    // 当 index 等于 原始字符串时，说明当前分支已经组合完毕
    // 可以结束递归了
    if (index >= digits.length) {
      result.push(str);
      return;
    }
    // 获取当前数字对应的 字母集合
    let map = dictionary[digits[index]];
    // 处理 1 、0 等异常边界
    if (map) {
      // 当前字母集合中的每一个元素和上层递归中生成的更多的字符组合
      for (let i of map) {
        // 需要加入组合的位置向后移动
        dfs(str + i, index + 1);
      }
    }
  };
  // 从字符串第一个位置开始组合
  dfs('', 0);

  return result;
};
// bfs
var letterCombinations = function (digits) {
  if (digits.length === 0) {
    return [];
  }

  const dictionary = {
    2: 'abc',
    3: 'def',
    4: 'ghi',
    5: 'jkl',
    6: 'mno',
    7: 'pqrs',
    8: 'tuv',
    9: 'wxyz',
  };

  let result = [];

  // bfs
  // 1、处理首位的 数值 为 1 或者 0 的情况
  // 2、生成初始 的 组合基准值 方便使用while循环（手动初始化迭代栈）
  if (digits[0] && digits[0] !== 1) {
    result.push(...dictionary[digits[0]]);
  }
  let index = 1,
    map,
    temp;
  while (index < digits.length) {
    // 获取当前数字对应的 字母集合
    map = dictionary[digits[index]];
    if (map) {
      // 用于记录 当前层的所有组合情况
      temp = [];
      for (let i = 0; i < map.length; i++) {
        for (let j = 0; j < result.length; j++) {
          // 以 前一个 数字 对应 组合条件为基准 生成的 组合状态
          temp.push(result[j] + map[i]);
        }
      }
      // 更新组合的状态
      result = temp;
    } else {
      // 遇到 0、1 循环终止
      break;
    }
    // 更新index，准备取下一个位置的数值
    index++;
  }

  return result;
};

const permute = (nums) => {
  const res = [];
  const used = {};

  function dfs(path) {
    if (path.length == nums.length) {
      res.push(path.slice());
      return;
    }
    for (const num of nums) {
      // if (path.includes(num)) continue; // 查找的时间是O(n)，别这么写，时间复杂度增加
      if (used[num]) continue;
      path.push(num);
      used[num] = true;
      dfs(path);
      path.pop();
      used[num] = false;
    }
  }

  dfs([]);
  return res;
};

const combine = (n, k) => {
  const res = [];

  const helper = (start, path) => {
    // start是枚举选择的起点 path是当前构建的路径（组合）
    if (path.length == k) {
      res.push(path.slice()); // 拷贝一份path，推入res
      return; // 结束当前递归
    }
    for (let i = start; i <= n; i++) {
      // 这里可以做一部剪纸的优化  i<=n-(k-path.length),因为后边不够k位了
      // 枚举出所有选择
      path.push(i); // 选择
      helper(i + 1, path); // 向下继续选择
      path.pop(); // 撤销选择
    }
  };

  helper(1, []); // 递归的入口，从数字1开始选
  return res;
};

var exist = function (board, word) {
  let l = word.length;
  let l1 = board.length,
    l2 = board[0].length;
  if (l > l1 * l2) {
    return false;
  }
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  let visited = new Array(l1).fill(0).map((e) => {
    return Array(l2).fill(0);
  });
  for (let i = 0; i < l1; i++) {
    for (let j = 0; j < l2; j++) {
      let flag = check(i, j, 0);
      if (flag) {
        return true;
      }
    }
  }
  return false;

  function check(x, y, k) {
    if (word[k] != board[x][y]) {
      return false;
    }
    if (k == l - 1) {
      return true;
    }
    visited[x][y] = 1;
    for (const [dx, dy] of directions) {
      let newx = x + dx,
        newy = y + dy;
      if (newx >= 0 && newx < l1 && newy >= 0 && newy < l2) {
        // 判断是否在区域内
        if (!visited[newx][newy]) {
          const flag = check(newx, newy, k + 1);
          if (flag) {
            return true;
          }
        }
      }
    }
    visited[x][y] = 0;
    return false;
  }
};

var numIslands = function (grid) {
  /** 解法一 DFS 关键：遇到1 则岛屿数量+1 且 将相邻所有陆地变为0 直至遍历完整个网格 */
  // 边界处理
  if (!grid.length) return 0;

  // 定义变量
  const row = grid.length,
    col = grid[0].length; // row 行数 col 列数
  let quantity = 0;

  // DFS
  const DFS = (grid, i, j) => {
    // 递归终止条件
    // 条件一 要在网格范围内
    if (i < 0 || j < 0 || i >= row || j >= col) return;
    // 条件二 当前值为 ‘1’
    if (grid[i][j] !== '1') return;

    // PS: 上述条件也可合并写 if (i < 0 || j < 0 || i >= row || j >= col || grid[i][j] !== '1') return 为了可读性 故拆开了

    // 处理当前层逻辑  ⚠️ 是 '0' 不是 0
    grid[i][j] = '0';

    // 向 上下左右发散
    for (let x of [-1, 0, 1]) {
      for (let y of [-1, 0, 1]) {
        // 过滤 对角线方向 (若为八个方向则移除此条件)
        if (x === y || x === -y) continue;
        DFS(grid, i + x, j + y);
      }
    }
  };

  // 遍历整个网格
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (grid[i][j] === '1') {
        quantity++;
        DFS(grid, i, j);
      }
    }
  }

  return quantity;
};

function fib(n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n - 1) + fib(n - 2);
}

// 很多重复计算，存储优化
function main(n) {
  var memo = new Array(n + 1).fill(-1);
  function fib(n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] == -1) {
      memo[n] = fib(n - 1) + fib(n - 2);
    }
    return memo[n];
  }
  fib(n);
}

// 动态规划-自下而上 - 递归会占用空间，而动态规划不会
function fib(n) {
  var memo = new Array(n + 1).fill(-1);
  memo[0] = 0;
  memo[1] = 1;
  for (i = 2; i <= n; i++) {
    memo[i] = memo[i - 1] + memo[i - 2];
  }
  return memo[n];
}

// 和菲波那切数列一样，需要存储优化
function climbStairs() {
  function calcWay(n) {
    if (n == 1) return 1;
    if (n == 2) return 2; // 走两节有两种方法
    return calcWay(n - 1) + calcWay(n - 2); // 走一步方法数+走两步的方法数
  }
}
// 动态规划方法也相同

// 递归
function intBreak(n) {
  var memo = new Array(n - 1).fill(-1);
  function breakInt(n) {
    var res = -1;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    for (i = 1; i < n - 1; i++) {
      res = Math.max(res, i * breakInt(n - i), i * n - i); // 自顶向下
    }
    memo[n] = res;
    return res;
  }
}
function intBreak(n) {
  var memo = new Array(n - 1).fill(-1);
  // 从底开始设置
  memo[1] = 1;
  for (i = 2; i < n; i++) {
    for (j = 1; j <= i - 1; j++) {
      // 主要为了拆分为j+(i-j)
      memo[i] = Math.max(memo[i], j * i - j, j * memo(i - j));
    }
  }
  return memo[n];
}

// 迭代-记忆化搜索-自顶向下
function rob(nums) {
  var memo = new Array(nums.length).fill(-1);
  // 考虑抢劫nums[index....nums.length]
  function tryRob(nums, index) {
    // 递归终止条件
    if (index > nums.length) return 0;
    if (memo[index] != -1) return memo[index];
    var res = 0;
    for (i = index; i < nums.length; i++) {
      res = Math.max(res, nums[index] + tryRob(index + 2));
    }
    memo[index] = res;
    return res;
  }
  tryRob(nums, 0);
}
// 动态规划- 从右侧开始才是从底往上，所以从n-1开始，n-1是因为0也算一位
function rob(nums) {
  var n = nums.length;
  var memo = new Array(n).fill(-1);
  // memo[i]表示考虑抢劫nums[i....n-1]
  memo[n - 1] = nums[n - 1]; // 如果只抢劫最后一个，那就只有一种可能，就得到一个价值，就是nums[n-1]
  for (i = n - 2; i >= 0; i--) {
    for (j = i; j < n; j++) {
      memo[i] = Math.max(memo[i], nums[j] + (j + 2 < n ? memo[j + 2] : 0));
    }
  }
  return memo[0];
}

// 递归
function knapsack(w, v, C) {
  var n = w.length;
  var memo = new Array(n).fill(0).map(() => new Array(C + 1)); // 因为有两个维度，所以需要二维数组做缓存
  function bestValue(w, v, index, c) {
    if (index < 0 || c <= 0) return 0;
    if (memo[index][c] != -1) return memo[index][c];
    res = bestValue(w, v, index - 1, c); // 不放入
    if (c >= w[index]) {
      res = Math.max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));
    }
    memo[index][c] = res;
    return res;
  }
  bestValue(w, v, n - 1, C);
}
// 动态规划
function knapsack(w, v, C) {
  var n = w.length;
  var memo = new Array(n).fill(0).map(() => new Array(C + 1));
  for (j = 0; j <= C; j++) {
    memo[0][j] = j > w[0] ? v[0] : 0;
  }
  for (i = 1; i < n; i++) {
    for (j = 0; j <= C; j++) {
      memo[i][j] = memo[i - 1][j]; // 不放入所以还是i-1
      if (j > w[i]) {
        memo[i][j] = Math.max(memo[i][j], v[i] + memo[i - 1][j - w[i]]);
      }
    }
  }
  return memo[n - 1][C];
}

var arr = [
  [[], []],
  [[], []],
];

// 迭代
function canPart(nums) {
  var sum = 0;
  for (i = 0; i < nums.length; i++) {
    sum += nums[i];
  }
  if (sum % 2 != 0) return false;
  // -1为未计算，0为不可填充即false，1为可填充即true
  // var memo = new Array(nums.length).fill(-1).map(() => new Array(sum/2+1));
  tryPart(nums, nums.length - 1, sum / 2);
  // nums[0...index]是否可以填满sum的背包
  function tryPart(nums, index, sum) {
    if (sum == 0) return true;
    if (sum < 0 || index <= 0) return false;
    // if(memo[index][sum] != -1) return memo[index][sum] = -1
    // memo[index][sum] = (tryPart(nums, index-1, sum) || tryPart(nums, index-1, sum-nums[index]))?1:0
    // return memo[index][sum] == 1
    return (
      tryPart(nums, index - 1, sum) ||
      tryPart(nums, index - 1, sum - nums[index])
    );
  }
}
// 动态规划
function canPart(nums) {
  var sum = 0;
  for (i = 0; i < nums.length; i++) {
    sum += nums[i];
  }
  if (sum % 2 != 0) return false;
  var n = nums.length;
  var C = sum / 2;
  var memo = new Array(C + 1).fill(false); // 从小向大，不会出现未计算的情况，节省一个空间复杂度
  for (i = 0; i < C; i++) {
    memo[i] = nums[0] == i; // 先拿出第一个看是否能填充
  }
  for (i = 1; i <= n; i++) {
    for (j = C; j > nums[i]; j--) {
      memo[j] = memo[j] || memo[j - nums[i]];
    }
  }
  return memo[C];
}

// 动态规划  自底向下
function LIS(nums) {
  if (nums.length == 0) return 0;
  // memo[i] 表示以nums[i]为结尾的最长上升子序列
  var memo = new Array(nums.length).fill(1);
  for (var i = 1; i < nums.length; i++) {
    // 因为第0位 取不取都是1种
    for (var j = 0; j < i; j++) {
      // 遍历之前的值做比较,判断是否小于当前值
      if (nums[j] < nums[i]) {
        memo[i] = Math.max(memo[j] + 1, memo[i]);
      }
    }
  }
  var res = 1;
  for (var i = 0; i < nums.length; i++) {
    res = Math.max(res, memo[i]);
  }
  return res;
}

var rotate = function (matrix) {
  let matrixLength = matrix.length;
  for (let i = 0; i < matrixLength; i++) {
    for (let j = i; j < matrixLength; j++) {
      let temp = matrix[i][j];
      matrix[i][j] = matrix[j][i];
      matrix[j][i] = temp;
    }
  }
  return matrix.map((item) => item.reverse());
};