泰戈尔说：“生命以痛吻我，让我报之以歌”
前言
大家好，我是柒八九。从今天起，我们又重新开辟了一个新的领域：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===05&1===1
1. 整数除法
题目描述：
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%'
提示：
1.当发生溢出时，返回最大的整数值。假设除数不能为0
2.只能存储 32 位有符号整数，其数值范围是
[−231, 231−1]
示例：输入： -15和2 输出： -7
分析：
- 从提示可知，此题中，值的范围是
[−231, 231−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)>=2carry是上一位的残留产物 - 最高位也需要考虑进位
代码实现
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 ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。找出并返回那个只出现了一次的元素。
提示：
-231 <= nums[i] <= 231 - 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官网
