常见算法公式

String

回文

回文判断

var isPalindrome = function(s) {
  // \w 匹配字母、数字、下划线。等价于 [A-Za-z0-9_]
  s = s.replace(/[^\w]/g, '').toLowerCase();
  return (
    s
      .split('')
      .reverse()
      .join('') === s
  );
};

回文数

转成字符串方式 (感觉这样会比较快)

1. 负数都是非回文数，10 的整数倍不是回文。
2. 将数字转为字符串，再逆序排列字符串。两者比较，相等就是回文数。

直接操作整数方式

1. 复制 x 到 temp;
2. 取 temp 末尾数字，方式为 temp 与 10 的求余；组成新数 reverse;
3. 每取完一位,temp 缩小 10 倍并且去掉小数。
4. reverse 要先扩大十倍再加上取下来的数
5. 当 temp === 0 时，表示已经取完；reverse 与 x 比较

/**
 * @param {number} x
 * @return {boolean}
 * 转成字符串
 */
var isPalindrome = function(x) {
  if (x < 0) return false;
  if (x === 0) return true;
  if (x % 10 === 0) return false;
  const str = x + '';
  const reverse = str
    .split('')
    .reverse()
    .join('');
  return str === reverse;
};

/**
 * 性能比字符串翻转好的多
 * @param {number} x
 * @return {boolean}
 * 不转成字符串
 */
var isPalindrome = function(x) {
  if (x < 0) return false;
  if (x === 0) return true;
  if (x % 10 === 0) return false;
  let temp = x;
  let reverse = 0;
  while (temp > 0) {
    let num = temp % 10;
    temp = (temp - num) / 10; // 或 temp = (temp / 10) >> 0,去除小数位
    reverse = reverse * 10 + num;
  }
  return x === reverse;
};

二分查找

在计算 mid 时不能使用 mid = (i + j) / 2 这种方式，因为 i + j 可能会导致加法溢出，应该使用 mid = i + (i - j) / 2

非递归版本：

const binarySearch = (arr, target) => {
  let i = 0,
    j = arr.length - 1;
  while (i <= j) {
    let mid = i + ((j - i) >> 1);
    if (target === arr[mid]) return mid;
    if (target < arr[mid]) {
      j = mid - 1;
    } else {
      i = mid + 1;
    }
  }
  return -1;
};

递归版本：

const binarySearch = (a, left, right, key) => {
  const mid = (left + right) >> 1;
  if (a[mid] === key) return mid;
  if (a[mid] > key) return binarySearch(a, left, mid - 1, key);
  if (a[mid] < key) return binarySearch(a, mid + 1, right, key);
};

DP

斐波那契

function fib(n) {
  if (n <= 1) return n;
  let i = 1,
    j = 1;
  for (let k = 3; k <= n; k++) {
    const sum = i + j;
    i = j;
    j = sum;
  }
  return j;
}

常见数据结构

链表节点

function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

树

class Node {
  constructor(value, children = []) {
    this.children = children;
    this.value = value;
  }
}

export default class Tree {
  root: Node = new Node();

  add(node: Node, value): Node {
    const child = new Node(value);
    node.children.push(child);
    return child;
  }

  remove() {}

  find(value, node) {
    if (node.value === value) return true;
    if (node.children.length < 1) return false;

    for (const child of node.children) {
      this.find(value, child);
    }
  }
}

class BinarySearchTree {
  constructor(...nodes) {
    this.root = null;
    for (let node of nodes) {
      this.put(node.key, node.value);
    }
  }

  put(key, value) {
    function _put(node, key, value) {
      if (node === null) return new Node(key, value);
      else if (key < node.key) {
        node.left = _put(node.left, key, value);
      } else if (key > node.key) {
        node.right = _put(node.right, key, value);
      } else {
        node.value = value;
      }
      return node;
    }
    this.root = _put(this.root, key, value);
  }

  get(key) {
    let x = this.root;
    while (x !== null) {
      if (key < x.key) x = x.left;
      // traverse left
      else if (key > x.key) x = x.right;
      // traverse right
      else return x.value; // found it!
    }
    return x;
  }

  delete(key) {
    function _delete(node, key) {
      if (node === null) return;
      if (key < node.key) {
        node.left = _delete(node.left, key);
      } else if (key > node.key) {
        node.right = _delete(node.right, key);
      } else {
        // node.key === key
        if (node.right === null) return node.left;
        if (node.left === null) return node.right;

        let t = node;
        node = min(t.right);
        node.right = removeMin(t.right);
        node.left = t.left;
      }
      return node;
    }

    function removeMin(node) {
      if (node.left === null) return node.right;
      node.left = removeMin(node.left);
      return node;
    }

    function min(node) {
      let x = node;
      while (x.left !== null) x = x.left;
      return x;
    }

    this.root = _delete(this.root, key);
  }

  contains(key) {
    return this.get(key) !== null;
  }

  isEmpty() {
    return this.root === null;
  }

  size() {
    function _size(node) {
      return node === null ? 0 : 1 + _size(node.left) + _size(node.right);
    }
    return _size(this.root);
  }

  inorder(fn) {
    function _inorder(node) {
      if (node === null) return;
      _inorder(node.left);
      fn(node);
      _inorder(node.right);
    }
    _inorder(this.root);
  }

  preorder(fn) {
    function _preorder(node) {
      if (node === null) return;
      fn(node);
      _preorder(node.left);
      _preorder(node.right);
    }
    _preorder(this.root);
  }

  postorder(fn) {
    function _postorder(node) {
      if (node === null) return;
      _postorder(node.left);
      _postorder(node.right);
      fn(node);
    }
    _postorder(this.root);
  }

  bfs(fn) {
    if (this.root === null) return;
    let queue = new Queue();
    queue.enqueue(this.root);
    while (!queue.isEmpty()) {
      let node = queue.dequeue();
      fn(node);
      if (node.left !== null) queue.enqueue(node.left);
      if (node.right !== null) queue.enqueue(node.right);
    }
  }
}

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class Queue {
  constructor(...items) {
    this.data = [];
    for (let item of items) {
      this.enqueue(item);
    }
  }

  enqueue(item) {
    this.data.unshift(item);
  }
  dequeue() {
    return this.data.pop();
  }
  isEmpty() {
    return this.data.length === 0;
  }
}