codility之PassingCars

PassingCars

题目:


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.

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

        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.

For example, consider array A such that:
  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).

Write a function:

    function solution($A);

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

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

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.

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.

其实就是求0,1的子序列。

要求:

时间复杂度O(n)、空间复杂度为O(1)。

如何解决?

双重循环绝逼不行, 仔细观察给的例子, 结合双重循环的解法,

可以发现其实双重循环重复计算了很多, 而这些计算往往是前面的

遍历中已经算过的。

再仔细研究下规律, 可以发现对于第一个0和第二个0而言, 当第二个0

继续遍历遇到1的时候、是一对(0,1)的时候, 对第一个0而言同样是一对(0,1).

由此我们只需要在遍历的时候计算0的个数zero_cnt, 当遇到1的时候我们就将pair_car_cnt增加zero_cnt,

而当遇到0的时候则累计爱zero_cnt即可。

代码:


function solution($A) {
    // write your code in PHP5.5
    $zero_cnt = 0;
    $pair_car_cnt = 0;
    foreach ($A as $v) {
        if ($v == 0) {
            $zero_cnt += 1;
        } else {
            $pair_car_cnt += $zero_cnt;
        }
        if ($pair_car_cnt > 1000000000) {
            return  -1;
        }
    }
    return $pair_car_cnt;
}

Leave a Reply

Your email address will not be published. Required fields are marked *


To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax