likes
comments
collection
share

TOP20大厂经典算法题总结(1)

作者站长头像
站长
· 阅读数 4

如果您也和我一样准备春招，只为TOP20大厂，欢迎加我微信sAnL1ng,一起交流面经，一起屡败屡战。

序

这一段时间里身边的朋友也在陆陆续续接到大厂的面试，我虚心请教了一下他们总结的经验：TOP20的面试难度主要在于全面的基础能力：算法、VUE、基础、JS/css八股、情商，而关于算法不少我的同学在面大厂时也吐槽到简单的不用看，太难的也不用看。原因就是简单的可以直接秒，太难的坐等被秒。那么我就在想这样考的目的在于什么呢？关于算法，我也准备了三种经典题型：树的搜索方式、列表组装成树状态结构、formatNumber。耐心看完，我终于知道了大厂这样考的真实目的！

树的搜索方式

当聊到关于树的搜索方式，我首先想到的就是BFS(Breadth First Search)和DFS(Deep First Search)这两种树的搜索方式：广度优先搜索和深度优先搜索，接着就是这两者的区别，于是我脑海里又有了这张图。

TOP20大厂经典算法题总结(1)

当我们有一个完全二叉树的结构，依次按照这两种不同遍历方式打印的结果不同：

  • BFS: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
  • DFS: 0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6

首先，一般这类解决问题的方式会出现在类似于迷宫问题之中，而面试官一上来就检验一下我们对数据结构的认识程度，先让我们手写一下这两种树的搜索方式，于是，我们早已胸有成竹，丝毫不慌地先拿最简单的DFS来开刀，再把目标转移到BFS。

手写DFS

  • DFS是一种纵深探索的策略，它沿着树的深度遍历树的节点，尽可能深地搜索，直到找到解决方案或无法继续深入为止。当遍历到目前所在节点的所在边都已被探寻过，搜索将回溯到发现节点的那条边的起始节点。

  • 实现DFS常常借助栈或递归调用。首先访问根节点，然后尝试尽可能深地探索，直到到达叶子节点或者无法前进为止，这时回溯到上一个分支点，继续探索其他分支 。

function dfs(node) {
    // 递归
    console.log(node.value);

    for (let child of node) {
        dfs(child);
    }
}

手写BFS

  • BFS是一种逐层搜索的策略，从根节点开始，首先访问所有与根节点相邻的节点，然后再按顺序访问下一层的所有节点。这样，离根节点近的节点会先被访问到，远的节点后被访问。

  • 在实际操作中，常使用队列数据结构来辅助实现。初始时，将根节点放入队列，然后每次从队列中取出一个节点并访问它，再将其所有未访问过的邻居节点加入队列 。

function bfs(root) {
    // 队列 FIFO
    console.log(root.value);
    
    // 创建一个队列，并将根节点放入队列中，队列遵循先进先出（FIFO）原则
    const queue = [root];
    
    // 当队列不为空时，持续执行循环
    while (queue.length) {
        // 弹出队列的第一个节点（即最先入队的节点）
        const currentNode = queue.shift(); 
        console.log(currentNode.value);

        // 检查当前节点是否还有子节点
        if (currentNode.children) {
            // 对于当前节点的每一个子节点依旧按顺序推入到队列尾部
            currentNode.children.foeEach(child => {
                queue.push(child);
            })
        }
    }
}

列表转树状结构

毫无疑问，TOP20以内的大厂不会直接地叫我们去手写BFS和DFS，而是绕个弯子出一道场景题考验我们的思维逻辑能力：在前后端交流的时候，后端从数据库拿到一个有很多items的list，并且它们之间有父子节点的关系，前端负责将这个列表结构转为对应的树状结构。

// 后端返回的就是列表项
// 前端要自行转树形结构
        const list = [
            {
                id: 1001,
                parentId: 0,
                name: "AA",
            },
            {
                id: 1002,
                parentId: 1001,
                name: "BB",
            },
            {
                id: 1003,
                parentId: 1001,
                name: "CC",
            },
            {
                id: 1004,
                parentId: 1003,
                name: "DD",
            },
            {
                id: 1005,
                parentId: 1003,
                name: "EE",
            },
            {
                id: 1006,
                parentId: 1002,
                name: "FF",
            },
            {
                id: 1007,
                parentId: 1002,
                name: "GG",
            },
            {
                id: 1008,
                parentId: 1004,
                name: "HH",
            },
            {
                id: 1009,
                parentId: 1005,
                name: "II",
            },
        ];

这时候，小伙伴们心里是否有一些解决方式？没错！我第一个想法想必和大家一样，先来硬的试试暴力解法是否可行，嘻嘻🤭

暴力解法

在将列表转换为树形结构的过程中，通过ForEach遍历整个数据列表来寻找每个元素的父节点。具体实现是每次遍历到一个节点时，都会在整个数据列表中查找其parentId对应的节点，并将其添加到父节点的children数组中。如果未找到父节点，则认为当前节点是一级节点，直接将其添加到结果数组res中。

// 暴力解法
        function listToSimpleTree(data) {
            const res = [];

            data.forEach(item => {
                const parent = data.find(node => node.id === item.parentId);
                if (parent) {
                    parent.children = parent.children || [];
                    parent.children.push(item);
                } else {
                    //一级节点
                    res.push(item)
                }
            })

            return res;
        }
  • 运行结果：

TOP20大厂经典算法题总结(1)

时间复杂度：O(n^2)

HashMap ——空间换时间

尽管暴力解法易于理解，但在数据量较大的情况下效率较低。所以我们接着给面试官介绍到我们另一种思路：通过HashMap优化时间复杂度，用空间换时间。

  • 优化后的做法是首先通过遍历数据创建一个键值对映射（哈希表），其中键是每个节点的id，值是节点本身。这样做的空间复杂度是O(n)，因为需要为每个节点存储一个映射关系。

  • 然后，在第二次遍历时，根据每个节点的parentId，可以直接通过哈希表在O(1)时间内查找到对应的父节点。这样就避免了重复遍历整个列表来查找父节点，极大地降低了时间复杂度 。

// 优化时间复杂度 用空间换时间
        function listToTree(data) {
            // 空间换时间
            const obj = {}
            // 当数据项很庞大的时候 比如中国的地市
            // O(1) 
            data.forEach(item => {
                obj[item.id] = item
            })

            const res = [];

            data.forEach(item => {
                const parent = obj[item.parentId]
                if (parent) {
                    parent.children = parent.children || [];
                    parent.children.push(item);
                } else {
                    res.push(item);
                }
            }
            )

            return res;
        }

时间复杂度：O(n)

递归解决

除了上述两种方式之外，我们还可以有新的解法吗？ 当然，我们来看看目前已知的特殊条件：就是这个数据结构中有明确的父子关系标识（这里的parentId和id），并且我们需要通过不断地对一个节点进行父子节点关系的查找，所以我们可以通过递归实现将子节点的id作为新的key然后调用自身，就可以实现由浅至深的树结构构建过程。

  • 递归的核心在于定义了一个名为loop的内部函数，这个函数接受一个参数key，代表当前待处理的父节点ID。函数通过遍历数据列表，对每个元素检查其parentId属性是否与key相等，若相等则说明该元素是当前父节点的子节点。

  • 对于每个找到的子节点，函数进一步对其调用自身（即loop(item.id)），以便继续向下查找其子节点，形成了逐层深入构建树形结构的过程。当遇到parentId为0的节点时，视为根节点，递归的起点由此开始。

// 递归解决
        function recursiveToTree(data) {
            function loop(key) {
                const arr = []
                data.forEach(item => {
                    if (item.parentId === key) {
                        item.children = loop(item.id)
                        arr.push(item)
                    }
                })
                return arr
            }
            return loop(0)
        }

时间复杂度：O(n)

formatNumber(数字格式转换)

除了关于树之类的算法题，面试官还热衷于问一些发散性的情景类题目：如何实现国外标准货币格式化表达,我们知道在国际通用货币表达方式中，大额数字通常采用每三位一组的方式分隔开来，例如“1,234,567”。

  • 同学，请看题：

  • 假如我们有一个非负数，他可能是正整数也有可能是非负的浮点数，请设计一个函数： 这个函数接受一个number数字，返回的结果为这个数字通过国外标准货币格式化后的number数字。

// 1,234,567 国外标准货币表达方式 
function formatNumber(number) {
    if (typeof number !== 'number') {
        return;
    }
    // 类型转换
    number += '';
    let [interger, decimal] = number.split('.')
    // 内部函数封装 复用 负责加入','
    const doSplit = (num, isInteger = true) => {
        if (num === '') return ''

        if (isInteger) num = num.split('').reverse()
        let str = []
        for (let i = 0; i < num.length; i++) {
            if (i !== 0 && i % 3 === 0) {
                str.push(',')
            }
            str.push(num[i]);
        }
        if(isInteger) return str.reverse().join('')
        return str.join('')
    }
    interger = doSplit(interger);
    decimal = doSplit(decimal,false);
    return interger + (decimal === '' ? '':'.' + decimal); 
}

console.log(formatNumber(12345.6789)); // 12,345.678,9

代码解释

  1. 当调用formatNumber函数并传入一个数字时，函数首先验证参数number的类型是否为数字。如果不是，函数会直接返回。

  2. 接着，将数字转换为字符串并分割出整数和小数部分。number加上空字符串使其变为字符串类型，然后使用split('.')方法分离整数和小数。

doSplit函数作为内部复用模块，用于给数字字符串添加千位分隔符。它接受两个参数：

  • num：要格式化的数字字符串。
  • isInteger：一个布尔值，表示是否处理的是整数部分，默认为true。

  1. 对于整数部分，doSplit首先检查num是否为空，若为空则返回空字符串。接着，如果isInteger为true，则将数字字符串反转以便从右向左添加逗号。然后创建一个空数组str，在遍历数字字符串的过程中，每当索引位置满足每三个字符一组时（即i % 3 === 0且i不为0），就在数组中插入一个逗号。之后，将所有字符依次推入数组。最后，如果是整数部分，则将数组反转并连接成字符串返回；否则，直接连接数组成员成字符串返回。

  2. 函数调用doSplit分别处理整数部分和小数部分，将处理过后的整数字符串赋值给interger，小数字符串赋值给decimal。

  3. 最后，函数将格式化后的整数和小数部分组合在一起，如果小数部分不存在（即decimal为空字符串），则只返回整数部分；否则，将两者以小数点分隔后返回。

总结

到目前为止，我总结了一些身边诸多朋友面百度、字节这类大厂时被问到的一些题目，但是更重要的是理解到了面试官的真实想法：面试官在考我们这些算法题目时，其目的并不在于考验我们的技术有多卓越，而是更注重我们的思路、想法如何，如果我们能从最简单的题目出发，举一反三，展示出我们的发散性思维将会是一个大大的加分项。