Codility 3.3 TapeEquilibrium

質問する

TapeEquilibrium

N個の整数からなる配列Aが与えられる.

指数Aを基準として、

配列Pを左右に分ける.

問題は、

程度のsub-arrayの和が最も小さい値を返すことです.

ex)[1,4,2,3,5,6],P=4(左=[1,4,2,3],右=[5,6])では左右合意差1が最小となるため,1の

を返す.

に答える

イニシャルコード

class Solution {
    public int solution(int[] A) {
        int right = 0;
        int left = 0;

        for (int el : A) {
            right += el;
        }

        int diff = right;

        for (int ii = 0; ii < A.length; ii++) {
            left += A[ii];
            right -= A[ii];
            
            int temp = Math.abs(left - right);
            diff = diff > temp ? temp : diff;
        }

        return diff;
    }
}

Aはすべて巡回し、右側に配列の和を格納します.

、すなわち左側のサブアレイが空の場合、右に1格移動し、最小値を求める.

全体の論理には問題はないはずだが、正しい答えは見つからなかった.理由は以下の通り.

diffの初期値は正しい.

の2番目のfor文は、右側が空に並んでいる場合に巡回される.

以上の2つのケースは[-1001000]テストで問題であることが分かった.

diffの初期値が右側の場合、右側には0または負の値が格納されるため、答えは0または負の条件なしである可能性があります.

forゲートが右に空いていて、左がAの場合、1番と同じ問題が発生します.

このため、コードは次のように変更されました.

class Solution {
    public int solution(int[] A) {
        int right = 0;
        int left = 0;

        for (int el : A) {
            right += el;
        }

        int diff = Integer.MAX_VALUE;

        for (int ii = 0; ii < A.length - 1; ii++) {
            left += A[ii];
            right -= A[ii];
            
            int temp = Math.abs(left - right);
            diff = diff > temp ? temp : diff;
        }

        return diff;
    }
}

diffの初期値はInteger.MAX_VALUEに初期化され、適切なdiffが継続的に格納される.

の最後の要素は巡回せず、上記の2番目の問題を阻止した.

全体の論理自体は簡単すぎますが、次は細かいテストケースで、これは不思議な間違いです.