2019前端面试题 —— 算法相关

[fengmiaosen]

1. 全排列算法

   https://segmentfault.com/a/1190000013434175

2. 多层嵌套数组去重排序

    var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];

    function isArray(item) {
        return Object.prototype.toString.call(item) === '[object Array]';
    }

    // // 方法一
    // function flat(arr){
    //     var newArr = arr.toString().split(",");
    //     var tempArr = [];

    //     newArr.map(item => {
    //         if(tempArr.indexOf(item) < 0){
    //             tempArr.push(item);
    //         }
    //     })

    //     return tempArr.map(t => +t).sort((a,b)=>{ return a-b});
    // }

    // 方法二 es6版本
    function flat (arr) {

         function toFlat (acc, current) {
           if (Array.isArray(current)) {
             current.forEach(item => {
               toFlat(acc, item)
             })
           } else {
             if (!acc.includes(current)) {
               acc.push(current)
             }
           }
           return acc
         }

         return arr.reduce(toFlat, []).sort((value1, value2) => value1 - value2)
    }

    // 方法三 es5版本
    function flat (arr) {
        function toFlat (acc, current) {
            if (isArray(current)) {
                for(var i=0;i<current.length;i++){
                    toFlat(acc, current[i])
                }
            } else {
                if (acc.indexOf(current) < 0) {
                    acc.push(current)
                }
            }
            return acc
        }

        var newArr = [];

        for(var j = 0; j < arr.length; j++){
            if(isArray(arr[j])){
                newArr = newArr.concat(toFlat([], arr[j]))
            } else {
                newArr.push(arr[j])
            }
        }

        return newArr.sort((value1, value2) => value1 - value2)
    }
    
    var newArr =  flat(arr);

    console.log(newArr)

https://github.com/Advanced-Frontend/Daily-Interview-Question/issues/8

3. 两个升序数组，合并为一个新的升序数组，注意不能使用concat和sort方法

   https://blog.csdn.net/u012194956/article/details/79388856
   http://xuhong.github.io/2014/04/01/concatsort/

4. 归并排序

   https://segmentfault.com/a/1190000008866524

5. 设计一个桌球游戏，写出包括球、球杆、球桌和游戏主程序类

   TODO

6. 图的深度优先遍历与广度优先遍历

   深度优先遍历与广度优先遍历 sisterAn/blog#25

7. JS数组常用算法详解

   JS数组常用算法详解 yygmind/blog#4

8. 单链表

   JavaScript中的数据结构 lvwxx/blog#1 (comment)

9. 递归、二叉树

   https://juejin.im/post/5b72f0caf265da282809f3b5#heading-0

10. 什么是红黑树
    https://juejin.im/post/5a27c6946fb9a04509096248

11. 控制并发数

    https://juejin.im/post/5dad327951882508652e525e#heading-7
    参照 https://github.com/timdp/es6-promise-pool

参考资料

• 前端笔试&面试爬坑系列---算法
• 面试专题总结：手撕代码
• 面试高频JS考查点手写实现