function find(array, target) {
    let row = array.length - 1;
    for (let i = row, j = 0; i >= 0 && j < array[i].length;) {
        if (target === array[i][j]) {
            return true
        } else if (target > array[i][j]) { //目标大于，则下移一行
            j++;  //向下移动一行
        } else {
            i--;  //向左一动一行
        }
    }
    return false
}

function replaceSpace(str) {
    let reg = new RegExp(/\s/g);
    return str.replace(reg, '--')
}

function printLinkedList(head) {
    let arr = [];
    while (head !== null) {
        arr.push(head);
        head = head.next();
    }
    return arr.reverse();
}

let arr1 = [], arr2 = [], result = [];

function push(head) {
    arr2.push(head);
    return arr
}

function shift() {
    if (arr1.length) {
        arr1.shift()
    } else if (arr2.length) {
        arr2.shift()
    } else {
        return null
    }
    return arr
}

function rotate(arr) {
    return arr.sort(function (a, b) {
        if (a < b)
            return -1;
        else return 1
    })[0];
//        return Math.min.apply(arr, arr);
}

function fibonacci(n) {
        if (n === 0 || n === 1)
            return n;
        else {
            var one = 0;
            var two = 1;
            var result = 0;
            for (var i = 2; i <= n; i++) {
                result = one + two;
                one = two;
                two = result
            }
            return result;
        }

    }

function fibonacci(n) {
        if (n === 1 || n === 2)
            return n;
        else {
            var one = 0;
            var two = 1;
            var result = 0;
            for (var i = 3; i <= n; i++) {
                result = one + two;
                one = two;
                two = result
            }
            return result;
        }

    }

function fibonacci(n) {
    var arr = [1, 2];
    if (n === 1 || n === 2)
        return arr[n - 1];
    else {
        var result = 0;
        for (var i = 3; i <= n; i++) {
            result = 1 + arr.reduce(function (total, currentValue) {
                return total + currentValue;
            });
            arr.push(result);
        }
        return result;
    }

}

function rectCover(number) {
    // write code here
    var n = number;
    var arr = [1, 2];
    var result = 0;
    if (n === 1 || n === 2)
        return arr[n - 1];
    else {
        for (var i = 3; i <= n; i++) {
            result = arr[arr.length - 1] + arr[arr.length - 2];
            arr.push(result);
        }
        return result
    }
}

111.232.213 ascqwdwd
111.232.213 qwdqwdqw
122.31.34.1 wdojqwodjqwp  
232.34.13.3 adhwdhwqhd

'111.232.213': [ 'ascqwdwd', 'qwdqwdqw' ],
'122.31.34.1': [ 'wdojqwodjqwp' ],
'232.34.13.3': [ 'adhwdhwqhd' ]

/** 求num中所有质数
 * 对比各种求质数的算法，试除法、筛选法两种时间复杂度较低，
 * 本方法是自己优化的筛选法，因为2,3是比较小的两个质数，大部分数都是他们的倍数，明显不是质数，
 * 所以使用2,3为基数，先筛选走这些非质数，然后在从5 7等向上筛选，这种方法明显循环次数要少。时间复杂度我也不知道该怎么计算。
 * **/
function prime(num) {
    //定义基数数组baseArr，用来存放较小的质数，res存放筛选结果，base存放[2,3]
    let baseArr = [], res = [], base = [];
    num = ~~num;  //取整
    //对2,3 特殊对待
    if (num < 4) {
        if (num === 1)
            alert('请输入大于1的整数')
        if (num === 2)
            base.push(2);
        else
            base.push(2, 3)
    }
    //筛选剩下的
    else {
        baseArr.push(2, 3);
        base.push(2, 3);
        for (let i = 2; i <= num; i++) {  //将2,3的倍数剔除，其余的放入res进行下一轮筛选
            if (i % 2 !== 0 && i % 3 !== 0) {
                res.push(i);
            }
        }
        for (let j = 0; j <= baseArr.length - 1; j++) {  //以大于3最小的质数开始筛选，
            for (let i = 1; i < res.length; i++) {
                if (res[i] % res[j] === 0 && i !== j) {  //除自身外，其他的是质数的倍数的数被剔除
                    res.splice(i, 1);
                }
            }
            if (res[j] < Math.sqrt(num)) {  //确保基数质数肯定小于sqrt(num)
                baseArr.push(res[j]);   //添加一个新的基数质数。
            }
        }
    }
    return base.concat(res)  //将特殊的[2,3]加入返回。
}
console.log(prime(100));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
// baseArr = [2,3,5,7]

function exchange(a,b){
    b=a-b;
    a=a-b;
    b=a+b;
    return [a,b]
}

function maxDiff(array) {
    return Math.max.apply(array,array) - Math.min.apply(array,array);
}
console.log(maxDiff(arr));

for(var i=1;i<4;i++){
    setTimeout(function () {
        console.log(i)
    },0)
}
console.log(i)

//4  这是for循环执行完成之后，i++此时的i已经变成4，所以for循环之后的所有关于i的值都是4

//4
//4
//4

function (){ ... }()；

//或者

function fName(){ ... }();

function name([param[, param[, ... param]]]) {
   statements
}

var f2 = function() {
    console.log("f2");
    }

//通过()来调用此函数

f2();

(function(){ /* code */ }()); 

// 或者

(function(){ /* code */ })();

(function (p) { return p})(parameter);

btn.onclick=function (){}

/** DOM2级事件处理程序  浏览器兼容
 * IE-attachEvent()  detachEvent()
 * 其他-addEventListener()  removeEventListener()
 * EventUtil: 全局对象
 * 使用：EventUtil.addHandler(ele,type,handler)
 * **/
let EventUtil = {
    addHandler: (element, type, handler) => {
        if (element.addEventListener) {
            element.addEventListener(type, handler, false)
        } else if (element.attachEvent) {
            element.attachEvent('on' + type, handler)
        } else {
            element['on' + type] = handler;
        }
    },
    removeHandler: (element, type, handler) => {
        if (element.removeEventListener) {
            element.removeEventListener(type, handler, false)
        } else if (element.detachEvent()) {
            element.detachEvent('on' + type, handler)
        } else {
            element['on' + type] = null;
        }
    }
}

function factorial(num){ 
    if (num <= 1){ 
        return 1; 
    } else { 
        return num * factorial(num-1); 
    } 
}

var anotherFactorial = factorial; 
factorial = null; 
alert(anotherFactorial(4)); //出错！

function factorial(num){ 
    if (num <= 1){ 
        return 1; 
    } else { 
        return num * arguments.callee(num-1); 
    } 
}

var factorial = (function f(num){ 
    if (num <= 1){  
        return 1; 
    } else { 
        return num * f(num-1); 
    } 
});

'usestrict';

/**=========================================================
 * 月(M)、日(d)、小时(h)、分(m)、秒(s)、季度(q) 可以用 1-2 个占位符，
 * 年(y)可以用 1-4 个占位符，毫秒(S)只能用 1 个占位符(是 1-3 位的数字)
 * 例子：
 * (new Date()).Format("yyyy-MM-dd hh:mm:ss.S") ==> 2006-07-02 08:09:04.423
 * (new Date()).Format("yyyy-M-d h:m:s.S") ==> 2006-7-2 8:9:4.18
 =========================================================*/

(function () {
    Date.prototype.format = function (fmt) {
        if (typeof(fmt) == "undefined") {
            fmt = "yyyy-MM-dd hh:mm:ss";
        }
        var o = {
            "M+": this.getMonth() + 1, //月份
            "d+": this.getDate(), //日
            "h+": this.getHours(), //小时
            "m+": this.getMinutes(), //分
            "s+": this.getSeconds(), //秒
            "q+": Math.floor((this.getMonth() + 3) / 3), //季度
            "S": this.getMilliseconds() //毫秒
        };
        //年份是最多表示有四位数，所以分开来处理
        if (/(y+)/.test(fmt)) {
            fmt = fmt.replace(RegExp.$1, (this.getFullYear() + "").substr(4 - RegExp.$1.length));
        }
        //遍历其他的都是两位数的时间内容
        for (var k in o) {
            if (new RegExp("(" + k + ")").test(fmt))
                fmt = fmt.replace(RegExp.$1, (RegExp.$1.length == 1) ? 
                    (o[k]) : (("00" + o[k]).substr(("" + o[k]).length)));
        }

        return fmt;
    };

    Date.prototype.formatDay = function () {
        return this.format("yyyy-MM-dd");
    };

    Date.prototype.formatDay2 = function () {
        return this.format("yyyyMMddhhmmss");
    };

})();

// 交换下标a、b对应的数组数值，此方法抽离处理，后面直接使用，不做说明
function exchange(a, b, obj) {
    let temp = obj[a];
    obj[a] = obj[b];
    obj[b] = temp;
//        return obj
}

function sort(array) {
    let count=0;
    for (let i = 0, len = array.length; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (array[i] < array[j]) {
                count++
                exchange(i, j, array)
            }
        }
    }
    //count=81
    return array;
}

function sort(array) {
    for (let i = 0, len = array.length; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (array[i] < array[j]) {
                exchange(i, j, array)
            }
        }
        for (let k = len - 1; k >= 0; k--) {  //从一个方向开始循环检查
            if (array[i] < array[k]){

                exchange(i, k, array)
            }
        }
    }
//  count=81
    return array;
}

/** 3、选择排序 **/
function sort(array) {
    let res = [], min;
    for (let i = 0, len = array.length; i < len - 1; i++) { //由于第一个开始跟后面对比，因此只需要对比n-1
        min = i;
        for (let j = i + 1; j < len; j++) {
            if (array[min] > array[j]) {
                min = j  //每一轮循环记下此轮最小值的下标，在后面将此下标值放到数列前面
            }
        }
        exchange(min, i, array)
    }
    return array;
}

/** 4、直接插入排序 **/
function sort(array) {
    for (let i = 1, len = array.length; i < len; i++) { //直接从第二个开始比较
        let current = array[i];  //将这次要比较的值存储起来，作为这一轮循环里面的常量
        let index = i;

        //从index前一位数开始比较比较，如果当前比较的数小于它的前一位，则将大的数后移一位
        while (current < array[index - 1] && index >= 0) {
            array[index] = array[index - 1];
            index--;  //于此同时，下标也前移一位，继续下一次比较
        }
        if (index !== i) {  //防止自己赋值给自己，
            array[index] = current //如果不是自己，则一定是之前后移空出来留给current的位置，插入进去
        }
    }
    return array;
}

/** 5、折半插入排序 **/
function sort(array) {
    for (let i = 1, len = array.length; i < len; i++) { //直接从第二个开始比较 i=1
        let low = 0, high = i - 1, current = array[i];
        //找中值对应的下标
        while (low <= high) {
//                let m = Math.floor((low+high) / 2);
            let m = (low + high) >> 1;   //x>>1 是位运算中的右移运算, 表示右移一位, 等同于x除以2再取整, 即 x>>1 == Math.floor(x/2) .
            if (array[i] <= array[m]) {
                high = m - 1   //保证low<=high顺利成立，将high定位低半区
            } else {
                low = m + 1     //同理
            }
        }

        //将在要插入值位置之后的所有元素后移，留出插入的位置
        for (let j = i; j > low; j--) {
            array[j] = array[j - 1];
            console.log(array)
        }
        array[low] = current  //插入

    }
    return array;
}

/** 6、希尔排序 **/
//封装直接插入排序
function dirSort(array, grap) {
    grap = arguments[1] ? grap : 1;  //如果grap传值了，则为grap传入的值，如果没有，则从1开始
//        debugger;
    for (let i = grap - 1, len = array.length; i < len; i++) { //直接从第grap-1个开始比较
        let current = array[i];  //将这次要比较的值存储起来，作为这一轮循环里面的常量
        let index = i;

        //只比较分组内的最大步长间距的两个数，循环一次就跳出来
        while (current < array[index - grap] && index >= 0) {
            array[index] = array[index - grap];  //如果当前比较的数小于它的前一位，则将大的数后移一位
            index -= grap;    //于此同时，下标也前移grap，继续下一次比较
        }


        if (index !== i) {  //防止自己赋值给自己，
            array[index] = current; //如果不是自己，则一定是之前后移空出来留给current的位置，插入进去
            console.log(array)
//                debugger
        }
    }
    return array;
}

function sort(array) {
    let gra = array.length >> 1;
    while (gra > 0) {
        dirSort(array, gra);
        gra = gra >> 1;
    }
    return array
}

/** 7、快速排序 **/
function sort(array) {
    if (array.length >= 1) {
        //选取基准点，基准点选取的好坏决定了排序速度的好坏，目前没有好的方法，一般居中选取
        let baseIndex = array.length >> 1;
        let left = [], right = [];  //定义基准点左右两边数组，小的都在左边，大的都在右边
        // 循环判断
        for (let i = 0; i < array.length; i++) {
            if (i !== baseIndex) {       //这一步很关键，一定不能把自身算进去
                if (array[i] < array[baseIndex]) {
                    left.push(array[i])
                } else
                    right.push(array[i])
            }
        }
//          最关键的一步：递归调用然后在用数组拼接
        return arguments.callee(left).concat(array[baseIndex], arguments.callee(right))
    }
    else
        return array;
}

/** 8、归并排序 **/
function sort(array) {
    if (array.length < 2)
        return array;
    else {
        let res = [];
        //上半部分拆分数组，
        let baseIndex = array.length >> 1;
        let left = array.slice(0, baseIndex),
            right = array.slice(baseIndex);

        //合并数组，
        function merge(left, right) {
            while (left.length && right.length) {
                let item = left[0] <= right[0] ? left.shift() : right.shift();
                res.push(item);
            }
            return res.concat(left.length ? left : right);  //返回排好数组
        }

        //递归调用，一边拆分，一边合并
        return merge(arguments.callee(left), arguments.callee(right));
    }
}