算法基础

[MJingv]

基础算法粉粉的学习网站

算法面试

排序算法（八种）

DFS

BFS

二分查找

回溯

分治

递归

最大公约数

1.辗转相除法

2.更相减损法【差给被减数tile 减数==被减数】

动态规划

最短编辑距离 硬币面值组合问题

拓扑排序

贪心

[MJingv]

无重复字符的最长子串

var lengthOfLongestSubstring = function(s) { 
    let map = new Map() 
    let start = -1, 
        maxLen = 0 
    arr = s.split("") 
    arr.forEach( (element, index, arr) => { 
        if (map.has(element)) { 
            start = Math.max(map.get(element), start)             
            } 
        map.set(element,index)        
        maxLen = Math.max(index-start, maxLen)        
    }) 
    return maxLen 
};

[MJingv]

找出缺失整数

[MJingv]

最长回文子串

let str = '123443';
let res = str.split('').join('#').split('');
console.log(res);
let fin = [];
for (let i = 0; i < res.length; i++) {
    for (let j = 1; i - j > 0 && i + j < res.length; j++) {
        if (res[i - j] !== res[i + j]) {
            break;
        } else {
            fin.push(res[i - j]);
        }
    }
}
fin = fin.filter(x => x != '#');

console.log('最长回文子串是',fin.join(''),'最长回文子串长度是', fin.length);

[MJingv]

去重

const unique = (arr) => {
  let res = [];
  let hashObj = {};
  for (let i = 0, l = arr.length; i < l; i++) {
    if (!hashObj[[arr[i]]]) {
      hashObj[[arr[i]]] = true;
      res.push(arr[i]);
    }
  }
  return res;
};

[MJingv]

选择排序

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

    }

  }
  return arr
}
const swap = (arr,a, b) => {
  let tmp = arr[a]
  arr[a] = arr[b]
  arr[b] = tmp
}

let res = selectSort([3, 4, 5, 2, 3, 4, 22, 1, 0])
console.log(res)

[MJingv]

插入排序

const insertSort = (arr) => {
  let n = arr.length
  for (let i = 1; i < n; i++) {
    for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
      swap(arr, j - 1, j)
    }
  }
  return arr
}
const swap = (arr, a, b) => {
  let tmp = arr[a]
  arr[a] = arr[b]
  arr[b] = tmp
}

let res = insertSort([3, 4, 5, 2, 3, 4, 22, 1, 0])
console.log(res)

改进插入排序

const insertSort = (arr) => {
  let n = arr.length
  for (let i = 1; i < n; i++) {
    let e = arr[i]
    let j = i
    for (j = i; j > 0 && e < arr[j - 1]; j--) {
      arr[j] = arr[j - 1]
    }
    arr[j] = e
  }
  return arr
}

let res = insertSort([3, 4, 5, 2, 3, 4, 22, 1, 0])
console.log(res)

[MJingv]

冒泡排序

const bSort = (arr) => {
  let n = arr.length
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n ; j++) {
      if (arr[j] < arr[i]) {
        swap(arr, i, j)
      }
    }
  }
  return arr
}

const swap = (arr, a, b) => {
  let tmp = arr[a]
  arr[a] = arr[b]
  arr[b] = tmp
}

let res = bSort([3, 4, 5, 2, 3, 4, 22, 1, 0])
console.log(res)

[MJingv]

快排

var quicksort = function (nums, l = 0, r = nums.length - 1) {
  if (l <= r) {
    const pivot = helper(nums, l, r)
    quicksort(nums, l, pivot - 1)
    quicksort(nums, pivot + 1, r)
  }
  return nums
}
const helper = (arr, l, r) => {
  let cur = arr[l]
  while (l < r) {
    while (l < r && arr[r] >= cur) r--
    swap(arr, l, r)
    while (l < r && arr[l] < cur) l++
    swap(arr, l, r)
  }
  return l
}
const swap = (arr, a, b) => {
  [arr[a], arr[b]] = [arr[b], arr[a]]
}

let res = quicksort([1, 4, 4, 7, 8, 3, 4])

console.log(res)

[MJingv]

归并

const mergeSort = (arr) => {
    const len = arr.length
    if (len < 2) return arr
    const mid = Math.floor(len / 2)
    const left = arr.slice(0, mid)
    const right = arr.slice(mid)
    return merge(mergeSort(left), mergeSort(right))
}
const merge = (left, right) => {
    let res = []
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            res.push(left.shift())
        } else {
            res.push(right.shift())
        }
    }
    if (left.length) {
        res = [...res, ...left]
    }
    if (right.length) {
        res = [...res, ...right]
    }

    return res
}

let res = mergeSort([1, 4, 4, 7, 8, 3, 4])

console.log(res)