分享一些用JavaScript刷题的Tips

zachzwy

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

论坛里关于用 JavaScript 刷题的帖子比较少，我想和大家分享一下我总结的一些常用语句以及模板。JavaScript 或者说 NodeJs，被越来越多的运用在后端中。如果你平常使用最多的语言是 JavaScript，那直接用它来刷题找工作没有问题。JavaScript 做起题来的代码量是相对比较少的，一方面是由于本身是一个 dynamically typed 的语言，另一方面是它支持很多简洁的语法。

先贴一下LeetCode Rating。总共参加了103场，都是用JS写的。

Tips:
(建议把以下代码复制到VSCode或者其它editor里面，并保存成.md文件使用。或者是直接下载附件。)

#### 1 Array
##### 1.1 Array creation
- Create a new array
`const A = [];`
- Create a subarray
`const A = B.slice(l, r); // From idx l to r, r is not included`
- Copy from other array
`const A = [...B];`
- Create an array from a set
`const A = [...mySet];`
- Create an array from a string
`const A = [...myStr];`
- Create an array from hashmap keys
`const A = Object.keys(myMap);`
- Create an array from hashmap values
`const A = Object.values(myMap);`
- Create an array from hashmap keys and values
`const A = Object.entries(myMap);`
- Create an array with length `m`
`const dp = Array(m);`
- Create an array with length `m`, initialized as `0`
`const dp = Array(m).fill(0);`
- Create a 2-D array with dimension `r x c`, initialized as `-1`
`const dp = Array.from(Array(r), () => Array(c).fill(-1));`
##### 1.2 Array modification
- Add an element
`A.push(x);`
- Add all elements from other array
`A.push(...B);`
- Add an element from left
`A.unshift(x);`
- Pop an element
`A.pop();`
- Pop an element from left
`A.shift();`
- Remove/add element(s)
`A.splice(idx, deleteCnt, x); // in place`
- Reverse an array
`A.reverse(); // in place`
- Sort an array in increasing order
`A.sort((a, b) => a - b); // in place`
- Other usages
`A.map(); A.filter(); A.every(); A.some();`
#### 2 String
- Create a string literal
`const s = "abcd";`
- Create a string from other string
`const s1 = s2.substring(l, r); // From idx l to r, r is not included`
- Create a string by joining an array
`const s = A.join("");`
- Create a string of repeating char
`const s = "xyz".repeat(5);`
- Reverse a string
`const s1 = [...s2].reverse().join("");`
- Loop a string
`for (const char of s) {}`
- Split a string
`const arr = s.split(" ");`
#### 3 Set
- Create a new set
`const seen = new Set();`
- Create a set from an array
`const seen = new Set(A);`
- Add an element
`seen.add(x);`
- Delete an element
`seen.delete(x);`
#### 4 Hashtable (object)
- Create a new hashtable
`const g = {};`
- Add a key value pair
`g[a] = b;`
- Delete a key
`delete g[a];`
- Detect key exists
`if (key in g) {}`
`if (g[key]) {} // Only works if you know there is no falsy value`
`if (g[key] !== undefined) {}`
- Loop through key value pair
`for (const [key, value] of Object.entries(g)) {}`
#### 5 Heap
- Create a min heap
`const minHeap = new Heap((a, b) => a - b);`
- Create a max heap
`const maxHeap = new Heap((a, b) => b - a);`
- Create a custom heap
`const heap = new Heap((a, b) => a[0] - b[0] ? a[0] - b[0] : a[1] - b[1]);`
- Create a heap from an array
`minHeap.heapify(A);`
- Add an element
`minHeap.add(x);`
- Pop an element
`minHeap.pop();`
- Peek an element
`minHeap.peek();`
- Delete an element
`minHeap.delete(x);`
- Heap implementation
```js
class Heap {
constructor(comparator) {
this.arr = [];
this.comparator = comparator;
}
getL() {
return this.arr.length;
}
getPIdx(i) {
return Math.floor((i - 1) / 2);
}
getLIdx(i) {
return 2 * i + 1;
}
getRIdx(i) {
return 2 * i + 2;
}
swap(i, j) {
[this.arr[i], this.arr[j]] = [this.arr[j], this.arr[i]];
}
peek() {
if (!this.arr.length) return null;
return this.arr[0];
}
pop() {
if (!this.arr.length) return null;
if (this.arr.length === 1) return this.arr.pop();
const res = this.arr[0];
// Move last item from end to head
this.arr[0] = this.arr.pop();
this.heapifyDown();
return res;
}
add(n) {
this.arr.push(n);
this.heapifyUp();
}
// Default idx is the first idx
heapifyDown(idx = 0) {
let p = idx;
let c;
// Compare parent with its children and swap with target child if necessary
// Do it in a loop
while (this.getLIdx(p) < this.arr.length) {
// Get target child first
if (
this.getRIdx(p) < this.arr.length &&
this.comparator(this.arr[this.getRIdx(p)], this.arr[this.getLIdx(p)]) <
0
)
c = this.getRIdx(p);
else c = this.getLIdx(p);
// Compare with parent, if not valid, break
if (this.comparator(this.arr[p], this.arr[c]) <= 0) break;
// Swap
this.swap(p, c);
p = c;
}
}
// Default idx is the last idx
heapifyUp(idx = this.arr.length - 1) {
let c = idx;
let p = null;
// While has parent
while (c) {
p = this.getPIdx(c);
if (this.comparator(this.arr[p], this.arr[c]) <= 0) break;
// Swap
this.swap(p, c);
c = p;
}
}
heapify(A) {
// Bottom up
// Heapify down each item
this.arr = A;
for (let i = Math.floor(A.length / 2); i >= 0; i--) {
this.heapifyDown(i);
}
}
delete(n) {
const idx = this.arr.indexOf(n);
this.arr[idx] = this.arr[this.arr.length - 1];
this.arr.pop();
this.heapifyDown(idx);
}
}
```
#### 6 Union find
```js
class DS {
constructor(n) {
this.root = [...Array(n + 1).keys()];
this.rank = Array(n + 1).fill(0);
}
find(i) {
if (i !== this.root[i]) this.root[i] = this.find(this.root[i]);
return this.root[i];
}
union(i, j) {
const [root1, root2] = [this.find(i), this.find(j)];
if (root1 === root2) return false;
if (this.rank[root1] > this.rank[root2]) this.root[root2] = root1;
else if (this.rank[root1] < this.rank[root2]) this.root[root1] = root2;
else {
this.root[root2] = root1;
this.rank[root1]++;
}
return true;
}
}
```
#### 7 Trie
```js
// Construct a trie from W (W is an array of words)
const trie = {};
W.forEach((w) => {
let node = trie;
for (const c of w) {
if (!node[c]) node[c] = {};
node = node[c];
}
node.end = true;
});
```
#### 8 Monotonic queue
e.g. 239-sliding-window-maximum
```js
const maxSlidingWindow = (A, k) => {
const win = []; // Store idx
const res = [];
for (let i = 0; i < A.length; i++) {
// Need to get max from win[0], so keep an descending queue
while (win.length && A[win[win.length - 1]] <= A[i]) win.pop();
win.push(i);
// Remove first element if it's out of window
if (win[0] === i - k) win.shift();
if (i >= k - 1) res.push(A[win[0]]);
}
return res;
};
```
#### 9 Quick sort/select
```js
const partition = (A, l, r) => {
let j = l;
let boundary = A[r];
for (let i = l; i < r; i++) {
if (A[i] < boundary) {
[A[i], A[j]] = [A[j], A[i]];
j++;
}
}
[A[j], A[r]] = [A[r], A[j]];
return j;
};
const quickSort = (A, l, r) => {
if (r <= l) return;
const idx = partition(A, l, r);
quickSort(A, l, idx - 1);
quickSort(A, idx + 1, r);
return A;
};
```
#### 10 Bianry index tree
```js
class BIT {
constructor(n) {
this.pre = Array(n + 1).fill(0);
}
update(i, delta) {
while (i < this.pre.length) {
this.pre[i] += delta;
i += i & -i;
}
}
getSum(i) {
let res = 0;
while (i) {
res += this.pre[i];
i -= i & -i;
}
return res;
}
}
```

复制代码

zachzwy

gagawoahlala 发表于 2022-4-15 19:32
楼主，你在面试的时候如果碰到了PQ的题咋办？要现场实现一个heap吗？

面试的时候碰到使用PQ的题，其实是个很好的和面试官交流的机会。这时候可以把“是否要现场实现一个heap”的问题抛回给面试官。在大部分情况下是不需要的，或者说是次要的。这时候可以先假设有这样一个heap的library存在（就像其它语言一样），直接调用即可。

语言只是实现算法，解决问题的工具。并不会因为某个语言本身不存在某个数据结构，或者是存在某个特殊的算法（比如next permutation），就会因此让你的面试结果被扣分，或者是加分。如果面试官想考的就是heap的实现，那么语言里有这个数据结构，也还是需要自己实现出来。

就我自己的经验而言，有时候面试官会追问heap的实现，这时候如果能够答出大概的实现方法，比如使用array，如何实现heapifyDown，heapifyUp等等，其实反而是一个加分的表现机会。

SoWhat0309

毕竟跑在浏览器里的lisp，要是带个好用点的堆的话估计也能抛弃python了（

gagawoahlala

楼主，你在面试的时候如果碰到了PQ的题咋办？要现场实现一个heap吗？

ny0707

我感觉面试如果考 PQ，一种是完整实现，另一种是基于这个解决问题，可以简单数组加排序实现，默认复杂度是 logn 就好

hys928

gagawoahlala 发表于 2022-04-15 19:32:47
楼主，你在面试的时候如果碰到了PQ的题咋办？要现场实现一个heap吗？

前端不会面PQ😹 类似Google这样面到了也只需要引用一个类似heapify的lib function就好了也不用跑

sybzd

你这个heap是O（n）的complexity，很多题过不去的。
js和python刷题的硬伤是没有native red black tree

zachzwy

sybzd 发表于 2022-4-16 00:51
你这个heap是O（n）的complexity，很多题过不去的。
js和python刷题的硬伤是没有native red black tree

你要是仔细看的话会发现这是nlgn的复杂度。我做的所有PQ的题目都可以通过。
如果你用了我的实现方法而没有通过的话，欢迎分享具体的题目。我们可以进一步探讨。

我个人一直认为每种语言都有自己的优缺点。单就刷题面试找工作而言，语言差异所带来的区分度其实是可以忽略不计的，不存在所谓的硬伤。

sybzd

zachzwy 发表于 2022-4-16 11:20
你要是仔细看的话会发现这是nlgn的复杂度。我做的所有PQ的题目都可以通过。
如果你用了我的实现方法而没 ...

push的里面用了while，而且是根据index走的，肯定不是log n
面试的时候考个heap的题，你光抄heap的code都抄不完，怎么不是硬伤。

[Leetcode] 分享一些用JavaScript刷题的Tips

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

评分

浏览过的版块