JS笔试常用方法

Posted by Mars at

记录笔试常用方法技巧

1. 各方法应用场景

1.1 二分查找

必要条件是:

  • ①顺序存储:数组结构;
  • ②通过任意一个下标获取子元素,可以缩小结果范围。

一般适用于:按序排列,且无重复元素的数据搜索。

1.2 滑动窗口

适用于:寻找空间连续的特定组合。

基本思路:

  1. 通过左右边界维护一个窗口:left,right;
  2. 右边界负责向右扩展窗口,每次探索到一个符合条件的窗口值就停止扩展;
  3. 收缩左边界,优化当前窗口值,直到不符合要求;
  4. 继续向右扩展右边界,重复1-3步骤,直到右边界到达末尾。

1.3 构造哈希表

适用于:快速判断一个值是否出现在集合中

缺点是空间复杂度高,是以空间换时间的方法。

三种哈希结构:数组、Set、Map

1.4 构建堆(优先级队列)

适用于:获取一个集合中,某一属性的前N名元素集合。

例如: 获取一个数组中出现次数最高的前N个元素。

为集合元素构建堆(大顶堆、小顶堆),可以通过堆排序,方便获取某一属性优先的前N个元素。

1. 数组操作

1.1 数组中随机取一个元素

let randPos = Math.floor( Math.random() * arr.length )
let res = arr[randPos]

1.2 数组中删除一个元素

arr.splice(position, 1)

1.3 数组中动态删除元素,考虑从右到左遍历

从右到左遍历,指针左侧的元素不会被动态修改,指针右侧的元素删除不影响指针的下一位置。

1.4 浅拷贝数组

Array.from(arr)

1.5 数组sort排序

// 字符串升序
arr.sort()
// 字符串降序
arr.sort().reverse()
// 数字升序
arr.sort( (a,b) => a-b )
// 数字降序
arr.sort( (a,b) => b-a )

2. 判断变量类型

// 精确返回变量类型,首字母大写
Object.prototype.toString.call(arg).slice(8,-1)

3. 链表操作

3.1 链表的前序、后序遍历

function iterate(nodeHead){
    while (nodeHead.next){
        // 这里写处理逻辑就是前序遍历:正序
        iterate(nodeHead.next)
        // 这里写处理逻辑就是后序遍历:倒序
    }
}

4. 数值操作

4.1 辗转相除找最大公约数

    function findGCD(num1,num2){
        let remainder,divider
        if (num1 >= num2){
            remainder = num1 % num2
            divider = num2
        } else {
            remainder = num2 % num1
            divider = num1
        }
        while (remainder !== 0){
            let temp = remainder
            remainder = divider % remainder
            divider = temp
        }
        return divider
    }

4.2 找两数最小公倍数

let LCM = num1 * num2 / findGCD(num1,num2)

4.3 ABC集合的合集元素数目

|A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

Keywords: JavaScript
previousPost nextPost
已经有 1000000 个小伙伴看完了这篇推文。