昨晚一位朋友去面試某一知名互聯(lián)網(wǎng)公司立由，對(duì)方出了一道題后裸，問(wèn)如何實(shí)現(xiàn)32位加法？
我第一時(shí)間反應(yīng)殖蚕，將兩個(gè)加數(shù)分別轉(zhuǎn)換成十進(jìn)制轿衔，再調(diào)用十進(jìn)制的“+” 進(jìn)行操作，結(jié)果再轉(zhuǎn)換回32進(jìn)制即可睦疫。
朋友告訴我害驹，對(duì)方不許轉(zhuǎn)10進(jìn)制。
我說(shuō)蛤育，那轉(zhuǎn)2進(jìn)制吧宛官，1位擴(kuò)展成5位，累加更方便瓦糕。結(jié)果長(zhǎng)度不被5整除底洗，頭部就補(bǔ)0，也好做咕娄。
對(duì)方說(shuō)亥揖，也不能轉(zhuǎn)2進(jìn)制。
那你明說(shuō)嘛圣勒，就是想要模擬我們小學(xué)的加號(hào)算法徐块，運(yùn)用到32進(jìn)制上，是不灾而？
對(duì)，就是這個(gè)意思扳剿！
OK旁趟，talk is cheap, show me the code：
import java.io.IOException
import scala.collection.mutable
/**
* Created by nicky_ye on 2018/2/8.
*/
object hex_32_add {
val char_list = List('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E',
'F', 'G', 'H', 'J', 'K', 'L', 'M', 'N', 'P', 'R', 'S', 'T', 'U', 'W', 'X', 'Y', 'Z')
val char_list_map: mutable.Map[Char, Int] = mutable.Map()
for (i <- char_list) {
char_list_map += (i -> char_list.indexOf(i))
}
def hex_32_add(string1: String, string2: String): String = {
if (!string1.forall(x => char_list.contains(x)) || !string2.forall(y => char_list.contains(y))) {
throw new IOException("Wrong Input String") ////pre check of input strings' legality
}
else {
var string1_reverse: Array[Char] = string1.reverse.toArray
var string2_reverse: Array[Char] = string2.reverse.toArray
var result_list: Array[Char] = Array()
var add_next_column = 0 //sign進(jìn)位標(biāo)志符
for (i <- 0 until math.max(string1_reverse.length, string2_reverse.length)) {
if (i >= string1_reverse.length) string1_reverse = string1_reverse.:+('0')
if (i >= string2_reverse.length) string2_reverse = string2_reverse.:+('0')
var column_result = char_list_map(string1_reverse(i)) + char_list_map(string2_reverse(i)) + add_next_column
if (column_result > 31) {
add_next_column = 1
column_result -= 32
}
else {
add_next_column = 0
}
result_list = result_list.:+(char_list(column_result))
}
if (add_next_column == 1) result_list = result_list.:+('1')
result_list.toList.toString.replace("List(","").replace(", ","").replace(")","").reverse
}
}
}
基本思想：
1：以?xún)蓚€(gè)String為輸入，以一個(gè)String為輸出，String代表32進(jìn)制字符
2：0到9锡搜，A到Z橙困，分別代表0~31，String中除此之外的字符不合法
3：add_next_column表示進(jìn)位標(biāo)識(shí)符耕餐，初始化0
4：輸入字符串 ---> 翻轉(zhuǎn)reverse---> 轉(zhuǎn)數(shù)組Array[Char]
5：若兩個(gè)輸入String長(zhǎng)度不相等凡傅，則短的翻轉(zhuǎn)后補(bǔ)0對(duì)齊
6：逐位相加再加進(jìn)位符，若結(jié)果超過(guò)32肠缔，進(jìn)位標(biāo)識(shí)符記1
7：所有位數(shù)對(duì)齊相加完畢后夏跷，若最后一位(即翻轉(zhuǎn)前的最高位)相加結(jié)果大于32，即進(jìn)位標(biāo)識(shí)符又為1明未，則結(jié)果列表中最后再加一位1
8：結(jié)果列表result_list轉(zhuǎn)換成String槽华，再翻轉(zhuǎn)reverse，即得最終結(jié)果
思路或者代碼中趟妥，從時(shí)間成本/內(nèi)存成本來(lái)考慮猫态，應(yīng)該有可以?xún)?yōu)化之處，幾個(gè)reverse操作披摄，開(kāi)銷(xiāo)感覺(jué)也不算小亲雪，但是應(yīng)該也不算大。
我不是專(zhuān)門(mén)做這類(lèi)優(yōu)化的疚膊，有了解的朋友歡迎指點(diǎn)义辕。
