跳转到内容
aswind7
GitHub
Blog

算法-常见算法

总览

一般常用常考的类型主要有：

  • 链表
  • 快排
  • 二分查找
  • 动态规划
  • 双指针
  • 滑动窗口
  • 二叉树

如果要应对前端面试，建议刷:

  1. hot 100
  2. leetcode-javascript

查找

二分查找

var search = function (nums, target) {
  let low = 0,
    high = nums.length - 1;

  while (low <= high) {
    const mid = Math.floor((high - low) / 2) + low;
    const num = nums[mid];
    if (num === target) {
      return mid;
    } else if (num > target) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
};

排序

冒泡排序

/**
 * 冒泡排序
 * 简介: 就像泡泡一样，每轮中待排序的最大的数字会冒泡到待排序数组的最右边,作为已排序数组;
 * https://upload.wikimedia.org/wikipedia/commons/3/37/Bubble_sort_animation.gif
 * @param    {Array}  需要排序的数组
 * @return   {Array}
 */
// 时间复杂度 O(n^2):  (1+n-1)*(n-1)/2
const bubbleSort = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    //  是有序的(没交换过，说明已经有序了,这轮结束不需要再比较了)
    let isOrder = true;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let t = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = t;
        isOrder = false;
      }
    }
    console.log(`第${i + 1}轮的数组结果:`, arr);
    if (isOrder) {
      console.log("已经有序，提前结束");
      break;
    }
  }
  return arr;
};

//  bubbleSort([5,4,3,2,1])    => 输出: [1,2,3,4,5]
//  bubbleSort([5,3,1,2,4])    => 输出: [1,2,3,4,5]

选择排序


/**
 * 选择排序
 * 方案: 每轮从待排序数组中的选取出最小的数字，与待排序的最左数字交换位置
 * https://pic3.zhimg.com/v2-495e1e8dbe7966a904985c4186a295de_b.webp
 * @param    {Array}  需要排序的数组
 * @return   {Array}
 */
// 时间复杂度 O(n^2)
const selectSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    // 最小的数的索引
    let minIndex = i - 1;
    for (let j = i; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 交换
    if (i - 1 !== minIndex) {
      let t = arr[i - 1];
      arr[i - 1] = arr[minIndex];
      arr[minIndex] = t;
    }
    console.log(`第${i}轮结果`, arr);
  }
  return arr;
};

//  selectSort([5,4,3,2,1])    => 输出: [1,2,3,4,5]
//  selectSort([5,3,1,2,4])    => 输出: [1,2,3,4,5]

链表

链表-裁剪节点

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */

a = { val: 3, next: null };
b = { val: 3121, next: a };
c = { val: 876, next: b };
d = { val: 312, next: c };

//  d => c => b => a 删除后: d => b => a
var deleteNode = function (node) {
  node.val = node.next.val;
  node.next = node.next.next;
};

链表-打印链表

a = { val: 3, next: null };
b = { val: 3121, next: a };
c = { val: 876, next: b };

// 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
const printListFromTail2Head = (linkedList) => {
  const arr = [linkedList.val];
  let cur = linkedList;

  while (cur.next) {
    cur = cur.next;
    arr.unshift(cur.val);
  }
  return arr;
};

链表-反转链表

a = { val: 3, next: null };
b = { val: 3121, next: a };
c = { val: 876, next: b };
d = { val: 312, next: c };

// 原来 d => c => b => a ; 反转后 a => b => c => d
// c. d  b a
// b. c d a
// a. b c d
// 第一轮之后: currentNode: c  head: d  headNode: c

const reverseLinkedList = (head) => {
  if (!head.next) {
    return head;
  }
  let cur = null;
  let headNode = head;

  // 将基准点的下一项移动到头部的第一项
  while (head && head.next) {
    cur = head.next;
    head.next = cur.next;
    cur.next = headNode;
    headNode = cur;
  }
  return headNode;
};

相关链接

Tags: