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

冷不防 2022-06-17 14:08 205阅读 0赞

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

数组相关[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)
    //----------------------20190204更新-------------------
    // 感觉上述代码不够优雅，后来觉得reduce很强大，于是尝试重写一下
    console.log(
      [1,2,3,4].reduce((sum, p) => { 
        if (sum.length === 0) return [[p]]
        const rs = []
        // n个元素的数组，有n+1个可插入位置
        const len = sum[0].length + 1
        for (let i = 0; i < len; i ++) { 
          sum.forEach((it) => { 
      	    const t = it.slice()
            t.splice(i, 0, p)
            rs.push(t)
          })
        }
        return rs
      }, [])
    )
    // reduce 函数执行过程
    [] + 1 
    [[1]] + 2
    [[2 1] [1 2]] + 3
    [[3 2 1] [2 3 1] [2 1 3] [3 1 2] [1 3 2] [1 2 3]] + 4
    // ...

// 四、寻找两个有序数组最小相同元素
    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映射到二维数组的坐标，只需要几行代码就能解决。
    // 本题考的是二分查找，相对一维数组，多了一个通过偏移量映射坐标的过程。

[API]: https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array
[lodash]: https://lodash.com/docs/4.17.5