泰戈尔说：“生命以痛吻我，让我报之以歌”

前言

大家好，我是柒八九。从今天起，我们又重新开辟了一个新的领域：JS算法编程。为什么，会强调 JS 呢。其实，市面上不乏优秀的算法书和资料。但是，可能是出书的人大部分都是后端，所用语言都是偏向java,C++等传统的OOP语言。而这恰恰也是前端同学(没接触过此类语言的同学，鄙人不才，上述语言都会点)，通过此类书籍进行学习算法的一个障碍。因为，有些语法和使用方式和平时自己开发中所使用的JS语法，大相径庭。导致在学习过程中，遇到了不小的阻力。

同时，由于JS自身的一些特性，导致在实现一些在其他语言看似常规操作的问题上，需要绕很多路。所以，在看这些书籍和资料的时候，需要有一个转换过程。

最后，但同样重要的是，尽管，市面上存在一些JS算法书籍(如果想要，我有资源，你懂的)，但是这些书籍都是介绍一些常规，简单的算法题。能懂吗？能懂。但是，在面试的时候，这些算法题，却显得有点力不从心。毕竟，基本上国内大厂，都是从leetcode上搜罗题。(国外大厂，另说)所以，我打算，通过翻译(语法转换：你可以认为我是一个编译器)一些优秀的算法书，为大家呈现针对前端的算法分析。(丑话说在前面，可能由于本人能力有限，有些解法不是最优化，但是这些解法是可以 AC (Accepted)的(如果参加过ACM编程比赛的话，看到AC你就会很高兴))

时间不早了，干点正事哇。(郭德纲语言包)

奇怪的知识点：

1. JavaScript 语言的底层根本没有整数，所有数字都是小数

2. 通过new Array(n)构建的Array实例,里面包含的仅仅是n个空位(empty)

3. JS中查看一个正整数的二进制格式(number).toString(2)number前后有括号，这涉及都JS优先级了

4. 用i>>1来计算"i/2",而且还是下取整。比Math.floor(i/2)简洁还快

5. 用 i&1来计算 "i%2"

6. i&(i-1)将整数i的最右边的1变成0

文章概要

整数除法
二进制加法
前 n 个数字二进制中 1 的个数
只出现一次的数字

知识点简讲

整数

由于，我们是针对算法的文章，所以有些最基本的知识点，会默认大家已经了解。然后，有一些比较重要的点，也只是浅尝辄止。不会占用很大的篇幅进行对于知识点的介绍。

JavaScript 内部，所有数字都是以64位浮点数形式储存，即使整数也是如此。所以，1与1.0是相同的，是同一个数。

JavaScript 语言的底层根本没有整数，所有数字都是小数

在JavaScript中数字是以IEEE 754双精度64位浮点数来存储的，它的表示格式为：从最左边开始（最高位）

第1位：符号位，0表示正数，1表示负数

第2位到第12位（共11位）：指数部分

第13位到第64位（共52位）：小数部分（即有效数字）

符号位决定了一个数的正负
指数部分决定了数值的大小 (指数部分在0到2047之间)
小数部分决定了数值的精度

JavaScript 提供的有效数字最长为53个二进制位

(-1)^符号位 * 1.xx...xx * 2^指数部分
复制代码

位运算

二进制与运算符（&）的规则是逐位比较两个运算子，两个二进制位之中只要有一个位为0，就返回0，否则返回1
异或运算（^）在两个二进制位不同时返回1，相同时返回0

数组

在JS中，通过arr = new Array(n)构建的Array实例arr,里面包含的仅仅是n个空位(empty),所以如果想动态构建一个数组实例，并且后续可能还会有针对某项的数据操作。最好的处理方式为arr = new Array(n).fill(0)这样就避免一些非法数据之间的报错。

二进制

JS中查看一个正整数的二进制格式 (number).toString(2) 例如：(3).toString(2) ==> '11'

在JS中，

用i>>1来计算"i/2" 例如：4>>1 ===25>>1===2 该运算是下取整。
用 i&1来计算 "i%2" 例如： 4&1===0 5&1===1

1. 整数除法

题目描述：

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%'

提示：

1.当发生溢出时，返回最大的整数值。假设除数不能为0

2.只能存储 32 位有符号整数，其数值范围是 [−2³¹, 2³¹−1]

示例：输入： -15和2 输出： -7

分析：

从提示可知，此题中，值的范围是[−2³¹, 2³¹−1],所以，我们可以定义边界值 MIN = -Math.pow(2, 31)/ MAX = Math.pow(2, 31) - 1
当数据发生溢出的时候，返回最大的整数值那就是当 a==MIN,b=-1,return MAX
当被除数和除数中有一个为负数，其商为负数，sign =(a>0)^(b>0) 位运算的异或运算(^)：在两个二进制位不同时返回1，相同时返回0 ,这样有一个好处，就是其实我们不关心，到底是哪个为正哪个为负。
由于负数的相减，会变成两数相加，增加了解题的心智模式，所以利用Math.abs(x)将x变更成正整数
基于减法实现触发，只有当被除数大于除数的时候，我们将其相减，直到不满足条件，然后记录减的次数（count） ==> 而最后的次数，就是所求的商

代码实现

function divide(a, b) {
    const MAX = Math.pow(2, 31) - 1, //最大值
          MIN = -Math.pow(2, 31)    //最小值
    if (a == MIN && b == -1) return MAX;  // 处理边界情况
    const sign = (a > 0) ^ (b > 0); // 处理商的正负问题
    a = Math.abs(a), b = Math.abs(b) // 变成正整数之间的相减
    let count = 0
    while(a >= b) {
        a -= b
        count++
    }
    // sign为正，说明，除数和被除数之间 有一个为负数
    return sign ? -count : count; 
};
复制代码

2. 二进制加法

题目描述：

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为非空字符串且只包含数字 1 和 0

示例：输入 a = "11", b = "10" 输出: "101"

分析：

参考十进制加法来完成二进制加法。在进行十进制加法操作时候，总是将两个数的右端对齐，然后从它们的个位开始从右向左相加同一位置的两个数。如果前一位置有进位，还要加上进位。

从上面分析可知，有几个关键点

从右向左，而我们得到的是字符串，也就是每个串需要一个游标（指针）来记录当前处理位置 (i/j)
存在进位 (carry)
还有一点需要注意，就是给定的字符串可能不是等长的，也就是说，在处理完，它们各自共有长度后，长的那个子串就直接拼接到处理后的子串上
JS中获取字符串中位于index处字符的ASCII码 str.charAt(index)
产生进位的条件 （digitA + digitB + carry)>=2 carry是上一位的残留产物
最高位也需要考虑进位

代码实现

function addBinary(a, b) {
    let result = ''; // 用于存储结果
    let i = a.length - 1; // 指针i
    let j = b.length -1; // 指针j
    let carry = 0; //  用于存储进位
    while(i>=0 || j>=0){  //只有有数据，就进行数据操作
        // 指定位置的数字(二进制0/1) 
        // 判断位置，以免位置出错 i >=0
        let digitA = i >=0 ? a.charAt(i--) -'0':0;
         // 指定位置的数字(二进制0/1)
         // 判断位置，以免位置出错 j >=0
        let digitB = j >=0 ? b.charAt(j--) -'0':0;
        // 求和处理
        let sum = digitA + digitB + carry;
        // 处理进位
        carry = sum >=2 ? 1 :0;
        // sum可能超过最大当前进度的最大值，
      //例如： 十进制的 7+8 = 15 ==> 指定的个位存 5 (15-10)
        sum = sum >=2 ? sum - 2:sum;
        result = sum + result;
    }
    // 最高位可能会产生进位
    if(carry ==1){
        result = '1' + result;
    }
    return result
};
复制代码

思路扩展

在平时面试的时候，其实大家可能遇到过，针对大数相加的问题。

给定两个十进制字符串 a 和 b ，请计算它们的和，并以字符串的形式输出。

输入为非空字符串

输入：a = "999" b= "121" 输出："1120"

其实，具体的解题思路，和我们上面解决二进制的思路是类似的，无非就是两个指针(i/j)用于记录处理的位置，一个用于记录当前两个数据之和是否存在进位(carry)

代码实现

function bigSum(a,b){
  let i = a.length-1;
  let j = b.length-1;
  let marry =0;//对应位的进位结果
  let result='';//最后的结果,还是存入字符串
  while(i>=0||j>=0){
    let digitA = i >=0 ? a.charAt(i--) -'0':0;
    let digitB = j >=0 ? b.charAt(j--) -'0':0;
    let sum = digitA + digitB + carry;
    //核心步骤，marry是获取上一步中的进位的值，也参与本轮计算
    sum = digitA +digitB +marry;
    carry = sum >=10 ? 1 :0;
    sum = sum >=10 ? sum - 10:sum;
    //顺序不能颠倒
    result = sum+result;
  }
  // 处理高位
  if(marry){
    result = marry+result;
  }
  return result;
}
复制代码

然后，翻到前面处理二进制加法的代码，不能说是一模一样，但是大差不差，八九不离十。所以，我们把这两个问题，做一个整合。可以将这两个问题，归并为一类问题：N进制大数相加

Talk is cheap,show your the code

function Nsum(a,b,n){
    let result = '';
    let i = a.length - 1;
    let j = b.length -1;
    let carry = 0;
    while(i>=0 || j>=0){
        let digitA = i >=0 ? a.charAt(i--) -'0':0;
        let digitB = j >=0 ? b.charAt(j--) -'0':0;
        let sum = digitA + digitB + carry;
        carry = sum >=n ? 1 :0;
        sum = sum >=n ? sum - n:sum;
        result = sum + result;
    }
    if(carry ==1){
        result +=1;
    }
    return result;
}
复制代码

有了，前面几个代码的解释，这里就会很一目了然了。a/b是要处理的数字串，而n就是规定处理进制。(这里有一个缺陷，这个代码不兼容十六进制)

3. 前 n 个数字二进制中 1 的个数

题目描述：

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

输入: n = 2 输出: [0,1,1]

解释:

0 --> 0

1 --> 1

2 --> 10

分析

我们可以为题目做一个转化，只要我们能求出一个整数i的二进制形式中1的个数，这个问题就迎刃而解。因为，最后的要的数组，无非就是将某一范围内数据的二进制中1的个数做一个统计。

我们能从题目中挖掘的主要信息有：

正整数
0~n之间的数，也就是这些数字是连续的

i&(i-1)

利用i&(i-1)将整数i的最右边的1变成0

整数i减去1,那么它最右边的1变成了0。例如：二进制1100,它减少1的结果是1011。而1100 & 1011 = 1000 。

所以我们可以利用这个特性，对0~n所有的数进行i&(i-1)处理。也就是需要两层循环，第一层循环是遍历整体数据，第二层循环是针对特定数据i。

码上见分晓

function countBits(n){
   // 构建一个长度为n+1 (0~n)，每项都是0的数组
   let result = new Array(n+1).fill(0);
   // 外层循环：处理整体数据
   for(let i=0;i<=n;i++){
        let j =i;
        // 内层循环：对特定数据进行j&(j-1)处理，直到 j里面不含有1，也就是为0
        while(j!=0){
            result[i]++;
            j = j & (j-1)
        }
    }
  return result;
}
复制代码

优化处理

整数i的二进制形式中1的个数比i&(i-1)的二进制形式中1的个数多1。并且,原来的代码中我们是从i=0开始整体遍历的，然后，根据常识可知，i=0中1的个数为0。根据这些条件，我们可以对上述代码，做一个优化处理，也就是合理利用已经计算出的结果。

function countBits(n){
   // 构建一个长度为n+1 (0~n)，每项都是0的数组
   let result = new Array(n+1).fill(0);
   // 从i=1开始遍历
   for(let i=1;i<=n;i++){
       result[i] = result[i&(i-1)]+1
    }
  return result;
}
复制代码

这样，少了一层遍历，然后对应的时间复杂度也减少了。

i/2

如果正整数i是一个偶数，那么i相当于将i/2左移一位的结果，因此偶数i和i/2的二进制形式中1的个数是相同的。

如果i是奇数，那么i相当于将i/2左移一位之后再将最右边的一位设为1的结果。因此，奇数i的二进制形式中1的个数比i/2的1的个数多1.

例如：整数3的二进制形式是11,有2个1。偶数6的二进制是110,有2个1。奇数7的二进制是111，有三个1。

function countBits(n){
   // 构建一个长度为n+1 (0~n)，每项都是0的数组
   let result = new Array(n+1).fill(0);
   // 从i=1开始遍历
   for(let i=1;i<=n;i++){
       result[i] = result[i>>1]+(i&1)
    }
  return result;
}
复制代码

result[i>>1]+(i&1)这里兼容了两种情况

如果i为偶数，那i&1就是0，那么result[i] == result[i>>1] +0
如果i为奇数，那i&1就是1，那么result[i] == result[i>>1] +1

这样能够合理利用已经被计算的结果。

4. 只出现一次的数字

题目描述：

一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现三次。找出并返回那个只出现了一次的元素。

提示：-2³¹ <= nums[i] <= 2³¹ - 1

输入：nums = [2,2,3,2] 输出：3

分析

从提示，我们可以得知，整数是由32个0和1组成的。我们可以将数组中的所有数字的同一位置相加。

将出现3次的数字单独拿出来，那么出现3次的数字的任意第i个数位之和都能被3整除，那么只出现一次的数字的第i个数位一定是0
如果数组中所有数字的第i个数位相加之和被3除余1,那么只出现一次的数字的第i个数位一定是1
在"前 n 个数字二进制中 1 的个数"中我们介绍了，i>>1通过右移动一位的方式，来快速获取 i/2,其实在位运算中，还可以i>>n。也就是将当前位的数右移N位。
因为，我们要求数组中所有数字指定位置(i)的二进制位。所以，(num>>(31-i))&1就是某个数字在i的位数。
num<<1 将当前num向右扩大一倍,从二进制角度看，就是将最右边位置补0
例子: 2的二进制位102<<1 == 4(二进制位100) 可以通过(4).toSting(2)进行验证

码上见分晓

function singleNumber(nums) {
    // 构建一个用于存储数组所有数字位数之和的数组
    let bitSums = new Array(32).fill(0);
    for(let num of nums){
        for(let i=0;i<32;i++){
         // 求num在i位置的位数，并将其与指定位置的位数相加
         bitSums[i] +=(num>>(31-i)) &1;
        }
    }
    let result =0;
    for(let i=0;i<32;i++){
        //从最地位(0)位开始遍历
        result = (result<<1) + bitSums[i]%3;
    }
    return result;
};
复制代码

代码中(result<<1) + bitSums[i]%3其实也承载了两种含义

如果bitSums[i]%3 ==0,也就是能被3整除，只出现一次的数字在该位置(i)没出现过
如果bitSums[i]%3 ==1,也就是能被3除余1，只出现一次的数字在该位置(i)出现过

触类旁通

只出现一次之外其他数字都出现两次

题目描述：

一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

输入: [2,2,1]输出: 1

我们将上面的代码，做一个简单的修改。

function singleNumber(nums) {
    // 构建一个用于存储数组所有数字位数之和的数组
    let bitSums = new Array(32).fill(0);
    for(let num of nums){
        for(let i=0;i<32;i++){
         // 求num在i位置的位数，并将其与指定位置的位数相加
         bitSums[i] +=(num>>(31-i)) &1;
        }
    }
    let result =0;
    for(let i=0;i<32;i++){
        //从最地位(0)位开始遍历
        result = (result<<1) + bitSums[i]%2;
    }
    return result;
};
复制代码

通过对比发现，其实我们就更改了一处地方将(result<<1) + bitSums[i]%3更换为了(result<<1) + bitSums[i]%2仅此而已。

其实，针对该题还有一个更简单的处理方式。是利用了位运算中异或运算（^）:两个二进制位不同时返回1，相同时返回0

function singleNumber(nums) {
  let result = 0;
  for(let i of nums){
      result ^= i;
  }
  return result
};
复制代码

result^=i 如果在位置i上存在两个相同的数字，通过异或处理，直接清零。类似于消消乐,他们两个互相抵消了。那么剩下的就是那个只出现一次的数字的位数了。

后记

分享是一种态度，这篇文章，主要的篇幅来自于《剑指Offer》，算是一个自我学习过程中的一种记录和总结。主要是把自己认为重要的点，都罗列出来。同时，也是为大家节省一下排雷和踩坑的时间。当然，可能由于自己认知能力所限，有些点，没能表达很好。如果大家想看原文，“墙裂推荐”看原文。

参考资料：

《剑指Offer》
JavaScript 标准参考教程
LeetCode官网

JS算法探险之整数

前言

文章概要

知识点简讲

整数

位运算

数组

二进制

1. 整数除法

分析：

代码实现

2. 二进制加法

分析：

代码实现

思路扩展

代码实现

Talk is cheap,show your the code

3. 前 n 个数字二进制中 1 的个数

分析

i&(i-1)

码上见分晓

优化处理

i/2

4. 只出现一次的数字

分析

码上见分晓

触类旁通

只出现一次之外其他数字都出现两次

后记

热门文章

最新文章

相关课程

相关电子书

相关实验场景

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

JS算法探险之整数

前言

文章概要

知识点简讲

整数

位运算

数组

二进制

1. 整数除法

分析：

代码实现

2. 二进制加法

分析：

代码实现

思路扩展

代码实现

Talk is cheap,show your the code

3. 前 n 个数字二进制中 1 的个数

分析

i&(i-1)

码上见分晓

优化处理

i/2

4. 只出现一次的数字

分析

码上见分晓

触类旁通

只出现一次之外其他数字都出现两次

后记

热门文章

最新文章

相关课程

相关电子书

相关实验场景