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

这些题目摘自《剑指offer》,会给出实现,思路,但是不会详细讲解,大家开动起脑筋吧

1.实现一个单例模式

1
2
3
4
5
6
function single(func){
var instance;
return function(config){
return instance || new func(config);
}
}

主要就是使创建的对象始终保存在一个引用中,下次创建的时候如果引用不为空则使用引用的值

2.二维数组的查找

题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function find(array,num){
var find = function(x,y){
if(x>array[0].length-1 || y>array.length-1) return false;
var value = array[x][y];
if(value<num){
return find(x+1,y) || find(x,y+1);
}else if(value>num){
return false;
}else if(value===num){
return {x: x,y: y}
}
}
return find(0,0);
}

思路:这个题理解题目意思很重要,发现该二维数组的特征,假设一个输入,根据数组的特征一步步代入,就会发现规律,我选择从左上角开始验证。

上述代码是初始形态,还不够完善,由于存在重复比较的情况,所以在这里引入一个二维数组来存储节点的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function find(array,num){
var dp = array.map(function(value){
return value.map(function(){
return false;
})
});
var find = function(x,y){
if(x>array[0].length-1 || y>array.length-1) return false;
if(dp[x][y]!==false) return dp[x][y];
var value = array[x][y];
if(value<num){
return find(x+1,y) || find(x,y+1);
}else if(value>num){
return dp[x][y] = false;
}else if(value===num){
return {x: x+1,y: y+1}
}
}
return find(0,0);
}

3.重建二叉树

题目:输入某二叉树的前序和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数组。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},输出它的头节点。

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
39
40
function buildBTree(front,middle){
var build = function(Node,Range){
var x = front.indexOf(Node.value),
y = middle.indexOf(Node.value),
leftTree = [Range.start,y-1],
rightTree = [y+1,Range.end],
leftTable = {},
rightTable = {},
leftNode,rightNode,leftStop,rightStop;
middle.slice(leftTree[0],leftTree[1]+1).forEach(function(value){
leftTable[value] = true;
});
middle.slice(rightTree[0],rightTree[1]+1).forEach(function(value){
rightTable[value] = true;
});
for(var i=x+1;i<front.length;i++){
if(!leftStop&&leftTable[front[i]]){
leftNode = {value: front[i]};
leftStop = true;
}
if(!rightStop&&rightTable[front[i]]){
rightNode = {value: front[i]};
rightStop = true;
}
if(leftStop&&rightStop) break;
}
Node.left = leftNode;
Node.right = rightNode;
if(leftNode) build(leftNode,{start: Range.start,end: y-1,});
if(rightNode) build(rightNode,{start: y+1,end: Range.end});
return;
}
var root = {value: front[0]};
build(root,{start: 0,end: middle.length-1});
return root;
}

做好这道题需要充分理解二叉树的前序,中序,和后序遍历的原理,结合两个序列,先自己重建一遍树的结构,然后找寻其中的规律

4.用两个栈实现队列

题目:用两个栈实现一个队列。队列的声明如下:请实现两个函数appendTail和deleteHead,分别完成在队列尾部插入节点和在队列头部删除结点的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function queue(){
this.stack1 = [],
this.stack2 = [];
}
queue.prototype.appendTail = function(item){
return this.stack2.push(item);
}
queue.prototype.deleteHead = function(){
if(!this.stack1.length){
while(this.stack2.length){
this.stack1.push(this.stack2.pop());
}
}
return this.stack1.pop();
}

思路: 利用两个栈,一个负责进一个负责出,出的时候只需要将进栈序列颠倒即可

5.旋转数组的最小数字

题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function findMin(arr){
var find = function(left,right){
var middle = parseInt((left+right)/2);
var mdValue = arr[middle];
var lValue = arr[left];
var rValue = arr[right];
if((right-left)===1) return rValue>lValue? lValue:rValue;
if(mdValue>rValue){
return find(middle,right);
}else if(mdValue<rValue){
min = mdValue;
return find(left,middle);
}
}
return find(0,arr.length-1);
}

思路:不要想着遍历所有的元素找出最小的,这是很低级的做法,这道题完全可以利用旋转数列的特征,虽然这个数列不是完全的有序数列,不过依然能够通过有序数列的排序算法求解,这里我使用基本的二分查找实现它

6.斐波那契数列

题目:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。斐波那契数列的定义如下:
f(0) = 0,f(1) = 1,f(n) = f(n-1)+f(n-2)

思路:有人说这道题不是很简单吗?直接写个递归不就好了,如下

1
2
3
4
5
function calc(n){
if(n===0) return 0;
if(n===1) return 1;
return calc(n-1)+calc(n-2);
}

仔细思考一下,这个方法是不是重复计算了,就跟第3道面试题是差不多的,是不是需要一个储存计算值的数组呢?像下面这样

1
2
3
4
5
6
7
8
9
10
11
function calc(n){
var dp = [];
var cal = function(index){
if(index===0) return 0;
if(index===1) return 1;
dp[index-1] = dp[index-1] || cal(index-1);
dp[index-2] = dp[index-2] || cal(index-2);
return dp[index-1]+dp[index-2];
}
return cal(n);
}

当然了,这道题还有一些其它的写法,不说了,都很简单。

7.二进制中1的个数

题目: 请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。例如把9表示成二进制是1001,有2位是1.因此如果输入9,该函数输出2.

1
2
3
4
5
6
7
8
9
10
function calc(num){
if(num===0) return 0;
var count = 0, moR;
while(num!==1){
moR = num % 2;
if(moR===1) count++;
num = (num-moR)/2;
}
return ++count;
}

思路:这道题都不会的小伙伴需要重新学习一下《计算机导论》。。。就是十进制转换成二进制,需要注意的就是一定要考虑全面,往往越简单的题,面试官期望得到的答案越全面。

8.数值的整数次方

题目: 实现函数double Power(double base , int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function calc(base, exponent){
if(base===0||base===1) return base;
if(exponent<0) return false;
var dp = [];
var do1 = function(base,exponent){
if(exponent===0) return 1;
if(exponent===1) return base;
if(exponent%2===0){
return dp[exponent] = dp[exponent] || do1(base,exponent/2)*do1(base,exponent/2);
}else{
dp[exponent-1] = dp[exponent-1] || do1(base,(exponent-1)/2)*do1(base,(exponent-1)/2);
return dp[exponent-1]*base;
}
}
return do1(base,exponent);
}

思路: 将exponent拆分成两个相同的部分,利用数组记录其中一个的结果,使用递归实现,需注意当exponent是偶数,拆分成两个exponent/2,如果是奇数则是两个(exponent-1 )/2 与一个base

9.调整数组顺序使奇数位于偶数前面

题目: 输入一个整数数组,实现一个函数来调整该书组的数字顺序,使得所有技术位于数组的前半部分,所有偶数位于数组的后半部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function calc(array){
var left = 0,
right = array.length-1,
temp,itemL,itemR;
while(right>=left){
console.log(right,left);
itemL = array[left]%2;
itemR = array[right]%2;
if(itemL===0) left++;
if(itemR!==0) right--;
if(itemL && !itemR) {
temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
}
return array;
}

思路: 根据题目的特点,可以轻易发现,只要每次判断数组两端的值即可,所以拿两个变量分别记录数组的首部和尾部,然后分情况讨论首尾是否移动

0%