Reka Bentuk Tindanan Dengan Operasi Penambahan

1381. Reka Bentuk Tindanan Dengan Operasi Penambahan

Kesukaran: Sederhana

Topik: Tatasusunan, Tindanan, Reka Bentuk

Reka bentuk tindanan yang menyokong operasi kenaikan pada elemennya.

Laksanakan kelas CustomStack:

• CustomStack(int maxSize) Memulakan objek dengan maxSize iaitu bilangan maksimum elemen dalam tindanan.
• void push(int x) Menambah x pada bahagian atas tindanan jika tindanan belum mencapai saiz maksimum.
• int pop() Muncul dan mengembalikan bahagian atas tindanan atau -1 jika tindanan kosong.
• void inc(int k, int val) Menambah elemen k bawah tindanan mengikut val. Jika terdapat kurang daripada k elemen dalam tindanan, tambah semua elemen dalam tindanan.

Contoh 1:

• Input:

  ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
  [[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]

• Output:

  [null,null,null,2,null,null,null,null,null,103,202,201,-1]

• Penjelasan:

   CustomStack stk = new CustomStack(3); // Stack is Empty []
   stk.push(1);                          // stack becomes [1]
   stk.push(2);                          // stack becomes [1, 2]
   stk.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
   stk.push(2);                          // stack becomes [1, 2]
   stk.push(3);                          // stack becomes [1, 2, 3]
   stk.push(4);                          // stack still [1, 2, 3], Do not add another elements as size is 4
   stk.increment(5, 100);                // stack becomes [101, 102, 103]
   stk.increment(2, 100);                // stack becomes [201, 202, 103]
   stk.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
   stk.pop();                            // return 202 --> Return top of the stack 202, stack becomes [201]
   stk.pop();                            // return 201 --> Return top of the stack 201, stack becomes []
   stk.pop();                            // return -1 --> Stack is empty return -1.

Kekangan:

• 1 <= maksSaiz, x, k <= 1000
• 0 <= val <= 100
• Maksimum 1000 panggilan akan dibuat untuk setiap kaedah kenaikan, tolak dan pop setiap satu secara berasingan.

Petunjuk:

1. Gunakan tatasusunan untuk mewakili tindanan. Tekan akan menambah integer baharu pada tatasusunan. Pop mengalih keluar elemen terakhir dalam tatasusunan dan kenaikan akan menambah val pada elemen k pertama tatasusunan.
2. Penyelesaian ini dijalankan dalam O(1) setiap tolak dan pop dan O(k) setiap kenaikan.

Penyelesaian:

Kita boleh mengikuti pelaksanaan tindanan biasa tetapi dengan kaedah tambahan yang membenarkan penambahan elemen k bawah dengan nilai yang diberikan. Operasi kenaikan akan berulang melalui elemen k pertama tindanan dan menambah nilai pada setiap satu.

Kami akan melaksanakan tindanan ini dalam PHP 5.6, menggunakan tatasusunan untuk mewakili tindanan. Operasi teras ialah:

1. tekan(x): Menambah elemen x pada bahagian atas tindanan, jika tindanan belum mencapai Saiz maksimumnya.
2. pop(): Mengalih keluar elemen atas tindanan dan mengembalikannya. Jika tindanan kosong, kembalikan -1.
3. increment(k, val): Menambah nilai val pada elemen k pertama dalam tindanan, atau pada semua elemen jika tindanan mengandungi kurang daripada k elemen.

Mari laksanakan penyelesaian ini dalam PHP: 1381. Reka Bentuk Tindanan Dengan Operasi Penambahan

<?php
class CustomStack {
    /**
     * @var array
     */
    private $stack;
    /**
     * @var int
     */
    private $maxSize;
    /**
     * Constructor to initialize the stack with a given maxSize
     *
     * @param Integer $maxSize
     */
    function __construct($maxSize) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }

    /**
     * Push an element to the stack if it has not reached the maxSize
     *
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }

    /**
     * Pop the top element from the stack and return it, return -1 if the stack is empty
     *
     * @return Integer
     */
    function pop() {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }

    /**
     * Increment the bottom k elements of the stack by val
     *
     * @param Integer $k
     * @param Integer $val
     * @return NULL
     */
    function increment($k, $val) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }
}

/**
 * Your CustomStack object will be instantiated and called as such:
 * $obj = CustomStack($maxSize);
 * $obj->push($x);
 * $ret_2 = $obj->pop();
 * $obj->increment($k, $val);
 */

// Example usage
$customStack = new CustomStack(3);  // Stack is Empty []
$customStack->push(1);              // stack becomes [1]
$customStack->push(2);              // stack becomes [1, 2]
echo $customStack->pop() . "\n";    // return 2, stack becomes [1]
$customStack->push(2);              // stack becomes [1, 2]
$customStack->push(3);              // stack becomes [1, 2, 3]
$customStack->push(4);              // stack still [1, 2, 3], maxSize is 3
$customStack->increment(5, 100);    // stack becomes [101, 102, 103]
$customStack->increment(2, 100);    // stack becomes [201, 202, 103]
echo $customStack->pop() . "\n";    // return 103, stack becomes [201, 202]
echo $customStack->pop() . "\n";    // return 202, stack becomes [201]
echo $customStack->pop() . "\n";    // return 201, stack becomes []
echo $customStack->pop() . "\n";    // return -1, stack is empty
?>




<h3>
  
  
  Penjelasan:
</h3>

<ol>
<li>
<p><strong>tolak($x)</strong>:</p>

<ul>
<li>Kami menggunakan array_push untuk menambah elemen pada tindanan. Kami menyemak sama ada saiz tindanan semasa adalah kurang daripada maxSize. Jika ya, kami menolak elemen baharu.</li>
</ul>
</li>
<li>
<p><strong>pop()</strong>:</p>

<ul>
<li>Kami menyemak sama ada tindanan kosong menggunakan empty($this->stack). Jika ia tidak kosong, kami memaparkan elemen teratas menggunakan array_pop dan mengembalikannya. Jika kosong, kami kembalikan -1.</li>
</ul>
</li>
<li>
<p><strong>kenaikan($k, $val)</strong>:</p>

<ul>
<li>Kami mengira minimum k dan saiz tindanan semasa untuk menentukan bilangan elemen untuk dinaikkan. Kami kemudian melingkari elemen ini, menambah val pada setiap elemen.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Contoh Pelaksanaan:
</h3>

<p>Untuk operasi input:<br>
</p>

<pre class="brush:php;toolbar:false">["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]

Outputnya ialah:

[null, null, null, 2, null, null, null, null, null, 103, 202, 201, -1]

Output ini adalah berdasarkan perkara berikut:

• tekan(1): Tindanan menjadi [1]
• tekan(2): Tindanan menjadi [1, 2]
• pop(): Mengembalikan 2, tindanan menjadi [1]
• tekan(2): Tindanan menjadi [1, 2]
• tekan(3): Tindanan menjadi [1, 2, 3]
• tekan(4): Tindanan kekal [1, 2, 3] (Saiz maksimum dicapai)
• kenaikan(5, 100): Tindanan menjadi [101, 102, 103]
• kenaikan(2, 100): Tindanan menjadi [201, 202, 103]
• pop(): Mengembalikan 103, tindanan menjadi [201, 202]
• pop(): Mengembalikan 202, tindanan menjadi [201]
• pop(): Mengembalikan 201, tindanan menjadi []
• pop(): Pulangan -1 (timbunan kosong)

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Reka Bentuk Tindanan Dengan Operasi Penambahan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!