MarsCode #3:数字字符串格式化
题干
小 M 在工作时遇到了一个问题,他需要将用户输入的不带千分位逗号的数字字符串转换为带千分位逗号的格式,并且保留小数部分。小M还发现,有时候输入的数字字符串前面会有无用的 0
,这些也需要精简掉。请你帮助小M编写程序,完成这个任务。
测试样例
样例1:
输入:
s = "1294512.12412"
输出:
'1,294,512.12412'
样例2:
输入:
s = "0000123456789.99"
输出:
'123,456,789.99'
样例3:
输入:
s = "987654321"
输出:
'987,654,321'
我的解法
function solution(s) {
// PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
// write code here
const [int, dec] = s.split(".");
const int_arr = int.split("");
const int_len = int_arr.length;
const int_res = [];
for (let n = int_len - 1; n >= 0; n--) {
int_res.push(int_arr[n]);
if ((int_len - n) % 3 === 0) {
int_res.push(",");
}
}
const res = `${int_res.reverse().join("")}${dec ? "." + dec : ""}`.replace(
/^[0,]+/,
""
);
return res;
}
function main() {
console.log(solution("1294512.12412") === "1,294,512.12412");
console.log(solution("0000123456789.99") === "123,456,789.99");
console.log(solution("987654321") === "987,654,321");
}
main();
AI 解法
function solution(s) {
// 去掉前面的无用0
s = s.replace(/^0+/, "");
// 分离整数部分和小数部分
let [integerPart, decimalPart] = s.split(".");
// 对整数部分添加千分位逗号
integerPart = integerPart.replace(/\B(?=(\d{3})+(?!\d))/g, ",");
// 合并整数部分和小数部分
return decimalPart ? `${integerPart}.${decimalPart}` : integerPart;
}
function main() {
console.log(solution("1294512.12412") === "1,294,512.12412");
console.log(solution("0000123456789.99") === "123,456,789.99");
console.log(solution("987654321") === "987,654,321");
}
main();
from collections import Counter
def solution(s:str) -> str:
if '.' in s:
integer_part, decimal_part = s.split('.')
else:
integer_part, decimal_part = s, None
formatted_integer = "{:,}".format(int(integer_part))
if decimal_part:
s = formatted_integer + '.' + decimal_part
else:
s = formatted_integer
return s.rstrip('0').rstrip('.')
if __name__ == '__main__':
print(solution(s = "1294512.12412") == '1,294,512.12412')
print(solution(s = "0000123456789.99") == '123,456,789.99')
print(solution(s = "987654321") == '987,654,321')
复盘
字节的这一套题都是比较偏实际生产的,所以 AI 给的题解也会用到大量语言特性。Python 的标准题解非常平庸,就不过多解读了。
JS 解法还是很有亮点的,拆分整数和小数部分的方式和我大同小异,不过 AI 选择在一开始就把多余的 0
去掉,这样降低时间复杂度的同时代码逻辑也会清晰一些。不过在代码格式化过程中 AI 使用了一个非常巧妙的正则表达式 \B(?=(\d{3})+(?!\d))
来在每三个数字之间插入逗号。
拆解一下这个正则:
\B
表示非单词边界,表示这条正则的匹配位置会在每两个数字之间。(?=)
是一个 positive lookahead 断言表示,如果是(?!)
则是 negative lookahead。如果是 lookbehind 则写作(?<)
。
再来看 positive lookahead 里面的内容。
\d{3}
表示三个数字的组合,+
表示至少出现一次。(?!\d)
表示在\d{3}
后面不是数字。
这个正则综合起来就能筛选出所有需要插入逗号的位置。
用 12345
举例:
第一步迭代,匹配位置在 1
之前,不满足 \B
条件,不插入逗号。
第二步迭代,匹配 1
和 2
之间的位置,满足 \B
条件,进入正向 lookahead。1
后面是连续的四个数字2345
,不满足 \d{3}
(剩余位数不是 3 的倍数),不插入逗号。
第三步迭代,匹配 2
和 3
之间的位置,满足 \B
条件,进入正向断言。2
后面是连续的三个数字345
,满足 \d{3}
,进入负相 lookahead. 345
后面不是数字(已经到末尾),满足 (?!\d)
条件,插入逗号。
第四五六步均不满足 \B
或 \d{3}
条件,不插入逗号。因此最后只有 2
和 3
之间的这个 token 符合条件,通过 replace(regex, ",")
插入一个逗号。
总结
首先是去掉冗余信息 0
的时机,越早越好。
其次是插入逗号的方式,传统的从后向前遍历是非常标准的题解,但是也可以通过构造正则表达式来比较巧妙的完成这个任务。不过虽然这个正则最终可以被转化为 DFA,但是实际的时间复杂度应当还是 O(n^2)
,不如从后向前遍历的 O(n)
优秀。第一眼看上去也不是很好理解,有点偏向炫技。(真不是酸)