const Singleton = {
  prop1: "prop1"
  prop2: "prop2"
  method1() {
    console.log("I am a method.");
  }
}

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();
    }
  }
}

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;
    }
  }
}

const Singleton = function() {
  const instance = this;

  this.prop = "prop";
  this.method = function() {
    console.log("I am a method.");
  }

  Singleton = function() {
    return instance;
  };
}

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
}

const mySet = new Set();
arr.forEach((val, index) => {
  if (mySet.has(val)) {
    console.log(val);
    return;
  } else {
    mySet.add(val);
  }
});

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]];
    }
  }
}

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);
}

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;
}

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

// 单向链表
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;
    }
  }

})();

// 双向链表
// 略

function recursivePrint(node) {
  if (node && node.next) {
    console.log(recursivePrint(node.next));
  } else {
    console.log(node.element);
  }
}

class BinaryTreeNode {
  constructor(element, left, right) {
    this.element = element;
    this.left = left;
    this.right = right;
  }
}

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);
}

class BinaryTreeNode {
  constructor(element, left, right, parent) {
    this.element = element;
    this.left = left;
    this.right = right;
    this.parent = parent;
  }
}

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;
  }
}

class Stack {
  constructor() {
    this.stack = []
  }

  get size() {
    return this.stack.length;
  }

  push(element) {
    return this.stack.push(element);
  }

  pop() {
    return this.stack.pop();
  }

}

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;
  }
}

class Queue {
  constructor() {
    this.queue = []
  }

  get size() {
    return this.stack.length;
  }

  in(element) {
    return this.stack.push(element);
  }

  out() {
    return this.stack.shift();
  }

}

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!");
  }
}

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;
}

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];
}

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;
}

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)
}

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];
}

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
}

function numOf1(n) {
  let cnt = 0,
      flag = 1;

  while(flag) {
    if (n & flag) {
      cnt++;
    }
    flag <<= 1;
  }

  return cnt;
}

function numOf1(n) {
  let cnt = 0;

  while(n) {
    ++cnt;
    n = (n-1) & n;
  }

  return cnt;
}

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;
}

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);
}

class LinkedListNode {
  constructor(value, next) {
    this.value = value;
    this.next = next
  }
}

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/.test(str);

// 类型转换
!isNaN(+str);

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;
}

class LinkedList {
  constructor(head) {
    this.head = head;
  }
}

class Node {
  constructor(next) {
    this.next = next;
  }
}

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;
}

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;
}

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;
  }
}

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;
}

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;
}

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);
  }
}

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);
}

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;
    }
  }
}

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;
  }
}

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);
  }
}

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;
}

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);
    }
  }
}

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,
      });
    }
  }
}

// 栈的数据结构实现略
// ...

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("换行");
      }
    }
  }
}

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;
}

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();
}

class ComplexLinkedListNode {
  constructor({value, next, extra}) {
    this.value = value;
    this.next = next;
    this.extra = extra;
  }
}

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;
}

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);
}

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);
}