反转二叉树

/**
 * 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 invertTree = function(root) {
  if (!root) return root;
  let tmp = root.left
  root.left = root.right
  root.right = tmp
  invertTree(root.left)
  invertTree(root.right) 
  return root
};

解析url

上述12-16行发现问题：需要完善代码
1.有些没有值
2.a&b&c 连 = 号都没有
3.url 有可能有[]以西是想解析成对象
4.可能有需要解码的时候
5.可能有数组

function parse (str) {
  return str.split('&').reduce((o, kv) => {
    const [key, value] = kv.split('=')
    if (!value) {
      return o
    }
    console.log( key.split(/[\[\]]/g).filter(x => x));
    // o[key] = value
    deep_set(o, key.split(/[\[\]]/g).filter(x => x), value)
    return o
  }, {})
}
function deep_set (o, path, value) {
  let i = 0
  for (; i < path.length - 1; i++) {
    if (!o[path[i]]) {
      if (path[i + 1].match(/^\d+$/)) {
        o[path[i]] = []
      } else {
        o[path[i]] = {}
      }
    }
    o = o[path[i]]
  }
  o[path[i]] = decodeURIComponent(value)
}
console.log(parse('p=4&spm_id_from=pageDriver'));
console.log(parse('a&b&c'));
console.log(parse('a[name]=fox&a[b]=c&c=d'));
console.log(parse('color=Deep%20Blue'));
console.log(parse('a[0]=1&a[1]=2'));

includes

includes()方法返回的是布尔值，也就是true和false，这样上面的例子就可以简化一下了。
if(str.includes(‘测试’)){
console.log(true); // 包含
}else{
console.log(false) //不包含
}

N个数字和为M的问题


/***
 * A 原数组
 * n 取几个数
 * m 要求的和
 * i 当前的层级数，也就是决策的数量
 * decisions 已经取出的数组
 */
// 第一层级有一个看选不选，第二个层级就是2个，以指数倍数递增的
function sum (A, n, m, i = 0, decisions = []) {
  console.log(A, n, m, i, decisions);
  // 经过前面的递归以后，和 等于0了，意思是刚好取好了，就直接输入数组
  if (m === 0) {
    return decisions
  }
  // 如果要当前层级数，已经和原来数组一致了，而且没有输出，就意思是没找到
  // 或者要取得个数没有了 ，已经无法再取值了，也没找到
  // 或者要取得数已经小于 0 了，也没找到， 这里是一个优化点
  // 剪枝，可以减少不必要的求解，虽然不影响结果，但是影响性能
  if (i === A.length || n === 0 || m < 0) {
    return null
  }
  // 转化成决策树，传入原数组，放入当前得数，这样要取得数，就少了一个，要求的结果也就少了一个，然后层数加1
  // 然后结果集做一个合并，如果有值，就在递归调用，如果返回了null ，就调用到了后面
  // 传入原数据，然后把层级 +1 ，输出结果集
  return sum(A, n - 1, m - A[i], i + 1, decisions.concat(A[i])) || sum(A, n, m, i + 1, decisions)
}
// console.log(sum([1, 9, 3, 7], 2, 10));
// 一种优化 因为上述 ，有一个concat 是一个O(n)的操作
// 谷歌指导书说，如果一直数据量不大的话，不要做微优化，除非是高性能场景，这样就需要优化到极致
function sumN (A, n, m) {
  // 最终结果
  let r = null
  // 决策
  const decisions = []
  function inner (i = 0, n, m) {
    // 如果已经有解，就终止递归
    if (r) {
      return
    }
    // 如果已经找到就输出r
    // 把当前的数组拷贝一份给r，然后输出，因为后面还在复用，可能回改变值
    if (m === 0) {
      r = decisions.slice()
      return
    }
    if (i === A.length || n === 0) {
      return
    }
    decisions.push(A[i])
    inner(i + 1, n - 1, m - A[i])
    decisions.pop(A[i])
    inner(i + 1, n, m)
  }
  inner(0, n, m)
  return r
}
console.log(sumN([1, 9, 3, 7], 2, 10));

误区

树的轮廓

// 最左侧的数字
// 递归 + 决策树
/**
 * 
 * @param {*} node 树的结构
 * @param {*} d 当前层数
 * @param {*} outline 表示
 */
function leftoutLineTree (node, d = 0, outline = []) {
  if (!node) {
    return
  }
  // 如果当前这一层没有值，就赋值，也就是运用了树的遍历顺序，如果有值就不操作了
  if (!outline[d]) {
    outline[d] = node.value
  }
  leftoutLineTree(node.left, d + 1, outline)
  leftoutLineTree(node.right, d + 1, outline)
  return outline
}

// 每一行的最大值
/**
 * 
 * @param {*} node 树的结构
 * @param {*} d 当前层数
 * @param {*} outline 表示
 */
function maxOfLine (node, d = 0, outline = []) {
  if (!node) {
    return
  }
  // 如果当前这一层没有值，就赋值，也就是运用了树的遍历顺序，如果有值就不操作了
  outline[d] = Math.max(outline[d] || -1, node.value)
  maxOfLine(node.left, d + 1, outline)
  maxOfLine(node.right, d + 1, outline)
  return outline
}

火车车厢重排问题

function isTrans (o, t) {
  // 不匹配的队列
  const q = []
  // 遍历要排成的新数组
  for (let x of t) {
    // 队列中的最后一个是不是跟 重排车厢中的 一个相同 ，如果是就放到重排车厢
    if (q[q.length - 1] === x) {
      // 取出最后一个，意思是可以放到重排车厢，也就是匹配上了
      q.pop()
    }
    let y = null
    // 每次都从原始队列中取出第一个，如果 相同就跳过，不相同就进入
    while (o.length > 0 && (y = o.shift()) !== x) {
      q.unshift(y)
    }
    // 循环不变式： o中下一个要么和x匹配，要么o为空
  }
  // 如果最后不匹配的车厢还有值，就说明无法匹配
  return q.length === 0
}

console.log(isTrans([1, 2, 3, 4, 5], [1, 3, 2, 4, 5]));
console.log(isTrans([1, 2, 3, 4, 5], [5, 4, 3, 2, 1]));

因为上面用的是数组模仿队列，shift 和 unshift 都是O(n)的操作，所以要用真队列来提高效率

网格路径

// 网格问题
function f (x, y) {
  if (x > 0 && y > 0) {
    return f(x - 1, y) + f(x, y - 1)
  }
  else if (x > 0) {
    return f(x - 1, y)
  }
  else if (y > 0) {
    return f(x, y - 1)
  }
  else {
    return 1
  }
}
// console.log(f(4, 3));

// 网格问题优化
// 数组中的横纵坐标是反着来的，y正好代表一行
function fy (x, y, dp = []) {
  // dp 是一个缓存数据，就不用每次都计算新值了
  if (!dp[y]) {
    dp[y] = []
  }
  if (dp[y][x] !== undefined) {
    return dp[y][x]
  }

  if (x > 0 && y > 0) {
    dp[y][x] = fy(x - 1, y, dp) + fy(x, y - 1, dp)
  }
  else if (x > 0) {
    dp[y][x] = f(x - 1, y, dp)
  }
  else if (y > 0) {
    dp[y][x] = f(x, y - 1, dp)
  }
  else {
    dp[y][x] = 1
  }
  return dp[y][x]
}
// console.log(fy(4, 3));
// 网格问题动态规划
function fd (w, h) {
  const dp = []
  for (let y = 0; y <= h; y++) {
    dp[y] = []
    for (let x = 0; x <= w; x++) {
      if (x === 0 && y === 0) {
        dp[y][x] = 1
      }
      else if (x === 0) {
        dp[y][x] = dp[y - 1][x]
      }
      else if (y === 0) {
        dp[y][x] = dp[y][x - 1]
      }
      else {
        dp[y][x] = dp[y][x - 1] + dp[y - 1][x]
      }
    }
  }
  return dp[h][w]
}
console.log(fd(4, 3));

两个栈实现一个队列

class Queue {
  constructor() {
    this.s1 = []
    this.s2 = []
  }
  // 入队
  enqueue (item) {
    this.s1.push(item)
  }
  // 出队
  // 看一下这里的复杂度，我们看13行好像每一次取值似乎都要遍历，像O(n)的操作
  // 但是其实如果现在没有新加入值得话，也就是第一次取值需要全部遍历一边，所以
  // 大体还是 O(1)得操作
  dequeue () {
    while (this.s1.length > 0) {
      this.s2.push(this.s1.pop())
    }
    if (this.s2.length > 0) {
      return this.s2.pop()
    }
  }
}
const queue = new Queue()
queue.enqueue(1)
queue.enqueue(2)
console.log(queue.dequeue());
console.log(queue.dequeue());

全栈算法

0215大厂真题