算法学习积累

算法口诀

两数之和： 一次遍历，数组存入数据，target相减存在即返回
冒泡算法： 两层遍历，大的往后排
选择排序： 选择最小的值跟头部的交换位置，第二次循环仅选择最小的index，且j=i+1;
插入排序： 从target开始，while 向前遍历j–，找到一个比目标元素小的的元素，插在其后
快速排序： 递归中间值；找到中间节点的值，forEach比该节点值大的放在右边，小的放在左边，进行递归
归并算法： 递归 双指针分而治之。
动态fib: 动态规划解决fib斐波那契数列 dp[i] = dp[i-1] + dp[i-2] （爬楼梯算法）
首字符串下标： map[item] = val ? val+1 : 1

算法

/**
 *
 * 两数之和
 * 给定一个数组 nums 和一个目标值 target，在该数组中找出和为目标值的两个数
 * nums: [8, 2, 6, 5, 4, 1, 3] ； target:7
 * [2, 5]
 * 
 * 关键点： 从map中查找是否存在 target-arr[i] 等于key，有则返回;
 * 
 */

function twoNumSum(arr, target) {
  let map = {}  
  for(let i = 0; i<arr.length; i++ ) {
    if (map[target-arr[i]]) {
      return [target-arr[i], arr[i]]
    } else {
      map[arr[i]] = i
    }
  }
}


const twoNumSum = (arr, target) => {
  let res = []
  for(let i=0; i<arr.length; i++) {
    if (res.includes(target-arr[i])) {
      return [target-arr[i], arr[i]]
    } else {
      res.push(arr[i])
    }
  }
}

/***
 * 
 * 冒泡排序
 * 关键点： 两层排序，大的往后排
 */

const bubbleSore = (arr)  => {
  let len = arr.length;
  for(let i = 0; i<len; i ++) {
    for(let j = 0; j<len-i-1; j++) {
      if (arr[j]>arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
      }
    }
  }
}

/***
 * 
 * 选择排序
 * 选择最小的值跟头部的交换位置，  第二次遍历仅选择最小的index
 */

const selectSort = (arr) => {
  let min = 0
  for (let i = 0; i< arr.length; i++) {
    min = i
    for(let j = i+1; j< arr.length; j++) {
      if (arr[j] < arr[min]) {
        min = j
      }
    }
    [arr[i], arr[min]] = [arr[min], arr[i]]
  }
}

/***
 * 
 * 插入排序
 * 关键： 从target开始，while 向前遍历，找到一个比目标元素小的的元素，插在其后
 */

const insertSort = ( arr) => {
  for(let i=0; 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
  }
}

/**
 * 
 * 快排 
 * 关键： 找到中间节点的值，比该节点值大的放在右边，小的放在左边，进行递归
 * 注意啊arr.length <= 1 推出返回arr
 */



const quickSort = ( arr ) => {
  if (arr.length <=  1) {
    return arr 
  }
  let index =  Math.floor(arr.length / 2 )
  let base = arr.splice(index, 1)[0]
  let left = []
  let right = []
  arr.forEach(item => {
    if (item < base) {
      left.push(item)
    } else {
      right.push(item)
    }
  })
  quickSort(left).concat(base, quickSort(right))
}

/**
 * 
 * 链式调用
 * 例如： 猴子吃完香蕉去跑步，然后睡觉
 * 
 */

let Monkey = function() {}

Monkey.prototype.eat = function( food ) {
  this.food = food;
  log(`Monkey eat ${this.food}`)
  return this 
}

Monkey.prototype.run = function( m ) {
  this.m = m;
  log(` and run ${this.m} 米`)
  return this 
}

Monkey.prototype.sleep = function( time ) {
  this.time = time;
  log(`and sleep ${this.time} 小时`)
  return this 
}

/**
 * 
 * 动态规划解决fib斐波那契数列
 * 关键： 从第三项开始，每项的值都是前两项之和 即 dp[i] = dp[i-1] + dp[i-2]
 */

const fib = (n) => {
  if (n < 2 ) {
    return 1
  }
  let dp = [1n,1n]
  for(let i=2, i<=n; i++) {
    dp[i] = dp[i-1] + dp[i-2]
  }
  return dp[n]
}

/***
 * 
 * 输出第一个不重复字符串的下标
 * 'abcabcde'
 * 输出： 6
 */


const findOneStr = (str) => {
  if (!str) return -1
  let arr = str.split('')
  let map = {}
  arr.forEach(item => {
    let val = map[item]
    map[item] = val ? val+1 : 1
  }) 
  for(let i=0; i< arr.length; i++) {
    if (map[arr[i]] === 1 ) {
      return i
    }
  }
}

/**
 * 
 * 
 * 归并排序
 * 双指针分而治之
 */

const merge = (left, right) => {
  let i=0, j=0;
  let res = []
  while(i<left.length && j < right.length) {
    if (left[i] < right[j]) {
      res.push(left[i])
      i++
    } else {
      res.push(right[j])
      j++
    }
  }

  while(i<left.length) {
    res.push(left[i])
    i++
  }

   while(j<right.length) {
    res.push(right[j])
    j++
  }

}


const mergeSort = (arr) => {
  if (arr.length <=1) {
    return arr
  }
  let midIndex = Math.floor(arr.length / 2 )
  let left = mergeSort(arr.slice(0, midIndex))
  let right = mergeSort(arr.slice( midIndex, arr.length))
  return merge(left, right)
}

/**
 * 
 * 大数相加
 * js大数相加会丢失精度，如何不丢失精度
 * 
 * let a = "9007199254740991";
 * let b = "1234567899999999999";
 * 输出： 1243575099254740990
 * 
 * 关键： 0补齐两数（字符串）长度，每位相加，设置进位，！！！！
 * 只需要关注每位数相加的结果，进位会在下一次循环中加给当前t,sum = t%10 + sum 即可
 */

let a = "9007199254740991";
let b = "1234567899999999999";
const addBigInt = (a,b) => {
  let maxLength = Math.max(a.length, b.length)
  a = a.padStart(maxLength, 0)
  b = b.padStart(maxLength, 0)
  let t = 0
  let f = 0
  let sum = ""
  for(let i = maxLength-1; i>=0; i--) {
    t = parseInt(a[i]) +  parseInt(b[i]) + f
    f = Math.floor(t/10)
    sum = t%10 + sum
  }
  if (f == 1) {
    sum = '1' + sum
  }
  return sum
}

// 展开树形结构
/**
 * 
 * let data = [
    { id: 1, title: "child1", parentId: 0 },
    { id: 2, title: "child2", parentId: 0 },
    { id: 3, title: "child1_1", parentId: 1 },
    { id: 4, title: "child1_2", parentId: 1 },
    { id: 5, title: "child2_1", parentId: 2 },
    { id: 6, title: "child2_1", parentId: 3 }
  ]
 *
 *
 * 将数组展开成树形结构，parentId 是其父节点
 */


const treeData = (data) => {
  let map = {}
  let resArr = []
  data.map(item => {
    map[id] = item
  })
  Object.keys(map).map(id => {
    // 处理非根节点
    if (map[id].parentId) {
      if (!map[map[id].parentId].children) {
        map[map[id].parentId].children = []
      }
      map[map[id].parentId].children.push(map[id])
    } else {
      resArr.push(map[id])
    }
  })
  return resArr
}

/***
 * 
 * 
 * let treeData = [
  {
    "id":1,
    "title":"child1",
    "parentId":0,
    "children":[
      {
        "id":3,
        "title":"child1_1",
        "parentId":1,
        "children":[
          {"id":6,"title":"child2_1","parentId":3}
        ]
      },
      {
        "id":4,
        "title":"child1_2",
        "parentId":1
      }
    ]
  },
  {
    "id":2,
    "title":"child2",
    "parentId":0,
    "children":[
      {"id":5,"title":"child2_1","parentId":2}
    ]
  }
]
 */
/**
 * 
 * 将树形结构转化为数组形式，根据parentId 和 ID的对应关系
 */

const deepTreeFlap = (tree, arr = []) => {
  if (!tree || !tree.length) return arr
  tree.forEach(data => {
    arr.push(data)
    if (data.children) {
      deepTreeFlap(data.children, arr)
      delete data.children
    }
  })
  return arr
}