《剑指Offer》JavaScript版解决方案

发表于 | 分类于 |

问题全部来自《剑指Offer》，顺序一致。

单例模式

1.使用字面量声明对象

1
2
3
4
5
6
7
const Singleton = {
  prop1: "prop1"
  prop2: "prop2"
  method1() {
    console.log("I am a method.");
  }
}

或者通过闭包封装自己的私有变量和方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const Singleton = function() {
  let privateProp = "You can't see me";
  function privateMethod() {
    console.log("You can't see me either.");
  }
  return {
    publicProp: `${privateProp}!`,
    publicMethod() {
      return privateMethod();
    }
  }
}

2.利用闭包

本质上和上面的方法类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const Singleton = function() {
  let instance;
  function init() {
    return {
      prop: "prop",
      method() {
        console.log("I am a method.");
      }
    };
  }
  return {
    getInstance() {
      // JS单线程，不考虑锁的问题
      if (!instance) {
        instance = init();
      }
      return instance;
    }
  }
}

还有一个酷炫的变种，不过是上面的构造函数写法

1
2
3
4
5
6
7
8
9
10
11
12
const Singleton = function() {
  const instance = this;
  this.prop = "prop";
  this.method = function() {
    console.log("I am a method.");
  }
  Singleton = function() {
    return instance;
  };
}

3.借助构造函数和JS中函数也是对象的特点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const Singleton = function() {
  // 这里不取名为instance也可以
  // 显式返回this
  if (typeof Singleton.instance === "object") {
    return Singleton.instance;
  }
  // 成员和方法
  this.prop = "prop";
  this.method = function() {
    console.log("I am a method.");
  }
  Singleton.instance = this;
  //隐式返回this
}

参考

找出数组中重复的数字

Set，使用ES6内建的数据结构。

1
2
3
4
5
6
7
8
9
const mySet = new Set();
arr.forEach((val, index) => {
  if (mySet.has(val)) {
    console.log(val);
    return;
  } else {
    mySet.add(val);
  }
});

Object或Array（空间复杂度O(n)），换汤不换药，略。

传统方法，时间复杂度O(n)，空间复杂度O(1)。交换当前元素和当前索引对应的元素，直到两者相等。（请参考原书中的前提，数字都在0~n-1之间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function findDuplicate(arr) {
  // 边界检测
  if (!arr || arr.length === 0) {
    return false;
  }
  for (let i = 0, len = arr.length; i < len; i++) {
    // 循环交换元素直到arr[i] == i
    while (arr[i] != i) {
      if (arr[i] === arr[arr[i]]) {
        return arr[i];
      }
      // 交换
      [arr[i], arr[arr[i]]] = [arr[arr[i]], arr[i]];
    }
  }
}

传统方法，且不修改数组，利用折半查找，递归寻找重复的元素。时间复杂度O(nlogn)，空间复杂度O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function findDuplicate(arr) {
  // 边界检测
  if (!arr || arr.length === 0) {
    return false;
  }
  function countRange (arr, start, end) {
    if (start > end) {
      return false;
    } else if (start === end) {
      return start;
    }
    const split = (start + end) / 2;
    const count = arr.reduce((last, val) => {
      return last + +(val >= start && val <= split);
    }, 0);
    if (count > split - start + 1) {
      countRange(arr, start, split);
    } else {
      countRange(arr, split + 1, end);
    }
  }
  return countRange(arr, 0, arr.length);
}

二维数组中的查找

前提：数组的每一行和每一列都递增

贪婪算法，从右上角开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function find(arr, val) {
  if (!arr || !arr.length) {
    return false;
  }
  let [rows, columns] = [arr.length, arr[0].length];
  if (!rows || !columns) {
    return false;
  }
  let [x, y] = [columns-1, 0]
  while(x > 0 && y < rows) {
    if (arr[y][x] === val) {
      return true;
    } else if (arr[y][x] > val) {
      x--;
    } else {
      y++;
    }
  }
  return false;
}

替换字符串中的空格

JavaScript中很好实现，可以直接使用库函数。

1
2
3
function replace(str) {
  return str.replace(" ", "%20");
}

使用传统方法，思路是先从前到后找到空格数，扩展出足够空间。再使用两个指针，从后到前，P1指向旧字符串的末尾，P2指向新字符串的末尾。碰到空格时，P2插入”%20”。碰到其他字符时，挨个复制即可。

这种双指针从后向前的思维还可以用在两有序数组合并。从尾到头比较A1和A2数字。

链表设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// 单向链表
let LinkedList2 = (function() {
  class Node {
    constructor(element) {
      this.element = element;
      this.next = null;
    }
  }
  class LinkedList {
    constructor() {
      this.length = 0;
      this.head = null;
    }
    append(element) {
      let node = new Node(element);
      if (this.head === null) {
        this.head = node;
      } else {
        let curr = this.head;
        while(curr.next) {
          curr = curr.next;
        }
        curr.next = node;
      }
      this.length++;
    }
    insert(pos, element) {
      if (pos < 0 || pos > this.length) {
        return false;
      }
      let curr = this.head,
          node = new Node(element);
      while(--pos >= 0) {
        curr = curr.next;
      }
      node.next = curr.next;
      curr.next = node;
      this.length++;
    }
    remove(pos) {
      if (pos < 0 || pos > this.length) {
        return false;
      }
      let curr = this.head;
          prev;
      while(--pos >= 0) {
        prev = curr;
        curr = curr.next;
      }
      if(isUndefined(prev)) {
        this.head = null;
      } else {
        prev.next = curr.next;
      }
      this.length--;
    }
    indexOf(element) {
      let curr = this.head,
          index = 0;
      while (curr) {
        if (element === curr.element) {
          return index;
        }
        index++;
        curr = curr.next;
      }
      return -1;
    }
  }
})();
// 双向链表
// 略

从尾到头打印链表

前提：单向链表。使用递归

1
2
3
4
5
6
7
function recursivePrint(node) {
  if (node && node.next) {
    console.log(recursivePrint(node.next));
  } else {
    console.log(node.element);
  }
}

重建二叉树

前提：根据前序和中序遍历的结果。

1
2
3
4
5
6
7
class BinaryTreeNode {
  constructor(element, left, right) {
    this.element = element;
    this.left = left;
    this.right = right;
  }
}

通过前序遍历找到根节点，结合中序遍历找到左右子树，之后递归构建左右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function constructTree(preorder, inorder) {
  if (preorder.length === 0) {
    return null;
  }
  function construct(preorder, inorder) {
    // 找到根节点元素
    let root = preorder[0];
    // 确定左右子树
    let index = inorder.indexOf(root),
        left = (index === 0 ? null : construct(preorder.slice(0, index), inorder.slice(0, index)));
        right = (index === inorder.length-1 ? null : construct(preorder.slice(index+1), inorder.slice(index+1)));
    return new BinaryTreeNode(root, left, right);
  }
  return construct(preorder, inorder);
}

二叉树的下一个节点

前提：树的每个节点除了有两个子节点的指针，还有一个指向父节点的指针。寻找中序遍历的下一个节点。

1
2
3
4
5
6
7
8
class BinaryTreeNode {
  constructor(element, left, right, parent) {
    this.element = element;
    this.left = left;
    this.right = right;
    this.parent = parent;
  }
}

二叉树中的节点和周围节点可能有四种关系（画图出来更直观）

  1. 左子树的父节点
  2. 右子树的父节点
  3. 父节点的左子树
  4. 父节点的右子树

从而有下面的流程：

  1. 关系2存在时，返回右子树的最左节点，否则到步骤2
  2. 关系3存在时，返回父节点，否则到步骤3
  3. 关系4存在时，向上回溯，对父节点使用步骤2，否则到步骤4
  4. （节点是根节点）返回null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function findNextNode(node) {
  let curr;
  if (node.right) {
    curr = node.right;
    while(curr = curr.left) {
      ;
    }
    return curr;
  } else if (node.parent) {
    if (node.parent.left === node) {
      return node.parent;
    } else if (node.parent.right === node) {
      curr = node.parent;
      while (curr.parent && curr.parent.right === curr) {
        curr = node.parent;
      }
      if (curr.parent) {
        return curr.parent;
      }
    }
  } else {
    return null;
  }
}

用两个栈实现队列

前提，实现append和delete功能，完成在队尾插入和队首删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Stack {
  constructor() {
    this.stack = []
  }
  get size() {
    return this.stack.length;
  }
  push(element) {
    return this.stack.push(element);
  }
  pop() {
    return this.stack.pop();
  }
}

思路，栈1只允许正序存放，栈2只允许倒序存放，由于栈2的内容始终较老，因此插入总发生在栈1。删除总发生在栈2（栈2为空时除外）。JS中没有泛型的概念，所以无需考虑栈中的数据类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Queue {
  constructor() {
    this.stack = new Stack();
    this.inverseStack = new Stack();
  }
  append(element) {
    this.stack.push(element);
    return this.stack.size + this.inverseStack.size;
  }
  delete() {
    if (!this.inverseStack.size) {
      while (!this.stack.size) {
        this.inverseStack.push(this.stack.pop());
      }
    }
    // 判断是否为空
    if (!this.inverseStack.size) {
      return this.inverseStack.pop();
    }
    console.warn("Empty queue!");
    return false;
  }
}

用两个队列实现栈

前提同上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Queue {
  constructor() {
    this.queue = []
  }
  get size() {
    return this.stack.length;
  }
  in(element) {
    return this.stack.push(element);
  }
  out() {
    return this.stack.shift();
  }
}

思路和上面类似，但不大一样。每次元素出队时，所有元素一定会转移到另一个队列中。因此，插入和删除一定发生在有元素的队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Stack {
  constructor() {
    this.queue = new Queue();
    this.backupQueue = new Queue();
  }
  append(element) {
    if (queue.size) {
      queue.in(element);
      return queue.size;
    } else {
      backupQueue.in(element);
      return backupQueue.size;
    }
  }
  delete() {
    if (queue.size) {
      let element;
      while(queue.size > 1) {
        element = queue.out();
        backupQueue.in(element);
      }
      return queue.out();
    } else if(backQueue.size > 1) {
      let element;
      while(backupQueue.size) {
        element = backupQueue.out();
        queue.in(element);
      }
      return backupQueue.out();
    }
    console.warn("Empty stack!");
  }
}

斐波那契数列

使用递归的代码好写，但是效率低；使用循环更好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function fibonacci(n) {
  if (n < 2) {
    return n;
  }
  let a = 0,
      b = 1,
      res = 1;
  for (let i = 2; i <= n; i++) {
    [res, a, b] = [a + b, b, res];
  }
  return res;
}

变种还有“青蛙跳台阶”等类最优子问题的问题。

旋转数组的最小数字

前提，将数组开头的部分元素搬运到数组的末尾，寻找最小的元素。

使用二分查找，右半边递增时，最小元素在左半边。左半边递增时，最小元素在右半边。注意下面两种情况：

  • 数组未做旋转
  • 旋转后，头尾元素相等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function findMin(arr) {
  if (!arr || !.arr.length) {
    return;
  }
  let lindex = 0,
      rindex = arr.length - 1,
      res = lindex;
  while (arr[lindex] >= arr[rindex]) {
    if (rindex - lindex === 1) {
      res = rindex;
    }
    res = (lindex + rindex) / 2;
    // 特殊情况
    if (arr[res] == arr[lindex] && arr[res] == arr[rindex]) {
      return arr.reduce((min, val) => {
        return Math.min(min, val);
      }, arr[0]);
    }
    if (arr[res] >= arr[lindex]) {
      lindex = res;
    } else if (arr[res] <= arr[rindex]) {
      rindex = res;
    }
  }
  return arr[res];
}

回溯法

通常适合用递归法实现，到达某个节点时，尝试所有可能，并在满足条件时递归到下一节点。

矩阵中的路径

前提，判断矩阵中有无一条不交叉路径能够返回指定字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function hasPath(arr, str) {
  if (!arr || !arr.length || !str) {
    return false;
  }
  // 使用数组记录历史数据，防止交叉
  let occupied = arr.map(() => {
    return arr[0].map(() => {
      return false;
    });
  });
  let pathMath = function(i, j, str) {
    if (!str) {
      return true;
    }
    if (i < 0 || i >= arr.length || j < 0 || i >= arr[0].length) {
      return false;
    }
    if (str.substr(0, 1) == arr[i][j]) {
      occupied[i][j] = true;
      let newStr = str.substr(1),
          res = pathMath(i-1, j, newStr) || pathMath(i+1, j, newStr) || pathMath(i, j-1, newStr) || pathMath(i, j+1, newStr);
      // 回溯
      if (!res) {
        occupied[i][j] = false;
      }
    }
    return res;
  }
  arr.foreach((val, i) => {
    val.foreach((val, j) => {
      if (pathMatch(i, j, str)) {
        return true;
      }
    });
  });
  return false;
}

机器人的运动范围

前提，m行n列的矩阵，机器人从(0,0)出发不能进入数位和大于k的格子，求能到的格子个数。

思路同上甚至更简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function gridCount(rowCount, colCount, limit) {
  if (limit < 0 || rowCount <= 0 || colCount <= 0) {
    return 0;
  }
  // 使用数组记录历史数据，减少冗余查询
  let walked = [];
  let count = function(row, col) {
    let cnt = 0;
    if (check(row, col)) {
      // 不必还原，减少重复查询
      walked[row * rowCount + col] = true;
      cnt = 1 + count(row-1, col) + count(row+1, col) + count(row, col-1) + count(row, col+1);
    }
    return cnt;
  },
    check = function () {
    return row >= 0 && col >= 0 && !walked[row * rowCount + col] && digitSum(row) + digitSum(col) <= limit;
  },
    digitSum = function(num) {
    let sum = 0;
    while(num > 0) {
      sum += num % 10;
      num /= 10;
    }
    return sum;
  };
  return count(row, col)
}

剪绳子

前提，绳长为整数，切成若干段，使得绳长乘积最大。

类似于《算法导论》里的裁切钢管。首先可以用动态规划。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function cutRope(len) {
  if (len < 4) {
    return len - 2;
  }
  let cut = [0, 1, 2];
  for (let i = 4; i <= len; i++) {
    let max = 0;
    for (let j = 1; j <= i / 2; j++) {
      let mul = cut[j-1] * cut[i-j-1];
      if (max < mul) {
        max = mul;
      }
    }
    cut.push(max);
  }
  return cut[len-1];
}

经过数学推导，n>=5时，2(n-2)>n且3(n-3)>n且2(n-2)>=3(n-3)，因此有最优子问题的解法。根据贪婪算法，应该尽量多切长度为3的绳子段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function cutRope(len) {
  if (len < 4) {
    return len - 2;
  }
  // 多切长度为3的绳子段
  let cntOf3 = len / 3,
      cntOf2 = 1,
      remain = len % 3;
  // 长度为4时，应该切成两个2
  if (remain === 1) {
    cntOf3--;
    cntOf2 = 2;
  }
  return Math.pow(3, cntOf3) * cntOf2
}

位运算

经常用于奇技淫巧。在C风格的解法中常用。JS中应该不常出现。

二进制中1的数目

通过移位操作，需要注意的是，对入参移位容易出现死循环，可以对1进行移位并比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
function numOf1(n) {
  let cnt = 0,
      flag = 1;
  while(flag) {
    if (n & flag) {
      cnt++;
    }
    flag <<= 1;
  }
  return cnt;
}

二进制整数减1相当于右侧0值变成1，最右侧1变成0，此时和原数做按位与，可以消掉最右侧0。利用这个特点可以进一步提高效率。这种思路可以用来解决很多二进制问题。

1
2
3
4
5
6
7
8
9
10
function numOf1(n) {
  let cnt = 0;
  while(n) {
    ++cnt;
    n = (n-1) & n;
  }
  return cnt;
}

数值的整数次方

前提，不得使用库函数，需要考虑大数问题

用类似二分法的思想，由2到4，由4到8，由8到16。时间复杂度O(logn)。同时注意边界情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function pow(base, exp) {
  let isNeg = exp > 0,
      res = 1;
  if (exp == 0) {
    return 1;
  }
  if (base == 0) {
    return 0;
  }
  function unsignedPow(base, exp) {
    if (exp === 0) {
      return 1;
    }
    if (exp === 1) {
      return base;
    }
    let res = unsigned(base, exp >> 1);
    res *= res;
    if (exp & 0x1 === 1) {
      res *= base;
    }
    return res;
  }
  res = unsignedPow(base, Math.abs(exp));
  if (isNeg) {
    res = 1 / res;
  }
  return res;
}

按顺序打印从0到最大的n位数字

大数问题。自定义数据结构实现整数+1操作，或者通过递归for循环依次打印每一位数字，像下面这样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function printNums(n) {
  function print(str, n) {
    if (1 === n) {
      for (let i = 0; i < 10; i++) {
        console.log(str + i);
      }
    } else {
      n--;
      for (let i = 0; i < 10; i++) {
        if (0 === i) {
          print(str, n);
        } else {
          print(str + i, n);
        }
      }
    }
  }
  if (n < 1) {
    return;
  }
  print('', n);
}

删除链表节点

1
2
3
4
5
6
class LinkedListNode {
  constructor(value, next) {
    this.value = value;
    this.next = next
  }
}

O(1)时间删除单向链表中某节点

通常思路，需要从头结点循环找到节点的上一个节点，将它的next属性设置删除节点的next。但是这么做是O(n)的复杂度。更好的方法是，借尸还魂，覆盖当前节点的next节点，然后重设next节点跳过下一节点。

（因为JS中没有指针一说，这种模拟不能完全还原原题的问题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function removeNode(head, node) {
  if (!head || !node) {
    return;
  }
  if (!node.next) { // 不是尾节点
    node.next = node.next.next;
    node.value = node.value;
  } else if (node == head) { // 链表只有一个节点
    head = null;
  } else { // 是尾节点，只能循环
    let n = head;
    while (n.next !== node) {
      n = n.next;
    }
    n.next = null;
  }
}

表示数值的字符串

考察思维的全面性。包括正数负数、小数、科学技术法都要考虑。格式遵循[+|-]?(\d+)(\.\d+)?([e|E][+|-]?\d+)?

1
2
3
4
5
// 正则表达式
/\d/.test(str);
// 类型转换
!isNaN(+str);

JS下解决问题并不如C++自然。下面是C++风格的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
bool judgeUnsignedInt(const char ** str) {
  const char * start = *str;
  while(**str != \0 && **str >= '0' && **str <= '9') {
    ++(*str);
  }
  return *str > start;
}
bool judgeInt(const char ** str) {
  if (**str === '+' || **str === '-') {
    ++(*str);
  }
  return judgeUnisignedInt(str);
}
bool isNumber(const char * str) {
  if (str == null) {
    return false;
  }
  // 先扫描整数部分
  bool res = judgeInt(&str);
  if (*str == '.') {
    ++str;
    // 扫描小数部分
    res = judgeUnsignedInt(&str) || res;
  }
  if (*str == 'e' || *str == 'E') {
    ++str;
    // 扫描指数部分
    res = judgeInt(&str) && res;
  }
  return res && *str == '\0';
}

调整整数数组中奇数和偶数的位置

前提，使得奇数都位于前边，偶数都位于后边。

考虑拓展性，用一个函数作为衡量指标，判断元素应该在前还是在后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function adjustArr(arr, standard) {
  if (!arr || !arr.length || arr.length < 2) {
    return arr;
  }
  let start = 0;
  let end = arr.length - 1;
  while (start < end) {
    while (start < end && !standard(arr[start])) {
      start++;
    }
    while (start < end && standard(arr[end])) {
      end--;
    }
    if (start < end) {
      [arr[start], arr[end]] = [arr[end], arr[start]];
    }
  }
}
// 在后面的标准
function standard (num) {
  return num / 2 == 0;
}

鲁棒性

链表的倒数第K的节点

1
2
3
4
5
6
7
8
9
10
11
class LinkedList {
  constructor(head) {
    this.head = head;
  }
}
class Node {
  constructor(next) {
    this.next = next;
  }
}

考虑鲁棒性：

  • 空数组
  • k超过数组长度
  • k=0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function findLastK(head, k) {
  if (!head || k === 0) {
    return null;
  }
  let flag = head;
  while (--k > 0) {
    if (head.next) {
      head = head.next;
    } else {
      return null
    }
  }
  let res = head;
  while(flag = flag.next) {
    res = res.next;
  }
  return res;
}
当一个指针不足以解决链表的问题时，通常两个指针就可以解决问题

链表中环的入口节点

思路：

  1. 链表中有环存在时，走得快的指针将会追上走得慢的指针。
  2. 确定环的长度k后，让两个指针同速，一个领先k位出发，相遇的位置即是入口

考虑鲁棒性：

  • 无环时
  • 寻找相遇点的时候注意next属性是否存在
  • 头结点为环入口时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
function entryOfLoop(list) {
  if (!list || !list.length || !list.length < 2) {
    return null;
  }
  // 找到相遇位置
  let slow, fast, meet;
  slow = fast = list.head;
  while (!!fast && !!slow) {
    if (fast === slow) {
      meet = fast;
    }
    slow = slow.next;
    fast = fast.next;
    if (!!fast) {
      fast = fast.next;
    }
  }
  // 无环存在时跳出
  if (!!meet) {
    return null;
  }
  // 确定环的长度
  let length = 1;
  let tmpNode = meet.next;
  while (tmpNode !== meet) {
    tmpNode = tmpNode.next;
    length++;
  }
  // 先移动一个指针
  let first = list.head;
  while (length > 0) {
    first = first.next;
    length--;
  }
  // 再移动第二个指针
  let next = list.head；
  while (next !== first) {
    first = first.next;
    next = next.next;
  }
  return first;
}

反转链表

前提：反转链表并输出反转后的头节点。

考虑鲁棒性：

  • 边界情况，如空链表或长度为1的链表
  • 反转过程中链表断裂
1
2
3
4
5
6
7
8
9
10
11
12
13
function reverseList(list) {
  let node = list.head;
  let prev = null;
  while(!!node) {
    if (!node.next) {
      return node;
    }
    node.next = prev;
    prev = node;
    node = node.next;
  }
}

合并两个排序的链表

类似归并排序。

考虑鲁棒性：

  • 空链表
  • 链表长度为1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function merge(list1, list2) {
  if (!list1) {
    return list2;
  } else if (!list2) {
    return list1;
  }
  let node = new Node();
  let list = new List(node);
  let h1 = list1.head;
  let h2 = list2.head;
  for (!!h1 || !!h2) {
    let next;
    if (!!h1 && !h2 || h1.value < h2.value) {
      next = h1.value;
      node = node.next;
      h1 = h1.next;
    } else {
      next = h2.value;
      h2 = h2.next;
    }
    node.next = new Node(next);
    node = node.next;
  }
  list.head = list.head.next;
  return list;
}

树的子结构

前提：判断树A中是否能找到和树B结构一样的子树。

使用递归思路更简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function hasSubTree(heap, needle) {
  function match(root1, root2) {
    if (!root2) {
      return true;
    }
    if (!root1) {
      return false;
    }
    return match(root1.left, root2.left) && match(root1.right, root2.right);
  }
  let root1 = heap.root;
  let root2 = needle.root;
  let res = false;
  if (!root1 && !root2) {
    if (root1.value === root2.value) {
      res = match(root1, root2);
    }
    if (!res) {
      res = hasSubTree(root1.left, root2);
    }
    if (!res) {
      res = hasSubTree(root1.right, root2);
    }
  }
  return res;
}

形象化

二叉树的镜像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function mirrorBinaryTree(root) {
  if (!root) {
    return;
  }
  // 跳过叶子节点
  if (!root.left && !root.right) {
    return;
  }
  [root.left, root.right] = [root.right, root.left];
  if (!!root.left) {
    mirrotBinaryTree(root.left);
  }
  if (!!root.right) {
    mirrotBinaryTree(root.right);
  }
}

对称的二叉树

即前序和对称遍历结果一致。和上面类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function isSymmetrical(root) {
  function judge(root1, root2) {
    if (root1 === null && root2 === null) {
      return true;
    }
    if (root1 === null || root2 === null) {
      return false;
    }
    if (root1.value !== root2.value2) {
      return false;
    }
    return judge(root1.left, root2.right) && judge(root1.right, root2.left);
  }
  return judge(root, root);
}

顺时针打印矩阵

  • 打印一行“删去”一行，打印一列“删去”一列。
  • 最后一圈先向右再向下再向上再向左，根据顺序共有4种可能，通过if语句区分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function printMatrix(matrix) {
  if (!matrix || !matrix.length || !matrix[0].length) {
    return;
  }
  let top = 0;
  let left = 0;
  let bottom = matrix.length - 1;
  let right = (matrix[0].length ? matrix[0].length - 1 : 0);
  while (left <= right && top <= bottom) {
    // 向右
    for (let i = left; i <= right; i++) {
      console.log(matrix[top][i] + ' ');
    }
    top++;
    // 向下
    if (top <= bottom) {
      for (let i = top; i <= bottom; i++) {
        console.log(matrix[i][right] + ' ');
      }
      right--;
    } else {
      return;
    }
    // 向左
    if (left <= right) {
      for (let i = right; i >= left; i--) {
        console.log(matrix[bottom][i] + ' ');
      }
      bottom--;
    } else {
      return;
    }
    // 向上
    if (top <= bottom) {
      for (let i = bottom; i >= top; i--) {
        console.log(matrix[i][left] + ' ');
      }
      left++;
    } else {
      return;
    }
  }
}

剑指offer上的思路是利用每圈的起始x和y坐标相等，判断循环终止条件，再根据条件决定一圈打印几行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
function printMatrix(matrix) {
  if (!matrix || !matrix.length || !matrix[0].length) {
    return;
  }
  function print() {
    let width = column - start - 1;
    let height = rows - start - 1;
    for (let i = start; i <= width; i++) {
      console.log(matrix[start][i]);
    }
    if (start < height) {
      for (let i = 0; i <= height; i++) {
        console.log(matrix[i][width]);
      }
    }
    if (start < width && start < height) {
      for (let i = width-1; i >= start; i--) {
        console.log(matrix[height][i]);
      }
    }
    if (start < width && start < height - 1) {
      for (let i = height-1; i < start+1; i--) {
        console.log(matrix[i][start]);
      }
    }
  }
  let start = 0;
  let rows = matrix.length;
  let column = matrix[0].length;
  while (column > 2 * start && rows > 2 * start) {
    print();
    ++start;
  }
}

包含min函数的栈

前提，设计栈的数据结构，使min、push和pop的时间复杂度都是O(1)。

注意：若使用变量保存最小元素，那么在最小元素出栈后会找不到次小元素。可见只使用一个变量是不够的，为配合原始栈的结构，需要有一个辅助栈记录最小元素的位置。（画图可以很容易理解）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Stack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }
  get min() {
    let len = this.minStack.length;
    return (len ? this.minStack[len-1] : Infinity);
  }
  push(element) {
    this.stack.push(element);
    this.minStack.push(Math.min(this.min, element));
  }
  pop() {
    this.stack.pop();
    this.minStack.pop();
  }
  top() {
    return (this.stack.length ? this.stack[this.stack.length-1] : null);
  }
}

栈的压入、弹出序列

前提：给定栈的压入顺序，判断某个出栈顺序是否可能

通过举例具象化思考。如入栈顺序为[1, 2, 3, 4, 5]，[4, 3, 5, 2, 1]就是一个可能的例子。首先，4是第一个出栈元素，则[1,2,3]此时已经入栈，4出栈后，3位栈顶，出栈后，5不在栈内，将5入栈。剩下的5，2，1同理。因此，可以发现下面规律。

  1. 第一个出栈元素前的入栈序列此时正在栈内
  2. 之后所有的出栈元素，先在栈顶寻找，若有，则出栈；若没有，在栈外元素中寻找
  3. 若找到，将其入栈，若找不到，则返回false
  4. 如此循环直到栈空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function isPopOrder(push, pop) {
  if (push.length !== pop.length) {
    return false;
  }
  if (!push.length) {
    return true;
  }
  // 寻找当前栈内元素
  let first = pop[0];
  let index = push.indexOf(first);
  let stack = [];
  if (index === -1) {
    return false;
  }
  for (let i = 0; i <= index-1; i++) {
    stack.push(push[i]);
  }
  let rest = push.slice(index);
  for (let i = 2, len = pop.length; i < len; i++) {
    let value = pop[i];
    if (!push.length || push[push.length-1] !== value) {
      let index = rest.indexOf(value);
      if (index === -1) {
        return false;
      }
      push.push(value);
      rest.splice(index, 1);
    } else {
      push.pop();
    }
  }
  return true;
}

从上到下打印二叉树

使用队列保证先后顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Queue {
  constructor() {
    this.queue = []
  }
  get length() {
    return this.queue.length;
  }
  in(element) {
    this.queue.push(element);
    return this.queue.length;
  }
  out() {
    return this.queue.shift();
  }
}
function printTreeByTier(root) {
  if (!root) {
    return;
  }
  let q = new Queue();
  q.in(root);
  while(q.length) {
    let node = q.out();
    console.log(node.value);
    if (node.left) {
      q.in(node.left);
    }
    if (node.right) {
      q.in(node.right);
    }
  }
}

进阶：分行从上到下打印二叉树

和上面类似，区别在入队时需要携带层数信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Queue {
  constructor() {
    this.queue = []
  }
  get length() {
    return this.queue.length;
  }
  in(element) {
    this.queue.push(element);
    return this.queue.length;
  }
  out() {
    return this.queue.shift();
  }
}
function printTreeByTier(root) {
  if (!root) {
    return;
  }
  let tier = 0;
  let q = new Queue();
  q.in({
    root,
    tier,
  });
  while (q.length) {
    let node = q.out();
    if (node.tier !== tier) {
      tier = node.tier;
      console.log("换行");
    }
    if (q.root.left) {
      q.in({
        root: q.root.left,
        tier: tier+1,
      })
    }
    if (q.root.right) {
      q.in({
        root: q.root.right,
        tier: tier+1,
      });
    }
  }
}

进阶2：之字形打印二叉树

前提：第一行从左到右打印，第二行从右到左打印，以此类推。

因为每层的顺序都相反，很适合栈存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 栈的数据结构实现略
// ...
function printTreeByZ(root) {
  if (!root) {
    return;
  }
  let stack1 = new Stack();
  let stack2 = new Stack();
  // 当前在哪个栈内
  let curr = 1;
  stack1.push(root);
  while (!stack1.empty() || !stack2.empty()) {
    if (curr == 1) {
      let node = stack1.pop();
      console.log(node.value);
      if (node.left) {
        stack2.push(node.left);
      }
      if (node.right) {
        stack2.push(node.right);
      }
      if (stack1.empty()) {
        curr = 2;
        console.log("换行");
      }
    } else {
      let node = stack2.pop();
      console.log(node.value);
      if (node.right) {
        stack1.push(node.right);
      }
      if (node.left) {
        stack1.push(node.left);
      }
      if (stack2.emtpy()) {
        curr = 1;
        console.log("换行");
      }
    }
  }
}

二叉搜索树的后序遍历序列

前提：判断整数序列是否是某个二叉搜索树的后序遍历序列，并假设所有数字都不相同

利用二叉搜索树的特点，结合后序遍历时尾元素为根节点，递归判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function verifySeqOfBST(seq) {
  if (!seq || seq.length <= 0) {
    return false;
  }
  let len = seq.length;
  let root = seq[len-1];
  // 找到右子树的起点
  let rightIndex = seq.findIndex((element) => {
    return element > root;
  });
  // 右子树的节点需要都大于左节点
  if (rightIndex == -1 || seq.slice(rightIndex).every((element)=>{ return element > root; })) {
    return false;
  }
  // 递归判断左右子树
  let left = rightIndex <= 0 || verifySeqOfBST(seq.slice(0, rightIndex));
  let right = rightIndex == -1 || verifySeqOfBST(seq.slice(rightIndex));
  return left && right;
}

二叉树中和为某值的路径

前提：找到所有满足要求的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function findPaths(root, target) {
  let path = [];
  let sum = 0;
  let node = root;
  // 利用闭包共享变量
  let find = () => {
    path.push(node);
    sum += node.value;
    if (sum === target) {
      console.log(path)
    }
    if (node.left) {
      node = node.left;
      find();
    }
    if (node.right) {
      node = node.right;
      find();
    }
    // 不要忘了弹出栈顶元素
    path.pop();
  }
  find();
}

分解

复杂链表的复制

前提：复杂链表中每个节点除了一个指向下个节点的指针外，还有一个指向任意节点的指针

1
2
3
4
5
6
7
class ComplexLinkedListNode {
  constructor({value, next, extra}) {
    this.value = value;
    this.next = next;
    this.extra = extra;
  }
}

困难在extra属性的复制，在O(n)的时间复杂度，O(1)的空间复杂度的要求下，问题可以分解成3步

  1. 在每个原始节点后接上复制节点
  2. 原样复制extra属性
  3. 将复制的链表拆出来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function copyLinkedList(head) {
  if (!head) {
    return null;
  }
  let node = head;
  // Step1: 在每个节点后添加一个复制节点
  while (node) {
    node.next = new ComplexLinkedListNode()({
      value: node.value,
      next: node.next
    });
    node = node.next;
  }
  // Step2: 复制每个节点的extra属性
  node = head;
  while (node) {
    // 这一步大大减少了时间复杂度
    node.next.extra = node.extra.next;
    node = node.next.next;
  }
  // Step3: 拆开两条链
  node = head
  let newNode = new ComplexLinkedListNode();
  while (node) {
    newNode.next = node.next;
    node.next = node.next.next;
    node = node.next;
    newNode = newNode.next;
  }
  return newNode.next;
}

二叉搜索树和双向链表

前提：将一个二叉搜索树转换成一个排序的双向链表，不允许新建节点。

一般涉及到树结构的问题，使用递归都要更直观方便。本题中，可以把问题拆解成，将根节点和已组装好的左右双向链表组装。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function transBSTToBilink(root) {
  if (!root) {
    return;
  }
  let split = (root, type) => {
    let node = new Node(root.value);
    let left = node;
    let right = node;
    if (root.left) {
      left = split(root.left, 'left');
      left.next = node;
      node.next = left;
    }
    if (root.right) {
      right = split(root.right, 'right')
      node.next = right;
      right.next = node;
    }
    // 通过type区分当前是左子树还是右子树，从而返回最大点或最小点
    return (type === 'left' ? right : left);
  }
  split(root);
}

序列化二叉树

要求：实习序列化和反序列化函数

通常情况需要两种遍历序列才能还原二叉树，这是因为二叉树非完全。对空缺的节点使用特殊字符，即可消除二义性，使用单一遍历序列还原二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class BinaryTree {
  // ...
}
BinaryTree.serialize = (root) => {
  let str = [];
  let serialize = (root) => {
    if (!root) {
      str.push('$');
      return;
    }
    str.push(root.value);
    serialize(root.left);
    serialize(root.right);
  });
  serialize(root);
  return str.join('');
}
BinaryTree.parse = (str) => {
  if (!str) {
    return null;
  }
  let i = 0;
  let len = str.length;
  let parse = (str) => {
    if (str[i] === '$') {
      return null;
    }
    let root = new Node(+str[i]);
    // 最后一个节点必是叶节点
    ++i, root.left = parse(str);
    ++i, root.right = parse(str);
    return root;
  }
  return parse(str);
}

字符串的排列

前提：不考虑重复字符的问题
要求：输入一个字符串，输出字符串中字符的所有排列

此题可以用递归，《剑指offer》上的解法简单易行。JS中对字符串的限制（只读）使得代码和C风格有别。这里我们考虑输入是一个字符数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function combinations(str) {
  if (!str.length) {
    return;
  }
  let len = str.length
  function combine(comb, strs, start) {
    if (start === len - 1) {
      console.log(comb + strs[start]);
    }
    for (let i = start; i < len; i++) {
      [strs[start], strs[i]] = [strs[i], strs[start]];
      // 需要通过slice方法传递复制
      combine(comb + strs[start], strs.slice(), start+1);
    }
  }
  combine('', str, 0);
}

求字符串的组合（也可以叫求子集）

总共的解数目为$2^n$。从最低位开始，向上寻找时，有两种可能：新字符不出现，新字符出现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function subsets(str) {
  if (!str.length) {
    return;
  }
  function reduce(res, i) {
    if (i === str.length-1) {
      console.log(res + str[i]);
      console.log(res);
      return;
    }
    reduce(res+str[i], i+1);
    reduce(res, i+1);
  }
  reduce('', 0)
}

输入8个数字的数组放在正方体的8个顶点，有无可能每对面对应的4个顶点和相等

相等于寻找全排列，使得a1+a2+a3+a4=a5+a6+a7+a8，且a1+a3+a5+a7=a2+a4+a6+a8，且a1+a2+a5+a6=a3+a4+a7+a8。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function findComb(nums) {
  let len = nums.length;
  function combine(nums, start) {
    if (start === len-1) {
      if(test(nums)) {
        console.log(nums);
      }
    }
    for (let i = start; i < len; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]];
      combine(nums.slice(), start + 1);
    }
  }
  function test(nums) {
    return nums[0] + nums[1] + nums[2] + nums[3] == nums[4] + nums[5] + nums[6] + nums[7] &&
        nums[0] + nums[2] + nums[4] + nums[5] == nums[1] + nums[3] + nums[5] + nums[7] &&
        nums[0] + nums[1] + nums[6] + nums[7] == nums[2] + nums[3] + nums[4] + nums[5];
  }
  combine(nums, 0);
}

8皇后问题

8皇后的限制条件在，不得同行同列，不得位于同一对角线。因此，为长度为8的数组初始化填入1~8，代表行数。填入的数代表列数，因为每行每列都只有一个皇后。所以全排列中，只需要删除满足下面条件的排列即可：

  • i-j != columns[i] - columns[j]且j-i != columns[i] - columns[j]，即不在一个对角线上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function eightQueens() {
  let count = 0;
  function combine(queens, start) {
    if (start === 7) {
      console.log(queens);
      count++;
    }
    for (let i = start; i < 8; i++) {
      [queens[start], queens[i]] = [queens[i], queens[start]];
      if (test(queens, start)) {
        combine(queens.slice(), start+1);
      } else {
        [queens[start], queens[i]] = [queens[i], queens[start]];
      }
    }
  }
  function test(queens, end) {
    for (let i = 0; i < end; i++) {
      let diff = queens[end] - queens[i];
      if (diff == end - i || -diff == end - i) {
        return false;
      }
    }
    return true;
  }
  combine([0,1,2,3,4,5,6,7], 0);
  console.log(count);
}

这种思路会带来重复的解，按照Matrix67的思路，可以通过位运算求解。使用row（列占用情况），ld（左下右上对角线占用），rd（右下左上对角线占用）三个变量存储当前列的禁用情况。使用“1”表示禁用，“0”表示可用。解决n皇后的问题代码仅在10行左右。详细解释见链接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function nQueens(n) {
  if (!n || n <= 0) return;
  let limit = (1 << n) - 1, sum = 0;
  function queen(row, ld, rd) {
    if (row !== limit) {
      let pos = limit & ~(row | ld | rd);
      while (pos) {
        let p = pos & -pos; // 得到最右侧可放子的位置
        pos -= p; // 除去这个位置
        queen(row|p, (ld|p) << 1, (rd|p) >> 1)
      }
    } else sum++;
  }
  queen(0, 0, 0);
  return sum;
}

时间效率

数组中出现次数超过一半的数字

思路1：超过一半的数组一定出现在中位数的位置，结合快排的思想，找到中位数
思路2：遍历所有数字，遇到与major相同的元素时，计数器+1，反之-1。计数器为0时，更换major。返回最后的major

注意：最后需要检查数组是否有满足条件的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function findMajor(nums) {
  if (!nums.length) {
    return;
  }
  let major;
  times = 0;
  nums.forEach((num) => {
    if (times === 0) {
      major = num;
      times = 1
    } else if (num === major) {
      times++;
    } else {
      times--;
    }
  });
  if (nums.reduce((sum, num) => { return sum + (num === major); }, 0) * 2 > nums.length) {
    return major;
  }
}

最小的k个数

同样的两种思路：

  1. 利用快排的中的partition，找到前k个数，时间复杂度O(n)，但是会修改数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    function partition(arr, start, end) {
      if (start >= end) {
        return;
      }
      let index = start -1;
      let split = arr[end];
      for (let i = start; i < end; i++) {
        if (arr[i] < split) {
          index++;
          if (i != index) {
            [arr[i], arr[index]] = [arr[index], arr[i]];
          }
        }
      }
      index++;
      arr[end] = arr[index];
      arr[index] = split;
      return index;
    }
    function minKNums(nums, k) {
      if (!nums || k <= 0) {
        return;
      }
      if (k >= nums.length) {
        return nums;
      }
      let start = 0,
          end = nums.length - 1,
          index = partition(nums, start, end);
      while(index != k-1) {
        if (index > k-1) {
          end = index - 1;
        } else {
          start = index + 1;
        }
        index = partition(nums, start, end);
      }
      console.log(nums.slice(0, k));
    }

  2. 维护一个排序的长度为k的数据容器，当容器满时，根据容器最大值更新容器，时间复杂度O(nlogk)，空间复杂度O(k)，但是在k较小时，性能很接近

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class MinSet {
  constructor() {
    //...
  }
  get max() {
    //...
  }
  get len() {
    //...
  }
  input(element) {
    //...
  }
  remove(element) {
    //...
  }
  toString() {
  }
}
function minKNums(nums, k) {
  if (!nums || k <= 0) {
    return;
  }
  if (k >= nums.length) {
    return nums;
  }
  let set = new MinSet();
  nums.forEach(num => {
    if (set.len === k) {
      if (set.max.value > num) {
        set.remove(set.max);
        set.input(num);
      }
    } else {
      set.input(num);
    }
  });
  set.toString();
}

数据流的中位数

使用二叉树、最大堆最小堆完成。保证最大堆和最小堆的数目差不超过1即可。当然，首先要实现最大和最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
function inherit(son, father) {
  let prototype = Object.create(father.prototype);
  prototype.constructor = son;
  son.constructor = prototype;
}
function Heap() {
  this.heap = [];
}
Heap.prototype.parent = function(i) {
  return (i+1) / 2 - 1;
}
Heap.prototype.left = function(i) {
  return 2 * i + 1;
}
Heap.prototype.right = function(i) {
  return 2 * i + 2;
}
Heap.prototype.size = function() {
  return this.heap.length;
}
function MinHeap() {
  Heap.call(this);
  function minify(index) {
    let l = this.left(index),
        r = this.right(index),
        size = this.length;
    if (l < size && this.heap[l] < this.heap[index]) {
      i = l;
    } else {
      i = index;
    }
    if (r < size && this.heap[r] < this.heap[i]) {
      i = r;
    }
    if (i != index) {
      [this.heap[index], this.heap[i]] = [this.heap[i], this.heap[index]];
      minify(i);
    }
    return;
  }
  this.add = function(num) {
    this.heap.push(num);
    minify(this.heap.length / 2 - 1);
  }
  this.shift = function() {
    let num = this.heap.shift();
    minify(this.heap.length / 2 - 1);
    return num;
  }
  this.top = function() {
    return this.heap[0];
  }
}
inherit(MinHeap, Heap);
function MaxHeap() {
  Heap.call(this);
  function maxify(index) {
    //... 同上
  }
  this.add = function(num) {
    //... 同上
  }
  this.shift = function() {
    let num = this.heap.shift();
    maxify(this.heap.length / 2 - 1);
    return num;
  }
  this.top = function() {
   //... 同上
  }
}
/* 借助上面的MinHeap和MaxHeap实现 */
function DynamicArray() {
  this.min = new MinHeap();
  this.max = new MaxHeap();
}
DynamicArray.prototype.insert = function(num) {
  let minSize = this.min.size(),
      maxSize = this.max.size();
  if (minSize === maxSize) {
    this.min.add(num);
    // 插入在最小堆，但是数字在最大堆的范围
    if (maxSize > 0 && num < this.max.top()) {
      this.max.add(this.min.shift());
    }
  } else {
    this.max.add(num);
    // 同理，插入在最大堆，但是数字在最小堆的范围
    if (minSize > 0 && num < this.min.top()) {
      this.min.add(this.max.shift());
    }
  }
}
DynamicArray.prototype.getMedian = function() {
  let size = this.min.size() + this.max.size();
  if (!size) {
    console.warn('Empty array.');
  }
  if (size & 0x01) {
    return this.min.top();
  } else {
    return (this.min.top() + this.max.top()) / 2;
  }
}

连续子数组的最大和

前提：数组由正负数组成。

经典的动态规划问题。用双指针的方法，采用贪婪算法，用f[i]表示以第i位结尾的最大和，当f[i-1]<=0时，可以抛弃之前的和，以当前元素为f[i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function maxSum(nums) {
  if (!nums.length) {
    return;
  }
  let len = nums.length;
  let res = nums[0];
  for (let i = 1; i < len; i++) {
    if (res <= 0) {
      res = nums[i];
    } else {
      res += nums[i];
    }
  }
  return res;
}

1~n整数中1出现的次数

这种数学题，多半会有找规律的简单方法。普通的方法是，逐个寻找每个数字中1出现的次数，时间复杂度O(nlogn)。逐位寻找1出现的次数，再累加，时间复杂度可以降至O(logn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function numOf1(num) {
  function count(str) {
    let first = str[0];
    let len = str.length;
    if (str.length === 1) {
      return first > 0;
    }
    // 第一位中1出现的次数
    let firstCount = 0;
    if (first > 1) {
      firstCount = Math.pow(10, len-1);
    } else if (first == 1) {
      firstCount = +str.substr(1) + 1;
    }
    // 剩下的位数可以通过排列组合计算
    let otherCount = first * (len - 1) * Math.pow(10, len-2);
    return firstCount + otherCount + count(str.substr(1));
  }
  if (num < 1) {
    return 0;
  }
  let numStr = `${num}`;
  count(numStr);
}

数字序列中某一位的数字

前提：数字以0123456789101112131415...的格式序列化

需要找到规律。1位数占用10位，2位数占用180位，3位数占用2700位，……，n位数占用9 * (10 ^ n)位。通过循环确定位数后，对n取余，能知道是n位数第几个数的第几位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function findKthDigit(k) {
  function countInDigits(n) {
    return (n === 1 ? 10 : 9 * Math.pow(10, n-1));
  }
  // 第m个n位数的第k位
  function find(n, m, k) {
    // 找到n位数的起始
    let start = Math.pow(10, n - 1);
    let num = start + m;
    return num / Math.pow(10, n - k - 1);
  }
  if (k < 0) {
    return -1;
  }
  let digits = 1;
  while (k >= countInDigits(digits)) {
    k -= countInDigits(digits++);
  }
  return find(digits, k / digits, k % digits);
}

把数组排成最小的数

要求：拼接数组中的数，使之最小

此题的思路在拓展排序的规则。当组合mn < nm时，说明m应该在前，即元素间的比较准则是mn和nm的大小关系。注意大数问题，应该比较字符串。

1
2
3
4
5
function minComb(nums) {
  nums.sort((a, b) => {
    return ('' + a + b > '' + b + a ? 1 : -1);
  });
}

把数字翻译成字符串

前提：0翻译成‘a’，1翻译成‘b’，逐位进行翻译，有时会有多种结果
要求：求可能的结果数目

动态规划，避免重复解决子问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function translateCount(numStr) {
  if (!numStr || +numStr < 0) {
    return 0;
  }
  let count;
  let counts = [];
  for (let i = numStr.length - 1; i >= 0; i--) {
    if (i === numStr.length) {
      count[i] = 1;
      continue;
    }
    count = count[i+1];
    let comb = +(count[i] + count[i+1]);
    if (comb <= 25 && comb >= 10) {
      count += (i < numStr.length - 2 ? counts[i+2] : 1);
    }
    count[i] = count;
  }
  return count[0];
}

礼物的最大价值

前提：从mn的格子中拿礼物，从左上角开始，每次向下或向右取一格，直到右下角
*要求：礼物价值总和最大

和上面的思路很类似，通过循环替代递归。比带有备忘录的递归更省时间和空间。坐标是(i, j)的格子最大总和只取决于(i-1, j)和(i, j-1)。因此可以用一维数组代替二维数组，减少空间使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function getMaxValue(nums) {
  if (!nums.length || !nums[0].length) {
    return 0;
  }
  let row = nums[0];
  let rows = nums.length;
  let columns = nums[0].length;
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < columns; j++) {
      let up = (i > 0 ? row[j] : 0)
      let left = (j > 0 ? row[j-1] : 0);
      row[j] = Math.max(left, up) + nums[i][j];
    }
  }
  return row[columns - 1];
}

最长的不包括重复字符的子字符串

要求：返回字符串的长度

用类似动态规划的思路，借助之前的结果递推。同时，使用Object存储对应字符上次出现的位置，可以保证O(n)的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function longestSubStrWithDup(str) {
  if (!str.length || str.length < 2) {
    return str.length;
  }
  let pos = {};
  let strArr = Array.from(str);
  let maxLen = 0;
  let curLen = 0;
  strArr.forEach((char, num) => {
    // 此前未出现过或出现在当前最长子字符串之外
    let position = pos[char];
    if (typeof position !== 'undefined' || position + curLen < i) {
      curLen++;
    } else {
      // 出现在此前的最长子字符串中时，需要更新长度值
      if (curLen > maxLen) {
        maxLen = curLen;
      }
      curLen = i - position;
    }
    // 更新位置
    pos[char] = i;
  })；
  if (curLen > maxLen) {
    maxLen = curLen;
  }
  return maxLen;
}

丑数

前提：丑数是指只包含因子2、3、5的数。求给定位置的丑数

普通的思路是通过循环依次判断数字是否为丑数直到找到。在允许空间消耗时，我们用数组去存储所有的丑数，并不断更新数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function uglyNum(k) {
  if (k <= 0) {
    return 0;
  }
  let count = 1;
  let ugly = [1];
  let ugly2 = 0;
  let ugly3 = 0;
  let ugly5 = 0;
  while(count < k) {
    uglynums.push(Math.min(ugly[ugly2]*2, ugly[ugly3]*3, ugly[ugly5]*5));
    while (ugly[ugly2]*2 <= ugly[count]) {
      ugly2++;
    }
    while (ugly[ugly3]*3 <= ugly[count]) {
      ugly3++;
    }
    while (ugly[ugly5]*5 <= ugly[count]) {
      ugly5++;
    }
    count++;
  }
  return ugly.pop();
}

第一个只出现一次的字符

哈希表，JavaScript中使用Object即可。第一次扫描时去除所有重复元素，第二次扫描时，打印第一个字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function firstUniqueChar(str) {
  let strArr = Array.from(str);
  let chars = {};
  strArr.forEach(char => {
    if (!chars[char]) {
      chars[char] = 1;
    } else {
      chars[char]++;
    }
  });
  strArr.forEach(char => {
    if (chars[char] === 1) {
      return char;
    }
  });
  return false;
}

类似问题都可以用哈希表解决。

数组中的逆序对

逆序对的存在是数组未排序的结果。因此使用排序算法得到交换元素的次数即可。最直观的使用冒泡排序，时间复杂度为O(n^2)。使用归并和快排可以达到O(nlogn)的时间复杂度。

略。

两个链表的第一个公共节点

因为链表从交汇节点后拥有相同的节点，所以，从后向前回溯，直到节点不同为止即可。时间复杂度O(m+n)，空间复杂度O(m+n)。若不使用辅助栈，空间复杂度还可降至O(1)。

1
2
3
4
5
6
7
8
9
10
11
function findFirstCommonNode(list1, list2) {
  if (!list1 || !list2) {
    return false;
  }
  // 遍历list1和list2到尾节点
  // ...
  // 向前回溯直到节点不同
  // ...
}

排序数组中查找数字（二分查找）

排序数组中数字出现的次数

思路是，查找到数字第一次出现的地方和最后一次出现的地方。通过二分法查找，数字较小时，在右半边；较大时，在左半边；相等时判断左/右是否还有该元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
function numOfK(arr, k) {
  if (!arr.length) {
    return 0;
  }
  function findFirst(start, end) {
    if (start > end) {
      return -1;
    }
    let middle = (start + end) / 2;
    let median = arr[middle];
    if (median < k) {
      start = middle + 1;
    } else if (median > k) {
      end = middle - 1;
    } else {
      if (middle > 0 && arr[middle-1] === median) {
        end = middle - 1;
      } else {
        return middle;
      }
    }
    return findFirst(start, end);
  }
  function findLast(start, end) {
    if (start > end) {
      return -1;
    }
    let middle = (start + end) / 2;
    let median = arr[middle];
    if (median < k) {
      start = middle + 1;
    } else if (median > k) {
      end = middle - 1;
    } else {
      if (middle < arr.length-1 && arr[middle+1] === median) {
        start = middle + 1;
      } else {
        return middle;
      }
    }
    return findLast(start, end);
  }
  let first = findFirst(0, arr.length-1);
  let last = findLast(0, arr.length-1);
  if (findFirst() === -1) {
    return 0;
  }
  return last - first + 1;
}

寻找从0~n-1中缺少的数字

数组事先排序时，借助二分法查找，时间复杂度O(logn)；未排序时，通过求和和n(n-1)/2求差得出（不考虑大数问题的话）。中间元素和下标相等时，在右半边寻找；不相等时，若左侧元素相等，则返回该元素，左侧元素不等时，在左半边寻找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function findLeftNum(arr) {
  let len = arr.length;
  if (!len || len < 2) {
    return;
  }
  let left = 0;
  let right = len - 1;
  while (left <= right) {
    let middle = (left + right) >> 1;
    if (arr[middle] === middle) {
      left = middle + 1;
    } else {
      if (middle > 0 && arr[middle-1] !== middle-1) {
        right = middle - 1;
      } else {
        return middle;
      }
    }
  }
  if (left > right) {
    return len;
  }
}

数组中和下标相等的元素

前提：数组元素都为整数，且单调递增。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function numsEqualsToIndex(nums) {
  if (!nums.length) {
    return -1;
  }
  let left = 0,
      right = nums.length-1;
  while (left <= right) {
    let mid = (left + right) >> 1;
    if (nums[mid] === mid) {
      return mid;
    }
    if (nums[mid] > mid) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
  return -1;
}

二叉搜索树的第k大的节点（遍历）

利用二叉搜索树的中序遍历的特点，找到第k大的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function findKthNode(root, k) {
  if (k < 1 || !root) {
    return null;
  }
  let res = null;
  if (root.left) {
    res = findKthNode(root.left, k);
  }
  if (res === null) {
    if (k === 1) {
      res = root;
    }
    k--;
  }
  if (root.right) {
    res = findKthNode(root.right, k);
  }
  return res;
}

二叉树的深度

使用递归，比较左右子树的深度，取较大值。

1
2
3
4
5
6
7
8
9
10
function treeDepth(root) {
  if (!root) {
    return 0;
  }
  let left = treeDepth(root.left);
  let right = treeDepth(root.right);
  return Math.max(left, right) + 1;
}

判断一棵树是否是平衡二叉树

可以使用上面的思路，递归判断除叶节点外每个节点的左右子树深度。但是这样会重复遍历节点。但是如果使用后序遍历，就可以先遍历左右子树，再回到根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function isBalanceTree(root) {
  function tree(root) {
    if (!root) {
      return {
        depth: 0,
        flag: true
      };
    }
    let left = tree(root.left);
    let right = tree(root.right);
    if (left.flag && right.flag) {
      let diff = left.depth - right.depth;
      if (diff <= 1 && diff >= -1) {
        return {
          depth: 1 + Math.max(left.depth, right.depth),
          flag: true
        };
      }
    }
    return {
      flag: false
    };
  }
  tree(root);
}

数组中数字出现的次数（位运算）

在数组中找到唯二两个只出现一次的元素

前提：数组中其他元素都出现两次。

还是使用异或，不过这次异或的结果是两个数组的异或结果。找到结果中第一位1，说明这一位两个数不同，据此将数组分成两部分，分别异或，得到最终结果。时间复杂度O(n)，空间复杂度O(1)。

1
2
3
4
5
6
7
8
9
10
function find2UniqueNums(nums) {
  let sum = nums.reduce((sum, cur) => sum ^ cur);
  let index = sum & -sum;
  let nums1 = nums.filter(num => num & index);
  let nums2 = nums.filter(num => !num & index);
  return {
    unique1: nums1.reduce((sum, cur) => sum ^ cur);
    unique2: nums2.reduce((sum, cur) => sum ^ cur);
  },
}

在数组中找到唯一一个出现一次的数字

前提：其余数字都出现3次。

使用和上面类似的思路，使用二进制表示每一个数，用数组存储各位1出现的和，累加后，将每一位数字对3取余，得到的数字就是结果的二进制表示。

略

和为s的若干数字（双指针）

2个数

前提：数组是单调递增的。因此可以在头尾放两个指针，向中间靠拢，逼近最终结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function sumS(nums, s) {
  let len = nums.length;
  if (!len || len < 3) {
    return [];
  }
  let left = 0;
  let right = len - 1;
  while (left < right) {
    let sum = nums[left] + nums[right];
    if (sum === s) {
      return [nums[left], nums[right]];
    } else if (sum < s) {
      left++;
    } else {
      right--;
    }
  }
  return [];
}

正数序列

前提：打印出和为s的连续正数序列，长度最少为1。

若使用双指针，需要先确定上下界。这里的序列起始的上界为n/2，下界是1。然后使用类似的方法，确定起始后，后移后界求序列。时间复杂度O(n^2)。然而，实际上，确定下界后，连续正数序列和与序列长度满足函数关系f(m, n) = (m + n)(n - m + 1) / 2（其中m为起始值，n为截止值）。问题变成了检验后界是否满足一元二次方程组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function sumSSeq(s) {
  if (s < 3) {
    return;
  }
  function print(i, j) {
    for (let index = i; index <= j; index++) {
      console.log(index);
    }
  }
  for (let i = 1, limit = Math.floor(s/2); i <= limit; i++) {
    let j = i+1;
    while (j <= limit+1) {
      let sum = (i + j) * (j - i + 1) / 2;
      if (sum >= s) {
        if (sum === s) {
          print(i, j);
        }
        break;
      }
      j++;
    }
  }
}

翻转字符串（多次翻转）

翻转单词的顺序

要求：翻转一句话中所有单词的顺序。

此题可以先翻转所有字符，再翻转每个单词内的字符顺序。

1
2
3
function reverseByWord(sentence) {
  return sentence.split(' ').reverse().join(' ');
}

左旋转字符串

要求：将字符串头部的若干字符转移到字符尾部。

使用类似上面的思路，可以不用substring方法，用翻转也可实现，不过在JS中无法对字符串自由写入，法2反而不如法1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 法1，使用substring
function leftReverse(str, n) {
  if (!str || n >= str.length) {
    return str;
  }
  return str.substring(n) + str.substring(0, n);
}
// 法2，使用reverse
function leftReverse(str, n) {
  if (!str || n >= str.length) {
    return str;
  }
  let strArr = Array.from(str);
  return strArr.slice(0, n).reverse().concat(strArr.slice(n).reverse()).reverse().join('');
}

队列的最大值（队列）

滑动窗口的最大值

前提：固定滑动窗口的宽度
要求：返回窗口内的最大值组成的数组

使用双端队列去维护滑动窗口内的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function maxInWindow(nums, k) {
  if (!nums.length || k > nums.length) {
    return;
  }
  let queue = [];
  let res = [];
  for (let i = 0; i < k; i++) {
    while(nums[queue[queue.length-1]] < nums[i]) {
      queue.pop();
    }
    queue.push(i);
  }
  for (let i = k; i < nums.length; i++) {
    res.push(nums[queue[0]]);
    while(nums[i] >= nums[queue[queue.length-1]]) {
      queue.pop();
    }
    // 出界的大值要移出
    if (queue[0] <= i - k) {
      queue.shift();
    }
    queue.push(i);
  }
  res.push(nums[queue[0]]);
  return res;
}

队列的最大值

要求：设计队列，使max，shift和push的时间复杂度为1。

因为在push和shift操作时，队列就像上面的滑动窗口，可以用相同方法实现max。

略。

建模能力

n个骰子的点数（化递归为循环）

要求：输入n，返回n个骰子朝上一面的点数之和的概率分布。

使用循环的角度考虑，骰子递增时，点数和为k的可能性为k-6，k-5，k-4，……，k-1的可能性之和。因此我们可以得到下面的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function posibilities(n) {
  if (n < 1) {
    return [];
  }
  let res = [0, 1, 1, 1, 1, 1, 1];
  for (let i = 2; i <= n; i++) {
    for (let j = 6 * n; j > 0; j--) {
      res[j] = res.slice(Math.max(0, j-6), j).reduce((sum, cur) => sum + (cur || 0), 0);
    }
  }
  return res.slice(1).map(num => num / Math.pow(6, n));
}

扑克牌中的顺子

前提：从扑克牌中随机取5张，大小王可以当做任意数字，判断是否为顺子

这里我们假设传入的数组已经按照扑克牌中的大小对牌进行了排序。整体分3步，首先向数组的指定项插入数字，然后判断0的数目，最后看0的数目是否能填满undefined的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function isSeq(nums) {
  if (!nums.length || nums.length < 1) {
    return false;
  }
  let numbers = [];
  let zeros = 0;
  let flag = false;
  let index = -1;
  nums.forEach(num => {
    if (num === 0) {
      zeros++;
      continue;
    }
    if (!numbers[num]) {
      numbers[num] = true;
    } else {
      // 有对子就不是顺子
      return false;
    }
  });
  numbers.forEach((num, idx) => {
    if (flag) {
      if (typeof num !== 'undefined') {
        zeros--;
        if (zeros-- < 0) {
          index = idx;
          return;
        }
      }
    } else {
      if (typeof num !== 'undefined') {
        flag = true;
      }
    }
  });
  return numbers.slice(index).every(num => typeof num === 'undefined');
}

约瑟夫问题

字面意义的解法就不说了。根据《剑指offer》上的递推公式，可以得到f(n,m)=[f(n-1,m)+m]%n。因此，可以用循环实现。

1
2
3
4
5
6
7
8
9
10
11
function joseph(n, m) {
  if (n < 1 || m < 1) {
    return -1;
  }
  let remains = 0;
  for (let i = 1; i < n; i++) {
    remains = (remains + m) % i;
  }
  return remains;
}

股票的最大利润

也即起始、末尾数对最大差值区间。当遍历到f[i]时，寻找之前的最小值，即可得到利润，遍历整个数组即可得到最大利润，时间复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function maxBenifit(nums) {
  const len = nums.length;
  if (!len || len < 2) {
    return;
  }
  let min = nums[0];
  let res;
  for (let i = 1; i < len; i++) {
    let benifit = nums[i] - min;
    if (typeof res === 'undefined' || res < benifit) {
      res = benifit;
    }
    if (benifit < 0) {
      min = nums[i];
    }
  }
  return res;
}

不使用控制结构语句求解1+2+3+…+n

使用递归等等价形式即可。

1
2
3
function sum(n) {
  return Array(n).reduce((sum, i) => sum + i, 0);
}

不用加减乘除做加法

使用异或可以得到没有进位的结果。可以通过位与运算得到都是1的位。和异或结果异或，直到位与结果都为0为止。

1
2
3
4
5
6
7
8
9
10
11
12
function add(a, b) {
  let sum = a ^ b,
      extra = a & b;
  while (!extra) {
    let tmp = sum & extra;
    sum = sum ^ (extra << 1);
    extra = tmp;
  }
  return sum;
}

构建乘积数组

要求：给定数组A，构建数组B，其中每个元素是A中缺少对应位元素的总乘积。不能使用除法。

使用两个辅助数组分别存储数组从前到后和从后到前两段元素的乘积。空间复杂度O(n)的情况下，可以在O(n)时间上得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function multiArr(nums) {
  if (!nums.length || nums.length < 2) {
    return [];
  }
  let m1 = 1,
      m2 = 1,
      mArr1 = [],
      mArr2 = [],
      res = [];
  for (let i = 0; i < n; i++) {
    m1 *= nums[i];
    m2 *= nums[n - i - 1];
    mArr1.push(m1);
    mArr2.unshift(m2);
  }
  for (let i = 0; i < n; i++) {
    res.push(mArr1[i] * mArr2[i]);
  }
  return res;
}