又到了对上周题目总结的时候了:
第一题:如何去掉一个数组中重复的值?
这道题如果只考虑最简单的情况的话:既整数数组的情况
比如输入: [1,13,24,11,11,14,1,2]
输出: [1,13,24,11,14,2]
需要去掉重复的11 和1 这两个元素
便可以使用object特性进行筛选:
for (let i=0;i < arr.length;i++){
if (!hash[arr[i]]) {
hash[arr[i]]=true;
data.push(arr[i]);
}
但是很多大神的指出了出题人的不足,如对重复的定义的问题:数字1与字符‘1’算不算相等,因此要做到完备,必须考虑很多事情。这里可以看看小虫大神推荐的文章:浅谈JavaScript数组去重
第二题:找出一个整数数组的最大差值,如输入[10,5,11,7,8,9] 输出 6
由于上一道题各位大神的指正,这道题直接规定了整数数组,解法也比较容易想到,利用循环的出数组的最大值与最小值,然后做差便可以得出答案:
for x in arr {
if (x>=max)
max=x;
if (x<=min)
min=x;
}
当然还有童靴提出可以先排序,但是排序如果不进行预处理的话,最优算法的时间复杂度是nlogn,这说明对数组进行排序是没有必要的,最后再贴出joel大神的代码,直接利用了Math函数:
let min = Math.min(...arr);
let max = Math.max(...arr);
ret=max - min;
其实前端面试很看重你对函数的了解情况以及对新知识的运用,比如上周的反转字符串的题目也是这样。
第三题:求整数数组的最大连续子串,如数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4]的最大连续子串是[4, -1, 2, 1]?
如果按照正常的思路,可以使用小虫大神的方法,先对数组位置进行标记,然后利用两个for循环对每个可能组成的值进行对比:
for(i=0; i < arr.length; i++) {
for(j = i; j < arr.length; j++) {
value = value + arr[j];
if(value > max.value) {
max.start = start;
max.end = j;
max.value = value;
}
有童靴指出可以只对正数进行操作,这是很正确的想法,再次进行鼓励。
其实还有O(n)的方法,这是一道很经典可以利用动态规划完成的题目:思想即对于每一位数,先取出前一位的信息进行判断前面连续子串的总和,如果总和大于等于0,则将自己与前面进行拼接,否则只保留自身,以此生成处理信息传递给下一位处理。数学推导式如下,其中a为原始数组,b为辅助数组:
b(j - 1) + a(j)(当b(j-1) >= 0)
b(j) = {//数学大括号
a(j) (当b(j-1) < 0)
既:
for(int i=1;i<=n;i++){
if(b>0)
b+=a[i];
else b=a[i];
}
全部代码可以参照网上一篇:求连续最大子串
第四题:已知 fn 为一个预定义函数,实现函数 curryIt,调用之后满足如下条件:
1、返回一个函数 a,a 的 length 属性值为 1(即显式声明 a 接收一个参数)
2、调用 a 之后,返回一个函数 b, b 的 length 属性值为 1
3、调用 b 之后,返回一个函数 c, c 的 length 属性值为 1
4、调用 c 之后,返回的结果与调用 fn 的返回值一致
5、fn 的参数依次为函数 a, b, c 的调用参数
如:var fn = function (a, b, c) {return a + b + c}; curryIt(fn)(1)(2)(3);
输出:6
这道题,小虫大神直接就看出来是考的函数柯里化
直接上解答:
functioncurryIt(fn) {
return functiona(xa){
return functionb(xb){
return functionc(xc){
return fn.call(this,xa,xb,xc);
};
};
};
}
关于函数柯里化,可以看下幺鹿大神的推荐函数珂里化