Java Codility路过的车

Codility passing car

提问by user2383728

A non-empty zero-indexed array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.

给出了一个由 N 个整数组成的非空零索引数组 A。数组 A 的连续元素表示道路上连续的汽车。

Array A contains only 0s and/or 1s:

数组 A 仅包含 0 和/或 1：

    0 represents a car traveling east,
    1 represents a car traveling west.

The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.

目标是统计过往车辆。我们说一对汽车 (P, Q)，其中 0 ≤ P < Q < N，当 P 向东行驶而 Q 向西行驶时正在通过。

For example, consider array A such that:

例如，考虑数组 A 使得：

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

We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

我们有五对过往车辆：(0, 1), (0, 3), (0, 4), (2, 3), (2, 4)。

Write a function:

写一个函数：

class Solution { public int solution(int[] A); } 

that, given a non-empty zero-indexed array A of N integers, returns the number of passing cars.

给定一个由 N 个整数组成的非空零索引数组 A，返回经过的汽车数量。

The function should return ?1 if the number of passing cars exceeds 1,000,000,000.

如果经过的汽车数量超过 1,000,000,000，该函数应返回 ?1。

For example, given:

例如，给定：

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

the function should return 5, as explained above.

如上所述，该函数应返回 5。

Assume that:

假使，假设：

    N is an integer within the range [1..100,000];
    each element of array A is an integer that can have one of the following values: 0, 1.

Complexity:

复杂：

    expected worst-case time complexity is O(N);
    expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

可以修改输入数组的元素。

I don't understand why there are five passing cars, instead of 6. Why doesn't (2,1) count as a passing car? Can someone provide some explanation on how to approach this problem?

我不明白为什么有五辆经过的汽车，而不是 6 辆。为什么 (2,1) 不算作经过的汽车？有人可以就如何解决这个问题提供一些解释吗？

采纳答案by Kromster

You need to count number of cars passings. Cars are positioned on the road as input says and start driving into either one of directions. When car drives, we can easily see that it will drive by cars moving in the opposite direction, but only if they were in front of it. Essentially that can be formulated as:

您需要计算经过的汽车数量。汽车按照输入的说法定位在道路上，并开始向任一方向行驶。当汽车行驶时，我们很容易看到它会被向相反方向行驶的汽车驱动，但前提是它们在它前面。基本上可以表述为：

1. Imagine array 0..N

2. Take element X (iterate from 0 to Nth element)

3. If value of element X is 0 then count how many 1 elements it has on the right

4. If value of element X is 1 then count how many 0 elements it has on left

5. Repeat for next X

6. Sum up and divide by 2 (cos it takes 2 cars to pass each other), that's the answer.

1. 想象一下数组 0..N

2. 取元素X（从0到第N个元素迭代）

3. 如果元素 X 的值为 0，则计算其右侧有多少个 1 元素

4. 如果元素 X 的值为 1，则计算其左侧有多少个 0 元素

5. 对下一个 X 重复

6. 总结并除以 2（因为需要 2 辆车才能相互通过），这就是答案。

In case with 0 1 0 1 1we have 3+1+2+2+2 = 10. Divide by 2 = 5 passings.

如果0 1 0 1 1我们有 3+1+2+2+2 = 10。除以 2 = 5 次传球。

We don't count pair 2-1 because 2nd car is driving to the East and never passes the 1st car that is driving away from it to the West.

我们不计算 2-1 对，因为第 2 辆车向东行驶，并且永远不会超过远离它向西行驶的第 1 辆车。

回答by Setra R

Scala result:

斯卡拉结果：

• 100% score

• Time complexity: O(N)

• 100% 分数

• 时间复杂度：O(N)

  def solution(a: Array[Int]): Int = {
    // write your code in Scala 2.12

    case class Survey(east: Int, pairCount: Int)

    a.foldLeft(Survey(0,0)) {
      (survey, passingCar) =>
        if (passingCar == 0) survey.copy( east = survey.east + 1)
        else {
          if( survey.pairCount > 1000000000) return -1
          survey.copy( pairCount = survey.pairCount + survey.east)
        }
    }.pairCount

  }

回答by Chigozie Orunta

A JavaScript solution of mine tested 100%.

我的一个 JavaScript 解决方案测试了 100%。

function solution(A) {
    let pairs = 0;
    let totalNumberOfZeros = 0;
    let totalPairs = 0;
    for(let i=0; i<A.length; i++) {
        if(A[i] === 0) {
            totalNumberOfZeros++;
            pairs = 0;
        }
        if(A[i] === 1) {
            pairs = 1;
            totalPairs += (totalNumberOfZeros*pairs);
        }
    }
    if(totalPairs > 1000000000) {
        totalPairs = -1;
    }
    return totalPairs;
}

回答by grimface

My code in java :) with O(N) complexity. Easier to understand. Just sum up all the ones backwards.

我的 Java 代码 :) 复杂度为 O(N)。更容易理解。只需向后总结所有的。

void calculateOnes(int[] A, int[] sum) {
    int N = A.length;
    sum[N - 1] = A[N - 1];
    for (int i = N - 2; i >= 0; i--) {
        sum[i] = A[i] + sum[i + 1];
    }
}

public int solution(int[] A) {
    int N = A.length;
    int[] sum = new int[N];
    calculateOnes(A, sum);
    int counter = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] == 0) {
            counter += sum[i];
        }
    }
    return counter;
}

回答by Rees

if it helps conceptually, think of the positions of the cars as all parked, engines off and facing either east or west in the order of the array. then they all start their engines and then start driving... thus, car #2 and car #1 never pass each other.

如果它在概念上有帮助，请将汽车的位置视为全部停放、发动机关闭并按阵列顺序面向东或西。然后他们都启动引擎，然后开始驾驶……因此，2 号车和 1 号车永远不会相互超越。

回答by Min2

Java: I did it in simple way 100% correctness and performance

Java：我以简单的方式做到了 100% 的正确性和性能

public int solution(int[] A) {
        // write your code in Java SE 8
         int output = 0;
      int noOfZero = 0;
      for (int i = 0; i < A.length; i++) {
         if (A[i] == 0) {
            noOfZero += 1;
            continue;
         }
         if (A[i] == 1 && noOfZero > 0) {
            output += noOfZero * A[i];
         }
      }
      if(output > 1000000000 || output < 0){
         return -1;
      }

      return output;
    }

回答by Fawad Masud

Objectve-C solution 100%

Objectve-C 解决方案 100%

int solution(NSMutableArray *A) {
// write your code in Objective-C 2.0


int n=0;
int long long t = 0;

for(int i=0;i<A.count;i++)
{
    if([A[i] intValue]==0)
    {
        n=n+1;
    }

    else
    {
        t = t+n*1;
    }    
}

 if(t>1000000000)
 {
    return -1;
 }
 else
 {
    return t;
 }
}

回答by Balaji Reddy

Passing cars solution in C

C中的超车解决方案

int solution(int A[], int N) {
    // write your code in C90
    int i=N-1,j=0,k=0;

    do
    {
        if (A[i]==0)
        {
            j+=k;
            if (j>1000000000)return -1;
        }
        else
            k += 1;

    }while(--i>=0);

    return j;
}

回答by Bagusflyer

Objective-c function:

Objective-C 函数：

-(int)carPairCount:(NSMutableArray *)A {

    if ( A.count > 0 )
    {
        int N = (int)A.count;
        int P = 0;
        int Q = 1;
        int count = 0;

        while ( P < Q && Q < N ) {

            if ([A[P] intValue] == 0 && [A[Q] intValue] == 1) {
                count++;

                if ( count > 1000000000)
                    return -1;
            }

            Q++;
            if ( Q == N )
            {
                P++;
                Q = P+1;
            }
        }

        return count;
    }

    return 0;
}

回答by tas

We need only to traverse the Zeros, in order to find the number of total crossings.

我们只需要遍历零点，就可以找到总交叉次数。

No need to run extra code for Ones, because the number of crossings for every Zero we check, is equal to the number of crossings we get, when we check all Ones for that particular Zero.

不需要为 1 运行额外的代码，因为我们检查的每个零的交叉次数等于我们检查所有 1 的特定零时得到的交叉次数。

public class passingCars {


public static void main(String[] args) {
    int k;
    int cnt = 0;
     // Test array
    int[] A = { 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1 };

    for (int i = 0; i < A.length; i++) {

        if (A[i] == 0) {
            k = i + 1;
            while (k < A.length) {
                if (A[k] == 1) {
                    cnt++;
                }
                k++;
            }

        }

    }

    System.out.println(cnt);

}

}

result: 17

结果：17

回答by user3662248

Time Complexity - O(n) Space Complexity - O(1) The logic I came up with goes like this.

时间复杂度 - O(n) 空间复杂度 - O(1) 我想出的逻辑是这样的。

• Have 2 variables. Count and IncrementVal. Initialize both to zero.
• Traverse through the array. Every time you find a 0, increment the IncrementVal.
• Every time you find a 1, modify count by adding the incrementVal to count.
• After the array traversal is completed, return back the count.

• 有2个变量。计数和增量值。将两者都初始化为零。
• 遍历数组。每次发现 0 时，增加 IncrementVal。
• 每次找到 1 时，通过将 incrementVal 添加到计数来修改计数。
• 数组遍历完成后，返回计数。

Note:: Example code provided below assumes static array and a predefined array size. You can make it dynamic using vectors.

注意：下面提供的示例代码假定静态数组和预定义的数组大小。您可以使用向量使其动态化。

#include <iostream>
using namespace std;

int getPass(int* A, int N)
{
    unsigned long count = 0;
    int incrementVal = 0;
    for(int i = 0; i < N; i++)
    {
        if(A[i]==0)
        {
            incrementVal++;
        }
        else if (A[i]==1)
        {
            count = count + incrementVal;
        }
        if(count > 1000000000) return -1;
    }
    return count;
}

int main()
{
   int A[]={0,1,0,1,1};
   int size = 5;
   int numPasses = getPass(A,size);
   cout << "Number of Passes: " << numPasses << endl;
}