算法

1. 时间复杂度

通常使用最差的时间复杂度来衡量⼀个算法的好坏。
常数时间 O(1) 代表这个操作和数据量没关系，是⼀个固定时间的操作，比如说四则运算。
对于⼀个算法来说，可能会计算出如下操作次数 aN + 1， N 代表数据量。那么该算法的时间复杂度就是 O(N) 。因为我们在计算时间复杂度的时候，数据量通常是非常大的，这时候低阶项和常数项可以忽略不计。
当然可能会出现两个算法都是 O(N) 的时间复杂度，那么对比两个算法的好坏就要通过对比低阶项和常数项了

2. 位运算

位运算在算法中很有用，速度可以比四则运算快很多。
在学习位运算之前应该知道十进制如何转⼆进制，⼆进制如何转十进制。这里说明下简单的计算方式
⼗进制 33 可以看成是 32 + 1 ，并且 33 应该是六位⼆进制的 ( 因为 33 近似 32 ，而 32 是 2 的五次方，所以是六位)，那么⼗进制 33 就是 100001 ，只要是 2 的次方，那么就是 1 否则都为 0 那么⼆进制 100001 同理，首位是 2^5 ，末位是 2^0 ，相加得出 33

左移 <<

10 << 1; // -> 20

左移就是将⼆进制全部往左移动， 10 在⼆进制中表示为 1010 ，左移⼀位后变成 10100 ，转换为⼗进制也就是 20 ，所以基本可以把左移看成以下公式 a \* (2 ^ b)

算数右移 >>

10 >> 1; // -> 5

算数右移就是将⼆进制全部往右移动并去除多余的右边， 10 在⼆进制中表示为 1010 ，右移⼀位后变成 101 ，转换为⼗进制也就是 5 ，所以基本可以把右移看成以下公式 int v = a / (2 ^ b)

右移很好用，比如可以用在⼆分算法中取中间值

13 >> 1; // -> 6

按位操作

按位与

每⼀位都为 1，结果才为 1

8 & 7; // -> 0
// 1000 & 0111 -> 0000 -> 0

按位或

其中⼀位为 1，结果就是 1

8 | 7; // -> 15
// 1000 | 0111 -> 1111 -> 15

按位异或

每⼀位都不同，结果才为 1

8 ^ 7; // -> 15
8 ^ 8; // -> 0
// 1000 ^ 0111 -> 1111 -> 15
// 1000 ^ 1000 -> 0000 -> 0

面试题：两个数不使用四则运算得出和

这道题中可以按位异或，因为按位异或就是不进位加法， 8 ^ 8 = 0 如果进位了，就是 16 了，所以我们只需要将两个数进行异或操作，然后进位。那么也就是说两个⼆进制都是 1 的位置，左边应该有⼀个进位 1 ，所以可以得出以下公式 a + b = (a ^ b) + ((a & b) << 1) ，然后通过迭代的方式模拟加法

function sum(a, b) {
  if (a == 0) return b;
  if (b == 0) return a;
  let newA = a ^ b;
  let newB = (a & b) << 1;
  return sum(newA, newB);
}

3. 排序

冒泡排序

冒泡排序的原理如下，从第⼀个元素开始，把当前元素和下⼀个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后⼀个元素，那么此时最后⼀个元素就是该数组中最大的数。下⼀轮重复以上操作，但是此时最后⼀个元素已经是最大数了，所以不需要再比较最后⼀个元素，只需要比较到 length - 1 的位置

以下是实现该算法的代码

function bubble(array) {
  checkArray(array);
  for (let i = array.length - 1; i > 0; i--) {
    // 从 0 到 `length - 1` 遍历
    for (let j = 0; j < i; j++) {
      if (array[j] > array[j + 1]) swap(array, j, j + 1);
    }
  }
  return array;
}

该算法的操作次数是⼀个等差数列 n + (n - 1) + (n - 2) + 1 ，去掉常数项以后得出时间复杂度是 O(n * n)

插入排序

入排序的原理如下。第⼀个元素默认是已排序元素，取出下⼀个元素和当前元素比较，如果当前元素大就交换位置。那么此时第⼀个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作

以下是实现该算法的代码

function insertion(array) {
  checkArray(array);
  for (let i = 1; i < array.length; i++) {
    for (let j = i - 1; j >= 0 && array[j] > array[j + 1]; j--)
      swap(array, j, j + 1);
  }
  return array;
}

该算法的操作次数是⼀个等差数列 n + (n - 1) + (n - 2) + 1 ，去掉常数项以后得出时间复杂度是 O(n * n)

选择排序

选择排序的原理如下。遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第⼀个元素和最小值索引上的值交换。如上操作后，第⼀个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作

以下是实现该算法的代码

function selection(array) {
  checkArray(array);
  for (let i = 0; i < array.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      minIndex = array[j] < array[minIndex] ? j : minIndex;
    }
    swap(array, i, minIndex);
  }
  return array;
}

该算法的操作次数是⼀个等差数列 n + (n - 1) + (n - 2) + 1 ，去掉常数项以后得出时间复杂度是 O(n * n)

归并排序

归并排序的原理如下。递归的将数组两两分开直到最多包含两个元素，然后将数组排序合并，最终合并为排序好的数组。假设我有⼀组数组 [3, 1, 2, 8, 9, 7, 6] ，中间数索引是 3 ，先排序数组 [3, 1, 2, 8] 。在这个左边数组上，继续拆分直到变成数组包含两个元素 ( 如果数组长度是奇数的话，会有⼀个拆分数组只包含⼀个元素) 。然后排序数组 [3, 1] 和 [2, 8] ，然后再排序数组 [1, 3, 2, 8] ，这样左边数组就排序完成，然后按照以上思路排序右边数组，最后将数组 [1, 2, 3, 8] 和 [6, 7, 9] 排序

以下是实现该算法的代码

function sort(array) {
  checkArray(array);
  mergeSort(array, 0, array.length - 1);
  return array;
}
function mergeSort(array, left, right) {
  // 左右索引相同说明已经只有⼀个数
  if (left === right) return;
  // 等同于 `left + (right - left) / 2`
  // 相比 `(left + right) / 2` 来说更加安全，不会溢出
  // 使用位运算是因为位运算比四则运算快
  let mid = parseInt(left + ((right - left) >> 1));
  mergeSort(array, left, mid);
  mergeSort(array, mid + 1, right);
  let help = [];
  let i = 0;
  let p1 = left;
  let p2 = mid + 1;
  while (p1 <= mid && p2 <= right) {
    help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
  }
  while (p1 <= mid) {
    help[i++] = array[p1++];
  }
  while (p2 <= right) {
    help[i++] = array[p2++];
  }
  for (let i = 0; i < help.length; i++) {
    array[left + i] = help[i];
  }
  return array;
}

以上算法使用了递归的思想。递归的本质就是压栈，每递归执行⼀次函数，就将该函数的信息 ( 比如参数，内部的变量，执行到的行数) 压栈，直到遇到终止条件，然后出栈并继续执行函数。对于以上递归函数的调用轨迹如下

mergeSort(data, 0, 6); // mid = 3
mergeSort(data, 0, 3); // mid = 1
mergeSort(data, 0, 1); // mid = 0
mergeSort(data, 0, 0); // 遇到终止， 回退到上⼀步
mergeSort(data, 1, 1); // 遇到终止， 回退到上⼀步
// 排序 p1 = 0, p2 = mid + 1 = 1
// 回退到 `mergeSort(data, 0, 3)` 执行下⼀个递归
mergeSort(2, 3); // mid = 2
mergeSort(3, 3); // 遇到终止， 回退到上⼀步
// 排序 p1 = 2, p2 = mid + 1 = 3
// 回退到 `mergeSort(data, 0, 3)` 执行合并逻辑
// 排序 p1 = 0, p2 = mid + 1 = 2
// 执行完毕回退
// 左边数组排序完毕，右边也是如上轨迹

该算法的操作次数是可以这样计算：递归了两次，每次数据量是数组的⼀半，并且最后把整个数组迭代了⼀次，所以得出表达式 2T(N / 2) + T(N) ( T 代表时间， N 代表数据量) 。根据该表达式可以套用该公式得出时间复杂度为 O(N \* logN)

快排

快排的原理如下。随机选取⼀个数组中的值作为基准值，从左至右取值与基准值对比大小。比基准值小的放数组左边，大的放右边，对比完成后将基准值和第⼀个比基准值大的值交换位置。然后将数组以基准值的位置分为两部分，继续递归以上操作

以下是实现该算法的代码

function sort( array) {
    checkArray(array);
    quickSort(array, 0, array.length - 1);
    return array;
}
function quickSort(array, left, right) {
    if (left < right) {
        swap(array, , right)
        // 随机取值，然后和末尾交换， 这样做比固定取⼀个位置的复杂度略低
        let indexs = part(array, parseInt(Math.random() * (right - left + 1)) +
        quickSort(array, left, indexs [0]);
        quickSort(array, indexs [1] + 1, right);
    }
}
function part(array, left, right) {
    let less = left - 1;
    let more = right;
    while (left < more) {
    if (array[left] < array[right]) {
    // 当前值比基准值小， `less` 和 `left` 都加⼀
    ++less;
    ++left;
    } else if (array[left] > array[right]) {
    // 当前值比基准值大，将当前值和右边的值交换
    // 并且不改变 `left`， 因为当前换过来的值还没有判断过大小
    swap(array, --more, left);
    } else {
    // 和基准值相同， 只移动下标
    left++;
    }
    }
    // 将基准值和比基准值大的第⼀个值交换位置
    // 这样数组就变成 `[比基准值小 , 基准值 , 比基准值大]`
    swap(array, right, more);
    return [less, more];
}

该算法的复杂度和归并排序是相同的，但是额外空间复杂度比归并排序少，只需 O(logN) ，并且相比归并排序来说，所需的常数时间也更少

面试题

Sort Colors：该题目来自 LeetCode ，题目需要我们将 [2,0,2,1,1,0] 排序成 [0,0,1,1,2,2] ，这个问题就可以使用三路快排的思想

var sortColors = function (nums) {
  let left = -1;
  let right = nums.length;
  let i = 0;
  // 下标如果遇到 right，说明已经排序完成
  while (i < right) {
    if (nums[i] == 0) {
      swap(nums, i++, ++left);
    } else if (nums[i] == 1) {
      i++;
    } else {
      swap(nums, i, --right);
    }
  }
};

4. 链表

反转单向链表

该题目来自 LeetCode ，题目需要将⼀个单向链表反转。思路很简单，使用三个变量分别表示当前节点和当前节点的前后节点，虽然这题很简单，但是却是⼀道面试常考题

var reverseList = function (head) {
  // 判断下变量边界问题
  if (!head || !head.next) return head;
  // 初始设置为空， 因为第⼀个节点反转后就是尾部，尾部节点指向 null
  let pre = null;
  let current = head;
  let next;
  // 判断当前节点是否为空
  // 不为空就先获取当前节点的下⼀节点
  // 然后把当前节点的 next 设为上⼀个节点
  // 然后把 current 设为下⼀个节点， pre 设为当前节点
  while (current) {
    next = current.next;
    current.next = pre;
    pre = current;
    current = next;
  }
  return pre;
};

5. 树

二叉树的先序，中序，后序遍历

先序遍历表示先访问根节点，然后访问左节点，最后访问右节点。
中序遍历表示先访问左节点，然后访问根节点，最后访问右节点。
后序遍历表示先访问左节点，然后访问右节点，最后访问根节点

递归实现

递归实现相当简单，代码如下

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}
var traversal = function (root) {
  if (root) {
    // 先序
    console.log(root);
    traversal(root.left);
    // 中序
    // console.log(root);
    traversal(root.right);
    // 后序
    // console.log(root);
  }
};

对于递归的实现来说，只需要理解每个节点都会被访问三次就明白为什么这样实现了

非递归实现

非递归实现使用了栈的结构，通过栈的先进后出模拟递归实现。

以下是先序遍历代码实现

function pre(root) {
  if (root) {
    let stack = [];
    // 先将根节点 push
    stack.push(root);
    // 判断栈中是否为空
    while (stack.length > 0) {
      // 弹出栈顶元素
      root = stack.pop();
      console.log(root);
      // 因为先序遍历是先左后右，栈是先进后出结构
      // 所以先 push 右边再 push 左边
      if (root.right) {
        stack.push(root.right);
      }
      if (root.left) {
        stack.push(root.left);
      }
    }
  }
}

以下是中序遍历代码实现

function mid(root) {
  if (root) {
    let stack = [];
    // 中序遍历是先左再根最后右
    // 所以首先应该先把最左边节点遍历到底依次 push 进栈
    // 当左边没有节点时，就打印栈顶元素，然后寻找右节点
    // 对于最左边的叶节点来说，可以把它看成是两个 null 节点的父节点
    // 左边打印不出东西就把父节点拿出来打印，然后再看右节点
    while (stack.length > 0 || root) {
      if (root) {
        stack.push(root);
        root = root.left;
      } else {
        root = stack.pop();
        console.log(root);
        root = root.right;
      }
    }
  }
}

以下是后序遍历代码实现，该代码使用了两个栈来实现遍历，相比⼀个栈的遍历来说要容易理解很多

function pos(root) {
  if (root) {
    let stack1 = [];
    let stack2 = [];
    // 后序遍历是先左再右最后根
    // 所以对于⼀个栈来说，应该先 push 根节点
    // 然后 push 右节点， 最后 push 左节点
    stack1.push(root);
    while (stack1.length > 0) {
      root = stack1.pop();
      stack2.push(root);
      if (root.left) {
        stack1.push(root.left);
      }
      if (root.right) {
        stack1.push(root.right);
      }
    }
    while (stack2.length > 0) {
      console.log(s2.pop());
    }
  }
}

中序遍历的前驱后继节点

实现这个算法的前提是节点有⼀个 parent 的指针指向父节点，根节点指向 null

前驱节点

对于节点 2 来说，他的前驱节点就是 4 ，按照中序遍历原则，可以得出以下结论

如果选取的节点的左节点不为空，就找该左节点最右的节点。对于节点 1 来说，他有左节点 2 ，那么节点 2 的最右节点就是 5
如果左节点为空，且目标节点是父节点的右节点，那么前驱节点为父节点。对于节点 5 来说，没有左节点，且是节点 2 的右节点，所以节点 2 是前驱节点
如果左节点为空，且目标节点是父节点的左节点，向上寻找到第⼀个是父节点的右节点的节点。对于节点 6 来说，没有左节点，且是节点 3 的左节点，所以向上寻找到节点 1 ，发现节点 3 是节点 1 的右节点，所以节点 1 是节点 6 的前驱节点

以下是算法实现

function predecessor(node) {
  if (!node) return;
  // 结论 1
  if (node.left) {
    return getRight(node.left);
  } else {
    let parent = node.parent;
    // 结论 2 3 的判断
    while (parent && parent.right === node) {
      node = parent;
      parent = node.parent;
    }
    return parent;
  }
}
function getRight(node) {
  if (!node) return;
  node = node.right;
  while (node) node = node.right;
  return node;
}

后继节点

对于节点 2 来说，他的后继节点就是 5 ，按照中序遍历原则，可以得出以下结论

如果有右节点，就找到该右节点的最左节点。对于节点 1 来说，他有右节点 3 ，那么节点 3 的最左节点就是 6
如果没有右节点，就向上遍历直到找到⼀个节点是父节点的左节点。对于节点 5 来说，没有右节点，就向上寻找到节点 2 ，该节点是父节点 1 的左节点，所以节点 1 是后继节点以下是算法实现

function successor(node) {
  if (!node) return;
  // 结论 1
  if (node.right) {
    return getLeft(node.right);
  } else {
    // 结论 2
    let parent = node.parent;
    // 判断 parent 为空
    while (parent && parent.left === node) {
      node = parent;
      parent = node.parent;
    }
    return parent;
  }
}
function getLeft(node) {
  if (!node) return;
  node = node.left;
  while (node) node = node.left;
  return node;
}

树的深度

树的最大深度：该题目来自 Leetcode ，题目需要求出⼀颗二叉树的最大深度

以下是算法实现

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

对于该递归函数可以这样理解：⼀旦没有找到节点就会返回 0 ，每弹出⼀次递归函数就会加⼀，树有三层就会得到 3

算法 ​

1. 时间复杂度 ​

2. 位运算 ​

左移 << ​

算数右移 >> ​

按位操作 ​

按位与 ​

按位或 ​

按位异或 ​

3. 排序 ​

冒泡排序 ​

插入排序 ​

选择排序 ​

归并排序 ​

快排 ​

面试题 ​

4. 链表 ​

反转单向链表 ​

5. 树 ​

递归实现 ​

非递归实现 ​

前驱节点 ​

后继节点 ​

树的深度 ​

算法

1. 时间复杂度

2. 位运算

左移 <<

算数右移 >>

按位操作

按位与

按位或

按位异或

3. 排序

冒泡排序

插入排序

选择排序

归并排序

快排

面试题

4. 链表

反转单向链表

5. 树

递归实现

非递归实现

前驱节点

后继节点

树的深度