一些面试题的JS实现(二)

接着上一部分的面试题继续

树的子结构

题目: 输入两颗二叉树A和B,判断B是不是A的子结构。

1
2
3
4
5
6
7
8
9
function calc(tree1,tree2){
if(!tree2) return true;
if(!tree1) return false;
if(tree1.value===tree2.value){
return calc(tree1.left,tree2.left) && calc(tree1.right,tree2.right);
}else{
return calc(tree1.left,tree2) || calc(tree1.right,tree2);
}
}

思路: 自己假想一下如果让你判断一个结构是否是另一个结构的子结构,你会怎么做,放心,你会发现规律的;

额外扩展题: 输入两个二叉树,找出它们的不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function diff(tre1,tre2){
var diffs = [];
var calc = function(tree1,tree2){
if(!tree1 && !tree2) return;
if(!tree1 || !tree2 || tree1.value!==tree2.value){
var v1 = tree1 && tree1.value,
v2 = tree2 && tree2.value;
diffs.push([v1,v2]);
}else if(tree1.value===tree2.value){
calc(tree1.left,tree2.left);
calc(tree1.right,tree2.right);
}
}
calc(tre1,tre2);
return diffs;
}

思路:跟上一题思路有相似之处,开动脑筋哦。

二叉树的镜像

题目:请完成一个函数,输入一个二叉树,该函数输出它的镜像。

1
2
3
4
5
6
7
8
9
function calc(tree){
if(!tree) return;
var temp = tree.left;
tree.left = tree.right;
tree.right = temp;
calc(tree.left);
calc(tree.right);
return tree;
}

思路:这道题,我想大家都知道怎么办了吧,观察镜像后二叉树的特征,很容易得到答案。

顺时针打印矩阵

题目: 输入一个矩阵,按照从外向里以顺时针的顺序一次打印出每一个数字。例如:如果输入如下矩阵
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
则打印出数字1、2、3、4、8、12、16、15、14、13、9、5、6、7、11、10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function calc(mar){
var start = {x: 0,y: 0},
rowLength = mar[0].length,
colLength = mar.length;
var doCalc = function(startP){
if(rowLength<=0 && colLength<=0) return;
var startX = startP.x,
startY = startP.y;
var rowEnd = startX+rowLength-1,
colEnd = startY+colLength-1;
var i;
//正方形的上边
for(i=startX;i<rowEnd;i++){
console.log(mar[startY][i]);
}
//右侧
for(i=startY;i<colEnd;i++){
console.log(mar[i][rowEnd]);
}
//下侧
for(i=rowEnd;i>startX;i--){
console.log(mar[colEnd][i]);
}
//左侧
for(i=colEnd;i>startY;i--){
console.log(mar[i][startX]);
}
rowLength -= 2;
colLength -= 2;
doCalc({x: startX+1, y: startY+1});
}
doCalc(start)
}

思路:每一圈当作一个循环,每一个循环的特征就是起始点不同,然后判断出结束状态,这道题很简单

包含min函数的栈

题目: 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min、push及pop的时间复杂度都是O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function minStack(){
this.mStack = [];
this.Stack = [];
}
minStack.prototype.push = function(num){
var Stack = this.Stack,
mStack = this.mStack;
Stack.push(num);
var min = mStack[mStack.length-1];
if(min>=num || typeof min === 'undefined'){
mStack.push(num);
}
}
minStack.prototype.pop = function(){
var Stack = this.Stack,
mStack = this.mStack;
var min = mStack[mStack.length-1];
var pop = Stack.pop();
if(min===pop){
mStack.pop();
}
return pop;
}
minStack.prototype.min = function(){
var Stack = this.Stack,
mStack = this.mStack;
return mStack[mStack.length-1];
}

思路:创建一个辅助栈,在栈顶存储进栈时最小的元素即可。

栈的压入、弹出序列

题目:输入两个整数序列,第一序列表示栈的压入顺序,请判断第二序列是否为该栈的弹出序列。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5是某栈的压栈序列,序列4、5、3、2、1是该栈序列对应的一个弹出序列,但4、3、5、1、2就不可能是该压栈序列的弹出序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function calc(enterQueue,popQueue){
for(var i=0;i<popQueue.length;i++){
var pop = popQueue[i];
var enterIndex = enterQueue.indexOf(pop);
var posPop1 = enterQueue[enterIndex+1];
var posPop2 = enterQueue[enterIndex-1];
var nextPop = popQueue[i+1];
var possiblePop = {};
possiblePop[posPop1] = enterIndex+1;
possiblePop[posPop2] = enterIndex-1;
console.log(pop,possiblePop,nextPop,enterIndex);
if(!nextPop){
return true;
}
if(possiblePop[nextPop] || possiblePop[nextPop]===0){
enterQueue.splice(enterIndex,1);
}else{
return false;
}
}
}

从上往下打印二叉树

题目:从上往下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

1
2
3
4
5
6
7
8
9
10
function calc(tree){
var queue = [tree];
while(queue.length>0){
var temp = queue.shift();
console.log(temp.value);
temp.left && queue.push(temp.left);
temp.right && queue.push(temp.right);
}
}

思路:利用队列的特性,完成二叉树的宽度优先遍历

二叉搜索树的后序遍历序列

题目: 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function calc(array){
var docalc = function(left,right){
if(left===right) return true;
var root = array[right];
var leftC = [], rightC = [];
for(var i=left;i<right;i++){
var item = array[i];
if(item<root && !push(leftC,{index: i,value: item})) return false;
if(item>root && !push(rightC,{index: i,value: item})) return false;
}
return docalc(leftC[0].index,leftC[leftC.length-1].index) && docalc(rightC[0].index,rightC[rightC.length-1].index);
};
var push = function(arr,obj){
var index = obj.index,
value = obj.value;
if(arr[arr.length-1] && (arr[arr.length-1].index+1)!==index && arr.length!==0){
return false;
}else{
arr.push(obj);
return true;
}
}
return docalc(0,array.length-1);
}

思路: 像这种给出序列去判断的问题,一般会先找到根节点,然后再递归判断

二叉树中和为某一值的路径

题目:输入一颗二叉树和一个整数,打印出二叉树节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function calc(tree,integer){
var path = [];
var docalc = function(tree,sum){
path.push(tree? tree.value : 'undefined');
if(!tree){
return;
}
sum = sum+tree.value;
if(sum===integer){
console.log(path);
}
docalc(tree.left,sum);
path.pop();
docalc(tree.right,sum);
path.pop();
}
docalc(tree,0);
}

思路: 不难看出保存路径的数据结构实际是一个栈,因为路径要与递归状态调用状态一致,而递归调用的本质就是一个压栈和出栈的过程。

字符串的排列

题目:输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function calc(str){
var strArray = str.split('');
var path = [];
var docalc = function(array){
if(array.length===1){
path.push(array[0]);
console.log(path);
path.pop();
return;
}
for(var i=0;i<array.length;i++){
var left = array[0];
array[0] = array[i];
array[i] = left;
path.push(array[0]);
docalc(array.slice(1));
path.pop();
var temp = array[0];
array[0] = left;
array[i] = temp;
}
}
docalc(strArray);
}

思路: 利用递归思想,想固定一个位置,然后求剩余位置的排列;

0%