Painless
PassingCars
道路を通過する車の数を数えます。
タスク説明
N個の整数で構成される空でない配列Aが与えられます。配列Aの連続する要素は、道路上の連続する車を表します。
配列Aには0または1、あるいはその両方が含まれています。
- 0は東に移動する車を表し、
- 1は西に移動する車を表します。
目標は、通過する車を数えることです。 Pが東に移動し、Qが西に移動しているときに、0≤P<Q <Nである2台の車（P、Q）が通過していると言います。
たとえば、次のような配列Aについて考えてみます。
例
A [0] = 0
A [1] = 1
A [2] = 0
A [3] = 1
A [4] = 1
（0、1）、（0、3）、（0、4）、（2、3）、（2、4）の5組の通過車があります。
関数を書く：
`class solution {public int solution(int [] A); }
これは、N個の整数の空でない配列Aが与えられると、通過する車のペアの数を返します。
通過する車のペアの数が1,000,000,000を超える場合、関数は-1を返す必要があります。
たとえば、次のようになります。
例
A [0] = 0
A [1] = 1
A [2] = 0
A [3] = 1
A [4] = 1
上で説明したように、関数は5を返す必要があります。
次の仮定のための効率的なアルゴリズムを記述します。
- Nは[1..100,000]の範囲内の整数です。
- 配列Aの各要素は、0、1のいずれかの値を持つことができる整数です。
解く
Program
PassingCarsSolution.java
public int solution(int[] A) {
int goal = 0;
int[] P = new int[A.length + 1];
P[0] = 0;
for (int i = 0; i < A.length; i++) {
P[i + 1] = P[i] + A[i];
}
for (int j = 0; j < A.length - 1; j++) {
if (A[j] == 0) {
goal += P[P.length - 1] - P[j + 1];
if (goal > 1000000000) {
return -1;
}
}
}
return goal;
}
Detected time complexity:
O(N)