诚征大神求解codility上两个测试题，智力和能力大考验！（我是被打击惨了，看看大神们如何吧）

不说了，有机会在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 $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  

 我是被打击惨了，最后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 0 && $A[$i-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 $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 0 && $A[$i-1]    
bool(true)bool(false)
    
  版主第一题的解法，我验证过，确实正确，感觉用这个巧妙的函数去掉一次循环。  

 我查了array_walk的介绍，还不能理解版主精妙的思路。版主能否提点两句？  

 还有，第二个题目，调整后的代码如下，供版主以及其他大神测试用  
$arr = array();$len = count($A);$check = false; for ($i=0;$i  

   再看第一题   
 同样计算的结果并没有错误，只是算法没有符合：时间复杂度为 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 $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 0 && $A[$i-1]   
bool(true)bool(false)bool(true)
  
  时间复杂度的简单判断  
 for() {  
   code  
 }  
 ==>  O(N)  

 for() {  
   code  
   for() {  
     code  
   }  
 }  
 ==>  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]            $flag = 1;  
           break;  
         }  
 其中，$A[$i]   
 我提供的测试例子是不是应该返回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 0 && $A[$i-1]    
bool(true)bool(false)bool(true)
    
  if($i > 0 && $A[$i-1]  else return false; //交换失败，返回。 原先漏掉了  

 if($A[$i]      $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 0 && $A[$i-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 0 && $A[$i-1]