奔三路 - 你30岁前的学习路!

奔三路学习网

当前位置: 主页 > 前端面试通 > 笔经面经 >

前端面试中常见的算法问题

时间:2017-10-31 21:23来源:百面网 作者:
判断一个字符串是否回文利用js数组实现js的数组是一个很强大的数据结构,我们可以活用其已实现的原生方法做很多事,比

判断一个字符串是否回文

利用js数组实现

js的数组是一个很强大的数据结构,我们可以活用其已实现的原生方法做很多事,比如,这个例子中,判断一个字符串是否是回文。

步骤:

  • 将字符串拆分成数组 将字符串拆分成数组其实也也有多种方法:
    • split()方法
    let str_to_array = function(str){
      return str.split('');
    }
    • Array.prototype.map()
    let str_to_array = function (str) {
      return Array.prototype.map.call(str,function(x){return x});
    }
  • 数组反转 reverse()
  • 拼接成字符串 join()
let checkPalindrom = function(str){
  return str_to_array(str).reverse().join('');
}

活用数组的reduceRight()方法

我们可以直接在字符串上调用数组的reduceRight()方法将字符串逆转

let rs = (str) =>{
    return Array.prototype.reduceRight.apply(str,[function(pre,current){
        return pre + current;
    },'']);
}
let checkPalindrom = function(str){
  return str == rs(str);
}

使用栈数据结构

我们在学习栈这个数据结构的时候,老师讲的最生动的一个例子就是,判断回文有木有。 先将字符串中字符依次入栈,然后出栈组成新的字符串,即为逆转的字符串,然后做比较。

去掉一些整型数组中重复的值

直接使用es6的Set

let unique = function(array){
  return [...new Set(array)];
}

使用Object

我们知道Object对象的键是唯一的,可以利用这个特性为数组去重。

let unique = function (array) {
    let ro = {};
    let ra = [];
    array.forEach(item=>{
        if(!ro[item]){
            ro[item] = item;
            ra.push(item);
        }
    });

    return ra;
}

统计一个字符串出现最多的字母

首先我们要先统计字符串中各个字符出现的次数,我们可以使用最笨的遍历方法进行统计:

let countChar = function countChar(str){
    let ro = {};
    for(let c of str){
        if(!ro[c]){
            ro[c] = 1;
        }else{
            ro[c] ++;
        }
    }
    return ro;
}

当然,也使用数组的reduce()方法进行统计,因为这个方法就适合进行统计计算。

let countChar = function countChar(str){
    return Array.prototype.reduce.call(str,function(pre,current){
        if(pre[current]){
            pre[current] ++;
        }else{
            pre[current ] = 1;
        }
        return pre;
    },{});
}

然后,从刚才统计出的数中查找出出现次数最多的字符

let findMaxDuplicateChar = function (str){
  let chars = countChar(str);
  let max = 0;
  let char = null;
  for(let c in chars){
    if(chars[c] > max){
      max = chars[c];
      char = c;
    }
  }
  return char;
}

不用临时变量,交换两个变量的值

原文中呢,作者教大家要合理运用+,-运算,最后给出如下答案:

function swap(a , b) {  
  b = b - a;
  a = a + b;
  b = a - b;
  return [a,b];
}
module.exports = swap;  

很巧妙,对吧,确实是合理运用了+,-运算,但是为什么呢?合理运用*,/运算呢?

a = a * b;
b = a / b;
a = a / b;

合理运用*,/好像也可以啊,对吧。 其实解决问题,我们应该从根上去解决,不能简单的说’合理运用’就敷衍过去了。 题目是,不用临时变量,临时变量是干嘛的呢?当然是存储临时值用的了,对吧。 那么,不用临时变量,我们可以把临时值存储到当前现有的变量中,对吧。 就好像是创造了一个临时变量一样。上面两个例子中,都是用两个变量的差或两个变量的积作为临时值,然后存储到其中一个变量,再由相应的运算交换两个变量的值。 明白了这个道理后,我们再合理一下嘛,对吧,利用两个变量的和作为临时值:

a = a + b;
b = a - b;
a = a - b;

注意:这里慎用两个变量的商作为临时值,因为如果两个变量除不尽,由于js中除法运算会舍掉余数,则会发生问题。

我们除了使用+,-,*,/四则运算创造‘临时变量’外,还可以使用位运算

a = a ^ b;
b = b ^ a;
a = a ^ b;

这个比上面的四则运算就要稍难理解了,这里运用了位运算中的异或运算。 对于异或运算的说明,还有不明白的可以回去翻翻大学的课本。 第一行 a = a ^ b;即创造了一个临时值存储在a中。

b = b ^ a

相当于

b = b ^ (a ^ b) = b ^ b ^ a = a

同理,

a = a ^ b

相当于

a = (a ^ b) ^ (b ^ (a ^ b)) = a^b^b^a^b = a^a^b^b^b = 0^0^b = b

找出数组中最大差值

可以直接遍历数组,找出最大值和最小值,然后做差。但是呢,那样就没意思了,对吧,我们可以直接使用数组的reduce()方法找出最大值和最小值。

let getMaxProfit = function getMaxProfit(arr) {
    let max_min = arr.reduce(function(pre,current){
        if(pre.min > current){
            pre.min = current;
        }
        if(pre.max < current){
            pre.max = current;
        }
        return pre;
    },{min:arr[0],max:arr[0]});

    return max_min.max - max_min.min;
}

当然,使用reduce()貌似还是有点麻烦啊,js的Math对象不是有max()和min()方法嘛,直接用这两个方法找出最大值和最小值就好了啊:

let getMaxProfit = function getMaxProfit(arr){
    let max = Math.max.apply(Math,arr);
    let min = Math.min.apply(Math,arr);
    return max - min;
}

这里使用了apply方法直接调用max()和min()来获取最大值和最小值。 我们都知道js中apply和call两个方法是功能相同的两个方法,只是传参方式不同。call方法传递参数列表,而apply传递参数对象或数组。 在es6中新添加了一个...操作符,用于将数组展开成列表,具体可参见MDN上的文档。 因此,我们这里可以使用该操作符,直接调用max()和min()方法:

let getMaxProfit = function getMaxProfit(arr){
    let max = Math.max(...arr);
    let min = Math.min(...arr);
    return max - min;
}

位操作

20世纪70年代末到80年代末,Digital Equipment的VAX计算机是一种非常流行的机型。它没有布尔运算AND和OR指令,只有bis(位设置)和bic(位清除)这两个指令。两种指令的输入都是一个数据字x和一个掩码字m。他们生成一个结果z,z是由根据掩码m的位来修改x的位得到的。使用bis指令,就是在m为1的每个位置上,将z对应的位设置为1.使用bic指令,在m为1的每个位置,将z对应的位设置为0。 只使用bis和bic指令,完成按位|^运算。

//bis和bic声明
int bis(int x,int m);
int bic(int x,int m);

//完成如下 | 运算 和 ^ 运算
int bool_or(int x,int y){
    int result = ______ ;
    return result;
}

int bool_xor(int x,int y){
    int result = ______ ;
    return result;
}

这其实是一道逻辑题目,由已知的bis运算逻辑和bic运算逻辑,用这两种运算去实现其他的运算。 bis运算就是在掩码位为1的位设置为1,其他位不变。而bic运算是在掩码位为1的位置设置为0,其他不变。 举个例子:

x   11010100
m   10100101
bis --------
    11110101


x   11010100
m   10100101
bic --------
    01010000

好了,那怎么利用这两种运算指令实现按位 | 和 ^ 运算呢? 仔细分析一下 bis 运算,所有掩码位为1的位,结果都是1,其他为0的位,还是按照原来的位,这不就是按位 | 运算么? 于是,第一个有了:

int bool_or(int x,int y){
    int result = bis(x,y) ;
    return result;
}

那 ^ 运算呢? 我们都知道,异或运算运算法则为:a⊕b=(¬a∧b)∨(a∧¬b),a⊕b=(¬a∨b)∧(a∨¬b)。至于为什么,可以列真值表验证。 这里我们采用第一个运算法则:a⊕b=(¬a∧b)∨(a∧¬b)。 bic运算是怎么来的呢?bic(a,b)是将a上对应b为1的位变为0,其他不变。那么,不就是相当于先将b取反,然后和a进行按位与&运算么,就是:

bic(a,b) = a & (~b)

于是,再利用异或第一个运算法则:a⊕b=(¬a∧b)∨(a∧¬b) 我们可以得出:

int bool_xor(int x,int y){
    int result = bis(bic(x,y),bic(y,x));
    return result;
}

js实现二叉搜索树

啥也不说了,直接看我github上的代码吧。 https://github.com/coolcao/dsa_js/blob/master/src/BSTree.js

(责任编辑:admin)
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片
发布者资料
史密斯 查看详细资料 发送留言 加为好友 用户等级:注册会员 注册时间:2017-11-24 11:11 最后登录:2018-09-02 11:09

关注奔三路