算法相关总结

绝地灬酷狼 2023-07-18 06:21 49阅读 0赞

//call apply bind 的实现
    //call的实现
    //将函数设为传入参数的属性
    //指定this到函数并传入给定参数执行函数
    //如果不传入参数或者参数为null，默认指向为 window / global
    //删除参数上的函数
    Function.prototype.call = function(content) {
        /** 如果第一个参数传入的是 null 或者是 undefined, 那么指向this指向 window/global */
        /** 如果第一个参数传入的不是null或者是undefined, 那么必须是一个对象 */
    
        if (!content) {
            content = typeof window === 'undefined' ? global : window
        }
        content.fn = this //this  指向的是当前的函数(Function的实例)
    
        let rest = [...arguments].slice(1) //获取除了this指向对象以外的参数, 空数组slice后返回的仍然是空数组
    
        let result = content.fn(...rest) //隐式绑定,当前函数的this指向了content.
    
        delete content.fn
        return result
    
    }
    
    //实现call
    // 模拟 call bar.mycall(null);
    //实现一个call方法：
    Function.prototype.myCall = function(context) {
        //此处没有考虑context非object情况
        context.fn = this;
        let args = [];
        for (let i = 1, len = arguments.length; i < len; i++) {
            args.push(arguments[i]);
        }
        context.fn(...args);
        let result = context.fn(...args);
        delete context.fn;
        return result;
    };
    //实现apply
    // 模拟 apply
    Function.prototype.myapply = function(context, arr) {
        var context = Object(context) || window;
        context.fn = this;
    
        var result;
        if (!arr) {
            result = context.fn();
        } else {
            var args = [];
            for (var i = 0, len = arr.length; i < len; i++) {
                args.push("arr[" + i + "]");
            }
            result = eval("context.fn(" + args + ")");
        }
    
        delete context.fn;
        return result;
    };
    //实现bind
    Function.prototype.mybind = function(context, ...rest) {
            return (...params) => this.call(context, ...rest, ...params);
        }
        // mdn的实现
    if (!Function.prototype.bind) {
        Function.prototype.bind = function(oThis) {
            if (typeof this !== 'function') {
                // closest thing possible to the ECMAScript 5
                // internal IsCallable function
                throw new TypeError('Function.prototype.bind - what is trying to be bound is not callable');
            }
    
            var aArgs = Array.prototype.slice.call(arguments, 1),
                fToBind = this,
                fNOP = function() {},
                fBound = function() {
                    // this instanceof fBound === true时,说明返回的fBound被当做new的构造函数调用
                    return fToBind.apply(this instanceof fBound ?
                        this :
                        oThis,
                        // 获取调用时(fBound)的传参.bind 返回的函数入参往往是这么传递的
                        aArgs.concat(Array.prototype.slice.call(arguments)));
                };
    
            // 维护原型关系
            if (this.prototype) {
                // Function.prototype doesn't have a prototype property
                fNOP.prototype = this.prototype;
            }
            // 下行的代码使fBound.prototype是fNOP的实例,因此
            // 返回的fBound若作为new的构造函数,new生成的新对象作为this传入fBound,新对象的__proto__就是fNOP的实例
            fBound.prototype = new fNOP();
    
            return fBound;
        };
    }
    
    //先打印a隔两秒打印b
    new Promise(function(resolve) {
        console.log('a')
        resolve()
    }).then(
        function() {
            setTimeout(function() {
                console.log('b')
            }, 2000)
        }
    )
    
    function test() {
        console.log('a');
        setTimeout(function() {
                console.log('b')
            },
            2000)
    }
    test();
    
    function test() {
        console.log(1)
        setTimeout(function() { // timer1
            console.log(2)
        }, 1000)
    }
    
    test();
    
    //apply  第二个参数必须是数组或者类数组
    Function.prototype.apply = function(context, rest) {
            if (!context) {
                //context为null或者是undefined时,设置默认值
                context = typeof window === 'undefined' ? global : window;
            }
            context.fn = this;
            let result;
            if (rest === undefined || rest === null) {
                //undefined 或者 是 null 不是 Iterator 对象，不能被 ...
                result = context.fn(rest);
            } else if (typeof rest === 'object') {
                result = context.fn(...rest);
            }
            delete context.fn;
            return result;
        }
        //bind()一个函数被 call/apply 的时候，会直接调用，但是 bind 会创建一个新函数。
        //当这个新函数被调用时，bind() 的第一个参数将作为它运行时的 this，之后的一序列参数将会在传递的实参前传入作为它的参数。
    
    //字符串操作
    //将单词的首字母大写
    const capitalizeEveryWorld = str => str.replace(/\b[a-z]/g, char => char.toUpperCase())
        //首字母大写
    const capital = ([first, ...rest]) => first.toUpperCase() + rest.join('')
        //字符串翻转
        //方法一
    var arr = str.split('')
    var newArr = []
    for (let i = 0; i < arr.length; i++) {
        newArr[i] = arr[arr.length - i - 1]
    }
    var newStr = newArr.join('')
        //方法二
    var newStr = ''
    for (var i = 0; i < str.length; i++) {
        newStr += str.charAt(str.length - i - 1)
    }
    //方法三
    var newStr = str.split('').reverse().join('')
        //方法四
    var arr = str.split('')
    var newArr = []
    while (arr.length > 0) {
        newArr.push(arr.pop())
    }
    var newStr = newArr.join('')
    
    //统计字符串出现最多的字母和次数(使用对象)
    var str = 'ssssssssssdddfgnghterg'
    var n = {}
    for (let i = 0; i < str.length; i++) {
        var a = str.charAt(i)
        if (n[a]) {
            n[a]++
        } else {
            n[a] = 1
        }
    }
    console.log(n)
    var max = 0;
    var maxchar = null
    for (var key in n) {
        if (max < n[key]) {
            max = n[key]
            maxchar = key
        }
    }
    console.log("最多的字符" + maxchar)
    console.log("出现次数" + max)
    
    // 统nums计数组中出现的次数的对象
    const nums = [3, 5, 2, 56, 45, 56, 87, 4, 3, 4, 2]
    const result = nums.reduce((tally, amt) => {
        tally[amt] ? tally[amt]++ : (tally[amt] = 1)
        return tally
    }, {})
    
    console.log(result)
    
    //深拷贝与浅拷贝
    //深拷贝
    //他无法实现对函数 、RegExp等特殊对象的克隆
    //会抛弃对象的constructor,所有的构造函数会指向Object
    //对象有循环引用,会报错
    const newObj = JSON.parse(JSON.stringify(oldobj))
        //深拷贝
        /**
         * deep clone
         * @param  {[type]} parent object 需要进行克隆的对象
         * @return {[type]}        深克隆后的对象
         */
    const clone = parent => {
        // 判断类型
        const isType = (obj, type) => {
            if (typeof obj !== "object") return false;
            const typeString = Object.prototype.toString.call(obj);
            let flag;
            switch (type) {
                case "Array":
                    flag = typeString === "[object Array]";
                    break;
                case "Date":
                    flag = typeString === "[object Date]";
                    break;
                case "RegExp":
                    flag = typeString === "[object RegExp]";
                    break;
                default:
                    flag = false;
            }
            return flag;
        };
    
        // 处理正则
        const getRegExp = re => {
            var flags = "";
            if (re.global) flags += "g";
            if (re.ignoreCase) flags += "i";
            if (re.multiline) flags += "m";
            return flags;
        };
        // 维护两个储存循环引用的数组
        const parents = [];
        const children = [];
    
        const _clone = parent => {
            if (parent === null) return null;
            if (typeof parent !== "object") return parent;
    
            let child, proto;
    
            if (isType(parent, "Array")) {
                // 对数组做特殊处理
                child = [];
            } else if (isType(parent, "RegExp")) {
                // 对正则对象做特殊处理
                child = new RegExp(parent.source, getRegExp(parent));
                if (parent.lastIndex) child.lastIndex = parent.lastIndex;
            } else if (isType(parent, "Date")) {
                // 对Date对象做特殊处理
                child = new Date(parent.getTime());
            } else {
                // 处理对象原型
                proto = Object.getPrototypeOf(parent);
                // 利用Object.create切断原型链
                child = Object.create(proto);
            }
    
            // 处理循环引用
            const index = parents.indexOf(parent);
    
            if (index != -1) {
                // 如果父数组存在本对象,说明之前已经被引用过,直接返回此对象
                return children[index];
            }
            parents.push(parent);
            children.push(child);
    
            for (let i in parent) {
                // 递归
                child[i] = _clone(parent[i]);
            }
    
            return child;
        };
        return _clone(parent);
    };
    //实现instanceof
    function instance_of(l, r) {
        var o = r.prototype
        l = l._proto_
        while (true) {
            if (l === null) return false
            if (o === l) {
                return true
                l = l._proto_
            }
    
        }
    }
    //实现一个简单的slice
    function my_slice(start, end) {
        var array = [];
        start = start ? start : 0;
        end = end ? end : this.length;
        for (var i = start, j = 0; i < end; i++, j++) {
            array[j] = this[i];
        }
        return array;
    }
    //实现new
    
    // 它创建了一个全新的对象
    // 它会被执行[[Prototype]]（也就是__proto__）链接
    // 它使this指向新创建的对象
    // 通过new创建的每个对象将最终被[[Prototype]]链接到这个函数的prototype对象上
    // 如果函数没有返回对象类型Object(包含Functoin, Array, Date, RegExg, Error)，那么new表达式中的函数调用将返回该对象引用
    
    function mynew() {
        const obj = new Object()
        const parent = [].shift.call(arguments)
        obj._proto_ = parent.prototype
        const ret = parent.apply(obj, arguments)
    
        return typeof ret === 'object' ? ret : obj
    }
    
    function new2(func) {
        // 创建了一个实例对象 o，并且这个对象__proto__指向func这个类的原型对象 
        let o = Object.create(func.prototype);
        // (在构造函数中this指向当前实例)让这个类作为普通函数值行 并且里面this为实例对象 
        let k = func.call(o);
        // 最后再将实例对象返回 如果你在类中显示指定返回值k，
        // 注意如果返回的是引用类型则将默认返回的实例对象o替代掉
        return typeof k === 'object' ? k : o;
    }
    
    //深拷贝
    function deepClone(obj, hash = new WeakMap()) { //递归拷贝
        if (obj instanceof RegExp) {
            return new RegExp(obj)
    
        }
        if (obj instanceof Date) {
            return new Date(obj)
        }
        if (obj === null || typeof obj != 'object') {
            return obj
        }
        if (hash.has(obj)) {
            return hash.get(obj)
        }
        //如果obj为数组的话，那么obj.constructor为[Functon:Array]
        let t = new obj.constructor()
        hash.set(obj, t)
        for (let key in obj) {
            if (obj.hasOwnProperty(key)) { //是否是自身的属性
                t[key] = deepClone(obj[key], hash)
            }
        }
        return t;
    }
    
    //浅拷贝
    
    //函数柯里化(函数柯里化是把接受多个参数的函数变换成接受一个单一参数（最初函数的第一个参数）的函数，并且返回接受余下的参数而且返回结果的新函数的技术。)
    
    function curry(fn, args = []) {
        return function() {
            let rest = [...args, ...arguments];
            if (rest.length < fn.length) {
                return curry.call(this, fn, rest);
            } else {
                return fn.apply(this, rest);
            }
        }
    }
    //test
    function sum(a, b, c) {
        return a + b + c;
    }
    let sumFn = curry(sum);
    console.log(sumFn(1)(2)(3)); //6
    console.log(sumFn(1)(2, 3)); //6
    //函数柯里化
    
    /**
     * 将函数柯里化
     * @param fn    待柯里化的原函数
     * @param len   所需的参数个数，默认为原函数的形参个数
     */
    function curry(fn, len = fn.length) {
        return _curry.call(this, fn, len)
    }
    
    /**
     * 中转函数
     * @param fn    待柯里化的原函数
     * @param len   所需的参数个数
     * @param args  已接收的参数列表
     */
    function _curry(fn, len, ...args) {
        return function(...params) {
            let _args = [...args, ...params];
            if (_args.length >= len) {
                return fn.apply(this, _args);
            } else {
                return _curry.call(this, fn, len, ..._args)
            }
        }
    }
    
    //函数柯里化-----接收一部分参数，返回一个函数接收剩余参数，接收足够参数后，执行原函数。
    /**
     * @param  fn           待柯里化的函数
     * @param  length       需要的参数个数，默认为函数的形参个数
     * @param  holder       占位符，默认当前柯里化函数
     * @return {Function}   柯里化后的函数
     */
    function curry(fn, length = fn.length, holder = curry) {
        return _curry.call(this, fn, length, holder, [], [])
    }
    /**
     * 中转函数
     * @param fn            柯里化的原函数
     * @param length        原函数需要的参数个数
     * @param holder        接收的占位符
     * @param args          已接收的参数列表
     * @param holders       已接收的占位符位置列表
     * @return {Function}   继续柯里化的函数 或 最终结果
     */
    function _curry(fn, length, holder, args, holders) {
        return function(..._args) {
            //将参数复制一份，避免多次操作同一函数导致参数混乱
            let params = args.slice();
            //将占位符位置列表复制一份，新增加的占位符增加至此
            let _holders = holders.slice();
            //循环入参，追加参数 或 替换占位符
            _args.forEach((arg, i) => {
                //真实参数 之前存在占位符 将占位符替换为真实参数
                if (arg !== holder && holders.length) {
                    let index = holders.shift();
                    _holders.splice(_holders.indexOf(index), 1);
                    params[index] = arg;
                }
                //真实参数 之前不存在占位符 将参数追加到参数列表中
                else if (arg !== holder && !holders.length) {
                    params.push(arg);
                }
                //传入的是占位符,之前不存在占位符 记录占位符的位置
                else if (arg === holder && !holders.length) {
                    params.push(arg);
                    _holders.push(params.length - 1);
                }
                //传入的是占位符,之前存在占位符 删除原占位符位置
                else if (arg === holder && holders.length) {
                    holders.shift();
                }
            });
            // params 中前 length 条记录中不包含占位符，执行函数
            if (params.length >= length && params.slice(0, length).every(i => i !== holder)) {
                return fn.apply(this, params);
            } else {
                return _curry.call(this, fn, length, holder, params, _holders)
            }
        }
    }
    //reduce函数的实现
    Array.prototype._reduce = function(callback, initvalue) {
            let i = 0;
            let result = initvalue
            if (typeof initvalue === 'undefined') {
                result = this[0]
                i++
            }
            for (let i = 0; i < this.length; i++) {
                result = callback(result, this[i])
            }
            return result
        }
        //add函数的应用
    function add() {
        //args用来存储所有的参数
        var _args = Array.prototype.slice.call(arguments)
            //申明函数利用闭包访问_args
        var adder = function() {
            _args.push(...arguments)
            return adder
        }
    
        // 利用toString隐式转换的特性，当最后执行时隐式转换，并计算最终的值返回
        adder.toString = function() {
            return _args.reduce(function(a, b) {
                return a + b;
            });
        }
        return adder;
    }
    //插入排序（从后往前比较 直到碰到比当前项 还要小的前一项时 将这一项插入到前一项的后面）
    function insertsort(arr) {
        let len = arr.length
        let preindex, current
        for (let i = 1; i < len; i++) {
            preindex = i - 1;
            current = arr[1]
            while (preindex >= 0 && current < arr[preindex]) {
                arr[preindex + 1] = arr[preindex]
                preindex--
            }
            arr[preindex + 1] = current
        }
        return arr
    }
    
    //全排列
    const permute = function(nums) {
        if (nums.length <= 1) return [nums]
    
        const permutes = []
        for (let i = 0; i < nums.length; i++) {
            const num = nums[i]
            const others = nums.slice(0, i).concat(nums.slice(i + 1))
            const list = permute(others)
            list.forEach(item => {
                permutes.push([num].concat(item))
            })
        }
        return permutes
    };
    const arr = [1, 2, 3]
    console.log(permute(arr))
    
    //选择排序
    function selectSort(arr) {
        let len = arr.length;
        let temp = null;
        let minIndex = null;
        for (let i = 0; i < len - 1; i++) { // 把当前值的索引作为最小值的索引一次去比较
            minIndex = i; // 假设当前项索引 为最小值索引
            for (let j = i + 1; j < len; j++) { // 当前项后面向一次比小
                if (arr[j] < arr[minIndex]) { // 比假设的值还要小 则保留最小值索引
                    minIndex = j; // 找到最小值的索引位置
                }
            }
            // 将当前值和比较出的最小值交换位置
            if (i !== minIndex) {
                temp = arr[i]
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
        return arr;
    }
    
    //快排
    //快速排序
    const QuickSort7 = (array) => {
        const sort = (arr, left = 0, right = arr.length - 1) => {
            if (left >= right) {
                return
            }
            let i = left
            let j = right
            const base = arr[j]
            while (i < j) {
                while (i < j && arr[i] <= base) {
                    i++
                }
                arr[j] = arr[i]
                while (j > i && arr[j] >= base) {
                    j--
                }
                arr[i] = arr[j]
            }
            arr[j] = base
            sort(arr, left, j - 1)
            sort(arr, j + 1, right)
        }
        const newArray = array.concat()
        sort(newArray)
        return newArray
    }
    
    const quickSort = (array) => {
            const sort = (arr, left = 0, right = arr.length - 1) => {
                if (left >= right) { //如果左边的索引大于等于右边的索引说明整理完毕
                    return
                }
                let i = left
                let j = right
                const baseVal = arr[j] // 取无序数组最后一个数为基准值
                while (i < j) { //把所有比基准值小的数放在左边大的数放在右边
                    while (i < j && arr[i] <= baseVal) { //找到一个比基准值大的数交换
                        i++
                    }
                    arr[j] = arr[i] // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
                    while (j > i && arr[j] >= baseVal) { //找到一个比基准值小的数交换
                        j--
                    }
                    arr[i] = arr[j] // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
                }
                arr[j] = baseVal // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
                sort(arr, left, j - 1) // 将左边的无序数组重复上面的操作
                sort(arr, j + 1, right) // 将右边的无序数组重复上面的操作
            }
            const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组
            sort(newArr)
            return newArr
        }
        // jsonp
    function foo(data) {
        console.log()
    }
    
    function addscriptTags(src) {
        var script = document.createElement('script')
        script.setAttribute("type", "text/javascript")
        script.src = src
        document.body.appendChild(script)
    }
    window.onload = function() {
        addscriptTags("http://example.com/ip?callback = foo")
    }
    
    
    //实现一个foo函数，返回自身调用次数：
    function helper() {
        var count = 0;
        return function() {
            count++;
            console.log("count", count)
        }
    }
    var foo = helper()
        //发布订阅者模式
        //创建一个对象(缓存列表)
        //on方法用来把回调函数fn都加到缓存列表中
        //emit方法取到arguments里第一个当做key，根据key值去执行对应缓存列表中的函数
        //remove方法可以根据key值取消订阅
    let event = {
        list: {},
        on(key, fn) {
            if (!this.list[key]) {
                this.list[key] = [];
            }
            this.list[key].push(fn);
        },
        emit() {
            let key = [].shift.call(arguments),
                fns = this.list[key];
    
            if (!fns || fns.length === 0) {
                return false;
            }
            fns.forEach(fn => {
                fn.apply(this, arguments);
            });
        },
        remove(key, fn) {
            // 这回我们加入了取消订阅的方法
            let fns = this.list[key];
            // 如果缓存列表中没有函数，返回false
            if (!fns) return false;
            // 如果没有传对应函数的话
            // 就会将key值对应缓存列表中的函数都清空掉
            if (!fn) {
                fns && (fns.length = 0);
            } else {
                // 遍历缓存列表，看看传入的fn与哪个函数相同
                // 如果相同就直接从缓存列表中删掉即可
                fns.forEach((cb, i) => {
                    if (cb === fn) {
                        fns.splice(i, 1);
                    }
                });
            }
        }
    };
    
    function cat() {
        console.log('一起喵喵喵');
    }
    
    function dog() {
        console.log('一起旺旺旺');
    }
    
    event.on('pet', data => {
        console.log('接收数据');
        console.log(data);
    });
    event.on('pet', cat);
    event.on('pet', dog);
    // 取消dog方法的订阅
    event.remove('pet', dog);
    // 发布
    event.emit('pet', ['二哈', '波斯猫']);
    /*
        接收数据
        [ '二哈', '波斯猫' ]
        一起喵喵喵
    */
    let crop = {}
    crop.list = {}
    crop.on = function(key, fn) {
        if (!this.list[key]) {
            this.list[key] = []
        }
        //有了的话直接把函数添加到缓存队列里
        this.list[key].push(fn)
    
    }
    crop.emit = function() {
        //用shift取出第一个参数---key值
        let key = [].shift.call(arguments)
            //把函数列表取出来放在fns中
        fns = this.list[key]
            //如果缓存队列没有函数的话就返回false
        if (!fns || fns.length === 0) {
            return false
        } else {
            fns.forEach(fn => {
                fn.apply(this, arguments)
            })
        }
    }
    
    //手写封装ajax的处理
    
    //LazyMan的实现
    //
    
    //要求任务并行完成，同时并行的任务不能超过两个。
    
    class Scheduler {
        constructor() {
            this.cur = 0;
            this.prepare = [];
        }
        run() {
            if (this.prepare.length == 0) return;
            const [task, resolve] = this.prepare.shift();
            this.cur += 1;
            task().then(_ => {
                this.cur -= 1
                resolve();
                this.run();
            })
        }
        add(promiseCreator) {
            return new Promise((res, rej) => {
                this.prepare.push([promiseCreator, res]);
                if (this.cur < 2) {
                    this.run();
                }
            })
        }
    }
    const timeout = (time) => new Promise(resolve => {
        console.log("in timeout:", time);
        setTimeout(resolve, time)
    });
    const scheduler = new Scheduler();
    const addTask = (time, order) => {
        scheduler.add(() => timeout(time)).then(() => console.log(order))
    };
    addTask(1000, '1')
    addTask(500, '2')
    addTask(300, '3')
    addTask(400, '4')
    addTask(100, '5')
        // output: 2 3 1 5 4
        // 一开始，1、2两个任务进入队列
        // 500ms时，2完成，输出2，任务3进队
        // 800ms时，3完成，输出3，任务4进队
        // 1000ms时，1完成，输出1，任务5进队
        // 1100ms时，5完成，输出5// 1200ms时，4完成，输出4
    
    //原生ajax
    function ajax(method, url, data, callback, type) {
        var xhr;
        if (window.XMLHttpRequest) {
            xhr = new XMLHttpRequest()
        } else {
            xhr = new ActiveXObject("Microsoft.XMLHttp")
        }
        xhr.onreadystateChange = function() {
            if (xhr.state == 200 && xhr.readyState == 4) {
                if (type == "json") {
                    var res = JSON.parse(xhr.responseText);
                } else if (type == "xml") {
                    var res = responseXML
                } else {
                    var res = xhr.responseText
                }
                callback(res)
            }
        }
        var param = ''
        if (JSON.stringify(data) != '{}') {
            url += '?'
            for (var i in data) {
                param += i + '=' + data[i] + "&"
            }
            param = param.slice(0, param.length - 1)
        }
    
        if (method == 'get') {
            url = url + param
        }
        //初始化请求
        xhr.open(method, url, true)
        if (method == 'post') {
            xhr.setRequestHeader("content-Type", "application/x-www-fprm-urlencoded")
            xhr.send(param)
        } else {
            xhr.send(null)
        }
    
    }
    //promise.all的实现
    Promise.all = function(promises) {
            return new Promise((resolve, reject) => {
                let index = 0;
                let result = [];
                if (promises.length === 0) {
                    resolve(result);
                } else {
                    function processValue(i, data) {
                        result[i] = data;
                        if (++index === promises.length) {
                            resolve(result);
                        }
                    }
                    for (let i = 0; i < promises.length; i++) {
                        //promises[i] 可能是普通值
                        Promise.resolve(promises[i]).then((data) => {
                            processValue(i, data);
                        }, (err) => {
                            reject(err);
                            return;
                        });
                    }
                }
            });
        }
        //防抖
    function debounce(fn, time) {
        let timer = null;
        return function() {
            if (timer) {
                clearTimeout(timer)
            }
            timer = setTimeout(() => {
                fn.apply(this, arguments)
            }, time)
        }
    }
    // 防抖函数
    const debounce = (fn, delay) => {
        let timer = null;
        return (...args) => {
            clearTimeout(timer);
            timer = setTimeout(() => {
                fn.apply(this, args);
            }, delay);
        };
    };
    //节流
    function throttle(fn, delay) {
        let flag = true
        return function() {
            if (!flag) return
            flag = false
            setTimeout(() => {
                fn.apply(this, arguments)
                flag = true
            }, delay)
        }
    }
    //数组去重
    //set(转化为数组有两种，拓展运算符，Array.from(new set(myarr)))
    function unique(arr) {
        var newArr = []
        for (let i = 0; i < arr.length; i++) {
            if (newArr.indexOf(arr[i]) === -1) {
                newArr.push(arr[i])
            }
        }
        return newArr
    }
    
    function unique1(arr) {
        var sortArr = arr.sort()
        var newArr = []
        for (let i = 0; i < arr.length; i++) {
            if ((sortArr[i] !== sortArr[i - 1])) {
                newArr.push(sortArr[i])
            }
        }
        return newArr;
    }
    
    function unique2(arr) {
        var newArr = []
        for (let i = 0; i < arr.length; i++) {
            if (newArr.includes(arr[i])) {
                newArr.push(arr[i])
            }
        }
    }
    
    function unique4(arr) {
        return Array.from(new set(arr))
    }
    
    function unique(arr) {
        var newarr = []
        newarr = arr.filter(function(item) {
            return newarr.includes(item) ? '' : newarr.push(item)
        })
        return newarr
    }
    
    function unipue5() {
        const newarr = []
        this.forEach((item) => {
            if (!newarr.includes(item)) {
                newarr.push(item)
            }
        })
        return newarr
    }
    
    function unique8() {
        const tmp = new Map()
        const newarr = []
        for (let i = 0; i < arr.length; i++) {
            if (!tmp.has(arr[i])) {
                tmp.set(arr[i], 1)
                newarr.push(arr[i])
            }
        }
    }
    
    function unique3(arr) {
        var obj = {}
        var newArr = []
        for (let i = 0; i < arr.length; i++) {
            if (!obj[arr[i]]) {
                obj[arr[i]] = 1
                newArr.push(arr[i])
            }
        }
        return newArr
    }
    //数组扁平化处理
    let arr = [
        [1, 2], 3, [
            [
                [4], 5
            ]
        ]
    ]; // 数组展平
    function flatten(arr) {
        return [].concat(
            ...arr.map(x => Array.isArray(x) ? flatten(x) : x)
        )
    }
    
    //全排列
    const permute = function(nums) {
        if (nums.length <= 1) return [nums]
    
        const permutes = []
        for (let i = 0; i < nums.length; i++) {
            const num = nums[i]
            const others = nums.slice(0, i).concat(nums.slice(i + 1))
            const list = permute(others)
            list.forEach(item => {
                permutes.push([num].concat(item))
            })
        }
        return permutes
    };
    const arr = [1, 2, 3]
    console.log(permute(arr))
    
    
    //根据数组某个属性去重
    function unique(arr) {
        const res = new Map()
        return arr.filter(item => {
            !res.has(item.productName) && res.set(item.productName, 1)
        })
    }
    //promise的finally实现
    Promise.prototype.finally = function(callback) {
            const p = this.constructor
            return this.then(
                value => p.resolve(callback()).then(() => value),
                reason => p.resolve(callback()).then(() => { throw reason })
            )
        }
        // computed的实现
        //1.data 属性初始化 getter setter
        //2. computed 计算属性初始化，提供的函数将用作属性 vm.reversedMessage 的 getter
        //3. 当首次获取 reversedMessage 计算属性的值时，Dep 开始依赖收集
        //4. 在执行 message getter 方法时，如果 Dep 处于依赖收集状态，则判定 message 为 reversedMessage 的依赖，并建立依赖关系
        //5. 当 message 发生变化时，根据依赖关系，触发 reverseMessage 的重新计算
        //十进制转化为其他进制(利用栈)
    function divideBy2(decNumber, base = 2) {
        let remStack = new Stack()
        let rem
        let binaryString = ''
        let digits = '0123456789ABCDEF'
        while (decNumber > 0) {
            rem = Math.floor(decNumber % base)
            remStack.push(rem)
            decNumber = Math.floor(decNumber / base)
        }
        while (!remStack.isEmpty()) {
            binaryString += digits[remStack.pop()].toString()
        }
        return binaryString
    }
    
    // 将十进制转换成其他进制
    let num = 100345
    num.toString(2) // "11000011111111001"
    num.toString(8) // "303771"
    
    console.log(divideBy2(num, 2)) // "11000011111111001"
    console.log(divideBy2(num, 8)) // "303771"
    
    //push 和pop的实现（Array的push底层实现是依赖于 数组的length属性的）
    Array.prototype.push2 = function(...rest) {
        this.splice(this.length, 0, ...rest)
        return this.length;
    }
    
    //简易promise的实现
    class Promise {
        constructor(fn) {
            this.status = 'Pending'
            setTimeout(() => {
                fn((data) => {
                    this.resolve(data)
                }, (error) => {
                    this.reject(error)
                })
            })
        }
    
        resolve(data) {
            if (this.status === 'Pending') {
                this.success(data)
                this.status = 'Fulfilled'
            }
        }
    
        reject(error) {
            if (this.status === 'Pending') {
                this.error(error)
                this.status = 'Rejected'
            }
        }
    
        then(success, error) {
            this.success = success
            this.error = error
        }
    }
    
    let p1 = new Promise((resolve, reject) => {
        // reject('hello error');
        setTimeout(() => {
            resolve('hello promise')
        }, 1000)
    })
    
    p1.then((data) => console.log(data), (err) => console.log(err))
    
    //在一个数组中 如a、b两项, 要保证a和b两项的差 与 a和b两项索引的差 的相加后的结果max 是数组中其他两项max 中的最大值 找出符合条件两项a, b的值 (不可以排序 或改变数组位置)
    // 思路：其实也就是找出数组中当前的每一项与自身索引相加后的和的最大值以及与索引相加后的最小值的和 找出符合条件的两项即可 如 let result = (maxItem-minItem) + (maxIndex-minIndex) 等价于 (maxItem+maxIndex) - (minItem+minIndex)
    
    // let arr = [1, 2, 3, 4, 5, 6]; // 最简单的测试数组 最小项1 最大项6
    // 很显然这个数组中最大值6与索引相加(6+5)是当中最大值11 1与索引相加(1+0)为当中的最小值1（6 + 5）-（1+0）= 10
    
    // 假设法
    let arr = [2, 10, 9, 1, 8, 3, 4];
    let minItem = arr[0]; // 假设第一项与自身索引的和是最小值 索引为0因此省略
    let maxItem = arr[0]; // 假设第一项与自身索引的和是最大值 索引为0因此省略
    let min = minItem; // 最小项
    let max = maxItem; // 最大项
    let minIndex = 0; // 最小项索引
    let maxIndex = 0; // 最大项索引
    for (let i = 1; i < arr.length; i++) {
        let cur = arr[i] + i; // 当前项和自身索引的和
        cur < minItem ? (minItem = cur, min = arr[i], minIndex = i) : null;
        cur > maxItem ? (maxItem = cur, max = arr[i], maxIndex = i) : null;
    }
    console.log(maxItem, minItem); // 最大项与索引的和 最小项与索引的和
    console.log(max, min); // 最大项 最小项
    console.log(maxIndex, minIndex); // 最大项的索引 最小项的索引