codility之TapeEquilibrium

TapeEquilibrium

题目:

A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape.
Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|
In other words, it is the absolute difference between the sum of the first part and the sum of the second part.
For example, consider array A such that:
  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3
We can split this tape in four places:
P = 1, difference = |3 − 10| = 7 
P = 2, difference = |4 − 9| = 5 
P = 3, difference = |6 − 7| = 1 
P = 4, difference = |10 − 3| = 7 
Write a function:
function solution($A);
that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.
For example, given:
  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3
the function should return 1, as explained above.

题目大致是给定非空的连续数组,求左右两边的差最小值。

要求:

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

如何解决?

思路

这个题目其实很类似求连续子序列和, 所以我们可以采用相同的方法去解决。

遍历数组的时候记录下左边的前P - 1项和、右边的P至 N - 1项和。

同时保存一个差值, 每次遍历的时候对比左右两边的差值, 如果新的差值较小则更新。

循环结束直接,这个差值就应该返回我们需要求的最小差值。

代码如下

PHP


// you can use print for debugging purposes, e.g.
// print "this is a debug message\n";

function solution($A) {
    // write your code in PHP5.5
    $sum_left = $A[0];
    $sum_right = array_sum(array_slice($A, 1));
    $diff_min = abs($sum_left - $sum_right);
    $len = count($A);
    $i = 1;
    for($i; $i < $len - 1; $i++){
        $sum_left += $A[$i];
        $sum_right -= $A[$i];
        $diff = abs($sum_left - $sum_right);
        if($diff_min > $diff){
            $diff_min = $diff;
        }
    }
   
    return $diff_min;
}

Python


# you can use print for debugging purposes, e.g.
# print "this is a debug message"

def solution(A):
    # write your code in Python 2.7
    sum_left = A[0]
    sum_right = sum(A[1:])
    diff_min = abs(sum_left - sum_right)
    length = len(A)
    i = 1
    for i in range(1, length - 1):
        sum_left += A[i]
        sum_right -= A[i]
        diff = abs(sum_left - sum_right)   
        if(diff_min > diff):
            diff_min = diff
            
    return diff_min

边界条件

这个题目主要的边界条件在于数组只有两个元素,即N=2的时候。

处理好了这个基本就没有问题了, 循环中的len – 1也就是为了正确的N = 2的场景。

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