Cacher is the code snippet organizer for pro developers

var arr = [0, 1, 2, 3, 4, 5, 6];

function binarySearch(arr: number[], result: number) {
  let len = arr.length;
  let low = 0;
  let high = len - 1;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (arr[mid] < result) {
      low = mid + 1;
    } else if (arr[mid] > result) {
      high = mid - 1;
    } else {
      return mid;
    }
  }

  return -1;
}

console.log(binarySearch(arr, 4));

// https://xxoo521.com/2020-02-04-btree-find-path/

interface Node {
  val: number;
  left: Node;
  right: Node;
}

function getPaths(sum: number, root: Node) {
  if (!root) {
    return [];
  }

  let paths: number[][] = [];
  searchPath(sum, root, paths, []);
  return paths;
}

function searchPath(
  sum: number,
  root: Node,
  paths: number[][],
  path: number[]
) {
  if (!root) {
    return;
  }

  path = [...path, root.val];

  if (root.left === null && root.right === null && root.val === sum) {
    paths.push(path);
    return;
  }

  searchPath(sum - root.val, root.left, paths, path);
  searchPath(sum - root.val, root.right, paths, path);
}

interface TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
}

const root: TreeNode = {
  val: 0,
  left: {
    val: 1,
    left: {
      val: 3,
      left: null,
      right: null
    },
    right: {
      val: 4,
      left: null,
      right: null
    }
  },
  right: {
    val: 2,
    left: {
      val: 5,
      left: null,
      right: null
    },
    right: {
      val: 6,
      left: null,
      right: null
    }
  }
};

function bfs(node: TreeNode) {
  if (node === null) {
    return;
  }

  let queue: TreeNode[] = [node];

  while (queue.length) {
    let currentNode = queue.shift();
    console.log(currentNode.val);
    currentNode.left && queue.push(currentNode.left);
    currentNode.right && queue.push(currentNode.right);
  }
}

new Array(10).fill(new Array(20).fill(0));

/**
 用 Javascript 构造一个双向链表，并且实现它的插入和删除方法，
 例如 insert(position, element) 表示在 position 
 位置插入值为 element 的节点，removeAt(position) 表示删除 position 位置的节点。
 */

interface LinkNode {
  value: number;
  next: LinkNode | null;
  prev: LinkNode | null;
}

class LinkList {
  public head: LinkNode | null = null;
  public length: number = 0;

  insert(position: number, node: LinkNode): boolean {}

  removeAt(position: number) {}
}

// 数组重复数组
var findDuplicates = function(nums) {
    if(!nums || nums.length < 1){return [];}
    nums.sort((a,b)=>{
        return a-b;
    })
    nums = nums.filter((item,index)=>{
        return nums[index] == nums[index+1]; 
    })
    return nums;
};

// 图遍历广搜
Graph.prototype.bfs = function(v) {
    var queue = [], marked = []
    marked[v] = true
    queue.push(v) // 添加到队尾
    while(queue.length > 0) {
        var s = queue.shift() // 从队首移除
        if (this.edges.has(s)) {
            console.log('visited vertex: ', s)
        }
        let neighbors = this.edges.get(s)
        for(let i=0;i<neighbors.length;i++) {
            var w = neighbors[i]
            if (!marked[w]) {
                marked[w] = true
                queue.push(w)
            }
        }
    }
}

// 图遍历深搜
Graph.prototype.dfs = function() {
    var marked = []
    for (var i=0; i<this.vertices.length; i++) {
        if (!marked[this.vertices[i]]) {
            dfsVisit(this.vertices[i])
        }
    }
    
    function dfsVisit(u) {
        let edges = this.edges
        marked[u] = true
        console.log(u)
        var neighbors = edges.get(u)
        for (var i=0; i<neighbors.length; i++) {
            var w = neighbors[i]
            if (!marked[w]) {
                dfsVisit(w)
            }
        }
    }
}

// 图类
function Graph() {
    this.vertices = [] // 顶点集合
    this.edges = new Map() // 边集合
}
Graph.prototype.addVertex = function(v) { // 添加顶点方法
    this.vertices.push(v)
    this.edges.set(v, [])
}
Graph.prototype.addEdge = function(v, w) { // 添加边方法
    let vEdge = this.edges.get(v)
    vEdge.push(w)
    let wEdge = this.edges.get(w)
    wEdge.push(v)
    this.edges.set(v, vEdge)
    this.edges.set(w, wEdge)
}
Graph.prototype.toString = function() {
    var s = ''
    for (var i=0; i<this.vertices.length; i++) {
        s += this.vertices[i] + ' -> '
        var neighors = this.edges.get(this.vertices[i])
        for (var j=0; j<neighors.length; j++) {
            s += neighors[j] + ' '
        }
        s += '\n'
    }
    return s
}

// 归并排序
function merge_sort(arr){
  if(arr.length < 2){
    return arr;
  }
  var middle = parseInt(arr.length/2);
  var left = arr.slice(0,middle);
  var right = arr.slice(middle);
  
  return merge(merge_sort(left),merge_sort(right));
}

// 合并两个有序数组
function merge(left,right){
  var result = [];
  var i = 0, j = 0;
  while(i < left.length && j < right.length){
    if(left[i] > right[j]){
      result.push(right[j++]);
    }
    else{
      result.push(left[i++]);
    }
  }
  while(i < left.length){
    result.push(left[i++]);
  }
  while(j < right.length){
    result.push(right[j++]);
  }
  
  return result;
}

var arr = [1, 2, 3, 5, 6, 7, 8, 9];
var result = merge_sort(arr);
console.log(result);  //[1, 2, 3, 5, 6, 7, 8, 9]





var arr1 = [1,3,5,5,5];
var arr2 = [2,3,6];

function merge(arr1, arr2) {
    var result = [];
    var i=0, j=0;
    
    while(i < arr1.length && j < arr2.length) {
        var num1 = arr1[i];
        var num2 = arr2[j];
        
        if (num1 <= num2) {
            result.push(num1);
            i++;
        } else {
            result.push(num2);
            j++;
        }
    }
    
    while(i < arr1.length) {
        result.push(arr1[i++]);
    }
    
    while(j < arr2.length) {
        result.push(arr2[j++]);
    }
    
    return result;
}


function max(num1, num2) {
    return num1 >= num2 ? num1 : num2;
}

console.log(merge(arr1, arr2));

// 时间复杂度 最优：nlogn  最坏：n2
function quickSort(arr: number[]) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr.splice(pivotIndex, 1)[0];

  const left: number[] = [];
  const right: number[] = [];

  arr.forEach(num => {
    if (num < pivot) {
      left.push(num);
    } else {
      right.push(num);
    }
  });

  return quickSort(left).concat([pivot], quickSort(right));
}

console.log(quickSort([2, 1, 3, 4, 5]));

// 快排
var quickSort = function(arr) {

　　if (arr.length <= 1) { return arr; }

　　var pivotIndex = Math.floor(arr.length / 2);

　　var pivot = arr.splice(pivotIndex, 1)[0];

　　var left = [];

　　var right = [];

　　for (var i = 0; i < arr.length; i++){

　　　　if (arr[i] < pivot) {

　　　　　　left.push(arr[i]);

　　　　} else {

　　　　　　right.push(arr[i]);

　　　　}

　　}

　　return quickSort(left).concat([pivot], quickSort(right));

};


Array.prototype.quickSort = function() {
    const len = this.length;
    if (len < 2) return this;
    
    const basic = this[0];
    let left = [];
    let right = [];
    
    for (let i=1; i<len; i++) {
        if(this[i] > basic) {
            right.push(this[i]);
        } else {
            left.push(this[i]);
        }
    }
    
    return left.quickSort().concat(basic, right.quickSort());
}

console.log([2,3,2,4].quickSort());

// 数组去重
arr.filter(function(item, i){
	return arr.indexOf(item) === i;
})

function unique(array) {
    // res用来存储结果
    var res = [];
    for (var i = 0, arrayLen = array.length; i < arrayLen; i++) {
        for (var j = 0, resLen = res.length; j < resLen; j++ ) {
            if (array[i] === res[j]) {
                break;
            }
        }
        // 如果array[i]是唯一的，那么执行完循环，j等于resLen
        if (j === resLen) {
            res.push(array[i])
        }
    }
    return res;
}


function unique(array) {
   return Array.from(new Set(array));
}

// 整数翻转
var reverse = function(x) {
    var min = -Math.pow(2, 31);
    var max = Math.pow(2, 31) - 1;
    var result = 0;

    while(x!=0) {
        console.log(result)
        result = result * 10 + x%10;
        x = parseInt(x / 10);
    }  
  
    if (result < min || result > max) {
        return 0;
    }
    
    return result;
};

// 斐波那契 fibonacci
function fibonacci(n) {
    if(n==0 || n == 1)
        return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

let fibonacci = (function() {
  let memory = []
  return function(n) {
      if(memory[n] !== undefined) {
        return memory[n]
    }
    return memory[n] = (n === 0 || n === 1) ? n : fibonacci(n-1) + fibonacci(n-2)
  }
})()


var fibonacci = (function () {
  var memory = {}
  return function(n) {
    if(n==0 || n == 1) {
      return n
    }
    if(memory[n-2] === undefined) {
      memory[n-2] = fibonacci(n-2)
    }
    if(memory[n-1] === undefined) {
      memory[n-1] = fibonacci(n-1)
    }
    return memory[n] = memory[n-1] + memory[n-2]
  }
})()

// 循环遍历
function fibonacci(n) {
    let n1 = 1,
        n2 = 1,
        sum = 1
    for(let i = 3; i <= n; i += 1) {
        sum = n1 + n2
        n1 = n2
        n2 = sum
    }
    return sum
}

// 尾调用方案
function fibonacci(n, n1, n2) {
    if(n <= 1) {
        return n2
    }
    return fibonacci(n - 1, n2, n1 + n2)
}

// 公式
function fibonacci(n){
    var sum = 0
    for(let i = 1; i <= n; i += 1) {
        sum += fib(i)
    }
    return sum

    function fib(n) {
      const SQRT_FIVE = Math.sqrt(5);
      return Math.round(1/SQRT_FIVE * (Math.pow(0.5 + SQRT_FIVE/2, n) - Math.pow(0.5 - SQRT_FIVE/2, n)));
    }
}

/**
 * 旋转数组
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    while(k--) {
        nums.unshift(nums.pop());
    }
    return nums;
};

// 最大子序和
var maxSubArray = function(nums) {
  var max = -Number.MAX_VALUE;
  var sum = 0;
  for (let num of nums) {
    if (sum < 0) {
      sum = 0;
    }
    sum += num;
    max = Math.max(max, sum);
  }
  return max;
}

function dp(str1: string, str2: string) {
  let maxLen = 0;
  let pointer = 0;

  let len1 = str1.length;
  let len2 = str2.length;
  let record = new Array(len1 + 1).fill(new Array(len2 + 1).fill(0));

  for (let i = 0; i < len1; i++) {
    for (let j = 0; j < len2; j++) {
      if (str1[i] === str2[j]) {
        record[i + 1][j + 1] = record[i][j] + 1;

        if (record[i + 1][j + 1] > maxLen) {
          maxLen = record[i + 1][j + 1];
          pointer = i;
        }
      }
    }
  }

  let result = "";

  while (maxLen--) {
    result = str1[pointer] + result;
    pointer--;
  }

  return result;
}

console.log(dp("1712391234", "12345"));

function maxWidth(root) {
  let queue = [root]
  let maxWidth = 0
  while (queue.length > 0) {
    let newQueue = []
    for (let i = 0; i < queue.length; i++) {
      newQueue = newQueue.concat(queue[i].children)
    }
    queue = newQueue
    maxWidth = Math.max(maxWidth, newQueue.length)
  }
  return maxWidth
}

// 深搜
function dfs(node,nodeList) {  
    if (node) {    
      nodeList.push(node);    
      var children = node.children;    
      for (var i = 0; i < children.length; i++) {
        dfs(children[i],nodeList);            
      }
    }    
    return nodeList;  
}  

var root = document.getElementById('root')
console.log(deepTraversal(root,nodeList=[]))

// 广搜
function bfs(node) {  
    var nodes = [];  
    if (node != null) {  
        var queue = [];  
        queue.unshift(node);  
        while (queue.length != 0) {  
            var item = queue.shift();  
            nodes.push(item);  
            var children = item.children;  
            for (var i = 0; i < children.length; i++)  
                queue.push(children[i]);  
        }  
    }  
    return nodes;  
}
var root = document.getElementById('root');
console.log(bfs(root));