Leetcode

LeetCodeアルゴリズムの問​​題-PoorPigs（Java実装）



Leetcode Algorithm Problem Poor Pigs



ユエレの本の数です。 235 最初に更新します 248 元の

01読書と準備

本日紹介されたのは、LeetCodeアルゴリズムのEasyレベルの102番目の質問です（注文番号は455です）。 1000個のバケツがあり、そのうちの1つだけに毒が含まれており、残りは毒性がありません。それらはすべて同じに見えます。豚が毒で水を飲むと、15分以内に死んでしまいます。どのバケツにバケツ内の最小量の毒が含まれているかを1時間以内に見つける必要があります。この質問に答えて、その後の一般的なケースのアルゴリズムを記述してください。



フォローアップ：nバレルの水があり、豚が有毒な水を飲み、m分以内に死亡する場合、「毒」バレルを見つけるためにp分で何匹の豚（x）を見つける必要がありますか？毒の入ったバケツは1つだけです。

この問題解決に使用される開発ツールはeclipseであり、jdkで使用されるバージョンは1.8であり、環境はJava言語で記述およびテストされたwin764ビットシステムです。



02問題解決

タイトルの3つのパラメーター、bucketsはバケットの数を示し、minutesToDieは豚が有毒な水を飲むのに必要な分数を示し、minutesToTestはテストする分数を示します。最後の2つのパラメーターを合わせると、テストできる回数であると理解されます。たとえば、豚は有毒な水を15分間飲んだ後に死亡し、60分間テストした後、4回テストできます。タイトルは、返される子豚の数を尋ねます。いくつかの例を見て、ルールを見つけましょう。

状況1：テストの回数は1回です。子豚は2匹います。いくつのバケットをテストできますか？

4つのバケツを1、2、3、4、子豚1と2、子豚2と3としてマークしました。15分後、豚aが死亡した場合、バケツ1は有毒でしたbは死んでおり、バケツ3が有毒であることを示しています豚aとbが死亡している場合、両方の子豚が死亡していない場合、2番目のバケツの水は有毒であり、バケツ4は有毒であることを意味します。テストの数は1で、4つのバケツをテストできる豚が2頭いました。



ケース2：テストの数はまだ2回です。子豚は2匹います。いくつのバケットをテストできますか？

1 2 3

4 5 6

7 8 9

バケットをマークするには、1から9までの数字を使用します。最初の豚aは最初の1、2、および3バレルの水を初めて飲み、2番目の豚aは4、5、および6を飲み、2番目の豚bは最初に飲みます。 7、2回目は2、5、8を飲みます。初めてaとbの両方が死んだ場合、aが初めて死んだ場合は1が有毒であることを意味し、bが2回目に死んだ場合は、2が有毒であることを示します。見下ろし続けると、潜在的に有毒なバケットは実際には座標であり、2次元配列としても理解できます。

上向きに伸ばし続けると、テスト回数は2回になり、3頭の豚を使用すると、最大27バレルの水を測定できます。したがって、3つの関係は、測定可能なバレルの数に等しいmのx乗を満たします。また、mは、テストできる回数に1を加えたものです。逆に、対数を取ることでxの値を取得できます。

public int poorPigs(int buckets, int minutesToDie, int minutesToTest) { int count = minutesToTest/minutesToDie + 1 return (int)Math.ceil(Math.log((double)buckets)/Math.log((double)count)) }

03まとめ

アルゴリズムのトピックは3か月以上経ちましたが、アルゴリズムのタイトル記事です。 102 +記事、パブリックアカウントダイアログの返信[ データ構造とアルゴリズム 】、【 アルゴリズム 】、【 データ構造 】シリーズのどのキーワードでも、記事のコレクションを取得します。

上記はすべての内容です、あなたが良いアイデア、提案または他の質問を持っているならば、あなたは下にメッセージを残すことができます、賞賛、メッセージ、転送は私の最大のリターンとサポートです！