javascript - Codility Peak JavaScript 实现

Question

我正在研究 Codility Peak problem :

Divide an array into the maximum number of same-sized blocks, each of which should contain an index P such that A[P - 1] < 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

我会建议这个算法:

• 根据他们与前任的距离对 peeks 进行排序。为此，识别“谷”可能更直观，即没有窥视的最大化范围，并按大小降序对它们进行排序

• 确定数组长度的除数，因为解必须是其中之一。例如，当数组长度为质数时，测试解决方案是浪费时间:在这种情况下，答案只能是 1(如果没有 peeks，则为零)。

• 按升序尝试每个除数(代表数组 block 的大小)，看看对于每个谷，这样的拆分是否会将其中一个 block 完全带入该谷内，即它不会包含 peek :在那种情况下，拒绝该尺寸作为解决方案，并尝试下一个尺寸。

数组交互输入的实现:

"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>