[算法]大数相减
今天在小米OJ上看到一道题(https://code.mi.com/problem/list/view?id=3), 很有意思, 试着做了一下
描述:
两个长度超出常规整形变量上限的大数相减，请避免使用各语言内置大数处理库，如 Java.math.BigInteger 等。
输入:
有 N 行测试数据，每一行有两个代表整数的字符串 a 和 b，长度超过百位。规定 a>=b，a, b > 0。 测试结果可以用 linux 小工具 bc进行测试是否正确。
输出:
返回表示结果整数的字符串。
输入样例: 1231231237812739878951331231231237812739878951331231231237812739878951331231231237812739878951331231231237812739878951331231231237812739870-89513312312312378127398789513312312312378127398789513312312312378127398789513 1231231237812739878951331231231237812739878951331231231237812739878951331230000000000000000000000001-331231231237812739878951331231231
输出样例: 1231231237812739878951331231231237812739878951331231231237812650365639018918853110413950365639018918853110413950365639018918853110413950357 1231231237812739878951331231231237812739878951331231231237812739878620099998762187260121048668768770
代码:
/**
* @param string line 单行测试数据
* @return string 返回处理结果
*/
function solution(line) {
let params = line.split('-')
// 被减数数组, 例如: [1, 0, 0, 0, 0]
let a = params[0].split('').map(c => parseInt(c))
// 减数数组
let b = params[1].split('').map(c => parseInt(c))
// 在减数数组前面补0
let pad = a.length - b.length
if (pad > 0) {
for (let i = 0; i < pad; ++i) {
b.unshift(0)
}
}
// 相减
for (let i = 0; i < a.length; ++i) {
let idxA = a.length - 1 - i
let idxB = b.length - 1 - i
let intA = a[idxA]
let intB = b[idxB]
if (intA >= intB) {
a[idxA] = intA - intB
} else {
a[idxA - 1] = a[idxA - 1] - 1
a[idxA] = intA + 10 - intB
}
}
let result = a.join('')
// 去除结果前面的'0'
result = result.replace(/^0+/, '')
return result
}腾讯云开发者
