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

Question

phpcodility智力

Answer 1

尼玛，仔细一看，第二题我的程序就有个明显错误，$arr = $A;应该放在第二个 for 的后面。
晕死。

Answer 2

先看第二题
原代码计算结果是正确的，而#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] < $A[$i]) {
      $temp = $A[$i+1];
      $A[$i+1] = $A[$i];
      $A[$i] = $temp;
      if($i > 0 && $A[$i-1] <= $A[$i]) $check++;
    }
  }     
  return $check == 1;
}bool(true)
bool(false)

Answer 3

再看第一题
同样计算的结果并没有错误，只是算法没有符合：时间复杂度为 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 < $begin) return;
      $total += $v;
      if($total == $S) {
        $temp = $end - $begin + 1;
        if ($temp > $slice) $slice = $temp;
      }
    }, $S);
  }
  return $slice;
}

Answer 4

感谢版主大驾光临啊。
不过对于第二题，我有不同看法：
1.你的思路是：检查相邻两个大小，若右边的小于左边的数值，则调换；且这种调换满足i左边的大小关系，则check++.
事实上，我在做题时考虑过这个思路，不过考虑这个例子：1,6,3,4,3,7.只要把6和第二个3调换一下，则可以满足非降数列，最后应该是true。但是，按照你的算法，这个题目返回false。关键点是：数字的调换可以是很巧妙的一次调换。2.第二题中，$arr = $A;应该放在第二个for后面，我又验证了一遍，不会出现未定义对象等错误。结果是正确的。
我的思路是每次把$A赋值给$arr，并且采用穷举法把任意两个不同数字调换一次，判断调换后的结果是不是非降数列。是的话，返回true，否的话，不改变check的false值。只要穷举法中，任意一次可以做到，check的值就变为true.这个思路是正确的，但就是时间复杂度不满足，扣分了。版主，你看呢？

Answer 5

版主第一题的解法，我验证过，确实正确，感觉用这个巧妙的函数去掉一次循环。我查了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;

Answer 6

对于第二题，我只是根据题目的示例而为之，的确没有考虑的 交换的位置不相邻的情况
所以也在纳闷为何是 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] < $A[$j+1]) {
          $flag = 1;
          break;
        }
      }
      $temp = $A[$j];
      $A[$j] = $A[$i];
      $A[$i] = $temp;
      if($i > 0 && $A[$i-1] <= $A[$i]) $check++;
      if(! $flag) $i--;
    }
  }
  return $check == 1;
}bool(true)
bool(false)
bool(true)

Answer 7

时间复杂度的简单判断
for() {
  code
}
==>  O(N)for() {
  code
  for() {
    code
  }
}
==>  O(N*log(N))for() {
  for() {
    code
  }
}
==>  O(N*N)

Answer 8

仔细测试了一下你的代码。短时间还没有办法理解版主的思路，不过我多测试了几个例子，大部分正确，但依然有问题。
比如这个例子，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呢？

Answer 9

if($i > 0 && $A[$i-1] <= $A[$i]) $check++; //交换成功，记录
else return false; //交换失败，返回。 原先漏掉了if($A[$i] < $A[$j+1]) {
    $flag = 1;
    break;
}
的意思是找到第一个大于 $A[$i] 的位置
要不要等号无所谓

Answer 10

修改后如下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] < $A[$j+1]) {
          $flag = 1;
          break;
        }
      }
      $temp = $A[$j]; //交换
      $A[$j] = $A[$i];
      $A[$i] = $temp;
      if($i > 0 && $A[$i-1] <= $A[$i]) $check++; //交换成功
      else return false; //交换失败
      if(! $flag) $i--; // $flag = 0 表示前面的查找是自然结束的，有待商榷
    }
  }
  return $check == 1;
}

Answer 11

毫无疑问，xuzuning 版主是我心目中努力的一个目标，程序算法犀利无比，再一次感受到啊。
啥也别说，肯定100分啊。对了，我查了一些资料，在引用codility题目时一般都隐去题目，因为涉及到版权问题。所以，xuzuning版主，是不是把题目具体文字隐去？或者其他方式处理？ 只是建议啊。

Answer 12

试试[6,3,4,2,7],这是可以的，交换6,2，但程序结果是false