兴许你我素未谋面,但很可能相见恨晚,我是前端胖头鱼
前言
金三银四大潮如期到来,在这个裁员
、降薪
、开张
无处不在的凛冽节令里,咱们都没有太多抉择的余地。唯有努力提高本身能力,能力在寒风凛冽中站住脚跟,抵挡随时到来的危险。
最近有个敌人在面字节时遇到了一道有意思的题,依照他的话说,差点就因为这个题寄了,不过好在他在最初几分钟,充分调动体内的洪荒之力,解出了答案,朝字节又迈进了一步。
要不要一起来做做这道题!!!
1.# 62进制的大数相加
// 实现两个62进制数的大数加法// 输出:两个 62 进制数,String 类型,仅思考整数// 输入:两数之和,String 类型// 62 进制数:依照 1-9,a-z,A-Z 递增function sum (a, b) {}
不晓得你们看到这道题时是什么感触!!!
我过后的想法是:“如同只听过2进制、8进制、16进制、32进制,62进制是什么鬼? ”
终于在看到这段信息后豁然开朗:62 进制数:依照 1-9,a-z,A-Z 递增,
我掰着手加脚指头
数了数...
- 0 ~ 9 是10个数
- a ~ z 是26个字母
- A ~ Z 是26个字母
加起来就是62个数,刚好凑齐62进制。
1.1 10进制大数相加(整数)
忽然看到求62进制的两数之和,我心田多少是有点懵逼的,懵逼的点在哪?
就是字母咋相加啊?比方 1a(10进制的72)
+ 2 = 1c(10进制的74)
不过作为承受过9年义务教育的社会主义接班人
,一年级咱们就学会了加法(也就是所谓的10进制加法)
。
回顾一下小学常识: 19 + 23?
1. 个位数相加:9 + 3 = 12。写下 2,进位 1。 19+ 23----- 2 2. 十位数相加并加上进位:1 + 2 + 1(进位)= 4。 19+ 23----- 42
非常简单是不是?咱们尝试一下用程序来计算两个10进制数的加法。
别放心,敌人,这段代码尽管看起来长了点,但它齐全模仿的小学加法,很容易看懂。
敲黑板:10进制的大数相加也是面试的热点
const addBigNumbers = (a, b) => { // 从尾部往前计算 let i = a.length - 1 let j = b.length - 1 // 进位标记,1或者0 let carry = 0 let result = '' while (i >= 0 || j >= 0 || carry) { const n1 = +(a[ i ] || 0) const n2 = +(b[ j ] || 0) // 以后位相加(蕴含进位局部) let sum = n1 + n2 + carry // 以后位相加如果>=10,阐明要往后退1,否则要重置进位标记 if (sum >= 10) { sum -= 10 carry = 1 } else { carry = 0 } // 递加往前算 i-- j-- // 以后位 + 后面低位的后果 result = sum + '' + result } return result}console.log(addBigNumbers('19', '23')) // 42console.log(addBigNumbers('100', '1024')) // 1124
1.2# 62进制与10进制之间如何转换?
其实咱们晓得如何实现10进制大数相加
之后,62进制的大数相加
也就实现了一大半,只有解决这2个问题,面试官就该给你过了。
- 62进制转化为10进制
- 10进制转化为62进制
想想只有能将62进制转化为10进制进行相加,再把后果转化为62进制,问题不就迎刃而解了吗?
1a (10进制的72) + 2 = 1c (10进制的74)
1.3# 62进制转化为10进制
让咱们一起来回顾一下计算机基础知识:62进制转化为10进制的规定
设 62 进制数为 d[n]d[n-1]...d[1]d[0],其中 d[i] 示意第 i 位的数字(从右向左,最低位为0)。
则该数的十进制值为:
d[0] * 62^0 + d[1] * 62^1 + ... + d[n] * 62^n
举个例子
1a = 1 * 62^1 + 10 * 62^0 // 62进制中的a代表10进制中的10,b代表的是11以此类推 = 1 * 62 + 10 * 1 = 62 + 10 = 72
有了这个法则用代码实现就很不便了.
const base62ToDecimal = (str) => { const base = 62 const digits = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ' let len = str.length let sum = 0 let n =0 // 最初一位是0,倒数第二位是1... while (len--) { let digit = digits.indexOf(str[ len ]) // 获取以后位的10进制数,例如a示意10进制的10,b示意11,c示意12... sum += digit * Math.pow(base, n) n++ } return sum}// 示例console.log(base62ToDecimal('1a')) // 72console.log(base62ToDecimal('1c')) // 74
1.4# 10进制转化为62进制
同样 10进制转化为62进制也有法则可言:
- 用输出的十进制数除以 62,失去商和余数。
- 将余数对应的 62 进制字符放在后果的最低位。
- 将商作为新的输出,反复步骤 1 和 2,直到商为 0。
- 将失去的所有余数依照逆序排列,就是最终的 62 进制示意。
举个例子: 将10进制的72转化为64进制是啥?
第一步,将 72 一直除以 62,失去的余数就是 62 进制数的低位数字。顺次计算如下:1. 72 ÷ 62 = 1 ... 10 (余数为 10,10对应的62进制字符为 'a')2. 1 ÷ 62 = 0 ... 1 (余数为 1,1对应的62进制字符为 '1')第二步,将每次失去的余数依照逆序排列,就是最终的62进制示意:72(10进制)= '1a'(62进制)
依据法则聪慧的你也能很快用程序来实现10进制到62进制的转换
const decimalToBase62 = (decimal) => { const base = 62 const digits = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ' let result = [] while (decimal > 0) { const remainder = decimal % base // 取余 result.push(digits[ remainder ]) // 将余数真正对应62进制字符存入数组 decimal = Math.floor(decimal / base) // 计算商,用于下次计算 } return result.reverse().join('') || '0' // 反转后果}console.log(decimalToBase62('72')) // 1aconsole.log(decimalToBase62('74')) // 1c
1.5 解题啦!!!
啰嗦了这么多,大家有没有发现解决62进制大数相加所需的知识点切实是太根底了
- 会小学加法
- 会进制转换
最初请丢出这份代码,亮瞎面试官的眼吧!!!
// 62进制转10进制const base62ToDecimal = (str) => { const base = 62 const digits = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ' let len = str.length let sum = 0 let n =0 // 最初一位是0,倒数第二位是1... while (len--) { let digit = digits.indexOf(str[ len ]) // 获取以后位的10进制数,例如a示意10进制的10,b示意11,c示意12... sum += digit * Math.pow(base, n) n++ } return sum}// 10进制转62进制const decimalToBase62 = (decimal) => { const base = 62 const digits = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ' let result = [] while (decimal > 0) { const remainder = decimal % base // 取余 result.push(digits[ remainder ]) // 将余数真正对应62进制字符存入数组 decimal = Math.floor(decimal / base) // 计算商,用于下次计算 } return result.reverse().join('') || '0' // 反转后果}const addBigBase62Numbers = (a, b) => { // 转化为10进制的字符串 a = '' + base62ToDecimal(a) b = '' + base62ToDecimal(b) // 从尾部往前计算 let i = a.length - 1 let j = b.length - 1 // 进位标记,1或者0 let carry = 0 let result = '' while (i >= 0 || j >= 0 || carry) { const n1 = +(a[ i ] || 0) const n2 = +(b[ j ] || 0) // 以后位相加(蕴含进位局部) let sum = n1 + n2 + carry // 以后位相加如果>=10,阐明要往后退1,否则要重置进位标记 if (sum >= 10) { sum -= 10 carry = 1 } else { carry = 0 } // 递加往前算 i-- j-- // 以后位 + 后面的 result = sum + '' + result } return decimalToBase62(result) // 将10进制再转化为62进制}console.log(addBigBase62Numbers('1a', '2')) // 1cconsole.log(addBigBase62Numbers('Z', '1')) // 10
2.# 另一种解法
咱们废了老大劲,写了一大坨的代码才实现这个性能,有没有其余更简便一点的解法呢?
其实62进制的数学性质和10进制相似,只是基数(62)不同而已,在10进制中是逢十进一
,62进制中就是逢62进一
了。所以在咱们晓得10进制的大数相加如何解之后,仅仅须要做大量的批改就能够变成62进制的大数相加。
搞起!!!
const addBigBase62Numbers = (a, b) => { const digits = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ' let i = a.length - 1 let j = b.length - 1 let carry = 0 let result = '' while (i >= 0 || j >= 0 || carry) { const n1 = digits.indexOf(a[i] || 0) // 获取以后位的10进制示意,如a示意10,b示意11 const n2 = digits.indexOf(b[j] || 0) // 获取以后位的10进制示意,如a示意10,b示意11 let sum = n1 + n2 + carry // 62进1 if (sum >= 62) { sum -= 62 carry = 1 } else { carry = 0 } // digits[sum] 将以后位转换回62进制 result = digits[sum] + result i-- j-- } return result}console.log(addBigBase62Numbers('1a', '2')) // 1cconsole.log(addBigBase62Numbers('Z', '1')) // 10
好舒畅、代码一下子少了一大坨,又能够和面试官吹牛逼了...
3.# 触类旁通
文中咱们只解决了整数的62进制大数相加,聪慧你能够尝试一下这几种场景
- 带小数的62进制大数相加?
- n进制的大数相加?
原理都是相似的,期待你在评论区写下你的答案,一起交换。