js常用算法整理

冒泡排序（时间复杂度O(n*n)）

let arr = [3,5,1,7,3,0]
function sort (arr){
  for(let i = 0; i< arr.length; i++){
    for(let j = 0; j < arr.length - i; j++){
      if(arr[j] > arr [j+1]){
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
      }
    }
  }
  return arr
}
sort(arr)
复制代码

快速排序（时间复杂度：O(nlogn)）

let arr = [3,5,1,7,3,0]
function sort (arr){
  if(arr.length <= 0) return arr;
  let index = Math.floor(arr.length/2)
  let basic = arr.splice(index, 1)[0];
  let left = [];
  let right = [];
  for(let i = 0; i < arr.length; i++){
    if(arr[i] > basic){
      right.push(arr[i])
    } else {
      left.push(arr[i])
    }
  }
  return [...sort(left), basic, ...(right)]
}
sort(arr)
复制代码

数组转树形结构

let list = [
  { id: 1, name: '部门1', parentId: 0 },
  { id: 2, name: '部门2', parentId: 1 },
  { id: 3, name: '部门3', parentId: 1 },
  { id: 4, name: '部门4', parentId: 3 },
  { id: 5, name: '部门5', parentId: 4 },
]

function convert(list) {
  let arr = []
  // let obj = list.reduce((res, v) => (res[v.id]=v, res), {})
  let obj = {};
  list.forEach((item) => (obj[item.id]= item))  // 浅拷贝，拷贝内存地址
  for(let item of list){
    if (item.parentId == 0){
      arr.push(item)
      continue
    }
    let parent = obj[item.parentId]
    parent.children = parent.children || []
    parent.children.push(item)
  }
  return arr
}
convert(list)
复制代码

树形结构转成列表

let tree = [
    {
        id: 1,
        text: '节点1',
        parentId: 0,
        children: [
            {
                id:2,
                text: '节点1_1',
                parentId:1
            }
        ]
    }
]
function tree2List (tree) {
  let result = [];
  tree.map(item => {
    if(Array.isArray(item.children)){
      result = [...result, item, ...tree2List(item.children)];
      delete item.children
    } else {
      result.push(item)
    }
  })
  return result
}
tree2List(tree)
复制代码

数组扁平化

let arr = [1, [2, [2, [3]], 3], 4, 5]  //  [1, 2, 2, 3, 3, 4, 5]
function arrFlatten (arr) {
  let newArr = []
  arr.forEach(item => {
    if(Array.isArray(item)){
      newArr = [...newArr, ...arrFlatten(item)]
    } else {
      newArr.push(item)
    }
  })
  return newArr
}
arrFlatten(arr)
复制代码

实现对象的扁平化

const obj = { a: 1, b: [1, 2, { c: true }], c: { e: 2, f: 3 }, g: null, };
let flatten = (obj) => {
    let result = {};
    let process = (key, value) => {
    	// 首先判断是基础数据类型还是引用数据类型
        if (Object(value) !== value) {
        	// 基础数据类型
            if (key) {
            	result[key] = value;
            }
        } else if(Array.isArray(value)){
       		for (let i = 0; i< value.length; i++) {
            	process(`${key}[${i}]`, value[i])
            }
            if (value.length === 0) {
            	result[key] = [];
            }
        } else {
            let objArr = Object.keys(value);
            objArr.forEach(item => {
            	process(key?`${key}.${item}`:`${item}`, value[item])
            });
            if (objArr.length === 0 && key) {
            	result[key] = {};
            }
        }
    }
    process('', obj)
    return result;
}
flatten(obj)
复制代码

DOM 节点输出 JSON 的格式

function dom2Json(vnode){
 let obj = {tag: vnode.targetName, childern: [] }
 vnode.childNodes.forEach(child => obj.childern.push(dom2Json(child)))
 return obj;
}
复制代码

虚拟 Dom 转化为真实 Dom

function render(vnode){
 if(typeof vnode == 'number') {
  vnode = vnode.toString();
 }
 if(typeof vnode == 'string') {
   return document.createTextNode(vnode)
 }
 let dom = document.createElement(vnode.tag)
 if(vnode.attr) {
   Object.keys(vnode.attr).forEach(item => {
      dom.setAttribute(vnode.attr, vnode.attr)
   })
 }
 if(vnode.children){
   vnode.children.forEach(child => {
   dom.appendChild(render(child))
  })
 }
 return dom;
}
复制代码

模板字符串解析

let template = '我是{{name}}，年龄{{age}}，性别{{sex}}';
let data = {
  name: '姓名',
  age: 18
}
function render(temp, data){
  return temp.replace(/\{\{(\w+)\}\}/g, function(match, key, index, source){
    return data[key]
  })
}
render(template, data); // 我是姓名，年龄18，性别undefined
复制代码

二分查找-确定一个数在一个有序数组中的位置

const dataArr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
function search (arr, key, start, end){
  let index = -1
  let mid = Math.floor((start + end) / 2);
  if(arr[mid] === key){
     index = mid;
     return index;
  }
  if(start >= end){
    return index;
  }
  if(arr[mid] < key){
    return search(arr, key, mid + 1, end)
  } else {
    return search(arr, key, start, mid - 1)
  }  
}

search(dataArr, 6, 0, dataArr.length - 1);
复制代码

大数相加

function add(a, b){
  let maxLen = Math.max(a.length, b.length)
  a = a.padStart(maxLen, 0);
  b = b.padStart(maxLen, 0);
  let sum = '';
  let flag = 0;
  for(let i = maxLen - 1; i >= 0; i--){
    let t = parseInt(a[i]) + parseInt(b[i]) + flag
    sum = t % 10 + sum;
    flag = Math.floor(t / 10)
  }
  if(flag != 0){
    sum = flag + '' + sum;
  }
  return sum;
}
add('7199254740991', '1234567899999999999')  // "1234575099254740991"
复制代码

前序遍历判断回文链表

/**
* 请判断一个链表是否为回文链表。
* 输入: 1->2; 输出: false
* 输入: 1->2->2->1;  输出: true
**/
/** 
* 方法一 
* 利用链表的后续遍历，使用函数调用栈作为后序遍历栈，来判断是否回文
**/
 var isPalindrome = function(head) { 
   let left = head; 
   function traverse(right) { 
     if (right == null) return true; 
     let res = traverse(right.next); 
     res = res && (right.val === left.val); 
     left = left.next; 
     return res; 
   } 
   return traverse(head); 
 };
 
/** 
* 方法二
* 通过快、慢指针找链表中点，然后反转链表，比较两个链表两侧是否相等，来判断是否是回文链表
**/
var isPalindrome = function(head) {
    // 反转 slower 链表
    let right = reverse(findCenter(head));
    let left = head;
    // 开始比较
    while (right != null) {
        if (left.val !== right.val) {
            return false;
        }
        left = left.next;
        right = right.next;
    }
    return true;
}
function findCenter(head) {
    let slower = head, faster = head;
    while (faster && faster.next != null) {
        slower = slower.next;
        faster = faster.next.next;
    }
    // 如果 faster 不等于 null，说明是奇数个，slower 再移动一格
    if (faster != null) {
        slower = slower.next;
    }
    return slower;
}
function reverse(head) {
    let prev = null, cur = head, nxt = head;
    while (cur != null) {
        nxt = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
}
复制代码

反转链表

/**
* 输入: head = [1,2,3,4,5]; 输出： [5,4,3,2,1]
* 输入: head = []; 输出： []
**/
var reverseList = function(head) {
    if (head == null || head.next == null) return head;
    let last = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return last;
};
复制代码

合并K个升序链表

var mergeKLists = function(lists) {
    if (lists.length === 0) return null;
    return mergeArr(lists);
};
function mergeArr(lists) {
    if (lists.length <= 1) return lists[0];
    let index = Math.floor(lists.length / 2);
    const left = mergeArr(lists.slice(0, index))
    const right = mergeArr(lists.slice(index));
    return merge(left, right);
}
function merge(l1, l2) {
    if (l1 == null && l2 == null) return null;
    if (l1 != null && l2 == null) return l1;
    if (l1 == null && l2 != null) return l2;
    let newHead = null, head = null;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            if (!head) {
                newHead = l1;
                head = l1;
            } else {
                newHead.next = l1;
                newHead = newHead.next;
            }
            l1 = l1.next;
        } else {
            if (!head) {
                newHead = l2;
                head = l2;
            } else {
                newHead.next = l2;
                newHead = newHead.next;
            }
            l2 = l2.next;
        }
    }
    newHead.next = l1 ? l1 : l2;
    return head;
}
复制代码