不说了，有机会在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
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 storage 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
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分。大神们，你们能得到多少分？
回复讨论(解决方案) 尼玛，仔细一看，第二题我的程序就有个明显错误，$arr = $a;应该放在第二个 for 的后面。
晕死。
不识英语。。 0分
第天回贴即可获得１０分可用分
就没有大神能来解决么？ 尤其第二道题，还是蛮有难度的。
先看第二题
原代码计算结果是正确的，而#1的补充是错误的！
如果将 $arr = $a; 放在第二个 for 的后面那么将出现一系列的使用未定义变量的警告
解答被扣分的原因在于你的答案不符合：时间复杂度为 o(n*log(n)) 的要求
可以写作这样 var_dump(solution([1,3,5,3,7]));var_dump(solution([1,3,5,3,4]));function solution($a) { $arr = array(); $len = count($a); $check = 0; for($i=0;$i<$len-1;$i++) { if($a[$i+1] 0 && $a[$i-1] <= $a[$i]) $check++; } } return $check == 1;}
bool(true)bool(false)
再看第一题
同样计算的结果并没有错误，只是算法没有符合：时间复杂度为 o(n) 的要求
你使用了双重循环，所以时间复杂度为 o(n*n)
可以用闭包来去掉一重循环 var_dump(solution([1,0,-1,1,1,-1,-1], 2));function solution($a, $s) { $len = count($a); $slice = -1; for ($begin=0; $begin<$len; $begin++) { $total = 0; array_walk($a, function($v, $end, $s) use ($begin, &$slice, &$total) { if($end $slice) $slice = $temp; } }, $s); } return $slice;}
感谢版主大驾光临啊。
不过对于第二题，我有不同看法：
1.你的思路是：检查相邻两个大小，若右边的小于左边的数值，则调换；且这种调换满足i左边的大小关系，则check++.
事实上，我在做题时考虑过这个思路，不过考虑这个例子：1,6,3,4,3,7.只要把6和第二个3调换一下，则可以满足非降数列，最后应该是true。但是，按照你的算法，这个题目返回false。
关键点是：数字的调换可以是很巧妙的一次调换。
2.第二题中，$arr = $a;应该放在第二个for后面，我又验证了一遍，不会出现未定义对象等错误。结果是正确的。
我的思路是每次把$a赋值给$arr，并且采用穷举法把任意两个不同数字调换一次，判断调换后的结果是不是非降数列。是的话，返回true，否的话，不改变check的false值。只要穷举法中，任意一次可以做到，check的值就变为true.
这个思路是正确的，但就是时间复杂度不满足，扣分了。
版主，你看呢？
先看第二题
原代码计算结果是正确的，而#1的补充是错误的！
如果将 $arr = $a; 放在第二个 for 的后面那么将出现一系列的使用未定义变量的警告
解答被扣分的原因在于你的答案不符合：时间复杂度为 o(n*log(n)) 的要求
可以写作这样 var_dump(solution([1,3,5,3,7]));var_dump(solution([1,3,5,3,4]));function solution($a) { $arr = array(); $len = count($a); $check = 0; for($i=0;$i<$len-1;$i++) { if($a[$i+1] 0 && $a[$i-1] <= $a[$i]) $check++; } } return $check == 1;}
bool(true)bool(false)
版主第一题的解法，我验证过，确实正确，感觉用这个巧妙的函数去掉一次循环。
我查了array_walk的介绍，还不能理解版主精妙的思路。版主能否提点两句？
还有，第二个题目，调整后的代码如下，供版主以及其他大神测试用
$arr = array();$len = count($a);$check = false; for ($i=0;$i<$len-1;$i++){ for ($j=$i+1;$j<$len;$j++) { $arr = $a; $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;
再看第一题
同样计算的结果并没有错误，只是算法没有符合：时间复杂度为 o(n) 的要求
你使用了双重循环，所以时间复杂度为 o(n*n)
可以用闭包来去掉一重循环 var_dump(solution([1,0,-1,1,1,-1,-1], 2));function solution($a, $s) { $len = count($a); $slice = -1; for ($begin=0; $begin<$len; $begin++) { $total = 0; array_walk($a, function($v, $end, $s) use ($begin, &$slice, &$total) { if($end $slice) $slice = $temp; } }, $s); } return $slice;}
对于第二题，我只是根据题目的示例而为之，的确没有考虑的 交换的位置不相邻的情况
所以也在纳闷为何是 o(n*log(n)) 呢？o(n)) 不就可以了吗
改写一下 var_dump(solution([1,3,5,3,7]));var_dump(solution([1,3,5,3,4]));var_dump(solution([1,6,3,4,3,7])); function solution($a) { $arr = array(); $len = count($a); $check = 0; for($i=0;$i<$len-1;$i++) { if($a[$i+1] < $a[$i]) { $flag = 0; for($j=$i+1; $j o(n*log(n))
for() {
for() {
code
}
}
==> o(n*n)
仔细测试了一下你的代码。短时间还没有办法理解版主的思路，不过我多测试了几个例子，大部分正确，但依然有问题。
比如这个例子，var_dump(solution([1,6,5,3,3,4,7]));
目测应该无法一次调换成功，但程序返回是正确的。
因为暂时还没有理解版主大神的思路，所以还不好评论，但我一直担心non-decreasing 非降，其中包括等号=的情况，比如下面
if($a[$i] < $a[$j+1]) {
$flag = 1;
break;
}
其中，$a[$i] < $a[$j+1]是否需要等号呢？
我提供的测试例子是不是应该返回false呢？
对于第二题，我只是根据题目的示例而为之，的确没有考虑的 交换的位置不相邻的情况
所以也在纳闷为何是 o(n*log(n)) 呢？o(n)) 不就可以了吗
改写一下 var_dump(solution([1,3,5,3,7]));var_dump(solution([1,3,5,3,4]));var_dump(solution([1,6,3,4,3,7])); function solution($a) { $arr = array(); $len = count($a); $check = 0; for($i=0;$i<$len-1;$i++) { if($a[$i+1] < $a[$i]) { $flag = 0; for($j=$i+1; $j<$len-1; $j++) { if($a[$i] 0 && $a[$i-1] 0 && $a[$i-1] <= $a[$i]) $check++; //交换成功，记录
else return false; //交换失败，返回。 原先漏掉了
if($a[$i] < $a[$j+1]) {
$flag = 1;
break;
}
的意思是找到第一个大于 $a[$i] 的位置
要不要等号无所谓
修改后如下 var_dump(solution([1,3,5,3,7]));var_dump(solution([1,3,5,3,4]));var_dump(solution([1,6,3,4,3,7]));var_dump(solution([1,6,5,3,3,4,7])); function solution($a) { $arr = array(); $len = count($a); $check = 0; for($i=0;$i<$len-1;$i++) { if($a[$i+1] < $a[$i]) { //如果降序 $flag = 0; for($j=$i+1; $j<$len-1; $j++) { //向后找到符合升序的位置 if($a[$i] 0 && $a[$i-1] <= $a[$i]) $check++; //交换成功 else return false; //交换失败 if(! $flag) $i--; // $flag = 0 表示前面的查找是自然结束的，有待商榷 } } return $check == 1;}
毫无疑问，xuzuning 版主是我心目中努力的一个目标，程序算法犀利无比，再一次感受到啊。
啥也别说，肯定100分啊。
对了，我查了一些资料，在引用codility题目时一般都隐去题目，因为涉及到版权问题。所以，xuzuning版主，是不是把题目具体文字隐去？或者其他方式处理？ 只是建议啊。
修改后如下 var_dump(solution([1,3,5,3,7]));var_dump(solution([1,3,5,3,4]));var_dump(solution([1,6,3,4,3,7]));var_dump(solution([1,6,5,3,3,4,7])); function solution($a) { $arr = array(); $len = count($a); $check = 0; for($i=0;$i<$len-1;$i++) { if($a[$i+1] < $a[$i]) { //如果降序 $flag = 0; for($j=$i+1; $j<$len-1; $j++) { //向后找到符合升序的位置 if($a[$i] 0 && $a[$i-1] <= $a[$i]) $check++; //交换成功 else return false; //交换失败 if(! $flag) $i--; // $flag = 0 表示前面的查找是自然结束的，有待商榷 } } return $check == 1;}