コミュニティ 学ぶ ツールライブラリ レジャー
検索
日本語
ホームページ > バックエンド開発 > PHPチュートリアル > 本文

。循環デックの設計

Barbara Streisand
リリース： 2024-09-29 06:13:02
オリジナル
830 人が閲覧しました

. Design Circular Deque

641。デザインサーキュラーデク

難易度: 中

トピック: 配列、リンク リスト、デザイン、キュー

循環両端キュー (deque) の実装を設計します。

MyCircularDeque クラスを実装します:

  • MyCircularDeque(int k) 最大サイズ k で両端キューを初期化します。
  • boolean insertFront() Deque の前に項目を追加します。操作が成功した場合は true を返し、それ以外の場合は false を返します。
  • boolean insertLast() Deque の後ろに項目を追加します。操作が成功した場合は true を返し、それ以外の場合は false を返します。
  • boolean deleteFront() Deque の前から項目を削除します。操作が成功した場合は true を返し、それ以外の場合は false を返します。
  • boolean deleteLast() Deque の後ろから項目を削除します。操作が成功した場合は true を返し、それ以外の場合は false を返します。
  • int getFront() Deque から先頭の項目を返します。デキューが空の場合は -1 を返します。
  • int getRear() Deque から最後の項目を返します。デキューが空の場合は -1 を返します。
  • boolean isEmpty()両端キューが空の場合は true を返し、それ以外の場合は false を返します。
  • boolean isFull() デキューがいっぱいの場合は true を返し、それ以外の場合は false を返します。

例 1:

  • 入力: 
  ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
  [[3], [1], [2], [3], [4], [], [], [], [4], []]
ログイン後にコピー
  • 出力: 
  [null, true, true, true, false, 2, true, true, true, 4]
ログイン後にコピー
  • 説明: 
  MyCircularDeque myCircularDeque = new MyCircularDeque(3);
  myCircularDeque.insertLast(1);  // return True
  myCircularDeque.insertLast(2);  // return True
  myCircularDeque.insertFront(3); // return True
  myCircularDeque.insertFront(4); // return False, the queue is full.
  myCircularDeque.getRear();      // return 2
  myCircularDeque.isFull();       // return True
  myCircularDeque.deleteLast();   // return True
  myCircularDeque.insertFront(4); // return True
  myCircularDeque.getFront();     // return 4
ログイン後にコピー

制約:

  • 1
  • 0
  • insertFront、insertLast、deleteFront、deleteLast、getFront、getRear、isEmpty、isFull に対して最大 2000 回の呼び出しが行われます。

解決策:

配列を使用して両端キュー構造を表すことができます。循環動作を実現するために必要に応じてラップアラウンドして、デクの前後を追跡するのに役立つヘッドとテールのポインタを維持します。

このソリューションを PHP で実装してみましょう: 641。デザイン円形デク

MyCircularDeque クラスの段階的なソリューションを次に示します。

<?php
class MyCircularDeque {
    /**
     * @var array
     */
    private $deque;
    /**
     * @var int
     */
    private $maxSize;
    /**
     * @var int
     */
    private $front;
    /**
     * @var int
     */
    private $rear;
    /**
     * @var int
     */
    private $size;

    /**
     * Initialize your data structure here. Set the size of the deque to be k.
     *
     * @param Integer $k
     */
    function __construct($k) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Adds an item at the front of Deque. Return true if the operation is successful.
     *
     * @param Integer $value
     * @return Boolean
     */
    function insertFront($value) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Adds an item at the rear of Deque. Return true if the operation is successful.
     *
     * @param Integer $value
     * @return Boolean
     */
    function insertLast($value) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Deletes an item from the front of Deque. Return true if the operation is successful.
     *
     * @return Boolean
     */
    function deleteFront() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Deletes an item from the rear of Deque. Return true if the operation is successful.
     *
     * @return Boolean
     */
    function deleteLast() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Get the front item from the deque. If the deque is empty, return -1.
     *
     * @return Integer
     */
    function getFront() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Get the last item from the deque. If the deque is empty, return -1.
     *
     * @return Integer
     */
    function getRear() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Checks whether the deque is empty or not.
     *
     * @return Boolean
     */
    function isEmpty() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Checks whether the deque is full or not.
     * 
     * @return Boolean
     */
    function isFull() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * $obj = MyCircularDeque($k);
 * $ret_1 = $obj->insertFront($value);
 * $ret_2 = $obj->insertLast($value);
 * $ret_3 = $obj->deleteFront();
 * $ret_4 = $obj->deleteLast();
 * $ret_5 = $obj->getFront();
 * $ret_6 = $obj->getRear();
 * $ret_7 = $obj->isEmpty();
 * $ret_8 = $obj->isFull();
 */

?>
ログイン後にコピー

説明：

  1. 初期化:

    • サイズ k の配列を使用して両端キューを初期化し、最初にすべての値を -1 に設定します。
    • 前後のポインタは 0 に初期化されます。
    • size は、両端キュー内の現在の要素数を追跡します。

  2. insertFront($value):

    • isFull() を使用して両端キューがいっぱいかどうかを確認します。
    • そうでない場合は、フロント ポインターをデクリメントします (モジュロを使用した循環ラップアラウンドを使用)。
    • 新しい先頭に値を配置し、サイズを増やします。

  3. insertLast($value):

    • 両端キューがいっぱいかどうかを確認します。
    • そうでない場合は、値を後ろに配置し、後ろのポインタを前に移動します (ラップアラウンドにモジュロを使用します)。
    • サイズを増やします。

  4. deleteFront():

    • isEmpty() を使用して両端キューが空かどうかを確認します。
    • そうでない場合は、フロント ポインター (円形の回り込み) を増加させ、サイズを減少させます。

  5. deleteLast():

    • 両端キューが空かどうかを確認します。
    • そうでない場合は、リア ポインタをデクリメントしてサイズを小さくします。

  6. getFront():

    • 両端キューが空の場合は、-1 を返します。
    • それ以外の場合は、先頭ポインタの要素を返します。

  7. getRear():

    • 両端キューが空の場合は、-1 を返します。
    • それ以外の場合は、現在のリア ポインタの前の要素を返します (リアは次に利用可能な位置を指すため)。

  8. isEmpty():

    • 両端キューが空 (サイズが 0) の場合は true を返します。

  9. isFull():

    • 両端キューがいっぱいの場合 (サイズが maxSize と等しい)、true を返します。

チュートリアルの例 

$myCircularDeque = new MyCircularDeque(3);  // Initialize deque with size 3

$myCircularDeque->insertLast(1);  // return true
$myCircularDeque->insertLast(2);  // return true
$myCircularDeque->insertFront(3); // return true
$myCircularDeque->insertFront(4); // return false, deque is full
echo $myCircularDeque->getRear(); // return 2
echo $myCircularDeque->isFull();  // return true
$myCircularDeque->deleteLast();   // return true
$myCircularDeque->insertFront(4); // return true
echo $myCircularDeque->getFront(); // return 4
ログイン後にコピー

時間計算量:

  • 各操作 (insertFront、insertLast、deleteFront、deleteLast、getFront、getRear、isEmpty、isFull) は、すべて定数時間の配列操作とポインター操作を伴うため、O(1) 時間で実行されます。

空間の複雑さ:

  • 空間計算量は O(k) です。ここで、k は両端キューのサイズです。 deque 配列内の k 要素にスペースを割り当てます。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

  • LinkedIn
  • GitHub

以上が。循環デックの設計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ソース：dev.to
前の記事：Laravel でテスト可能なファサードを作成する 次の記事：RSA 暗号化と復号化によるプラットフォーム間でのデータの保護
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
最新の問題
function_exists() はカスタム関数を決定できません Function test () {return true;} if (function_exists ('test')) {echo "テストは関数です";
から 2024-04-29 11:01:01
0
2
1988
Google Chromeのモバイル版を表示する方法 こんにちは、先生、Google Chrome をモバイル版に変更するにはどうすればよいですか?
から 2024-04-23 00:22:19
0
10
2149
子ウィンドウは親ウィンドウを操作しますが、出力は応答しません。 最初の 2 つの文は実行可能ですが、最後の文は実装できません。
から 2024-04-19 15:37:47
0
1
1815
親ウィンドウには出力がありません document.onclick = function(){ window.opener.document.write('私は子ウィンドウの出力です');
から 2024-04-18 23:52:34
0
1
1707
CSS マインド マッピングに関するコースウェアはどこにありますか? コースウェア
から 2024-04-16 10:10:18
0
0
1725
関連トピック
詳細>
人気のおすすめ
人気のチュートリアル
詳細>
関連するチュートリアル
人気のおすすめ
最新のコース
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート