私たちは、知性と能力をテストするコディリティに関する 2 つのテスト問題を解決する専門家を探しています。 （私はひどい打撃を受けました、偉大な神々が何をするか見てみましょう）

言うまでもなく、私は Codility に関する 2 つのテスト問題を解き、PHP を使用してそれらを解く機会がありました。プログラムを 2 つ書き、その時点では問題ないと思われましたが、結果を見ると 200 点中 50 点でした。私のプログラムのエラーとその解決策を指摘してくれる専門家を探しています
他には何も言いませんが、本題から始めましょう:
1. N から構成される空でないゼロインデックスの配列 A が与えられます。配列 A の各要素は、?1、0、または 1 です。

0 ≤ P ≤ Q
整数 S が与えられます。目標は、その合計が得られる最大のスライスを見つけることです。

たとえば、次のような整数 S = 2 と配列 A について考えてみましょう:

A[0] = 1
A[1] = 0
A[2] = -1
A[3] = 1
A[4] = 1
A[5] = -1
A[6] = -1
ちょうど 2 つのスライス (0, 4) と (3, 4) があり、その合計は 2 になります。そのような最大のスライスは (0 , 4) であり、その長さは 5 に等しい。

次の関数を作成します。

function solution($A, $S);

N 整数と整数 S からなる空ではないインデックス付き配列 A が与えられた場合、合計が S に等しい最大のスライスの長さを返します。

たとえば、S = 2 かつ次の場合、関数は ?1 を返します。

A[0] = 1
A[1] ] = 0
A[2] = -1
A[3] = 1
A[4] = 1
A[5] = -1
A[6] = -1
説明したように、関数は 5 を返す必要があります

N と S は [1..100,000] の範囲内の整数であると仮定します。
配列 A の各要素は [?1..1] の範囲内の整数です。

期待されます。最悪の場合の時間計算量は O(N) です。
予想される最悪の場合の空間計算量は、入力ストレージを超えます (入力引数に必要なストレージは考慮しません)


。 2.N 個の整数で構成される空でないゼロインデックスの配列 A が与えられます。

配列 A で 1 つのスワップ演算を実行できます。この演算は、0 ≤ I ≤ J
目的は、配列 A を 1 回のスワップ操作だけで非降順に並べ替えられるかどうかを確認することです

たとえば、配列を考えてみましょう。そのようなA:

A[0] = 1
A[1] = 3
A[2] = 5
A[3] = 3
A[4] = 7
値を交換した後、A[2 ] と A[3] を使用すると、非降順でソートされた配列 [1, 3, 3, 5, 7] が得られます。

function solution($A); という関数を書きます。これは、N 整数で構成される空ではないゼロインデックス配列 A が与えられた場合、その配列が 1 回のスワップ操作によって非減少順序に並べ替えられる場合は true を返し、そうでない場合は false を返します。

たとえば、次のようになります:

A[0] = 1
A[1] = 3
A[2] = 5
A[3] = 3
A[4] = 7
関数true を返す必要があります。上で説明したとおりです。

一方、次の配列の場合:

A[0] = 1
A[1] = 3
A[2] = 5
A[3] = 3
A[4] = 4
配列を並べ替える単一のスワップ操作がないため、関数は false を返す必要があります。

次のように仮定します。

N は [1..100,000] の範囲内の整数です。
配列 A の各要素は、[1..1,000,000,000] の範囲内の整数です。
複雑さ:

予想される最悪の場合の時間複雑さは O(N*log(N)) です。
予想される最悪の場合のスペースの複雑さは、入力ストレージを超えて O(N) です (入力引数に必要なストレージは考慮しません)。
入力配列の要素は変更できます。


我的序列：
针对第一题：

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 < $len; $end ++)        {            $total = $total + $A[$end];            if ($total == $S)            {                $temp = $end - $begin +1;                if ($temp > $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 回の回復はすぐに得られます 10 分の有効期限

大きな神の能力は解決できませんか？ 2 番目の問題を見てください。

原代コードの計算結果は良好ですが、#1 の追加は危険です。

結果として $arr = $A; 2 番目のその後の面に、一連の使用期限切れの警告が表示されます

解決対象の理由は、你的応答案不一致の原因です: 時間は 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)

再看第一题
同蠷计算的結果并不错误，只是算法不符合： 時間间复杂度是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;}

感谢版主大驾光临啊。
不过对于第二题，我有不同看法：
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] < $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)

版主第一题的解法，我验证过，确实正确，感觉用这个巧妙的函数去掉一次循环。

我查了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 < $begin) return;      $total += $v;      if($total == $S) {        $temp = $end - $begin + 1;        if ($temp > $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<$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)

时间复杂度的简单判断
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<$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)

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<$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;}

毫无疑问，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] < $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;}