编程题（一）

最近迷上做js算法题了，哈哈哈，以后会持续更新我做过比较经典有意思的算法题，我目前只做一些比较基础的，查缺补漏，感觉自己的js基础还是欠缺，勤能补拙，先把地基打好才能盖出好房子，你说是吧~~

数组降维

将多维数组降成一维数组结构
方法一：

function _myFlat(arr) {
    var res = [];
    for (var i = 0; i < arr.length; i++) {
        // 判断当前元素是否是数组
        if (Array.isArray(arr[i])) {
            // arguments.callee（）：匿名函数的递归调用，保证函数的封装性，与函数名解耦
            res = res.concat(arguments.callee(arr[i]));
        } else {
            res = res.concat(arr[i])
        }
    };
    return res;
};
console.log(_myFlat([1, 2, 4, [5, [6, [8]]]])); // [1,2,4,5,6,8]

方法二：

[1, 2, 4, [5, [6, [8]]]].flat(Infinity);  // 由于是es2019新特性，so不兼容IE，需要babel转义

数组对象方法扩展

题目描述：
已知数组 data= [{ name: ‘低风险’, value: 300 }, { name: ‘中风险’, value: 230 }, { name: ‘高风险’, value: 409 }]；
获取指定key值所对应的value数组

const getName = function(arr, key) {
    if (!Array.isArray(arr) || !key) {
        throw new Error("param is error");
    };
    let res = [];
    arr.map(function(item, index) {
        if (item[key]) {
            res.push(item[key]);
        }
    });
    return res;
};

var data = [{
    name: '低风险',
    value: 300
}, {
    name: '中风险',
    value: 230
}, {
    name: '高风险',
    value: 409
}];
let names = getName(data, "name");

console.log(names); // ["低风险", "中风险", "高风险"]

函数防抖/节流

 // 函数防抖

 // 就是指触发事件后，在 n 秒内函数只能执行一次，如果触发事件后在 n 秒内又触发了事件，则会重新计算函数延执行时间。

 // 常见需要防抖事件 onresize，scroll，mousemove ,mousehover

 function debounce(fn, wait) {
     var timer = null;
     return function() {
         if (timer !== null) {
             clearTimeout(timer);
         };
         timer = setTimeout(fn, wait)
     }
 };

 function handle() {
     console.log(Math.random())
 };

 window.addEventListener("resize", debounce(handle, 1000));

 /**

  + 函数节流

  作用：减少代码执行次数，提升网页性能 
  函数节流使用场景： oninput/ onmousemove /onscroll /onresize 等事件

  + 1 搜索框搜索输入，只需用户最后一次输入完，再发送请求

  + 2 防止用户多次点击提交表单

 */


 function throttle(fn, delay) {
     let timer = null;
     let flag = true;
     // 闭包 方便调用，避免全局变量污染
     return function() {
         if (!flag) return;
         flag = false;
         timer && clearTimeout(timer);
         setTimeout(() => {
             fn();
             flag = true;
         }, delay);
     };
 };

 function scroll() {
     console.log(Math.random());
 };

// 冒泡：从里面往外面触发事件
// 捕获：从外面往里面触发事件
// addEventListener()第三个参数： true 是捕获，false是冒泡
 window.addEventListener('resize', throttle(scroll, 3000), false);

二分查找算法

function search(arr, data) {
    var max = arr.length - 1, //最大值
        min = 0; //最小值
    while (min <= max) {
        var mid = Math.floor((max + min) / 2); //中间值
        if (arr[mid] < data) {
            min += 1;
        } else if (arr[mid] > data) {
            max -= 1;
        } else {
            return mid;
        }
    }
    return -1; //没找到返回-1
}
// console.log(search([1, 2, 3, 4, 8], 8));

冒泡排序

原理
依次比较相邻的两个值，如果后面的比前面的小，则将小的元素排到前面。依照这个规则进行多次并且递减的迭代，直到顺序正确。

function bubbleSort(arr) {
    // 利用双层循环实现
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j + 1] < arr[j]) {
                let temp = arr[j]; // 将最大的值暂存
                arr[j] = arr[j + 1]; // 重新进行赋值
                arr[j + 1] = temp;
            }
        }
    };
    return arr;
};
bubbleSort([1, 3, 10, 6, 4, 0, 2]);

快速排序

原理
从数组中选定一个基数，然后把数组中的每一项与此基数做比较，小的放入一个新数组，大的放入另外一个新数组。然后再采用这样的方法操作新数组。直到所有子集只剩下一个元素，排序完成。

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    } //判断数组，一个长度直接返回 
    var baseNum = arr[0];
    var left = [];
    var right = [];
    var mid = [];
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < baseNum) {
            left.push(arr[i])
        } else if (arr[i] > baseNum) {
            right.push(arr[i]);
        } else {
            mid.push(arr[i]);
        }
    }
    return quickSort(left).concat(mid, quickSort(right));
};
var _sort = quickSort([1, 3, 2, 4]);
console.log(_sort); // [1,2,3,4]

插入排序

原理
快速排序类似于整理扑克牌，每次将下一个值和上一个值进行比较大小，然后互换位置，在小规模数据或者基本有序数据时特别高效.

function insertSort(arr) {
    let temp;
    for (let i = 1; i < arr.length; i++) {
        for (let j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        };
    };
    return arr;
};

let res = insertSort([2, 5, 10, 7, 10, 32, 90, 9, 11, 1, 0, 10]);
console.log(res) // [0, 1, 2, 5, 7, 9, 10, 10, 10, 11, 32, 90]

选择排序

原理
首先从原始数组中找到最小的元素，并把该元素放在数组的最前面，然后再从剩下的元素中寻找最小的元素，放在之前最小元素的后面，知道排序完毕。

function selectSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let minIndex = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                minIndex = j;
            };
        };
        let temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    };
    console.log(arr); // [0, 1, 2, 3, 4, 6, 10]
};
selectSort([1, 3, 10, 6, 4, 0, 2]);

//minIndex始终保存着最小值的位置的索引，随着i的自增，遍历的数组长度越来越短，直到完成排序。

vue 实现双向绑定原理

vue2.x版本

vue实现数据双向绑定主要是：
采用数据劫持结合发布者-订阅者模式的方式，通过 Object.defineProperty() 来劫持各个属性的 setter ， getter ，在数据变动时发布消息给订阅者，触发相应监听回调。
当把一个普通 Javascript 对象传给 Vue 实例来作为它的 data 选项时，Vue 将遍历它的属性，用 Object.defineProperty() 将它们转为 getter/setter 。
用户看不到 getter/setter ，但是在内部它们让 Vue 追踪依赖，在属性被访问和修改时通知变化。

let obj = {}; 
let value = ""; 
Object.defineProperty(obj, "value", {

    get() {
	// 读取值得时候会触发get操作
        console.log("get")
        return value;
    },
    set(newVal) {
	// 修改对象的value值时触发set
        console.log("set");
        return value = newVal;
    }

}); 

obj.value = 123; // 触发set
console.log(obj.value); // 触发get