前端面试中常见的算法问题读后整理

看到有一篇写前端面试中常见的算法文章，里面的例子很简单，但也挺有趣。
重要的是，其实每个问题，都不止一个解答，我们可以从各个方面细想一下，拓展一下思路。

判断一个字符串是否回文

利用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 = Array.prototype.reduceRight.apply('abc',[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