# 算法

function bubbleSort(arr) {
    var len = arr.length;
    // 先确保最后一位是正确的，每塞一个，就占位一个，然后准备塞倒数第二位
    for (let outer = len ; outer >= 2; outer--) {
        // 从第一个开始一个个比较
        for(let inner = 0; inner <=outer - 1; inner++) {
            // 一个个比较，把最小的放到后面一位
            if(arr[inner] > arr[inner + 1]) {
                [arr[inner],arr[inner+1]] = [arr[inner+1],arr[inner]]
            }
        }
    }
    return arr;
}

function selectSort(arr) {
    var len = arr.length;
    //先把第一个选中
    for(let i = 0 ;i < len - 1; i++) {
        // 让他和其他的依次比较，小就直接换位
        for(let j = i ; j<len; j++) {
            if(arr[j] < arr[i]) {
                [arr[i],arr[j]] = [arr[j],arr[i]];
            }
        }
    }
    return arr
}

function insertSort(arr) {
    //外循环从1开始，默认arr[0]是有序段
    for(let i = 1; i < arr.length; i++) {  
        //j = i,将arr[j]依次插入有序段中
        for(let j = i; j > 0; j--) {  
            if(arr[j] < arr[j-1]) {
                [arr[j],arr[j-1]] = [arr[j-1],arr[j]];
            }
        }
    }
    return arr;
}

function shellSort(arr,gap) {
    console.log(arr)//为了方便观察过程，使用时去除
    for(let i = 0; i<gap.length; i++) {  //最外层循环，一次取不同的步长，步长需要预先给出
        let n = gap[i]; //步长为n
        for(let j = i + n; j < arr.length; j++) { //接下类和插入排序一样，j循环依次取后面的数
            for(let k = j; k > 0; k-=n) { //k循环进行比较，和直接插入的唯一区别是1变为了n
                if(arr[k] < arr[k-n]) {
                    [arr[k],arr[k-n]] = [arr[k-n],arr[k]];
                    console.log(`当前序列为[${arr}] \n 交换了${arr[k]}和${arr[k-n]}`)//为了观察过程
                } else {
                    continue;
                }
            }
        }
    }
    return arr;
}

function merge(leftArr, rightArr){  
    var result = [];  
    while (leftArr.length > 0 && rightArr.length > 0){  
      if (leftArr[0] < rightArr[0])  
        result.push(leftArr.shift()); //把最小的最先取出，放到结果集中   
      else   
        result.push(rightArr.shift());  
    }   
    return result.concat(leftArr).concat(rightArr);  //剩下的就是合并，这样就排好序了  
}  

function mergeSort(array){  
    if (array.length == 1) return array;  
    var middle = Math.floor(array.length / 2);       //求出中点  
    var left = array.slice(0, middle);               //分割数组  
    var right = array.slice(middle);  
    return merge(mergeSort(left), mergeSort(right)); //递归合并与排序  
}  

var arr = mergeSort([32,12,56,78,76,45,36]);
console.log(arr);   // [12, 32, 36, 45, 56, 76, 78]

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;  //递归出口
    }
    var left = [],
        right = [],
        current = arr.splice(0,1); //注意splice后，数组长度少了一个
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < current) {
            left.push(arr[i])  //放在左边
        } else {
            right.push(arr[i]) //放在右边
        }
    }
    return quickSort(left).concat(current,quickSort(right)); //递归
}

// 创建堆，其实是对data数组做一个结构调整，使其具有堆的特性
function buildHeap(data) {
    var len = data.length;
    for(var i=Math.floor(len/2); i>=0; i--) {
        heapAjust(data, i, len);
    }
}
// 堆调整函数，即调整当前data为大根堆
function heapAjust(data, i, len) {
    var child = 2*i + 1;
    // 如果有孩子结点，默认情况是左孩子
    while(child <= len) {
        var temp = data[i];
        // 如果右孩子存在且其值大于左孩子的值，则将child指向右孩子
        if(child + 1 <= len && data[child] < data[child + 1]) {
            child = child + 1;
        }
        // 如果当前结点的值小于其孩子结点的值，则交换，直至循环结束
        if(data[i] < data[child]) {
            data[i] = data[child];
            data[child] = temp;
            i = child;
            child = 2*i + 1
        }else {
            break
        }
    }
}
// 排序
function heapSort(data) {
    var data = data.slice(0);
    if(!(data instanceof Array)) {
        return null;
    }
    if(data instanceof Array && data.length == 1) {
        return data;
    }
    // 将data数组改造为“堆”的结构
    buildHeap(data);

    var len = data.length;
    // 下面需要注意的时候参数的边界，参考文档里面程序中i的值是不对的
    for(var i=len-1; i>=0; i--) {
        swap(data, i, 0);
        heapAjust(data, 0, i-1);
    }
    return data;
}
const arr = [62, 88, 58, 47, 35, 73, 51, 99, 37, 93];
var newArr = heapSort(arr);
console.log(newArr);  // [35, 37, 47, 51, 58, 62, 73, 88, 93, 99]

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    // 1. Recursive solution
    if (!root) return [];
    return [root.val].concat(preorderTraversal(root.left)).concat(preorderTraversal(root.right));
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
  if (!root) return [];
  const ret = [];
  const stack = [root];
  let t = stack.pop();
  
  while (t) {
    //先将根节点入栈
    ret.push(t.val);
    //如果有右节点则入栈
    if (t.right) {
      stack.push(t.right);
    }
    //如果有左节点则入栈
    if (t.left) {
      stack.push(t.left);
    }
    //然后出栈，直到栈内没内容为止
    t = stack.pop();
  }

  return ret;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    //使用递归的方案
    if(!root) return [];
    let left = root.left?inorderTraversal(root.left):[];
    let right = root.right?inorderTraversal(root.right):[];
    return left.concat(root.val).concat(right);
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    //使用递归的方案
    // if(!root) return [];
    // let left = root.left?inorderTraversal(root.left):[];
    // let right = root.right?inorderTraversal(root.right):[];
    // return left.concat(root.val).concat(right);
    //使用栈的方案
    if (!root) return [];
    const stack = [root];
    const ret = [];
    let left = root.left;

    let item = null; // stack 中弹出的当前项
    //先将左节点全部压入栈
    while(left) {
        stack.push(left);
        left = left.left;
    }
    //首先处理所有加入栈的左节点们
    while(item = stack.pop()) {
        //取出栈内值
        ret.push(item.val);
        let t = item.right;
        //如果存在右节点，压入栈，并将其所有的左节点压入栈
        while(t) {
            stack.push(t);
            t = t.left;     
        }
    }

    return ret;
};

 /**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    if(!root) return [];
    let left = root.left?postorderTraversal(root.left):[];
    let right = root.right?postorderTraversal(root.right):[];
    return left.concat(right).concat(root.val)
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
  //使用栈的方案
  if (!root) return [];
  const ret = [];
  const stack = [root];
  let p = root; // 标识元素，用来判断节点是否应该出栈

  while (stack.length > 0) {
    //对栈尾元素进行判断
    const top = stack[stack.length - 1];
    if (
      top.left === p ||
      top.right === p || // 子节点已经遍历过了
      (top.left === null && top.right === null) // 叶子元素
    ) {
      //满足条件则出栈，并存入结果列表
      p = stack.pop();
      ret.push(p.val);
    } else {
      //否则将其右节点和左节点依次入栈
      if (top.right) {
        stack.push(top.right);
      }
      if (top.left) {
        stack.push(top.left);
      }
    }
  }

  return ret;
};

function reverseList(head) {
    // 链表只有一个元素时
    if( head.next === null ) return head;
    // 否则
    let current = head.next,
        preNode = head;
    // 链表反向后原来的头就变成尾了
    preNode.pre = null; // 相当于 head.pre = null;
    while( current.next ){
        current.pre = preNode;  // 建立反向联系
        // 指针后移
        preNode = current;
        current = current.next;
    }
    current.pre = preNode;  // 建立最后一个元素和倒数第二个元素的联系

    // 至此，一个双向链表已经完成了
    // 然后就要开始往前遍历了
    while( current.pre ){
        // 指向反向
        current.next = current.pre;
        // 使"先指针"和"后指针"都指向当前对象
        preNode = current;
        // "先指针"前移
        current = current.pre;
        // 将初始从前向后遍历时新增的属性删掉
        delete preNode.pre;
    }
    // 修正原链表第一个元素的指向
    current.next = current.pre;
    delete current.pre;
}

function reverseList(node) {  // 传入链表的头结点
    if( node.next === null ) {
        /*
        * 能走到这里的有只有两种情况：
        *   1.链表只有一个元素
        *   2.链表不止一个元素同时已经遍历到链表的最后一个元素了
        * */
        return node;
    } else{
        const nextNode = reverseList(node.next);
        nextNode.next = node;
        node.next = null;   // 如果不是原链表的第一个元素，则会在上一次递归的作用域中被修改
        return node;
    }
}

function getClimbingWays(n) {
  if (n < 1) {
    return 0;
  }
    if (n === 1) {
      return 1;
  }
  if (n === 2) {
    return 2;
  }
  return getClimbingWays(n - 1) + getClimbingWays(n - 2);
}

let map = new Map(); 
function getClimbingWays(n) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  if (n === 2) {
    return 2;
  }
  if (map.has(n)) {
    return map.get(n);
  } else {
    let value = getClimbingWays(n - 1) + getClimbingWays(n - 2); 
    map.set(n, value);
    return value;
  }
}

function getClimbingWays(n) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
      return 1;
  }
  if (n === 2) {
    return 2; 
  }
  let a = 1, b = 2, temp = 0;
  for (let i = 3; i <= n; i++) { 
    temp = a + b;
    a = b;
    b = temp;
  }
  return temp;
}