Codility：在 Lua 中过往汽车

Question

我目前正在练习编程问题，出于兴趣，我正在 Lua 中尝试一些 Codility 练习。我一直被 Passing Cars 问题困扰了一段时间。

问题：

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.

我在 Lua 中的尝试一直失败，但我似乎找不到问题所在。

local function solution(A)
    local zeroes = 0
    local pairs = 0
    for i = 1, #A do
        if A[i] == 0 then
           zeroes = zeroes + 1
        else
            pairs = pairs + zeroes
            if pairs > 1e9 then
                return -1
            end
        end
    end
    return pairs
end

就时间 space 复杂性限制而言，我认为它应该通过，所以我似乎找不到问题所在。我究竟做错了什么？任何使我的代码更高效的建议或技巧将不胜感激。仅供参考：当所需的示例结果为 5 时，我一直得到 2 的结果。

Answer 1

问题陈述说 A 是基于 0 的，所以如果我们忽略第一个并从 1 开始，输出将是 2 而不是 5。在 Lua 中应该避免基于 0 的表，它们会违反惯例，会导致很多错误：for i=1,#A do 不会做你想做的事。

function solution1based(A)
    local zeroes = 0
    local pairs = 0
    for i = 1, #A do
        if A[i] == 0 then
           zeroes = zeroes + 1
        else
            pairs = pairs + zeroes
            if pairs > 1e9 then
               return -1
            end
        end
    end
    return pairs
end
print(solution1based{0, 1, 0, 1, 1}) -- prints 5 as you wanted

function solution0based(A)
    local zeroes = 0
    local pairs = 0
    for i = 0, #A do
        if A[i] == 0 then
           zeroes = zeroes + 1
        else
            pairs = pairs + zeroes
            if pairs > 1e9 then
               return -1
            end
        end
    end
    return pairs
end

print(solution0based{[0]=0, [1]=1, [2]=0, [3]=1, [4]=1}) -- prints 5

Codility：在 Lua 中过往汽车

Codility: Passing cars in Lua

lua