js实用算法

浅浅的花香味﹌ 2021-09-15 05:38 221阅读 0赞

# 判断文本是否为回文 #

定义：如果将一个文本翻转过来，能和原文本完全相等，那么就可以称之为“回文”。

## 方法一（字符串、数组内置方法） ##

// PS：方法简单，但效率不高，会产生一个新的变量

## 方法二（循环） ##

PS：网上还有其他解法，大多为以上两种的变形。

# 反转字符串 #

## 方法一（字符串、数组内置方法）） ##

借用反转字符串的方法

## 方法二（循环） ##

循环系列

<table style="border-spacing:0px;margin:0px;width:auto;border:none;font-size:14px;"> 
 <tbody> 
  <tr style="background-color:rgb(249,249,249);"> 
   <td style="padding:0px;vertical-align:middle;border-style:none;"><pre style="font-family:consolas, Menlo, 'PingFang SC', 'Microsoft YaHei', monospace;font-size:14px;margin-bottom:0px;padding:10px;color:rgb(134,145,148);background:rgb(239,242,243);line-height:1.6;border:none;text-align:right;"></pre> 
    <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> 
    <div style="height:20px;">
      15 
    </div> 
    <div style="height:20px;">
      16 
    </div> 
    <div style="height:20px;">
      17 
    </div> 
    <div style="height:20px;">
      18 
    </div> 
    <div style="height:20px;">
      19 
    </div> 
    <div style="height:20px;">
      20 
    </div> 
    <div style="height:20px;">
      21 
    </div> 
    <div style="height:20px;">
      22 
    </div> 
    <div style="height:20px;">
      23 
    </div> 
    <div style="height:20px;">
      24 
    </div> 
    <div style="height:20px;">
      25 
    </div> 
    <div style="height:20px;">
      26 
    </div> 
    <div style="height:20px;">
      27 
    </div> 
    <div style="height:20px;">
      28 
    </div> 
    <div style="height:20px;">
      29 
    </div> 
    <div style="height:20px;">
      30 
    </div> 
    <div style="height:20px;">
      31 
    </div> 
    <div style="height:20px;">
      32 
    </div> 
    <div style="height:20px;">
      33 
    </div> 
    <div style="height:20px;">
      34 
    </div> 
    <div style="height:20px;">
      35 
    </div></td> 
   <td style="padding:0px;vertical-align:middle;border-style:none;"><pre style="font-family:consolas, Menlo, 'PingFang SC', 'Microsoft YaHei', monospace;font-size:14px;margin-bottom:0px;padding:10px;color:rgb(77,77,76);background:rgb(247,247,247);line-height:1.6;border:none;width:382px;"></pre> 
    <div style="height:20px;">
      /* 
    </div> 
    <div style="height:20px;">
      * 反转字符串 
    </div> 
    <div style="height:20px;">
      * @param {string} val 需要反转的字符串 
    </div> 
    <div style="height:20px;">
      * @return {string} str 反转后的字符串 
    </div> 
    <div style="height:20px;">
      */ 
    </div> 
    <div style="height:20px;">
      function reverseVal2(val){ 
    </div> 
    <div style="height:20px;">
      if (typeof val !== 'string') return; 
    </div> 
    <div style="height:20px;"> 
    </div> 
    <div style="height:20px;">
      let str = '', 
    </div> 
    <div style="height:20px;">
      i = 0, 
    </div> 
    <div style="height:20px;">
      len = val.length; 
    </div> 
    <div style="height:20px;">
      while(i &lt; len){ 
    </div> 
    <div style="height:20px;">
      str += val.charAt(len - 1 - i); 
    </div> 
    <div style="height:20px;">
      i++; 
    </div> 
    <div style="height:20px;">
      } 
    </div> 
    <div style="height:20px;"> 
    </div> 
    <div style="height:20px;">
      return str; 
    </div> 
    <div style="height:20px;">
      } 
    </div> 
    <div style="height:20px;"></div> 
    <div style="height:20px;">
      /* 
    </div> 
    <div style="height:20px;">
      * 反转字符串 
    </div> 
    <div style="height:20px;">
      * @param {string} val 需要反转的字符串 
    </div> 
    <div style="height:20px;">
      * @return {string} str 反转后的字符串 
    </div> 
    <div style="height:20px;">
      */ 
    </div> 
    <div style="height:20px;">
      function reverseVal3(val){ 
    </div> 
    <div style="height:20px;">
      if (typeof val !== 'string') return; 
    </div> 
    <div style="height:20px;"> 
    </div> 
    <div style="height:20px;">
      let str = '', 
    </div> 
    <div style="height:20px;">
      len = val.length; 
    </div> 
    <div style="height:20px;">
      for(let i = len - 1; i &gt;= 0; i--){ 
    </div> 
    <div style="height:20px;">
      str += val.charAt(i) 
    </div> 
    <div style="height:20px;">
      } 
    </div> 
    <div style="height:20px;"> 
    </div> 
    <div style="height:20px;">
      return str; 
    </div> 
    <div style="height:20px;">
      } 
    </div></td> 
  </tr> 
 </tbody> 
</table>

测试：reverseVal(‘abc’) // ‘cba’

# 阶乘 #

## 方法一（递归） ##

PS：上面代码是一个阶乘函数，计算n的阶乘，最多需要保存n个调用记录，复杂度 O(n) 。  
递归非常耗费内存，因为需要同时保存成千上百个调用帧，很容易发生“栈溢出”错误（stack overflow）。

## 方法二（ES6尾调用优化） ##

（递归优化版）

PS：[ES6尾调用优化][ES6]但对于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误。  
尾调用（Tail Call）是函数式编程的一个重要概念，本身非常简单，一句话就能说清楚，就是指某个函数的最后一步是调用另一个函数。

## 方法三（循环） ##

测试：factorialize1(3) // 6

# 随机生成长度为n字符串 #

## 方法一 ##

PS：Math.round(Math.random() *(str.length - 1))  
Math.ceil(Math.random() *(str.length - 1))  
Math.floor(Math.random() \* str.length)  
这三种方式等价，都能生成\[0, str.length-1\]随机数

## 方法二（进制转化） ##

PS：该方法原理为随机产生的数转换为指定进制字符串  
toString(n)，n为\[2,36\]，n<=10时只产生0-9也就是10进制数字  
该方法有个缺点，产生字符串的长度有一定的限制。

## 方法三（随机码点） ##

PS：可以参考对于的[ASCII码表][ASCII]。  
测试：randomString1(3) // ‘1sd’

# 数组去重 #

## 方法一（ES6的Set数据结构） ##

## 方法二（对象的key唯一性） ##

PS：该方法存在一定问题，数组的元素全部被转化为字符串，因为ES6之前对象的key只能是字符串。  
会把数字1和字符串’1’，会被视为同一个值。

## 方法三（临时数组判断插入） ##

## 方法四（判断首次出现的位置） ##

如果当前数组的第i项在当前数组中第一次出现的位置不是i，那么表示第i项是重复的，忽略掉。否则存入结果数组。

## 方法五（排序后逐个比较插入） ##

给传入数组排序，排序后相同值相邻，然后遍历时新数组只加入不与前一值重复的值。

PS：返回的数组顺序发生了改变。

## 方法六（） ##

获取没有重复的最右一值放入新数组（检测到有重复值时终止当前循环同时进入顶层循环的下一轮判断）。

测试：unique1(\[1, 2, 3, 2\]) // \[1, 2, 3\]

# 出现次数最多的字符 #

## 方法一（对象key的唯一性进行累加） ##

<table style="border-spacing:0px;margin:0px;width:auto;border:none;font-size:14px;"> 
 <tbody> 
  <tr style="background-color:rgb(249,249,249);"> 
   <td style="padding:0px;vertical-align:middle;border-style:none;"><pre style="font-family:consolas, Menlo, 'PingFang SC', 'Microsoft YaHei', monospace;font-size:14px;margin-bottom:0px;padding:10px;color:rgb(134,145,148);background:rgb(239,242,243);line-height:1.6;border:none;text-align:right;"></pre> 
    <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> 
    <div style="height:20px;">
      15 
    </div> 
    <div style="height:20px;">
      16 
    </div> 
    <div style="height:20px;">
      17 
    </div> 
    <div style="height:20px;">
      18 
    </div> 
    <div style="height:20px;">
      19 
    </div> 
    <div style="height:20px;">
      20 
    </div> 
    <div style="height:20px;">
      21 
    </div> 
    <div style="height:20px;">
      22 
    </div> 
    <div style="height:20px;">
      23 
    </div> 
    <div style="height:20px;">
      24 
    </div></td> 
   <td style="padding:0px;vertical-align:middle;border-style:none;"><pre style="font-family:consolas, Menlo, 'PingFang SC', 'Microsoft YaHei', monospace;font-size:14px;margin-bottom:0px;padding:10px;color:rgb(77,77,76);background:rgb(247,247,247);line-height:1.6;border:none;width:601px;"></pre> 
    <div style="height:20px;">
      function maxNum1(str){ 
    </div> 
    <div style="height:20px;">
      if(typeof(str) !== 'string') str = str.toString(); 
    </div> 
    <div style="height:20px;">
      let obj = {}, 
    </div> 
    <div style="height:20px;">
      maxChar = []; // 使用数组保存出现最多次的某些字符 
    </div> 
    <div style="height:20px;">
      str.split('').forEach( (val) =&gt; { 
    </div> 
    <div style="height:20px;">
      if(!obj[val]){ 
    </div> 
    <div style="height:20px;">
      let demo = obj[val] = 1; 
    </div> 
    <div style="height:20px;"></div> 
    <div style="height:20px;">
      }else{ 
    </div> 
    <div style="height:20px;">
      obj[val]++; 
    </div> 
    <div style="height:20px;">
      } 
    </div> 
    <div style="height:20px;">
      }) 
    </div> 
    <div style="height:20px;"></div> 
    <div style="height:20px;">
      let maxCount = Math.max.apply(null, Object.values(obj)) 
    </div> 
    <div style="height:20px;"></div> 
    <div style="height:20px;">
      // forEach方法总是返回 undefined 且 没有办法中止或者跳出 forEach 循环。 
    </div> 
    <div style="height:20px;">
      Object.entries(obj).forEach( item =&gt; { 
    </div> 
    <div style="height:20px;">
      if(item[1] == maxCount){ 
    </div> 
    <div style="height:20px;">
      maxChar.push(item[0]) 
    </div> 
    <div style="height:20px;">
      } 
    </div> 
    <div style="height:20px;">
      }) 
    </div> 
    <div style="height:20px;"></div> 
    <div style="height:20px;">
      return maxChar; 
    </div> 
    <div style="height:20px;">
      } 
    </div></td> 
  </tr> 
 </tbody> 
</table>

测试：maxNum1(‘11223333’) // ‘3’

# 数组扁平化 #

实现方法：Array.prototype.flatten(depth)，参数depth表示需要扁平化的层数，返回一个新的数组。

## 方法一（递归遍历数组拼接） ##

PS：可以处理多层数组。

## 方法二（reduce结合concat） ##

PS：可以处理多层数组。

## 方法三（转化为字符串） ##

PS：返回的数组项将为字符串。

## 方法四（解构数组） ##

PS：只能处理2维数组。  
测试：getMaxProfit1(\[1, 2, 3, \[4, 5, 6\]\]) // \[1, 2, 3, 4, 5, 6\]

# 数组中最大差值 #

## 方法一 ##

测试：getMaxProfit1(\[1, 2, 3, 4\]) // 3

# 斐波那契数列 #

这里我们只实现通项公式

## 方法一 ##

PS：时间复杂度为O(2^n)，空间复杂度为O(n)

## 方法二 ##

PS：时间复杂度为O(n)，空间复杂度为O(n)

## 方法三 ##

PS：时间复杂度为O(n)，空间复杂度为O(1)  
测试：fib2(3) // 2

# 判断是否为质数（prime number）素数 #

质数：只能被1和自己整除且大于1的数。  
合数：数大于1且因数多余2个（大于1的数质数的补集）。

测试：isPrimeNumber1(2) // true

# 最小公约数 #

<table style="border-spacing:0px;margin:0px;width:auto;border:none;font-size:14px;"> 
 <tbody> 
  <tr style="background-color:rgb(249,249,249);"> 
   <td style="padding:0px;vertical-align:middle;border-style:none;"><pre style="font-family:consolas, Menlo, 'PingFang SC', 'Microsoft YaHei', monospace;font-size:14px;margin-bottom:0px;padding:10px;color:rgb(134,145,148);background:rgb(239,242,243);line-height:1.6;border:none;text-align:right;"></pre> 
    <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> 
    <div style="height:20px;">
      15 
    </div> 
    <div style="height:20px;">
      16 
    </div> 
    <div style="height:20px;">
      17 
    </div> 
    <div style="height:20px;">
      18 
    </div> 
    <div style="height:20px;">
      19 
    </div> 
    <div style="height:20px;">
      20 
    </div> 
    <div style="height:20px;">
      21 
    </div> 
    <div style="height:20px;">
      22 
    </div> 
    <div style="height:20px;">
      23 
    </div> 
    <div style="height:20px;">
      24 
    </div> 
    <div style="height:20px;">
      25 
    </div> 
    <div style="height:20px;">
      26 
    </div> 
    <div style="height:20px;">
      27 
    </div> 
    <div style="height:20px;">
      28 
    </div></td> 
   <td style="padding:0px;vertical-align:middle;border-style:none;"><pre style="font-family:consolas, Menlo, 'PingFang SC', 'Microsoft YaHei', monospace;font-size:14px;margin-bottom:0px;padding:10px;color:rgb(77,77,76);background:rgb(247,247,247);line-height:1.6;border:none;width:494px;"></pre> 
    <div style="height:20px;">
      function greatestCommonDivisor1(a, b){ 
    </div> 
    <div style="height:20px;">
      if(a &lt; 0 || b &lt; 0) throw new Error('参数只能为正整数'); 
    </div> 
    <div style="height:20px;">
      if(a &lt; 2 || b &lt; 2) return 1; 
    </div> 
    <div style="height:20px;">
      let min = a, 
    </div> 
    <div style="height:20px;">
      max = b, 
    </div> 
    <div style="height:20px;">
      arymin = []; 
    </div> 
    <div style="height:20px;"></div> 
    <div style="height:20px;">
      if(a &gt; b) { 
    </div> 
    <div style="height:20px;">
      min = b; 
    </div> 
    <div style="height:20px;">
      max = a; 
    </div> 
    <div style="height:20px;">
      } 
    </div> 
    <div style="height:20px;"></div> 
    <div style="height:20px;">
      for(let i = 1; i &lt;= min; i++){ 
    </div> 
    <div style="height:20px;">
      if(min % i === 0){ 
    </div> 
    <div style="height:20px;">
      arymin.push(i); 
    </div> 
    <div style="height:20px;">
      console.log(1) 
    </div> 
    <div style="height:20px;">
      } 
    </div> 
    <div style="height:20px;">
      } 
    </div> 
    <div style="height:20px;"></div> 
    <div style="height:20px;">
      arymin.reverse(); 
    </div> 
    <div style="height:20px;"></div> 
    <div style="height:20px;">
      for(let j = 0, len = arymin.length; j &lt; len; j++){ 
    </div> 
    <div style="height:20px;">
      if(max % arymin[j] === 0){ 
    </div> 
    <div style="height:20px;">
      return arymin[j]; 
    </div> 
    <div style="height:20px;">
      } 
    </div> 
    <div style="height:20px;">
      } 
    </div> 
    <div style="height:20px;"></div> 
    <div style="height:20px;">
      } 
    </div></td> 
  </tr> 
 </tbody> 
</table>

测试：greatestCommonDivisor1(5, 10) // 5

# 金额转大写 #

测试：money2Chinese(1234) // 壹仟贰佰叁拾肆元整

[ES6]: http://es6.ruanyifeng.com/#docs/function%23%E5%B0%BE%E8%B0%83%E7%94%A8%E4%BC%98%E5%8C%96
[ASCII]: https://baike.baidu.com/item/ASCII/309296?fr=aladdin