1

昨夜、Codility でデモ Equi タスクを見ていて、次の関数で 12/100 を獲得しました。

function solution(A) {
    var n = A.length;
    var p = 0;
    var sum = 0;
    var sumLeft = 0;
    var sumRight = 0;
    var equilExists = 0;

    if (n == 0) {
        return -1;
    }

    for (i=0; i<=n; i++) {
        sum = A[i];
        for (j=0; j<=n; j++) {
        if (j < i) {
            sumLeft += A[j];
        } else if (j > i) {
            sumRight += A[j];
        }
        if (sumLeft == sumRight) {
            equilExists = 1;
            p = i;
            return p;
                }
        }
    }

    if (equilExists == 0) {
        return -1;
    }
}

タスクに慣れていない方は、http://blog.codility.com/2011/03/solutions-for-task-equi.htmlで見つけることができます。

私のソリューションが失敗する場所を誰かが指摘するのを手伝ってくれるかどうか疑問に思っていましたか?

どうもありがとう！

4

11 に答える 11

1

ソリューションの最大の問題は、ネストされたループです。

各インデックスで配列全体を反復処理して、現在のインデックスで左部分と右部分の合計を計算します。彼らの要件の 1 つは O(n) の複雑さですが、あなたの要件は O(n^2) です (私はそう思います)。

配列を 2 回ループするだけで済みます。1 回目は要素の合計を取得するため、もう 1 回は平衡を見つけるためです。2 番目のループの開始時に、左側の合計 == 0 と右側の合計 == 合計。合計を更新する必要がある要素を反復処理します。右の合計 = 合計 - 左の合計 - 現在のインデックスの値。次に、右 == 左の場合を比較し、そうでない場合 - 左の合計は現在のインデックスの値だけ大きくなります。

私はこれで100ポイントを獲得しました：

function solution(A) {
  var total = (function(a){ var l = a.length, s = 0; while(--l>-1){ s+=a[l] } return s; }(A)), 
  eq = -1, 
  l = A.length, 
  Lsum = 0, 
  Rsum = 0; 
  A.forEach(function(n,i){ 
    Rsum = total - Lsum - n; 
    if(Rsum == Lsum){ eq = i; /* in fact no need to continue, should terminate here. */ } 
    Lsum += n; 
  }); 
  return eq;
}
于 2013-09-26T13:29:46.663 に答える
0

私の答えはこれです：

function balance(arr){

var N = arr.length;
if (N == 0){ return -1};

var suma = 0;
for (var i=0; i<N; i++){
    suma += arr[i];
}

var suma_iz = 0;
for(i=0; i<N; i++){
    var suma_de = suma - suma_iz - arr[i];
    if (suma_iz == suma_de){
        return i};
    suma_iz += arr[i];
}

  return -1;}

この解は O(n) 要件を満たします

于 2016-02-27T11:38:42.390 に答える
0

少し違うもの (100pts):

function solution(list) {
  var length = list.length,
      sumRight,
      sumLeft = 0,
      equi_index = -1;

  if (length === 0) {
    return equi_index;
  } else if (length === 1) {
    return 0;
  }

  var total = (function(){
    var sum = 0;
    while (length--) {
      sum += list[length];
    }
    return sum;
  })();

  list.some(function(each, index){
    sumRight = total - sumLeft - each;
    if (sumLeft === sumRight) {
      equi_index = index;
      return true; // stop iteration
    }

    sumLeft += each;
  });

  return equi_index;
}
于 2016-05-20T21:31:09.813 に答える
0

まず、関数は常に 0 を返します (n>0 の場合)。これはif (sumLeft == sumRight)、内側の for ループの内側に を配置したためです。
これを修正しても、変数sumLeftとsumRightが内側の for ループの前に初期化されないため、まだ問題があります。これらの問題を修正すると、関数は少なくとも正しく、75 点を獲得します。ただし、アルゴリズムは明らかに二次です。これを解決するには、1 増やしたときに左と右の合計がどのように変化するかを自問する必要がありますi。両方を最初から再計算する必要がありますか?

于 2013-08-24T21:49:07.670 に答える
0

JS solution Scores - 100% and performs pretty fast

function solution(A) {
   const values = new Set(A) // dedupe array
   let i = 0
   while(++i) { // iterate from 1, the first possible positive integer greater than 0 
       if(!values.has(i)) { // check if set has value and break loop if it does not
           break
       }
   }
   return i
}
于 2021-02-27T04:05:35.847 に答える