JavaScript - 算法

数组相关

各种排序算法

• 关于排序的稳定性：
  • 稳定：冒泡、插入、归并、桶排（计数排序）
  • 不稳定：选择、快排、希尔、堆排
• 桶排
  • 在这里简单讲一下，桶排看这里 (opens new window)
• 冒泡

var arr = [29, 45, 51, ,90, 68, 72, 97];
function Up_sort(arr) {
  for(let i=0; i<arr.length-1; i++){
    for(let j=0; j<arr.length-1-i; j++){
      if(arr[j] > arr[j+1]){
          
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]] //es6的解构赋值，直接交换两个数。
      }
    }
  }
  return arr;
}
console.log(Up_sort(arr));  // [29, 45, 51, 68, 72, 90, 97]

• 快速排序
  1. 定义一个函数，传入参数，判断这个参数的长度，如果长度是1，直接ruturn出去，如果是进入下一步。
  2. 将这个数组从中间截取，取出这个数组的中位数，定义两个新的数组arrleft,arrright,r然后让原数组中剩余的数与这个中位数比较，比中位数小的放到arrleft数组，比中位数大的放到arrright,然后再对这两个数组进行递归。
  3. 最后将arrleft,中位数，arrright拼接。return出去

var array = [29, 45, 51, 90, 68, 72, 97];
function quickSort(arr) {
  if(arr.length <= 1){
    return arr;
  }
  let contentIndex = Math.floor(arr.length / 2);
  // 把比较的数字从数组里删掉
  let contentValue = arr.splice(contentIndex, 1)[0];
  let left = [], right = [];
  for(let i=0; i<arr.length; i++){
    let item = arr[i];
    item > contentValue ? right.push(item) : left.push(item);
  }
  return quickSort(left).concat(contentValue, quickSort(right));
}
array = quickSort(array);
console.log(array);     // [29, 45, 51, 68, 72, 90, 97]

• 插入排序

// 插入排序
function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let j = i;
    let target = arr[j];
    while (j > 0 && arr[j - 1] > target) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = target;
  }
  return arr;
}
// console.log(insertSort([3, 6, 2, 4, 1]));

• 归并

//归并排序
function mergeSort(arr) {
  // 合
  function merge(left, right) {
    let arr = [];
    while(left[0] && right[0]) {
      left[0] < right[0] ? arr.push(left.shift()) : arr.push(right.shift());
    }
    return arr.concat(left).concat(right);
  }
  // 分
  function sort(arr) {
    if(arr.length < 2) return arr;
    let mid = Math.floor(arr.length / 2);
    return merge(sort(arr.slice(0, mid)), sort(arr.slice(mid)));
  }
  return sort(arr)
}

const arr1 = [1,6,5,4,2,3,8]
console.log(mergeSort(arr1))

• 选择排序

function selectSort(arr) {
  // 缓存数组长度
  const len = arr.length;
  // 定义 minIndex，缓存当前区间最小值的索引，注意是索引
  let minIndex;
  // i 是当前排序区间的起点
  for (let i = 0; i < len - 1; i++) {
    // 初始化 minIndex 为当前区间第一个元素
    minIndex = i;
    // i、j分别定义当前区间的上下界，i是左边界，j是右边界
    for (let j = i; j < len; j++) {
      // 若 j 处的数据项比当前最小值还要小，则更新最小值索引为 j
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 如果 minIndex 对应元素不是目前的头部元素，则交换两者
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}
// console.log(quickSort([3, 6, 2, 4, 1]));

数组扁平化（拍平）

• 数组拍平，即把数组里面的数组打开，合并成一个数组。
• 例如：var arr = [1,2,[3,4,5,[6,7,8],9],10,[11,12]];

1. 递归

function fn(array) {
  let arr = [];
  arr.forEach((val) => {
      if(val instanceof Array){
        arr1 = arr1.concat(fn(val))
      } else {
          arr1.push(val)
      }
  })
  return arr1
}

2. reduce实现

• reduce:对数组中的所有元素调用指定的回调函数。该函数的返回值为累积结果，并且此返回值在下一次调用 该回调函数时作为参数。

• 语法：arr1.reduce(callbackfn[,initiaValue])

  • callbackfn：回调函数,prev是指上一次的返回值or初始值，curr是当前值
  • initiaValue：可选，如果指定，则它将作为初始值。

  function fn(arr) {
    return arr.reduce((prev, cur) => {
        return prev.concat(Array.isArray(cur)? fn(cur):cur)
    },[])
  }
  

  • 图是这样的
  • 

3. flat

arr.flat(Infinity)

4. 扩展运算符

function fn(arr) {
  let arr1 = []
  let bStop = true
  arr.forEach((val) => {
      if(Array.isArray(val)){
          arr1.push(...val)
            bStop = false
      } else {
          arr1.push(val)
      }
  })
  if(bStop){
      return arr1
  }
  return fn(arr1)
}

5. toString

let arr1 = arr.toString().split(',').map((val)=>{
    return parseInt(val)
})
console.log(arr1)

6. apply

function fn(arr) {
  while(arr.some(item => Array.isArray(item))){
      arr = [].concat.apply([], arr)
  }
  return arr
}

数组去重

• map

var a = new Array(1,2,3,4,5,6,7,8,8);
function unique(arr) {
    let map = new Map();
    let res = new Array();
    for(let i=0; i<arr.length; i++) {
        // key存在
        if(map.has(arr[i])) map.set(arr[i], true);
        // key不存在
        else {
            map.set(arr[i], false);
            res.push(arr[i]);
        }
    }
    return res;
}
console.log(unique(a));

• splice

  • 两层循环，通过splice来删除重复元素。缺点：无法对NaN去重，因为比较时NaN !== NaN.

  function distinct(arr) {
    var arr = this, i, j;
    len = arr.length;
    for(i=0; i<len; i++){
        for(j=i+1; j<len; j++){
            if(arr[i] === arr[j]){
                arr.splice(j, 1);
                len--;    // 保证len长度随着删除而变化
                j--;      
            }
        }
    }
    return arr;
  }
  var a = [1,2,3,4,4,4,5,6,7];
  var b = distinct(a);
  console.log(b.toString())   //1,2,3,4,5,6,7
  

• indexOf

  • 新建空数组，遍历需要去重的数组，将数组元素存入新数组中，存放前判断数组中是否已含有当前元素，没有 则存入。缺点：无法对NaN去重
  • indexOf: 返回String中第一次出现的指定的值的索引，没有则返回-1

  function distinct(arr) {
    const newArr = [];
    arr.forEach(item => {
        if(newArr.indexOf(item) === -1) newArr.push(item);
    })
    return newArr;
  }
  const a = [1,2,3,3,4,5,6,7];
  const res = distinct(a);
  console.log(res)
  

• sort()

function unique(arr) {
    if(!Array.isArray(arr)) return "type err!";
    arr = arr.sort();
    var array = [arr[0]];
    for(let i=1; i<arr.length; i++){
        if(arr[i] !== arr[i-1]) array.push(arr[i]);
    }
    return array;
}

• set (ES6最常用)

let a = [1,2,3,3,4,5,6,7,8];
function unique(arr) {
  return Array.from(new Set(arr));
}
console.log(unique(a));

防抖节流

防抖

function debounce(fn, wait) {
    let timer;
    return function () {
      const args = arguments
      if(timer) clearTimeout(timer)
      let timer = setTimeout(() => {
          fn.apply(this, args)
      },wait)
    }
}
// 验证
window.addEventListener(
    "scroll",
    debounce(() => {
        console.log(111)
    },1000)
)

节流

function throttle(fn, wait) {
  let flag = true;
  return () => {
      if(!flag) return
      flag = false
    timer = setTimeout(() => {
        fn()
        falg = true
    },wait)
  }
}
// 验证
window.addEventListener(
        "scroll",
        throttle(() => {
          console.log(222)
        },1000)
)

计算数组中每个元素出现的次数

• reduce

let names = ["apple", "banana", "apple", "pair"];
let countedNames = names.reduce((obj, name) => {
    if(name in obj) obj[name]++;
    else obj[name]=1;
    return obj;
}, {})
// {}是obj的初始值
console.log(countedNames);
// {apple: 2, banana: 1, pair: 1}

• map

let names = ["apple", "banana", "apple", "pair"];
function getEleNums(data) {
    let map = {};
    for(let i=0; i<data.length; i++) {
        let key = data[i];
        if(map[key]) map[key]+=1;
        else map[key]=1;
    }
    return map;
}
console.log(getEleNums(names));

将二维数组转一维

• 参考上面的数组拍平（一样的）

对象扁平化

• 题

// 实现一个 flatten 函数，实现如下的转换功能
const obj = {
  a: 1,
  b: [1, 2, { c: true }],
  c: { e: 2, f: 3 },
  g: null,
};
// 转换为
let objRes = {
  a: 1,
  "b[0]": 1,
  "b[1]": 2,
  "b[2].c": true,
  "c.e": 2,
  "c.f": 3,
  g: null,
};

• 基本思路与题解：其实思路都是一样的。就是遍历对象，判断每个属性的数据类型，然后做相应的处理。

function flatten(obj) {
    let res = {}
    let process = (key, val) => {
        console.log(Object(val))
        if(Object(val) !== val){
            if(key) res[key] = val;
        } else if(Array.isArray(val)){
            for(let i=0; i<val.length; i++){
                process(`${key}[${i}]`, val[i])
            }
            if(val.length === 0) res[key] = []
        } else {
            let objArr = Object.keys(val)
            objArr.forEach(item => {
                process(key? `${key}.${item}` : `${item}`, val[item])
            })
            if(objArr.length === 0 && key) res[key] = {}
        }
    }
    process('', obj)
    return res;
}
console.log(flatten(obj))

对象里的属性求和

• reduce

let obj = [
  {name: "a", price: 14},
  {name: "b", price: 24},
  {name: "c", price: 25},
];
let total = obj.reduce((pre,cur) => {
    return pre+cur.price;
}, 0);
console.log(total);

二叉树遍历

• 前序

const preOrder = (root) => {
    console.log(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

• 中序

const inOrder = (root) => {
    inOrder(root.left);
    console.log(root.val);
    inOrder(root.right);
}

• 后序

const postOrder = (root) => {
    postOrder(root.left);
    postOrder(root.right);
    console.log(root.val);
}

手写instanceof

• 用于测试构造函数的prototype属性是否出现在对象原型链中的任何位置。
• 思路：instanceof左侧必须是对象，右侧必须是函数，因为只有对象能找到原型链，函数才有prototype属性。然后 迭代，左侧对象的原型不等于右侧的prototype，沿着原型链重新赋值

//L instanceof R 变量R的原型存在于变量L的原型链上。
function my_instanceof(L, R) {
  // 验证如果为基本数据类型，就直接返回false
  const bastType = ['string', 'number', 'boolean', 'null', 'undefined', 'symbol'];
  if(bastType.includes(typeof (L))) return false;
  let RP = R.prototype;     // 取R的显式原型
  L = L.__proto__;          // 取L的隐式原型
  while(true) {
      if(L === null) return false;  // 找到最顶层
      if(L === RP) return true;     // 严格相等
      L = L.__proto__;      //没找到继续向上一层原型链查找
  }
}

Promise

all

function all(args) {
  return new Promise((resolve, reject) => {
      const result = [];
      let index=0, fullCount=0;
      for(const item of args){
          let resIndex = index;
          index += 1;
          Promise.resolve(item).then(res => {
              result[resIndex] = res;
              fullCount += 1;
              if(fullCount === index) resolve(res);
          }).catch(err => {
              reject(err);
          })
      }
      if(index === 0) resolve(res);
  })
}
// test
let p1 = new Promise((res, rej) => {
    res('p1 success');
})
let p2 = new Promise((res, rej) => {
  rej('p2 failed');
})
this.all([p1, p2]);

race

function my_race(args) {
  return new Promise((resolve, reject) => { 
      for(let i=0; i<args.length; i++){
          args[i].then(resolve, reject);
      }
  })
}
// test
let p1 = new Promise((res, rej) => {
  res('p1 success');
})
let p2 = new Promise((res, rej) => {
  rej('p2 failed');
})
this.my_race([p1, p2]);

allSelected

• 无论参数实例resolve还是reject，Promise.allSettled都会执行then方法的第一个回调函数 （意思就是不会catch到参数实例的reject状态），其回调函数的参数返回的数组的每一项是一个包 含status和value或者reason的一组对象。
• 无论参数实例是否reject，最终Promise.allSettled内部都会resolve，只不过会添加一个状态 status来记录对应的参数实例是否执行成功。我们可以依据这个状态去过滤掉rejected的数据，只操 作fulfilled的数据，就会得到我们想要的业务逻辑了。

//定义状态和返回结果
const formatSettledResult = (success,value)=>
success 
? {status:'fulfilled',value}
: {status:'rejected',reason:value};

//定义all_settled
Promise.all_settled = function(iterators){
    //转为数组
    const promises = Array.from(iterators);
    //传入Promise 实例的数量
    const num = promises.length;
    //返回的结果数组
    const resultList = new Array(num);
    //对要处理的传入参数的promise实例的计数
    let resultNum = 0;
    //返回一个Promise实例，由于allSettled 总返回 fulfilled 状态所以这里仅在 resolve 回调中处理
    return new Promise((resolve)=>{
        //遍历传入的promise实例数组
        promises.forEach((promise,index)=>{
            //用Promise.resolve包裹
            Promise.resolve(promise)
            .then(value=>{
                //fulfilled状态，结果数组中添加每个实例的状态
                resultList[index] = formatSettledResult(true,value);
                if(++resultNum === num){
                    //实例处理完成，返回结果数组
                    resolve(resultList);
                }
            })
            .catch(error=>{
                //rejected状态，结果数组中添加每个实例的状态
                resultList[index] = formatSettledResult(false,error);
                if(++resultNum === num){
                    //实例处理完成，返回结果数组
                    resolve(resultList);
                }
            })
        })
    })
}
 
//测试
const resolved = Promise.resolve(42);
const rejected = Promise.reject(-1);
const allSettedPromise = Promise.all_settled([resolved, rejected]);
allSettedPromise.then(function (results) {
    console.log(results);
});

Vue相关

template引擎实现

let template = '我是{{name}}，年龄{{age}}，性别{{sex}}';
let data = {
  name: '姓名',
  age: 18
}
render(template, data); // 我是姓名，年龄18，性别undefined
function render(template, data) {
  const reg = /\{\{(\w+)\}\}/; // 模板字符串正则
  if (reg.test(template)) { // 判断模板里是否有模板字符串
    const name = reg.exec(template)[1]; // 查找当前模板里第一个模板字符串的字段
    template = template.replace(reg, data[name]); // 将第一个模板字符串渲染
    return render(template, data); // 递归的渲染并返回渲染后的结构
  }
  return template; // 如果模板没有模板字符串直接返回
}