常见面试算法

八月 26, 2021

面试

leetcode find me here

尽量每天 leetcode 一道算法题, 简单题我重拳出击, 中等题我边缘 OB

你说困难题怎么办? 我唯唯诺诺直奔解题区 (只做了解就好,不能强求哈哈)

简单算法

排序

插入排序

插入排序

function insertSort(arr) {
  let res = [arr.splice(0, 1)[0]];
  while (arr.length > 0) {
    let cur = arr.splice(0, 1)[0];
    for (let i = 0; i < res.length; i++) {
      if (cur <= res[i]) {
        res.splice(i, 0, cur);
        break;
      } else if (i === res.length - 1) {
        res.push(cur);
        break;
      }
    }
  }
  return res;
}

冒泡排序

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; 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]];
      }
    }
  }
  return arr;
}

快速排序

快速排序

function quickSort(arr) {
  if (arr.length < 2) return arr;
  let midindex = parseInt(arr.length / 2);
  let mid = arr.splice(midindex, 1)[0];
  let left = [];
  let right = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] <= mid) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), mid, ...quickSort(right)];
}

选择排序

选择排序

function selectSort(arr) {
  const res = [];
  while (arr.length > 1) {
    let min = 0;
    for (let i = 1; i < arr.length; i++) {
      if (arr[min] > arr[i]) min = i;
    }
    res.push(arr.splice(min, 1)[0]);
  }
  res.push(arr[0]);
  return res;
}

等等

排序图解：js 排序算法实现
 快速排序

二分法

初始条件：low = 0, height = length-1, mid = parseInt((height - low) / 2) + low

终止：low === height (即 while(low !== height){})

向左查找：height = mid

向右查找: low = mid + 1

链表

反转链表

展开查看

  
   var reverseList = function(head) {
    if (!head) return null;
    let pre = null, cur = head;
    while (cur) {
        // 关键: 保存下一个节点的值
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
  };

链表回文
合并两个升序链表
合并 k 个升序链表
K 个一组翻转链表
环形链表
链表排序
链表相交
链表倒数第 k 项值 (双指针,慢指针等待 k 步)

字符串

数组

二叉树

深度优先遍历 (前序,中序,后序)

// DFS
function walk(head) {
  if (!head) return;
  // 前序 handle head
  walk(head.left);
  // 中序 handle head
  walk(head.right);
  // 后序 handle head
}

广度优先遍历 (层序)

// BFS
const list = [head];
while (list.length) {
  let len = list.length;
  while (len) {
    let cur = list.pop();
    // handle cur
    if (cur.left) list.push(cur.left);
    if (cur.right) list.push(cur.right);
    len--;
  }
}

二叉树最大深度
二叉树的最小深度
将有序数组转换为二叉搜索树
验证二叉搜索树
验证平衡二叉树
二叉树的最近公共祖先
二叉搜索树中的搜索
二叉树的锯齿形层序遍历【二叉树】

Leetcode 初级算法

前端算法练习指南

字节跳动最爱考的 64 道算法题

「2021」LeetCode 面试常考题目

未来再更…