CodilityピークJavaScript実装

Question

IはCodility Peak problemに取り組んでいます：

分割インデックスPようA [Pことを含むべきそれぞれが同じサイズのブロックの最大数に配列 - A] [P + 1]を含む。

私のソリューションは以下のとおりですが、得点は45％です。だから私の質問は：

私はまだ解決策を改善することができますか？

function solution(A) { 
    var storage = [], counter = 0; 
    // 1. So first I used a loop to find all the peaks 
    // and stored them all into an array called storage 
    for(var i = 1; i < A.length - 1; i++) { 
    if (A[i] > A[i-1] && A[i] > A[i+1]) { 
     storage.push(i); 
    } 
    } 
    // 2. Go and write the function canBeSeparatedInto 
    // 3. Use the for loop to check the counter 
    for(var j = 1; j < A.length; j++) { 
    if (canBeSeparatedInto(j, A, storage)) { 
     counter = j; 
    } 
    } 
    return counter; 
} 

/* this function tells if it is possible to divide the given array into given parts 
* we will be passing our function with parameters: 
* @param parts[number]: number of parts that we intend to divide the array into 
* @param array[array]: the original array 
* @param peaks[array]: an storage array that store all the index of the peaks 
* @return [boolean]: true if the given array can be divided into given parts 
*/ 
function canBeSeparatedInto(parts, array, peaks) { 
    var i = 1, result = false; 
    var blockSize = array.length/parts; 
    peaks.forEach(function(elem) { 
    // test to see if there is an element in the array belongs to the ith part 
     if ((elem+1)/blockSize <= i && (elem+1)/blockSize> i-1) { 
      i++; 
     } 
    }); 
    // set the result to true if there are indeed peaks for every parts 
    if (i > parts) { 
     result = true; 
    } 
    return result; 
} 

私のコードの主な問題は、それが性能試験に合格しないということです。私は自分自身をより明確にするためにいくつかの余分なコメントを追加しましたので、

コードスニペットは、長いようです。あなたはそれについて私にいくつかのヒントを教えていただけますか？

Answer 1

配列がK個の部分に分割できるかどうかをチェックするとき、最悪の場合（[1,2,1,2,1、...]の配列）N/2個のチェックを行いますあらゆるピーク）。

これは、巧妙なデータ構造を使用してKステップで行うことができます。 ピークをバイナリ配列（0 - ピークなし、1 - ピーク）で表します。それ以上の接頭辞の合計を計算します。ブロックにピークが含まれているかどうかを確認するには、ブロックの先頭と最後でプリフィックスの合計を比較するだけです。

また、他にも小さな問題があります。配列のサイズを分割しないブロックの数を確認しないでください。

Answer 2

私はこのアルゴリズムを示唆している：

• は彼らの前任者と持た距離で覗き見を並べ替えます。これを行うには、「谷」を特定すること、すなわちピークを持たない最大範囲を特定し、それらをサイズ順に降順で並べ替えることがより便利かもしれません。

• ソリューションの長さの約数を特定するそれら。たとえば、配列の長さがプライムのときに解をテストするのは時間の無駄です。その場合、答えは1にしかなりません（またはピークがない場合はゼロ）。

• それぞれの除数を昇順（配列チャンクのサイズを表す）で試して、その谷のそれぞれがその谷の中のチャンクの1つを完全に持っているかどうかを確認します。その場合は解決策としてそのサイズを拒否し、次のサイズを試してください。

配列のインタラクティブな入力と実装：

"use strict"; 
 
// Helper function to collect the integer divisors of a given n 
 
function divisors(n) { 
 
    var factors = [], 
 
     factors2 = [], 
 
     sq = Math.sqrt(n); 
 
    for (var i = 1; i <= sq; i++) { 
 
     if (n % i === 0) { 
 
      factors.push(n/i); 
 
      // Save time by storing complementary factor as well 
 
      factors2.push(i); 
 
     } 
 
    } 
 
    // Eliminate possible duplicate when n is a square 
 
    if (factors[factors.length-1] === factors2[factors2.length-1]) factors.pop(); 
 
    // Return them sorted in descending order, so smallest is at end 
 
    return factors.concat(factors2.reverse()); 
 
} 
 

 
function solution(A) { 
 
    var valleys = [], 
 
     start = 0, 
 
     size, sizes, i; 
 
    // Collect the maximum ranges that have no peeks 
 
    for (i = 1; i < A.length - 1; i++) { 
 
     if (A[i] > A[i-1] && A[i] > A[i+1]) { 
 
      valleys.push({ 
 
       start, 
 
       end: i, 
 
       size: i - start, 
 
      }); 
 
      start = i + 1; 
 
     } 
 
    } 
 
    // Add final valley 
 
    valleys.push({ 
 
     start, 
 
     end: A.length, 
 
     size: A.length - start 
 
    }); 
 
    if (valleys.length === 1) return 0; // no peeks = no solution 
 
    // Sort the valleys by descending size 
 
    // to improve the rest of the algorithm's performance 
 
    valleys.sort((a, b) => b.size - a.size); 
 
    // Collect factors of n, as all chunks must have same, integer size 
 
    sizes = divisors(A.length) 
 
    // For each valley, require that a solution must not 
 
    // generate a chunk that falls completely inside it 
 
    do { 
 
     size = sizes.pop(); // attempted solution (starting with small size) 
 
     for (i = 0; 
 
      i < valleys.length && 
 
      // chunk must not fit entirely inside this valley 
 
      Math.ceil(valleys[i].start/size) * size + size > valleys[i].end; i++) { 
 
     } 
 
    } while (i < valleys.length); // keep going until all valleys pass the test 
 
    // Return the number of chunks 
 
    return A.length/size; 
 
} 
 

 
// Helper function: chops up a given array into an 
 
// array of sub arrays, which all have given size, 
 
// except maybe last one, which could be smaller. 
 
function chunk(arr, size) { 
 
    var chunks = []; 
 
    for (var i = 0; i < arr.length; i += size) { 
 
     chunks.push(arr.slice(i, i + size)); 
 
    } 
 
    return chunks; 
 
} 
 

 
// I/O management 
 
inp.oninput = function() { 
 
    // Get input as an array of positive integers (ignore non-digits) 
 
    if (!this.value) return; 
 
    var arr = this.value.match(/\d+/g).map(v => +v); 
 
    var parts = solution(arr); 
 
    // Output the array, chopped up into its parts: 
 
    outCount.textContent = parts; 
 
    outChunks.textContent = chunk(arr, arr.length/parts).join('\n'); 
 
}

Array (positive integers, any separator): <input id="inp" style="width:100%"> 
 
Chunks: <span id="outCount"></span> 
 
<pre id="outChunks"></pre>