如何快速将 '*' 重复 9 次?
文章目录
如果是将 '*' 重复 8 次,一下子就可以想到这种快速算法:
-
'*'+'*'=>'**' -
'**'+'**'=>'****' -
'****'+'****'=> Bingo!
用 JavaScript 代码实现:
var n = 8;
var str = '*';
while ((n >>>= 1) > 0) {
str += str;
}
console.log(str);
同样的算法可用于 16 次、32 次、64 次、1024 次...
但是如果是要求重复 9 次呢?这就需要调整一下上述的算法。
先抽象出一个函数 repeat: (str: string, n: number) => string:
-
repeat('*', 3)=>'***' -
repeat('ab', 1)=>'ab' -
repeat('abcd', 0)=>'' ...
然后开始分析:
-
当
n为偶数时:-
repeat(str, n)<=repeat(str, n >>> 1) + repeat(str, n >>> 1) - 比如:
repeat('abc', 12)<=repeat('abc', 6) + repeat('abc', 6)
-
-
当
n为奇数时,即n - 1为偶数:-
repeat(str, n)<=str + repeat(str, n - 1) - 比如:
repeat('*', 21)<='*' + repeat('*', 20)
-
- 当
n为1时:repeat(str, 1)<=str - 当
n为0时:repeat(str, 0)<=''
用 JavaScript 代码实现:
function repeat(str/*:string*/, n/*:number*/) {
if (n === 0) return '';
if (n === 1) return str;
// `n` 为奇数
if (n % 2) return str + repeat(str, n - 1);
// `n` 为偶数,
// 但是要把 `repeat(str, n >>> 1)` 缓存起来,
// 以避免重复两次计算
return (str = repeat(str, n >>> 1)) + str;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论