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

た入场券 2022-09-29 06:14 214阅读 0赞

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

原文：[前端面试中的常见的算法问题][Link 1]

## 判断一个字符串是否回文 ##

### 利用js数组实现 ###

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

#### 步骤： ####

*  将字符串拆分成数组  
    将字符串拆分成数组其实也也有多种方法：
    
     *  split()方法
        
        <table style="border-collapse:collapse; border-spacing:0px; margin:0px; width:auto; border:none; font-size:14px; table-layout:fixed"> 
         <tbody> 
          <tr style="background-color:rgb(249,249,249)"> 
           <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px 20px 1px 1px; color:rgb(102,102,102); background:rgb(45,45,45); line-height:1.6; border:none; text-align:right">
                 
                  
             <div style="height:20px">
              
                   
                  1
                 
                  
             </div>
                 
                  
             <div style="height:20px">
              
                   
                  2
                 
                  
             </div>
                 
                  
             <div style="height:20px">
              
                   
                  3
                 
                  
             </div></pre> </td> 
           <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px; color:rgb(204,204,204); background:rgb(45,45,45); line-height:1.6; border:none">
                 
                  
             <div style="height:20px">
                  
                   
              <span style="color:rgb(204,153,204)">let</span> str_to_array = 
                  
                   
              <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">function</span>(<span style="color:rgb(249,145,87)">str</span>)</span>{
                 
                  
             </div>
                 
                  
             <div style="height:20px">  
                  
                   
              <span style="color:rgb(204,153,204)">return</span> str.split(
                  
                   
              <span style="color:rgb(153,204,153)">''</span>);
                 
                  
             </div>
                 
                  
             <div style="height:20px">
              
                   
                  }
                 
                  
             </div></pre> </td> 
          </tr> 
         </tbody> 
        </table>
     *  Array.prototype.map()
        
        <table style="border-collapse:collapse; border-spacing:0px; margin:0px; width:auto; border:none; font-size:14px; table-layout:fixed"> 
         <tbody> 
          <tr style="background-color:rgb(249,249,249)"> 
           <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px 20px 1px 1px; color:rgb(102,102,102); background:rgb(45,45,45); line-height:1.6; border:none; text-align:right">
                 
                  
             <div style="height:20px">
              
                   
                  1
                 
                  
             </div>
                 
                  
             <div style="height:20px">
              
                   
                  2
                 
                  
             </div>
                 
                  
             <div style="height:20px">
              
                   
                  3
                 
                  
             </div></pre> </td> 
           <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px; color:rgb(204,204,204); background:rgb(45,45,45); line-height:1.6; border:none">
                 
                  
             <div style="height:20px">
                  
                   
              <span style="color:rgb(204,153,204)">let</span> str_to_array = 
                  
                   
              <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">function</span> (<span style="color:rgb(249,145,87)">str</span>) </span>{
                 
                  
             </div>
                 
                  
             <div style="height:20px">  
                  
                   
              <span style="color:rgb(204,153,204)">return</span> 
                  
                   
              <span style="color:rgb(249,145,87)">Array</span>.prototype.map.call(str,
                  
                   
              <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">function</span>(<span style="color:rgb(249,145,87)">x</span>)</span>{
                  
                   
              <span style="color:rgb(204,153,204)">return</span> x});
                 
                  
             </div>
                 
                  
             <div style="height:20px">
              
                   
                  }
                 
                  
             </div></pre> </td> 
          </tr> 
         </tbody> 
        </table>
 *  数组反转 `reverse()`
 *  拼接成字符串 `join()`

### 活用数组的reduceRight()方法 ###

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

### 使用栈数据结构 ###

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

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

### 直接使用es6的Set ###

### 使用Object ###

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

<table style="border-collapse:collapse; border-spacing:0px; margin:0px; width:auto; border:none; font-size:14px; table-layout:fixed"> 
 <tbody> 
  <tr style="background-color:rgb(249,249,249)"> 
   <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px 20px 1px 1px; color:rgb(102,102,102); background:rgb(45,45,45); line-height:1.6; border:none; text-align:right">
     
      
     <div style="height:20px">
      
       
      1
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      2
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      3
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      4
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      5
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      6
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      7
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      8
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      9
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      10
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      11
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      12
     
      
     </div></pre> </td> 
   <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px; color:rgb(204,204,204); background:rgb(45,45,45); line-height:1.6; border:none">
     
      
     <div style="height:20px">
      
       
      <span style="color:rgb(204,153,204)">let</span> unique = 
      
       
      <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">function</span> (<span style="color:rgb(249,145,87)">array</span>) </span>{
     
      
     </div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">let</span> ro = {};
     
      
     </div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">let</span> ra = [];
     
      
     </div>
     
      
     <div style="height:20px">
      
       
          array.forEach(
      
       
      <span style="color:rgb(102,153,204)"><span style="color:rgb(249,145,87)">item</span>=&gt;</span>{
     
      
     </div>
     
      
     <div style="height:20px">        
      
       
      <span style="color:rgb(204,153,204)">if</span>(!ro[item]){
     
      
     </div>
     
      
     <div style="height:20px">
      
       
                  ro[item] = item;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
                  ra.push(item);
     
      
     </div>
     
      
     <div style="height:20px">
      
       
              }
     
      
     </div>
     
      
     <div style="height:20px">
      
       
          });
     
      
     </div>
     
      
     <div style="height:20px"></div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">return</span> ra;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      }
     
      
     </div></pre> </td> 
  </tr> 
 </tbody> 
</table>

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

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

<table style="border-collapse:collapse; border-spacing:0px; margin:0px; width:auto; border:none; font-size:14px; table-layout:fixed"> 
 <tbody> 
  <tr style="background-color:rgb(249,249,249)"> 
   <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px 20px 1px 1px; color:rgb(102,102,102); background:rgb(45,45,45); line-height:1.6; border:none; text-align:right">
     
      
     <div style="height:20px">
      
       
      1
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      2
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      3
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      4
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      5
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      6
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      7
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      8
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      9
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      10
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      11
     
      
     </div></pre> </td> 
   <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px; color:rgb(204,204,204); background:rgb(45,45,45); line-height:1.6; border:none">
     
      
     <div style="height:20px">
      
       
      <span style="color:rgb(204,153,204)">let</span> countChar = 
      
       
      <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">function</span> <span style="color:rgb(102,204,204)">countChar</span>(<span style="color:rgb(249,145,87)">str</span>)</span>{
     
      
     </div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">let</span> ro = {};
     
      
     </div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">for</span>(
      
       
      <span style="color:rgb(204,153,204)">let</span> c 
      
       
      <span style="color:rgb(204,153,204)">of</span> str){
     
      
     </div>
     
      
     <div style="height:20px">        
      
       
      <span style="color:rgb(204,153,204)">if</span>(!ro[c]){
     
      
     </div>
     
      
     <div style="height:20px">
      
       
                  ro[c] = 
      
       
      <span style="color:rgb(153,204,153)">1</span>;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
              }
      
       
      <span style="color:rgb(204,153,204)">else</span>{
     
      
     </div>
     
      
     <div style="height:20px">
      
       
                  ro[c] ++;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
              }
     
      
     </div>
     
      
     <div style="height:20px">
      
       
          }
     
      
     </div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">return</span> ro;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      }
     
      
     </div></pre> </td> 
  </tr> 
 </tbody> 
</table>

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

<table style="border-collapse:collapse; border-spacing:0px; margin:0px; width:auto; border:none; font-size:14px; table-layout:fixed"> 
 <tbody> 
  <tr style="background-color:rgb(249,249,249)"> 
   <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px 20px 1px 1px; color:rgb(102,102,102); background:rgb(45,45,45); line-height:1.6; border:none; text-align:right">
     
      
     <div style="height:20px">
      
       
      1
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      2
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      3
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      4
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      5
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      6
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      7
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      8
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      9
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      10
     
      
     </div></pre> </td> 
   <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px; color:rgb(204,204,204); background:rgb(45,45,45); line-height:1.6; border:none">
     
      
     <div style="height:20px">
      
       
      <span style="color:rgb(204,153,204)">let</span> countChar = 
      
       
      <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">function</span> <span style="color:rgb(102,204,204)">countChar</span>(<span style="color:rgb(249,145,87)">str</span>)</span>{
     
      
     </div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">return</span> 
      
       
      <span style="color:rgb(249,145,87)">Array</span>.prototype.reduce.call(str,
      
       
      <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">function</span>(<span style="color:rgb(249,145,87)">pre,current</span>)</span>{
     
      
     </div>
     
      
     <div style="height:20px">        
      
       
      <span style="color:rgb(204,153,204)">if</span>(pre[current]){
     
      
     </div>
     
      
     <div style="height:20px">
      
       
                  pre[current] ++;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
              }
      
       
      <span style="color:rgb(204,153,204)">else</span>{
     
      
     </div>
     
      
     <div style="height:20px">
      
       
                  pre[current ] = 
      
       
      <span style="color:rgb(153,204,153)">1</span>;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
              }
     
      
     </div>
     
      
     <div style="height:20px">        
      
       
      <span style="color:rgb(204,153,204)">return</span> pre;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
          },{});
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      }
     
      
     </div></pre> </td> 
  </tr> 
 </tbody> 
</table>

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

<table style="border-collapse:collapse; border-spacing:0px; margin:0px; width:auto; border:none; font-size:14px; table-layout:fixed"> 
 <tbody> 
  <tr style="background-color:rgb(249,249,249)"> 
   <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px 20px 1px 1px; color:rgb(102,102,102); background:rgb(45,45,45); line-height:1.6; border:none; text-align:right">
     
      
     <div style="height:20px">
      
       
      1
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      2
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      3
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      4
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      5
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      6
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      7
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      8
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      9
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      10
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      11
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      12
     
      
     </div></pre> </td> 
   <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px; color:rgb(204,204,204); background:rgb(45,45,45); line-height:1.6; border:none">
     
      
     <div style="height:20px">
      
       
      <span style="color:rgb(204,153,204)">let</span> findMaxDuplicateChar = 
      
       
      <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">function</span> (<span style="color:rgb(249,145,87)">str</span>)</span>{
     
      
     </div>
     
      
     <div style="height:20px">  
      
       
      <span style="color:rgb(204,153,204)">let</span> chars = countChar(str);
     
      
     </div>
     
      
     <div style="height:20px">  
      
       
      <span style="color:rgb(204,153,204)">let</span> max = 
      
       
      <span style="color:rgb(153,204,153)">0</span>;
     
      
     </div>
     
      
     <div style="height:20px">  
      
       
      <span style="color:rgb(204,153,204)">let</span> char = 
      
       
      <span style="color:rgb(249,145,87)">null</span>;
     
      
     </div>
     
      
     <div style="height:20px">  
      
       
      <span style="color:rgb(204,153,204)">for</span>(
      
       
      <span style="color:rgb(204,153,204)">let</span> c 
      
       
      <span style="color:rgb(204,153,204)">in</span> chars){
     
      
     </div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">if</span>(chars[c] &gt; max){
     
      
     </div>
     
      
     <div style="height:20px">
      
       
            max = chars[c];
     
      
     </div>
     
      
     <div style="height:20px">
      
       
            char = c;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
          }
     
      
     </div>
     
      
     <div style="height:20px">
      
       
        }
     
      
     </div>
     
      
     <div style="height:20px">  
      
       
      <span style="color:rgb(204,153,204)">return</span> char;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      }
     
      
     </div></pre> </td> 
  </tr> 
 </tbody> 
</table>

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

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

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

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

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

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

这个比上面的四则运算就要稍难理解了，这里运用了位运算中的`异或`运算。  
对于异或运算的说明，还有不明白的可以回去翻翻大学的课本。  
第一行 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()方法找出最大值和最小值。

<table style="border-collapse:collapse; border-spacing:0px; margin:0px; width:auto; border:none; font-size:14px; table-layout:fixed"> 
 <tbody> 
  <tr style="background-color:rgb(249,249,249)"> 
   <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px 20px 1px 1px; color:rgb(102,102,102); background:rgb(45,45,45); line-height:1.6; border:none; text-align:right">
     
      
     <div style="height:20px">
      
       
      1
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      2
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      3
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      4
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      5
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      6
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      7
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      8
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      9
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      10
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      11
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      12
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      13
     
      
     </div></pre> </td> 
   <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px; color:rgb(204,204,204); background:rgb(45,45,45); line-height:1.6; border:none">
     
      
     <div style="height:20px">
      
       
      <span style="color:rgb(204,153,204)">let</span> getMaxProfit = 
      
       
      <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">function</span> <span style="color:rgb(102,204,204)">getMaxProfit</span>(<span style="color:rgb(249,145,87)">arr</span>) </span>{
     
      
     </div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">let</span> max_min = arr.reduce(
      
       
      <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">function</span>(<span style="color:rgb(249,145,87)">pre,current</span>)</span>{
     
      
     </div>
     
      
     <div style="height:20px">        
      
       
      <span style="color:rgb(204,153,204)">if</span>(pre.min &gt; current){
     
      
     </div>
     
      
     <div style="height:20px">
      
       
                  pre.min = current;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
              }
     
      
     </div>
     
      
     <div style="height:20px">        
      
       
      <span style="color:rgb(204,153,204)">if</span>(pre.max &lt; current){
     
      
     </div>
     
      
     <div style="height:20px">
      
       
                  pre.max = current;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
              }
     
      
     </div>
     
      
     <div style="height:20px">        
      
       
      <span style="color:rgb(204,153,204)">return</span> pre;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
          },{
      
       
      <span>min</span>:arr[
      
       
      <span style="color:rgb(153,204,153)">0</span>],
      
       
      <span>max</span>:arr[
      
       
      <span style="color:rgb(153,204,153)">0</span>]});
     
      
     </div>
     
      
     <div style="height:20px"></div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">return</span> max_min.max - max_min.min;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      }
     
      
     </div></pre> </td> 
  </tr> 
 </tbody> 
</table>

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

这里使用了apply方法直接调用max()和min()来获取最大值和最小值。  
我们都知道js中apply和call两个方法是功能相同的两个方法，只是传参方式不同。call方法传递参数列表，而apply传递参数对象或数组。  
在es6中新添加了一个`...`操作符，用于将数组展开成列表，具体可参见[MDN上的文档][MDN]。  
因此，我们这里可以使用该操作符，直接调用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指令，完成按位`|`和`^`运算。

<table style="border-collapse:collapse; border-spacing:0px; margin:0px; width:auto; border:none; font-size:14px; table-layout:fixed"> 
 <tbody> 
  <tr style="background-color:rgb(249,249,249)"> 
   <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px 20px 1px 1px; color:rgb(102,102,102); background:rgb(45,45,45); line-height:1.6; border:none; text-align:right">
     
      
     <div style="height:20px">
      
       
      1
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      2
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      3
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      4
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      5
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      6
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      7
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      8
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      9
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      10
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      11
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      12
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      13
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      14
     
      
     </div></pre> </td> 
   <td style="padding:0px; vertical-align:middle; border:none"> <pre style="overflow:auto; font-family:consolas,Menlo,&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,monospace; font-size:13px; margin-top:0px; margin-bottom:0px; padding:1px; color:rgb(204,204,204); background:rgb(45,45,45); line-height:1.6; border:none">
     
      
     <div style="height:20px">
      
       
      <span style="color:rgb(153,153,153)">//bis和bic声明</span>
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">int</span> <span style="color:rgb(102,204,204)">bis</span><span style="color:rgb(249,145,87)">(<span style="color:rgb(204,153,204)">int</span> x,<span style="color:rgb(204,153,204)">int</span> m)</span></span>;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">int</span> <span style="color:rgb(102,204,204)">bic</span><span style="color:rgb(249,145,87)">(<span style="color:rgb(204,153,204)">int</span> x,<span style="color:rgb(204,153,204)">int</span> m)</span></span>;
     
      
     </div>
     
      
     <div style="height:20px"></div>
     
      
     <div style="height:20px">
      
       
      <span style="color:rgb(153,153,153)">//完成如下 | 运算 和 ^ 运算</span>
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">int</span> <span style="color:rgb(102,204,204)">bool_or</span><span style="color:rgb(249,145,87)">(<span style="color:rgb(204,153,204)">int</span> x,<span style="color:rgb(204,153,204)">int</span> y)</span></span>{
     
      
     </div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">int</span> result = ______ ;
     
      
     </div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">return</span> result;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      }
     
      
     </div>
     
      
     <div style="height:20px"></div>
     
      
     <div style="height:20px">
      
       
      <span style="color:rgb(102,153,204)"><span style="color:rgb(204,153,204)">int</span> <span style="color:rgb(102,204,204)">bool_xor</span><span style="color:rgb(249,145,87)">(<span style="color:rgb(204,153,204)">int</span> x,<span style="color:rgb(204,153,204)">int</span> y)</span></span>{
     
      
     </div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">int</span> result = ______ ;
     
      
     </div>
     
      
     <div style="height:20px">    
      
       
      <span style="color:rgb(204,153,204)">return</span> result;
     
      
     </div>
     
      
     <div style="height:20px">
      
       
      }
     
      
     </div></pre> </td> 
  </tr> 
 </tbody> 
</table>

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

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

那 `^` 运算呢？  
我们都知道，异或运算运算法则为：`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进行按位与`&`运算么，就是：

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

## js实现二叉搜索树 ##

啥也不说了，直接看我github上的代码吧。  
[https://github.com/coolcao/dsa\_js/blob/master/src/BSTree.js][https_github.com_coolcao_dsa_js_blob_master_src_BSTree.js]

转载：http://coolcao.com/2016/11/07/%E5%89%8D%E7%AB%AF%E9%9D%A2%E8%AF%95%E4%B8%AD%E5%B8%B8%E8%A7%81%E7%9A%84%E7%AE%97%E6%B3%95%E9%97%AE%E9%A2%98%E8%AF%BB%E5%90%8E%E6%95%B4%E7%90%86/

个人建了前端学习群，旨在一起学习前端。纯净、纯粹技术讨论，非前端人员勿扰！入群加我[微信][Link 2]：iamaixiaoxiao。

![1460000008545203_w_276_h_261][]

[Link 1]: http://www.jackpu.com/qian-duan-mian-shi-zhong-de-chang-jian-de-suan-fa-wen-ti/
[MDN]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Spread_operator
[https_github.com_coolcao_dsa_js_blob_master_src_BSTree.js]: https://github.com/coolcao/dsa_js/blob/master/src/BSTree.js
[Link 2]: http://lib.csdn.net/base/wechat
[1460000008545203_w_276_h_261]: /images/20220708/39782c77e1c543a3b1ff359e01aa22e5.png