导航

介绍下深度优先遍历和广度优先遍历，如何实现？

深度优先遍历
- 是指从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个顶点进行访问。重复此步骤，直至所有结点都被访问完为止。
广度优先遍历
- 是从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点所有未被访问的邻结点，访问完后再访问这些结点中第一个邻结点的所有结点，重复此方法，直到所有结点都被访问完为止。

// 1.深度优先遍历的递归写法
function deepTraversal(node) {
  let nodes = [];
  if (node != null) {
    nodes.push[node];
    let children = node.children;
    for (let i = 0; i < children.length; i++) {
      deepTraversal(children[i]);
    }
  }
  return nodes;
}

// 2.深度优先遍历的非递归写法
function deepTraversal(node) {
  let nodes = [];
  if (node != null) {
    let stack = [];
    // 同来存放将来要访问的节点
    stack.push(node);
    while (stack.length !== 0) {
      let item = stack.pop();
      // 正在访问的节点
      nodes.push(item);
      let children = item.children;
      for (let i = children.length - 1; i >= 0; i--) {
        // 将现在访问点的节点的子节点存入stack，供将来访问
        stack.push(children[i]);
      }
    }
  }
  return nodes;
}

// 3.广度优先遍历的递归写法
function wideTraversal(node) {
  let nodes = [], i = 0;
  if (node != null) {
    nodes.push(node);
    wideTraversal(node.nextElementSibling);
    node = nodes[i++];
    wideTraversal(node.firstElementChild);
  }
  return nodes;
}

// 4.广度优先遍历的非递归写法
function wideTraversal(node) {
  let nodes = [], i = 0;
  while (node != null) {
    nodes.push(node);
    node = nodes[i++];
    let children = node.children;
    for (let i = 0; i < children.length; i++) {
      nodes.push(children[i]);
    }
  }
  return nodes;
}

深度遍历广度遍历的区别？

对于算法来说无非就是时间换空间空间换时间

1、深度优先不需要记住所有的节点, 所以占用空间小, 而广度优先需要先记录所有的节点占用空间大
2、深度优先有回溯的操作(没有路走了需要回头)所以相对而言时间会长一点
3、深度优先采用的是堆栈的形式, 即先进后出
4、广度优先则采用的是队列的形式, 即先进先出

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log(m+n))。

示例1： nums1 = [1, 3] nums2 = [2] 中位数是 2.0

示例2： nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3) / 2 = 2.5

const findMedianSortedArrays = function(nums1, nums2) {
  const lenN1 = nums1.length;
  const lenN2 = nums2.length;
  const median = Math.ceil((lenN1 + lenN2 + 1) / 2);
  const isOddLen = (lenN1 + lenN2) % 2 === 0;
  const result = new Array(median);
  let i = 0; // pointer for nums1
  let j = 0; // pointer for nums2
  for (let k = 0; k < median; k++) {
    if (i < lenN1 && j < lenN2) {
      if (nums1[i] < nums2[j]) {
        result[i + j] = nums1[i++];
      } else {
        result[i + j] = nums2[j++];
      }
    } else if (i < lenN1) {
      result[i + j] = nums1[i++];
    } else if (j < lenN2) {
      result[i + j] = nums2[j++];
    }
  }
  if (isOddLen) {
    return (result[median - 1] + result[median - 2]) / 2;
  } else {
    return result[median - 1];
  }
};

说出几种你能想到的JS 变量交换的方法

方法一：算术运算法

实现原理：

把 a、b 看做数轴上的点，围绕两点间的距离来进行计算。

let a = 8;
let b = 6;

a = b - a;
b = b - a;
a = b + a;

console.log("a：" + a + " ，b：" + b); // 输出 a：6 ，b：8 交换成功

具体过程：

第一句：“a=b-a”求出 ab 两点的距离，并且将其保存在 a 中
第二句：“b=b-a”求出 a 到原点的距离（b 到原点的距离与 ab 两点距离之差），并且将其保存在 b 中
第三句：“a=b+a”求出 b 到原点的距离（a 到原点距离与 ab 两点距离之和），并且将其保存在 a 中

完成交换！

方法二：借助数组特性交换

实现原理：

借助数组的下标及运算符的优先级实现

let a = 1,
  b = 2;

a = [a, b]; // 让 a 变成数组
b = a[0]; // 先取出 b
a = a[1]; // 再覆盖 a

console.log("a：" + a + " ，b：" + b); // 输出 a：2 ，b：1 完成交换

方法三：位运算

代码实现

let a = 1, // 二进制：0001
  b = 2; // 二进制 0010

a ^= b; // a = a ^ b = 1 ^ 2 = 3
b ^= a; // b = b ^ (a ^ b) = 2 ^ (1 ^ 2) = 1
a ^= b;

console.log("a：" + a + " ，b：" + b); // 输出 a：2 ，b：1 完成交换

实现原理：

^运算符跟|类似，但有一点不同的是如果两个操作位都为 1 的话，结果产生 0
1 的二进制表示为 0 0 0 0 0 0 1
3 的二进制表示为 0 0 0 0 0 1 1
所以 1 ^ 3的结果为2

方法四：ES6 的解构

用解构的语法特性，一次性解决，简单粗暴 !

更重要的一点：解构语法还适用于其他类型的变量进行互换。
所以，用解构可以很 easy 地进行互换。

let a = 1,
  b = 2;

[a, b] = [b, a];

console.log("a：" + a + " ，b：" + b); // 输出 a：2 ，b：1 交换完成

方法五：借助对象的键值对

实现原理：

把 a 先变成了一个对象，这个对象保存着应该交换后的键值对，最后赋值搞定

let a = 1,
  b = 2;

a = { a: b, b: a };
b = a.b;
a = a.a;

console.log("a：" + a + " ，b：" + b); // 输出 a：2 ，b：1 完成交换