前端面试中的算法题

前言

本人最近去了一次面试，被问到两题面试题，是考察算法的，觉得挺基础的，也比较有趣，分享一下

第一题

第一题的要求是，根据顺序输出二叉树的每个节点的值。这一题在算法中比较的基础，其实也没有什么难度。面试官的要求是需要使用时间复杂度为O(n)的方式进行输出。可能当时有点紧张吧，没有仔细思考之后就开始动手写代码了。那接下来，我就先讲一下正确的解题思路吧

解题思路

其实这里考察了一下队列的知识。下面我们来看一下队列的基本描述图：

队列图

根据队列的思想，首先访问第一个节点，然后输出该节点的值，然后判断它是否具备子节点。如果具备将子节点放入队列，然后依次遍历队列，知道遍历到队列的最后一个。

代码

var node7 = {
    num: 7,
    children: []
};             //节点7
var node6 = {
    num: 6,
    children: []
};
var node5 = {
    num: 5,
    children: []
};
var node4 = {
    num: 4,
    children: []
};
var node3 = {
    num: 3,
    children: [node6, node7]
};
var node2 = {
    num: 2,
    children: [node4, node5]
};
var node1 = {
    num: 1,
    children: [node2, node3]
};

var queue = [];      //队列
queue.push(node1);           //现将第一个节点push进去
for(var i=0; i<queue.length ; i++){
    var node = queue[i];
    console.log(node.num);
    if(node.children.length !== 0){             //判断是否含有子节点
        for(var j=0; j<node.children.length ; j++){
            queue.push(node.children[j]);
        }
    }
}

第二题部分

第二题

第二题的要求是给定一个字符串，这个字符串是由()、[]两种括号组成的，还是要求算法复杂度是O(n)，即遍历一次字符串。当时，看到这道题内心是拒绝的，由于长时间没有接触算法的东西，一下子也没什么好的办法。在思考的过程中，想出过一种解决方案：两个循环，从两边开始遍历，相等的情况直接提取，不相等的情况，右边的变量继续往左移动，直到第二次相等，将剩余的字符串提取出来，继续进行相同的操作，直到最后两边的变量重合。

第一种方案图

其实这是一种解决方案，只是它的算法复杂度并不等于O(n)，所以，我们来看接下来的解决方案。
经过面试官的提醒，我顺利地想到了使用栈的方式去解决问题，栈的大体介绍如下：

解题思路

首先，我们建立一个栈对象，之后遍历字符串，当前字符与下一个字符不相同时，去判断栈的最后一位是否与之相同，如果相同，则将栈中最后一位与当期位一起打印出来，如果不相同，则将当前的字符压入栈中，依次往下。

栈图

代码

var stack = [];
var string1 = '(([]()[])[])';

for(var i=0; i < string1.length; i++){
    if(countNum(string1[i]) + countNum(string1[i+1]) === 0){    //首先判断当前字符与下一个字符是否匹配，若匹配直接打印，并将变量i加一
        console.log(string1[i] + string1[i+1]);
        i++;
        continue;
    }else{      //若不匹配
        if(stack.length === 0){    先查看栈内是否有字符，没有就直接放入栈中
            stack.push(string1[i]);
            continue;
        }else{       //若有的话，判断栈的最后一个字符是否与之匹配
            var len = stack.length;
            if(countNum(stack[len-1]) + countNum(string1[i]) === 0){   直接匹配的话，则打印两个字符，并且将栈的最后一个字符去除
                console.log(stack[len-1]+string1[i]);
                stack.pop();
                continue;
            }else{       //若不匹配，则将该字符继续放入栈中
                stack.push(string1[i]);
                continue;
            }
        }
    }
}

function countNum(chr){                   //为了方便匹配每个字符，将字符用数字表示
    switch(chr){
        case '(': return 1;break;
        case ')': return -1; break;
        case '[': return 2; break;
        case ']': return -2; break;
        default: return 0;
    }
}

经历过这一次的面试，我忽然明白自己做前端这么久，却忽略了计算机中最重要的东西——算法。或许，做前端的多数时候都在处理用户交互和UI组件，以及界面等问题吧，哈哈。但是，现在才明白做前端的，不能将自己局限起来，或许不久的将来，前端也会注重以前我们忽略的东西。

如果你喜欢我的文章，就给个喜欢与关注吧。我的文章会不定期的更新，谢谢点赞和支持。当然，你也可以留言，与我一起研究和讨论。