JS算法探险之整数
前言
大家好,我是柒八九
。从今天起,我们又重新开辟了一个新的领域: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 ===2
5>>1===2
该运算是下取整。 - 用
i&1
来计算 "i%2" 例如:4&1===0
5&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)>=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 ,除某个元素仅出现 一次 外,其余每个元素都恰出现 「三次」 。找出并返回那个只出现了一次的元素。 提示:
-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的二进制位10
2<<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官网
相关文章
- 【NLP基础】英文关键词抽取RAKE算法
- js原型对象
- 不用React Vue,只用原生JS,如何开发单页面应用?
- js android 换行符,关于js对textarea换行符的处理方法浅析
- JS算法题 JavaScript常见算法题 基础语法案例(持续更新)2022年3月30日
- 前端常见算法(js)「建议收藏」
- html如何只刷新页面指定,js控制页面刷新 JS刷新当前页面的几种方法总结
- js用户注册表单验证_onclick调用js函数
- lodash判断对象数组是否相等_js删除数组中指定元素并返回剩下的
- js 洗牌算法_数据库洗牌算法
- js实现的A星算法[通俗易懂]
- JS算法之动态规划
- 【JS 逆向百例】猿人学系列 web 比赛第五题:js 混淆 - 乱码增强,详细剖析
- JS动态引入js、CSS动态创建script/link/style标签详解编程语言
- Discovering the Power of Node.js on Linux: An Introduction(nodejslinux)
- JS技术连接Oracle数据库实现数据交互(js连接oracle实例)
- js本身的局限性别让javascript做太多事
- CSS和JS标签style属性对照表(方便js开发的朋友)
- 封装了一个js图片轮换效果的函数
- 远离JS灾难css灾难之js私有函数和css选择器作为容器
- JS添加网页桌面快捷方式的代码详细整理
- js编码、解码函数介绍及其使用示例
- js控制淡入淡出示例代码
- 消除js以及jsp文件中的警告方法
- node.js中的fs.truncateSync方法使用说明