javascript - 如何处理javascript中for循环内的大量数字？

Question

我正在研究黑客等级问题。重复字符串[1]:https://www.hackerrank.com/challenges/repeated-string/problem

function main() {
    var s = readLine();
    var n = parseInt(readLine());
    var rep = 0;
    var repArray = []

//calculate each case 

  while(repArray.length < n){
      for(let j = 0; j < s.length; j++){
           if(repArray.length > n){
              break;
         }
          repArray.push(s[j])
      }
  }

  for(let a = 0; a < repArray.length; a++){
     if(repArray[a] === 'a'){
          rep++
      } 
  }
  console.log(rep)
}

我收到输入错误A1000000000000

我的代码的输出是<--- 最后几次 GC --->

1836 ms: Mark-sweep 597.4 (605.3) -> 359.7 (368.6) MB, 101.7 / 0.0 ms [allocation failure] [GC in old space requested].
1938 ms: Mark-sweep 359.7 (368.6) -> 359.7 (368.6) MB, 102.3 / 0.0 ms [allocation failure] [GC in old space requested].
2040 ms: Mark-sweep 359.7 (368.6) -> 359.7 (367.6) MB, 101.6 / 0.0 ms [last resort gc].
2142 ms: Mark-sweep 359.7 (367.6) -> 359.7 (367.6) MB, 101.7 / 0.0 ms [last resort gc].

<--- JS 堆栈跟踪 --->

==== JS 堆栈跟踪 ========================================== =

Security context: 0x10178c2cfb51 2: main [/run-N6KBYU8cQzCneXKH0Tbm/solution.js:~30] [pc=0x2859725aec0] (this=0x10178c2e6119 ) 3: /* anonymous */ [/run-N6KBYU8cQzCneXKH0Tbm/solution.js:21] [pc=0x2859725717e] (this=0x2af8d3a77e81 ) 4: emitNone(aka emitNone) [events.js:91] [pc=0x28597256c33] (this=0x10178c204381 ,handler=0x2af8d3a78049 ,is...

这段代码的错误是

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory 1: node::Abort() [/usr/local/nodejs-binary/bin/node] 2: 0x1098b2c [/usr/local/nodejs-binary/bin/node] 3: v8::Utils::ReportApiFailure(char const*, char const*) [/usr/local/nodejs-binary/bin/node] 4: v8::internal::V8::FatalProcessOutOfMemory(char const*, bool) [/usr/local/nodejs-binary/bin/node] 5: v8::internal::Factory::NewUninitializedFixedArray(int) [/usr/local/nodejs-binary/bin/node] 6: 0xc4553f [/usr/local/nodejs-binary/bin/node] 7: v8::internal::Runtime_GrowArrayElements(int, v8::internal::Object**, v8::internal::Isolate*) [/usr/local/nodejs-binary/bin/node] 8: 0x285971079a7

Answer 1

寻找高效的算法是一个问题。您不能使用暴力来解决此类问题。

n故意设置为较高的值，这样您就不会尝试暴力破解。 10^12是 1 Trillion ，即使您可以在 one nano second 中运行循环的每次迭代这需要1000 seconds ，鉴于不可能在 one nano second 中运行每次迭代，这很长.

您面临的问题是由于 Space complexity ，您正在尝试存储 (n=10^12)内存中的(最大值)字符。如果每个字符取1 byte那么我们需要的内存大小是

10^12 bytes = 1000 Giga bytes = 1 Terra byte

我确信您的程序不会获得该内存。鉴于必须有其他人同时尝试解决这个问题。 Hackerrank无法为所有人提供这么多资源。

问题从来没有让你在内存中存储这个值。目的是让您找到一种巧妙的方法来解决该问题，而无需存储所有值。

现在聪明的方法是你可以数一下有多少 a位于 s 。现在您所要做的就是找出有多少个字符串 s如果您只有n，您可以重复字符。

下面有剧透(点击/悬停查看答案):

可以通过 Math.floor(n / s.length) 来计算。现在末尾可能有一些剩余的字符串，其长度为 n % s.length 。所以解决方案是 count = Math.floor(n / s.length) * CountAsIn(s) + CountAsIn(s.substring(n % s.length))