前端面试算法

搜索

您当前位置：首页 > 文章中心 > 网页编程 > Javascript

【Javascript】

下载

新闻

文章

收集的部分前端面试算法

一、在只容许使用++操作符的情况下，请完成下面代码，实现减法、乘法和除法。注意：假设操作数全为正整数，并且可以不考虑性能，不能使用--，*，/等操作符。

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;//开始用正侧浪费不少时间
}