目次
回论论(解決案)
ホームページ バックエンド開発 PHPチュートリアル 私たちは、知性と能力をテストするコディリティに関する 2 つのテスト問題を解決する専門家を探しています。 (私はひどい打撃を受けました、偉大な神々が何をするか見てみましょう)

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

Jun 23, 2016 pm 01:48 PM
偉大なる神 解決する

言うまでもなく、私は 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] < $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] < $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] <= $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] < $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;}
ログイン後にコピー
ログイン後にコピー

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

Python で最小公倍数を見つけるアルゴリズムを作成するにはどうすればよいですか? Python で最小公倍数を見つけるアルゴリズムを作成するにはどうすればよいですか? Sep 19, 2023 am 11:25 AM

Python で最小公倍数を見つけるアルゴリズムを作成するにはどうすればよいですか?最小公倍数は、2 つの数値を割り算できる最小の整数です。数学では、最小公倍数を解くことは基本的な数学的タスクであり、コンピューター プログラミングでは、Python を使用して最小公倍数を解くアルゴリズムを作成できます。以下では、基本的な最小公倍数アルゴリズムを紹介し、具体的なコード例を示します。最小公倍数の数学的定義は次のとおりです。 a が n で割り切れ、b が n で割り切れる場合、n は a と b の最小公倍数です。最低限のことを解決するには

逆行列を計算する簡単な方法 - Numpy の実装 逆行列を計算する簡単な方法 - Numpy の実装 Jan 24, 2024 am 08:47 AM

Numpy は Python のよく知られた科学計算ライブラリであり、大規模な多次元配列と行列を処理するための豊富な関数と効率的な計算方法を提供します。データ サイエンスと機械学習の世界では、逆行列は一般的なタスクです。この記事では、Numpy ライブラリを使用して逆行列をすばやく解く方法と、具体的なコード例を紹介します。まず、Numpy ライブラリをインストールして Python 環境に導入しましょう。 Numpy は、次のコマンドを使用してターミナルにインストールできます: pipinsta

Python を使用して階乗を解くアルゴリズムを実装するにはどうすればよいですか? Python を使用して階乗を解くアルゴリズムを実装するにはどうすればよいですか? Sep 19, 2023 am 10:30 AM

Python を使用して階乗を解くアルゴリズムを実装するにはどうすればよいですか?階乗は数学における重要な概念です。数値が 1 になるまで、数値そのものを乗算してから 1 を引いたものを乗算し、次にそれ自体を乗算してから 1 を引いた値を乗算することを意味します。階乗は通常「!」という記号で表され、例えば5の階乗は5!と表され、計算式は5!=5×4×3×2×1=120となります。 Python では、ループを使用して単純な階乗アルゴリズムを実装できます。サンプルコードを以下に示します。

win7と8.1どちらが良いですか?マスターが教えます win7と8.1どちらが良いですか?マスターが教えます Jul 19, 2023 pm 12:21 PM

Windows システムといえば、多くの人がよく知っていると思いますが、現在私たちの多くは Windows システムを使用していますが、Windows には win7 や win8.1 など複数のシステム バージョンが含まれています。一部のネチズンは、win7 システムと 8.1 システムのどちらを選択すべきか迷っています。win7 と 8.1 のどちらが優れていますか? win7とwin8.1の違いと選択肢をマスターが教えます。 Windows8.1はインターフェイスが豪華です。しかし、改善点のほうが大きいですが、欠点もより大きくなります。より明らかなものには、ぼやけたゲーム フォントやメモリ不足のバグなどが含まれます。メモリがどれほど大きくても、一部のゲームを実行すると、メモリが不足しているため閉じる必要があるというメッセージが表示されます。実際、検査中、記憶は正常でした。 1 つはメモリ管理メカニズムに問題があること、もう 1 つは

C言語プログラミングを使用して最大公約数を解く C言語プログラミングを使用して最大公約数を解く Feb 21, 2024 pm 07:30 PM

タイトル: C 言語プログラミングを使用して最大公約数ソリューションを実装する 最大公約数 (Greatest Common Divisor、略して GCD) とは、2 つ以上の整数を同時に除算できる最大の正の整数を指します。最大公約数を解くことは、一部のアルゴリズムや問題解決に非常に役立ちます。この記事では、最大公約数を求める機能をC言語プログラミングで実装し、具体的なコード例を紹介します。 C 言語では、ユークリッド アルゴリズムを使用して最大値を解くことができます。

初心者からマスターまで: Go 言語プロジェクト開発の経験を共有する 初心者からマスターまで: Go 言語プロジェクト開発の経験を共有する Nov 02, 2023 pm 03:15 PM

初心者からマスターまで: Go 言語プロジェクト開発の経験を共有する 近年、Go 言語はそのシンプルさと効率性のため、開発者の間でますます人気が高まっています。オープンソース プログラミング言語である Go には、強力な同時実行性、静的型チェック、自動メモリ管理という利点があり、多くの大手インターネット企業に好まれています。私はゼロから Go を学び始めた初心者開発者として、プロジェクトの開発プロセスで探索と学習を続け、徐々に Go プロジェクトを自主的に開発できるマスターに成長し、経験と洞察を蓄積しました。大きい

C言語で最大公約数を求める方法を学びましょう C言語で最大公約数を求める方法を学びましょう Feb 21, 2024 pm 11:18 PM

C 言語で最大公約数を見つける方法を学ぶには、具体的なコード例が必要です。最大公約数 (Greatest Common Divisor、略して GCD) は、それらを割り切れる 2 つ以上の整数のうち最大の正の整数を指します。最大公約数は、コンピューター プログラミングで、特に分数の処理、分数の簡略化、整数の最も単純な比などの問題を解くときによく使用されます。この記事では、C言語を使って最大公約数を求める方法と具体的なコード例を紹介します。ユークリッドなどの最大公約数を解く方法はたくさんあります。

C/C++ でモジュラー方程式を解くプログラムを作成しますか? C/C++ でモジュラー方程式を解くプログラムを作成しますか? Sep 12, 2023 pm 02:21 PM

ここではモジュラー方程式に関連した興味深い問題を見てみましょう。 A と B という 2 つの値があるとします。 (AmodX)=B が成り立つような、変数 X が取り得る値の数を見つけなければなりません。 A が 26 で B が 2 だとします。したがって、X の推奨値は {3,4,6,8,12,24} となり、カウントは 6 になります。これが答えです。よりよく理解するためにアルゴリズムを見てみましょう。アルゴリズム possibleWayCount(a,b) - 開始 ifa=b、その後無限の解がある ifa

See all articles