algorithm by javascript

使用 JavaScript 实现的算法

我们在平时的工作和算法 coding 中，经常会用到一些算法，这里将一些常用的算法总结下。

一般算法

最大公约数

获取两个数的最大公约数

import { gcd } from '@xiaowenzi/algorithm.js';

gcd(6, 4); // 2

数组

合并两个有序数

合并两个有序数组成新的有序数组。

import { mergeSortedArray } from '@xiaowenzi/algorithm.js';

mergeSortedArray([1, 3, 5], [2, 4, 6, 8]); // [1, 2, 3, 4, 5, 6, 8]

删除数组中的连续重复项

删除数组中的连续重复项，若合并后依然有连续的重复项，继续删除。

• 第 1 个参数：要删除连续重复数据的数组；
• 第 2 个参数：连续重复几个就可以删除，默认为 2；

import { removeDuplicates } from '@xiaowenzi/algorithm.js';

removeDuplicates([1, 1, 2, 2, 2, 2, 1, 1, 3], 3); // [3]

字符串

数字

质数相关

判断是否为质数

import { isPrime } from '@xiaowenzi/algorithm.js';

isPrime(10); // false
isPrime(11); // true

统计不大于某数的质数的个数

import { countPrimeEqualOrLessNum } from '@xiaowenzi/algorithm.js';

countPrimeEqualOrLessNum(20); // 8
countPrimeEqualOrLessNum(100); // 25

获取不大于某数的所有质数

import { getAllPrimesEqualOrLessNum } from '@xiaowenzi/algorithm.js';

getAllPrimesEqualOrLessNum(1); // []
getAllPrimesEqualOrLessNum(10); // [2, 3, 5, 7]
getAllPrimesEqualOrLessNum(20); // [2, 3, 5,7, 11, 13, 17, 19]

链表

判断链表是否有环

这里采用了经典的快慢指针，若快指针能追的上慢指针，则说明有环，返回 true；否则返回 false。

import { hasCycleLinkedList } from '@xiaowenzi/algorithm.js';

const head = new ListNode(0);
const node1 = new ListNode(1);
const node2 = new ListNode(2);

head.next = node1;
node1.next = node2;
node2.next = head;

hasCycleLinkedList(head); // true

翻转链表

翻转单向链表，并返回新的链表头指针。

import { reverseLinkedList } from '@xiaowenzi/algorithm.js';

const head = new ListNode(0);
const node1 = new ListNode(1);
const node2 = new ListNode(2);

head.next = node1;
node1.next = node2;

const reverseHead = reverseLinkedList(head);

树

二叉树

二叉树相关的算法很多。

LeetCode 中奖数组转为二叉树

LeetCode 中的一些关于二叉树的样例数据，都是用数组来表示的，本地调试时非常不方便，这里写了一个方法，将数组转为二叉树的结构。

import { array2binary } from '@xiaowenzi/algorithm.js';

const root = array2binary([3, 9, 20, null, null, 15, 7]);

二叉树的多种遍历方式

二叉树中常用的遍历方式主要有：前序遍历、中序遍历、后续遍历、层序遍历等。

import { getTreeByPreOrder, getTreeByMidOrder, getTreeByPostOrder, getTreeByLevelOrder } from '@xiaowenzi/algorithm.js';

getTreeByPreOrder(root); // 前序遍历
getTreeByMidOrder(root); // 中序遍历
getTreeByPostOrder(root); // 后序遍历
getTreeByLevelOrder(root); // 层序遍历，返回的是一个二维数组，每层的数据在一个数组中

翻转二叉树

这个题目出名的原因，是因为 homebrew 的作者 Max Howell 面试谷歌时因为没在白板上写出反转二叉树的算法，结果面试面试挂掉了。

leetcode-invert-binary-tree

import { reverseTree } from '@xiaowenzi/algorithm.js';

reverseTree(root); // root

判断二叉树是否左右对称

import { isSymmetricTree } from '@xiaowenzi/algorithm.js';

isSymmetricTree(root); // boolean

是否子树

前缀树的插入和搜索

• search(word, isWord): 在前缀树中查找单词，若 isWord 为 true，则必须是完整的单词，默认为 false；
• insert(word): 在前缀树中插入单词；

import { TrieTree } from '@xiaowenzi/algorithm.js';

const trie = new TrieTree(['cat', 'bat', 'rat', 'cabt']);
trie.search('ca'); // true
trie.search('ca', true); // false, 前缀树中没有完整的ca单词
trie.insert('aabb');
trie.search('aabb', true); // true

栈

队列

先进先出的数据结构，内部我们是用链表来实现的。

import { Queue } from '@xiaowenzi/algorithm.js';

const queue = new Queue();
const limitQueue = new Queue(5);

初始化时，可以传入一个数字，表示队列空间的大小（比如传入一个数字 5），当超过限制时（当压入第 6 个数据时），则会无法添加。默认不传参数，没有限制。

• push(): 添加元素；
• pop(): 头部删除元素并返回；
• front(): 返回头部元素，若没有元素则返回 null；
• end(): 返回尾部元素，若没有元素则返回 null；
• empty(): 判断队列是否为空；
• size(): 获取队列的长度；