欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

javascript/前端 有关数组的面试题

程序员文章站 2022-04-11 11:56:54
...

前言:近期面试被问到多个有关数组的面试题,平时面试别人也喜欢考数组相关的题目。在这里举几个例子记录一下。

数组相关API常用的不多(ES5/6/7新增部分,使用时需要注意兼容性),也简单易懂,但组合使用起来会很灵活,出题方式多,向面试者描述也很容易被理解。
如果能熟练应用,平时写代码的效率也能提高不少,经验相对丰富的前端开发不可避免地会经常与数据打交道。总结起来就是很适合做面试题。。。

开始之前先推荐超实用的工具库lodash,提供了很多实用的工具函数。

以下代码使用ES6语法,新版Chrome浏览器可以直接运行,不需要babel编译。

// 一、将字符串反向 'abc123' => '321cba'

// 很多不熟悉数组api的小伙伴会回答 for循环。。。循环当然是可以的,两年前我也这么回答。。
// 加分回答
'abc123'.split('').reverse().join('')
// 二、打平嵌套数组 [1, [2, [3], 4], 5] => [1, 2, 3, 4, 5]
// 我现场写的代码:
const arr = [1,[2,[3],4],5]
function flatten(arr) {
    for (let i in arr) {
        if (Array.isArray(arr[i])) {
            arr.splice(i, 1, ...flatten(arr[i]))
        }
    }
    return arr
}
flatten(arr)

// 偶然发现 arr.toString() 或 arr.join() => '1,2,3,4,5'
// 于是可以写的简便些
const arr = [1,[2,[3],4],5]
arr.join()
    .split(',')
    .map(it => Number(it))

// 网上搜了下,还可以这么写。。。
const arr = [1, [2, [3], 4], 5]
JSON.parse(`[${arr}]`)

// 这个题面试官想考查的应该是递归和深度优先遍历,上面第二、三种回答只适合应付元素为数字的场景,第一种回答讨巧避开了深度优先遍历过程,直接在原数组上修改,并不推荐。
// 如果要有较好适应性,还是写递归吧。同时可以参考下 [underscore flatten](http://www.css88.com/doc/underscore/docs/underscore.html) 的实现。
// 三、打印数组全排列
// [1,2,3] => [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 没有明确的遍历界限时都使用递归吧,实际应用场景,若非尾递归形式需要考虑是否可能栈溢出。
// 采用递归需要重点考虑参数及返回值的设定,本例使用有副作用的方式实现,这样实现逻辑上比较好理解,只有当满足条件时添加一条排列,递归中的返回值用起来总感觉头晕。。
function allRange (arr, path, res) {
    if (!arr.length) {
        res.push(path)
        return
    }
    arr.forEach((v, idx) => {
        const t = arr.slice()
        const p = path.slice()
        t.splice(idx, 1)
        p.push(v)
        allRange(t, p, res)
    })
}
var a = [1, 2, 3, 4]
const b = []
allRange(a, [], b)
console.log(b)
// 四、寻找两个有序数组最小相同元素
const a = [1, 2, 5, 9, 10]
const b = [3, 4, 6, 9, 10]

function findElement (a, b) {
    let i = j = 0
    while (i < a.length || j < b.length) {
        if (a[i] === b[j]) {
            return a[i]
        } else if (a[i] > b[j]) {
            j ++
        } else if (a[i] < b[j]) {
            i ++
        }
    }
    return null
}

console.log(findElement(a, b))
// => 9
// 看到这个题目第一想法是 遍历第一个数组,二分法查找第二个。经面试官提醒,采用游标,更加简单易懂。
// 五、有序二维数组寻找某元素坐标
const data = [[1, 2, 5, 9, 10],
              [12, 22, 35, 49, 51],
              [61, 62, 75, 79, 81]]

const len = data[0].length
function findOffset (e, a, b) {
    if (a > b) return null 

    const offset = (b - a) / 2 + a

    // 映射位置偏移到坐标
    const x = offset % len
    const y = ~~(offset / len)

    if (data[y][x] === e) {
        return [x, y]
    } else if (e > data[y][x]) {
        return findOffset(e, offset + 1, b)
    } else {
        return findOffset(e, a, offset - 1)
    }
}
findOffset(75, 0, len * data.length - 1)
// => [2, 2]

// 看到这个题目第一想法是打平数组使用indexOf得到下标,再根据data[0].length映射到二维数组的坐标,只需要几行代码就能解决。
// 本题考的是二分查找,相对一维数组,多了一个通过偏移量映射坐标的过程。