不说了，有机会在codility上做了两个测试题，用php解。我写了两个程序，当时感觉还行，但出来结果一看，200分就得了50分。诚征大神指出我的程序中的错误，以及大神们的solution.
啥都不说了，先上题目：
1. You are given a non-empty zero-indexed array A consisting of N integers. Each element of array A can be ?1, 0 or 1.
A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P + 1] + … + A[Q].
You are given integer S. The goal is to find the largest slice whose sum equals S.
For example, consider integer S = 2 and array A such that:
A[0] = 1
A[1] = 0
A[2] = -1
A[3] = 1
A[4] = 1
A[5] = -1
A[6] = -1
There are exactly two slices (0, 4) and (3, 4) whose sum equals 2. The largest such slice is (0, 4) and its length equals 5.
Write a function:
function solution($A, $S);
that, given a non-empty zero-indexed array A consisting of N integers and an integer S, returns the length of the largest slice whose sum equals S.
The function should return ?1 if there is no such slice.
For example, given S = 2 and:
A[0] = 1
A[1] = 0
A[2] = -1
A[3] = 1
A[4] = 1
A[5] = -1
A[6] = -1
the function should return 5, as explained above.
Assume that:
N and S are integers within the range [1..100,000];
each element of array A is an integer within the range [?1..1].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the sto@本文来源gaodai$ma#com搞$代*码6网搞代gaodaima码rage required for input arguments).
Elements of input arrays can be modified.
2.A non-empty zero-indexed array A consisting of N integers is given.
You can perform a single swap operation in array A. This operation takes two indices I and J, such that 0 ≤ I ≤ J < N, and exchanges the values of A[I] and A[J].
The goal is to check whether array A can be sorted into non-decreasing order by performing only one swap operation.
For example, consider array A such that:
A[0] = 1
A[1] = 3
A[2] = 5
A[3] = 3
A[4] = 7
After exchanging the values A[2] and A[3] we obtain an array [1, 3, 3, 5, 7], which is sorted in non-decreasing order.
Write a function:
function solution($A);
that, given a non-empty zero-indexed array A consisting of N integers, returns true if the array can be sorted into non-decreasing order by one swap operation or false otherwise.
For example, given:
A[0] = 1
A[1] = 3
A[2] = 5
A[3] = 3
A[4] = 7
the function should return true, as explained above.
On the other hand, for the following array:
A[0] = 1
A[1] = 3
A[2] = 5
A[3] = 3
A[4] = 4
the function should return false, as there is no single swap operation that sorts the array.
Assume that:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [1..1,000,000,000].
Complexity:
expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
我的程序：
针对第一题：
function solution($A, $S) { // write your code in PHP5.3 $len = count($A); $slice = -1; for ($begin=0; $begin<$len;$begin++) { $total = 0; for ($end = $begin; $end $slice) { $slice = $temp; } } } } return $slice;}
针对第二题：
function solution($A) { // write your code in PHP5.3 $arr = array(); $len = count($A); $check = false; for ($i=0;$i<$len-1;$i++) { $arr = $A; for ($j=$i+1;$j<$len;$j++) { $temp = $arr[$j]; $arr[$j] = $arr[$i]; $arr[$i] = $temp; $no_decrease = true; for ($k=1;$k< $len;$k++) { if ($arr[$k]<$arr[$k-1]) { $no_decrease = false; } } if ($no_decrease == true) { $check = true; } } } return $check; }
我是被打击惨了，最后200分中只得了50分。大神们，你们能得到多少分？
转载请注明原文链接：诚征大神求解codility上两个测试题，智力和能力大考验！（我是被打击惨了，看看大神们如何吧）
