实现字符串 repeat 方法

问题

实现一个 repeat 方法，将目标字符串重复 n 次并拼接返回。

解答

方法一：Array.join

利用数组的 join 方法，创建指定长度的数组并用目标字符串连接。

function repeat(target, n) {
  return (new Array(n + 1)).join(target);
}

方法二：类数组对象

省去创建数组的开销，直接使用类数组对象调用 join 方法。

function repeat(target, n) {
  return Array.prototype.join.call({
    length: n + 1
  }, target);
}

方法三：闭包缓存

通过闭包缓存 join 方法和对象引用，避免重复查找和创建。

var repeat = (function () {
  var join = Array.prototype.join, obj = {};
  return function(target, n) {
    obj.length = n + 1;
    return join.call(obj, target);
  };
})();

方法四：二分法

使用位运算和二分思想，减少字符串拼接次数，时间复杂度 O(log n)。

function repeat(target, n) {
  var s = target, total = [];
  while (n > 0) {
    if (n % 2 === 1) {
      total[total.length] = s;
    }
    if (n === 1) {
      break;
    }
    s += s;
    n = n >> 1;
  }
  return total.join('');
}

方法五：二分法优化（字符串直接拼接）

去掉数组和 join，直接拼接字符串，但会产生额外长度需要截取。

function repeat(target, n) {
  var s = target, c = s.length * n;
  do {
    s += s;
  } while (n = n >> 1);
  s = s.substring(0, c);
  return s;
}

方法六：二分法改良

结合方法四的思路，用字符串直接拼接替代数组。

function repeat(target, n) {
  var s = target, total = "";
  while (n > 0) {
    if (n % 2 === 1) {
      total += s;
    }
    if (n === 1) {
      break;
    }
    s += s;
    n = n >> 1;
  }
  return total;
}

关键点

• 方法一、二、三基于数组 join，简单但性能一般，适合小规模重复
• 方法三通过闭包缓存提升性能，避免重复创建对象和查找方法
• 方法四、五、六使用二分法，时间复杂度从 O(n) 降至 O(log n)，适合大量重复
• 位运算 n >> 1 等价于 Math.floor(n / 2)，性能更优
• 二分法的核心思想：每次将字符串翻倍，根据 n 的奇偶性决定是否累加当前结果