乐趣区

关于算法:你不知道的-LeetCode-技巧第一篇

jiezi

明天来给应用 JS 刷题 的敌人分享 三个 LeetCode 上你或者不晓得的刷题技巧。

tip1 – ES6+

首先交叉一个小常识：咱们提交的 JS 是如何被 LeetCode 执行的？

咱们在力扣提交的代码是放到力扣后盾运行的，而 JS 代码在力扣后盾是在 node 中以 –harmony 形式运行的。

大略是这样：

node --harmony  index.js

其中 index.js 就是你提交的代码。

比方：

// 后面 LeetCode 会增加一些代码
function sum(a, b) {// you code}

// 这里是 LeetCode 的测试用例
expect(sum(1, 2)).toBe(3);
expect(sum(1, 8)).toBe(9); // 如果测试用例不通过，则间接抛出谬误给前端

因而 ES6 个性是齐全反对的，大家能够放心使用。

比方咱们能够应用 ES6 的解构语法实现数组两个值的替换。

[a, b] = [b, a];

如下就是应用了 ES6 的数组解构语法，更多 ES6+ 请参考相干文档。

tip2 – lodash

在 LeetCode 中 lodash 默认可间接通过 _ 拜访。

这是因为 LeetCode 间接将 lodash require 进来了。相似：

const _ = require("lodash");

// 后面 LeetCode 会增加一些代码
function sum(a, b) {
  // you code
  // 你的代码能够通过 _ 拜访到 lodash 的所有性能。}

// 这里是 LeetCode 的测试用例
expect(sum(1, 2)).toBe(3);
expect(sum(1, 8)).toBe(9); // 如果测试用例不通过，则间接抛出谬误给前端

lodash 有很多有用的性能可间接应用。西法倡议你 如果让你手写你可能写出，那么就能够释怀的应用 lodash 提供的性能。

比方数组拍平：

_.flatten([1, [2, [3, [4]], 5]]);
// => [1, 2, [3, [4]], 5]

再比方深拷贝：

var objects = [{a: 1}, {b: 2}];

var deep = _.cloneDeep(objects);
console.log(deep[0] === objects[0]);
// => false

更多 API 可参考官网文档。

tip3 – queue & priority-queue

为了补救 JS 内置数据结构的缺失。除了 JS 内置数据结构之外，LeetCode 平台还对 JS 提供了两种额定的数据结构，它们别离是:

  • queue
  • priority-queue

这两个数据结构都应用的是第三方 datastructures-js 实现的版本，代码我看过了，还是很容易看懂的。

queue

LeetCode 提供了 JS 对队列的反对。

// empty queue
const queue = new Queue();

// from an array
const queue = new Queue([1, 2, 3]);

其中 queue 的实现也是应用数组模仿。不过不是间接应用 shift 来删除头部元素，因为间接应用 shift 删除最坏状况工夫复杂度是 $O(n)$。这里它应用了一种标记技巧，即每次删除头部元素并不是真的移除，而是标记其曾经被移除。

这种做法工夫复杂度能够升高到 $O(1)$。只不过如果不停入队和出队，空间复杂度会很高，因为会保留所有的曾经出队的元素。因而它会在每次出队超过一半的时候执行一次 缩容（相似于数组扩容）。这样工夫复杂度会增大到 $O(logn)$，然而空间会省。

具体用法能够参考：https://github.com/datastruct…

另外西法我本人实现了一套 queue，我是应用链表实现的，实践上 复杂度更好，插入和删除工夫复杂度都是 O(1)，也不会有空间的节约，外围代码就20 行。但理论应用的话性能不肯定谁好，为什么呢，大家能够思考一下？

  • 西法本人实现的 deque

priority-queue

除了一般队列，LeetCode 还提供了一种非凡的队列 – 优先队列。

// empty queue with default priority the element value itself.
const numbersQueue = new MinPriorityQueue();

// empty queue, will provide priority in .enqueue
const patientsQueue = new MinPriorityQueue();

// empty queue with priority returned from a prop of the queued object
const biddersQueue = new MaxPriorityQueue({priority: (bid) => bid.value });

priority-queue 的 api 则能够参考 https://github.com/datastruct…

同样，西法也实现了堆，大家能够参考一下。

  • 西法本人实现的 heap

值得一提的是，西法还实现了一些堆的高级性能，详情参考 indexed_priority_queue

总结

LeetCode 对 JS 的反对次要有：

  • ES6+ 语法的反对
  • 内置 lodash 库，可间接通过 _ 来应用其上的性能函数。
  • 内置数据结构反对队列和优先队列。

文中提到的我本人实现的数据结构代码来自 js-algorithm-light，它是轻量级的 JavaScript 数据结构与算法库。为了让应用 JS 刷题的敌人学习和应用一些罕用的数据结构，我开拓了这个仓库，暂定的指标是对标 Python 所有的内置数据结构和算法。

贴一下西法曾经实现的数据结构。

求个一键三连反对一下，点赞多的话西法立马就安顿下一篇。下一次给大家分享几个 你不晓得的 LeetCode 通用小技巧。

退出移动版