前言
本人最近去了一次面试，被问到两题面试题，是考察算法的，觉得挺基础的，也比较有趣，分享一下
第一题的要求是，根据顺序输出二叉树的每个节点的值。这一题在算法中比较的基础，其实也没有什么难度。面试官的要求是需要使用时间复杂度为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组件，以及界面等问题吧，哈哈。但是，现在才明白做前端的，不能将自己局限起来，或许不久的将来，前端也会注重以前我们忽略的东西。
如果你喜欢我的文章，就给个喜欢与关注吧。我的文章会不定期的更新，谢谢点赞和支持。当然，你也可以留言，与我一起研究和讨论。
