[Codility] 第五課 PassingCars

一個不是空陣列的 A ，含有連續  N 個整數，
這些 A 陣列連續 N 個整數代表連續的車輛，

陣列 A 只有包含 0 或是 1：

• 0代表一輛向東行駛的汽車
• 1代表一輛向西行駛的汽車

目標是要數路過的車輛，我們假設有一組 (P, Q)，範圍是 0 < P < Q < N，
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)。

寫一個 function
int solution(int A[], int N);

給一個不是空的陣列 A 並且有 N 個整數，返回值為幾組路過車輛的數字。
如果數字大於 1,000,000,000 則返回 -1

舉例來說，A 陣列如下：

A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1

則 function 返回 5 。

條件：

• N的範圍必須是 0~100,000
• 陣列 A 的每個元素不是 0 就是 1

複雜度：

• 最糟的時間複雜度為 O(N)
• 最糟的空間複雜度為 O(1) (不含 input 的參數)

Java 程式碼

// you can also use imports, for example:
// you can also use imports, for example:
import java.util.*;
 
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
 
class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
          // write your code in Java SE 8
       int zCount = 0;
       int total = 0;
       for(int i =0;i<A.length;i++){
           if(A[i] == 0){
               zCount++;
           }else{
               total +=zCount;
           }
         
       }
       
         if(Math.abs(total) > 1000000000){
               return -1;
           }
        return total;
    }
}

分數共拿 100%，
任何問題歡迎交流討論，一起學習！

更多面試相關

⇒ [Codility] 面試寫題目經驗感想