前端面试算法

稿件来源: 阳光企业网站管理系统   撰稿作者: 太阳光   发表日期: 2015-5-19   阅读次数: 2   查看权限: 游客查看

收集的部分前端面试算法

一、在只容许使用++操作符的情况下,请完成下面代码,实现减法、乘法和除法。注意:假设操作数全为正整数,并且可以不考虑性能,不能使用--,*,/等操作符。 
a). 乘法: multi(int opl,int op2){//op1*op2} 
b). 减法: sub(int op1,int op2){//op1-op2} 
c). 除法: div(int op1,int op2){//op1/op2}
function multi(opl,op2){
  for(var i = 0,a = 0;i < opl;i ++){
    for(var l = 0;l < op2;l ++,a ++);
  }
  return a;//乖法 opl*op2
}

function sub(op1,op2){
  var min = Math.min(op1,op2),max = Math.max(op1,op2)
  for(var i = 0;min < max;min ++,i ++);
  return op1 >= op2 ? i : (i=~i,++i);//减法 op1-op2
}

function div(op1,op2){
  for(var i = 0;i < op1; i++){
    var a = i;
    if(multi(a,op2) == op1 || multi(++a,op2) > op1){
      return i;//除法  op1/op2
    }
  }
}

乘法比较好理解,两个循环不断数数得出积,但如果数值比较大就会卡死。当然这是限制条件考验算法就不要求性能问题。

减法计算因考虑可能会是负数,而又不能用减号故巧用了~按位取反运算符。

除法只取整,因没法得出小数问题。

 

二、实现字符串转换“I love thisgame”转换成“game this love I”

var a = "I love this game".split(" ").reverse().join(" ");
console.log(a);

类似这种字符操作先分割数组再反转是最直接快速方法。甚至直接用正侧来分割数组。

 

三、已知数组如X=[1,2,3,4],输出其所有子集,如1,2,3,4,12,23,34,123,234,1234…

var result = [],t = [1,2,3,4];
function group(a, len){
    var arr = a.slice(0),item = [arr.shift()];
    (function func(item,arr){
        var itemc,temp = arr.slice(0),l = len - item.length;
        if( l == 0){
            result.push(item);
        }else if( l == 1){
            for(var j in arr){
                itemc = item.slice(0);
                itemc.push(arr[j]);
                result.push(itemc);
            }
        }else if( l > 1){
            itemc = item.slice(0);
            itemc.push(temp.shift());
            func(itemc,temp);
            item.length + temp.length >= len && func(item,temp);
        }
    })(item,arr);
    arr.length >= len && group(arr, len);
}
for(var i = 1;i < t.length;i ++){
    group(t,i);
}
console.log(result);

此题算法比较难,网上已有的解法甚少。group()是在一个数组中取n个元素共有多少种组合的方法。然后循环取出所有子集组合即可。

四、将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5

function fj(n){
    var sum = n,x = "",i = 2;
    while(i <= sum){
        if(sum % i ==0){
            x += "*"+ i;
            sum /= i;
        }else{
            i++;
        }
    }
    return n +"="+ x.substring(1);
}

五、求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)

function sum(n){
  var i=1 ,a = 0;
  (function(){
    a += i;
    i++ < n && arguments.callee();
  })();
  return a;
}

六、有两个有序的集合,集合的每个元素都是一段范围,求其交集,例如集合[[4,8],[9,13]]和[6,12]的交集为[[6,8],[9,12]]

var arr1  = [[4,8],[9,13]];
var arr2 = [6,12];
var arr3 = [];
if(!(arr2[1] < arr1[0][0] || arr2[0] > arr1[1][1] || arr2[0] > arr1[0][1] && arr2[1] < arr1[1][0])){
    if(arr2[1] < arr1[1][0]) {
        arr3 = [Math.max(arr1[0][0], arr2[0]), Math.min(arr1[0][1], arr2[1])];
    }else if(arr2[0] > arr1[0][1]){
        arr3 = [Math.max(arr1[1][0], arr2[0]), Math.min(arr1[1][1], arr2[1])];
    }else{
        arr3 = [[Math.max(arr1[0][0], arr2[0]),arr1[0][1]],[arr1[1][0],Math.min(arr1[1][1], arr2[1])]];
    }
}
console.log(arr3);

以上方法判断有点复杂,而且假如arr1为不定项时不够灵活,我们可以用更巧更精的循环判断法:

var arr1  = [[4,8],[12,13]];//支持N个有序集合
var arr2 = [9,12];
var arr3 = [];
for (var i = 0;i < arr1.length;i ++){
  if (arr2[1] >= arr1[i][0] && arr2[0] <= arr1[i][1]){
    arr3.push([Math.max(arr1[i][0],arr2[0]),Math.min(arr1[i][1],arr2[1])]);
  }
}
console.log(arr3);

//此方法甚至能扩展到arr2也可为不定项有序集合

七、指定某个时刻如17:32,请问时针跟分针的最小夹角是多少度?

答:|30*(小时%12+分钟/60)-6*分钟|

八、输入一个字符串,如何求最大重复出现的字符串呢?比如输入ttabcftrgabcd,输出结果为abc,canffcancd,输出结果为can。

function getStr(str){
  for(var i = Math.ceil(++str.length /2);i--;){
    if(str.match(new RegExp("(\\w{"+i+"}).*\\1+","g")))return RegExp.$1;
  }
}
alert(getStr("ttabcftrgabcd"));

此方法巧用正侧的\1匹配方法,而且循环时使用了Math.ceil(++str.length /2),而不是直接使用.length来循环,优化了程序。

九、输入一个正整数A,求与A的二进制1的个数相同的B,且A和B之间的距离|A-B|最小。

分析:除了0其他数的二进制都有1,同时如果是系统支持的最大数全是1,那么返回也是它本身(区分32还是64位系统)。假如二进制含有10的,从尾找起,找到互换一下位置,如果全是1的第2个位置插入一个0即可。

var num = 18;//输入的A数
var str = parseInt(num).toString(2),n;
if(/10/.test(str)){
  n = str.replace(/^(\d*)10(0*)$/g,function($,b,c,d){return b+"01"+d});
}else{
  n = /\d{63,}/.test(str) ? str : str.replace(/^1(1*)$/g,function($,b){return "10"+b});
  //暂定64位系统
}
console.log(parseInt(n,2));//得出B数

十、给定数字0-9各若干个。你可以以任意顺序排列这些数字,但必须全部使用。目标是使得最后得到的数尽可能小(注意0不能做首位)。例如:给定两个0,两个1,三个5,一个8,我们得到的最小的数就是10015558。

"10015558".split("").sort().join("").replace(/^(0*)([^0])(\d*)$/g,function(a,b,c,d){
  alert(c+b+d);//重排后把最小的非0数提到前面即可。
});

十一、用脚本代码实现:从自然数1到1000中随机取900个不重复的数并打印出来。

var array = [],n,l = 1000;
for(var i = l + 1;--i;){
  array.push(i);
}
for(i = 0;i<l;i++){  
   n = parseInt(Math.random()*l);  
   array[i] = [array[n],array[n] = array[i]][0];//深度打乱  
}
array.length = l - 100;
console.log(array.join(","));

十二、请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。

var str = "google"; 
for(var s = "#", i = 0,l = str.length; i<l; i++){
  if(str.split(str.charAt(i)).length == 2){
    s = str.charAt(i);
    break;
  }
} 
alert(s);//暂没找到一下正侧出来的方法

十三、编程实现将中文的“贰仟零伍亿叁佰扒拾万零叁拾”转换为“200503800030”。

function getNumb(str) {
    var obj = {"亿": 100000000,"万": 10000,"仟":1000,"佰":100,"拾":10,"壹":1,"贰": 2,"叁": 3,"肆": 4,"伍": 5,"陆": 6,"柒": 7,"捌": 8,"玖": 9},
        arr = str.replace(/(零|佰|^)拾/g, "$1壹拾").replace(/零/g, "").split(/(亿|万|仟|佰|拾)/).filter(function (a) {return a != ""}),
        a = 0, l = 0, f,n;
    for (var i = 0; i < arr.length;i = i + 2 ) {
        f = arr[i],n = arr[i + 1];
        if (/亿|万/.test(f)) {
            a += l * obj[f];l = 0;
            i --;
        }else if (/亿|万/.test(n)) {
            a += (l + obj[f]) * obj[n];l = 0;
        } else {
            l += obj[f] * (obj[n] ? obj[n] : 1);
        }
    }
    return a + l;//开始用正侧浪费不少时间
}

 

关键词: js面试题   编辑时间: 2015-6-25 18:00:24

  • 感到高兴

    0

    高兴
  • 感到支持

    0

    支持
  • 感到搞笑

    0

    搞笑
  • 感到不解

    0

    不解
  • 感到谎言

    0

    谎言
  • 感到枪稿

    0

    枪稿
  • 感到震惊

    0

    震惊
  • 感到无奈

    0

    无奈
  • 感到无聊

    0

    无聊
  • 感到反对

    0

    反对
  • 感到愤怒

    0

    愤怒
0%(0)
0%(0)
共有0 条评论 发言请遵守【相关规定

网友评论

会员头像
发 表同步腾讯微博  匿名评论  验证码:  点击更新
  • 暂无评论
关闭模块文章图片 article Pictrue
  • 代码覆盖率工具 Istanbul 入门教程
  • 全栈工程师的武器——MEAN
  • 9款超炫的 CSS3 复选框(Checkbox)
  • 微信开发在线翻译功能
  • CSS3那些不为人知的高级属性
  • 给easyui的datebox添加清空事件
  • flash写字效果
  • kendoUI系列教程之DropDownList下拉菜单
  • kendoUI系列教程之datetimepicker日期时间选择
  • kendoUI系列教程之datepicker日期选择
  • kendoUI系列教程之combobox下拉列表框
  • kendoUI系列教程之colorpicker
  • kendoUI系列教程之calendar日历表
  • kendoUI系列教程之autocomplete自动补齐
  • kendo ui简介
  • QQ登录网站实战教程