欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基础班:第三节

程序员文章站 2022-07-12 19:19:55
...

一.用数组结构实现双端队列

什么是双端队列(或双向队列)Deque,全名double-ended queue?

  • 即元素可以在队列的任意一段入队或出队,如果我们把这些方法叫做insertLeft()和insertRight(),以及removeLeft()和removeRight()。
  • 如果严格禁止调用insertLeft()和removeLeft()方法(或禁用右段的操作),双端队列功能就和栈一样。
  • 禁止调用insertLeft()和removeRight()(或相反的另一对方法),它的功能就和队列一样了。
  • 双端队列与栈或队列相比,是一种多用途的数据结构。
<?php
class DoubleEndedQueue
{ 
    public $queue = array(); 
    
    /**(尾部)入队  **/ 
    public function addLast($value)  
    { 
        return array_push($this->queue,$value); 
    } 
    /**(尾部)出队**/ 
    public function removeLast()  
    { 
        return array_pop($this->queue); 
    } 
    /**(头部)入队**/ 
    public function addFirst($value)  
    { 
        return array_unshift($this->queue,$value); 
    } 
    /**(头部)出队**/ 
    public function removeFirst()  
    { 
        return array_shift($this->queue); 
    } 
    /**清空队列**/ 
    public function makeEmpty()  
    { 
        unset($this->queue);
    } 
    
    /**获取列头**/
    public function getFirst()  
    { 
        return reset($this->queue); 
    } 
 
    /** 获取列尾 **/
    public function getLast()  
    { 
        return end($this->queue); 
    }
 
    /** 获取长度 **/
    public function getLength()  
    { 
        return count($this->queue); 
    }
    
}

二.实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作

要求:
  • pop、push、getMin操作的时间复杂度都是O(1)
  • 设计的栈类型可以使用现成的栈结构
class GetMinStackService
{
    public function __construct(&$data, &$minArray)
    {
        $this->data = &$data; // 栈
        $this->minArray = &$minArray; // 最小值栈
    }

    // 出栈操作
    public function pop()
    {
        // 弹出最小值栈
        array_pop($this->minArray);
        // 弹出栈
        array_pop($this->data);
    }

    // 入栈操作
    public function push($number)
    {
        // 压入最小值栈
        if (count($this->minArray) == 0) {
            array_push($this->minArray, $number);
        } else {
            $min = end($this->minArray) > $number ? $number : end($this->minArray); 
            array_push($this->minArray, $min);
        }
        // 压入栈
        array_push($this->data, $number); 
    }

    // 获取最小值
    public function getMin()
    {
        return end($this->minArray);
    }
}

三.如何仅用队列结构实现栈结构?如何仅用栈结构实现队列结构?

3.1 如何仅用队列结构实现栈结构

class TwoQueuesStack {

    public function __construct(&$data, &$help)
    {
        $this->data = &$data;
        $this->help = &$help;
    }

    // 出栈
    public function pop()
    {
        // data队列 倒入 到help队列
        while (count($this->data) > 1) {
            array_push($this->help, array_shift($this->data));
        }
        array_shift($this->data);
        $this->swap();
    }

    // 入栈
    public function push($number)
    {
        array_push($this->data, $number);
    }

    public function swap()
    {
        // help队列 倒入 data队列
        while (count($this->help) > 0 ) {
            array_push($this->data, array_shift($this->help));
        }
    }
}

3.2 如何仅用栈结构实现队列结构

class TwoStacksQueue {

    public function __construct(&$data, &$help)
    {
        $this->data = &$data;
        $this->help = &$help;
    }

    // 入队
    public function push($number)
    {
        array_push($this->data, $number);
    }

    // 出队
    public function shift()
    {
        // data栈 倒入 到 help 栈
        while (count($this->data) > 1) {
            array_push($this->help, array_pop($this->data));
        }

        // 弹出最后一个
        array_pop($this->data);

        // help 栈 倒入 到data栈
        while (count($this->help) > 0) {
            array_push($this->data, array_pop($this->help));
        }
    }
}

四.猫狗队列

【题目】 宠物、狗和猫的类如下:
public class Pet { 
	private String type;
	
	public Pet(String type) { 
		this.type = type; 
	}
	
	public String getPetType() { 
		return this.type; 
	}
}

public class Dog extends Pet { 
	public Dog() { 
		super("dog");
	} 
}

public class Cat extends Pet { 
	public Cat() { 
		super("cat"); 
	} 
}
实现一种狗猫队列的结构,要求如下:
  • 用户可以调用add方法将cat类或dog类的实例放入队列中;
  • 用户可以调用pollAll方法,将队列中所有的实例按照进队列
    的先后顺序依次弹出;
  • 用户可以调用pollDog方法,将队列中dog类的实例按照
    进队列的先后顺序依次弹出;
  • 用户可以调用pollCat方法,将队列中cat类的实
    例按照进队列的先后顺序依次弹出;
  • 用户可以调用isEmpty方法,检查队列中是
    否还有dog或cat的实例;
  • 用户可以调用isDogEmpty方法,检查队列中是否有dog
    类的实例;
  • 用户可以调用isCatEmpty方法,检查队列中是否有cat类的实例。
父类Pet
namespace App\Services;

class Pet
{
    private $type;

    public function __construct(string $type)
    {
        $this->type = $type;
    }

    public function getPetType() : string {

        return $this->type;
    }

    public function __toString()
    {

        return json_encode([
                'type' => $this->type
            ]);
    }
}
继承父类Pet的Cat类和Dog类
namespace App\Services;

use App\Services\Pet;

class Dog extends Pet
{
    public function __construct()
    {
        parent::__construct('dog');
    }
    
}
namespace App\Services;

use App\Services\Pet;

class Cat extends Pet
{
    public function __construct()
    {
        parent::__construct('cat');
    }
}
Pet包装类 PetWrapper, $id 记录入队的先后顺序
namespace App\Services;

class PetWrapper
{
    protected $pet;

    protected $id;

    public function __construct(Pet $pet, int $id)
    {
        $this->pet = $pet;

        if (is_null($id)) {
            $id = time();
        }

        $this->id = $id;
    }

    // 出队时返回对象
    public function getPet() : Pet
    {

        return $this->pet;
    }

    public function getId() : int
    {

        return $this->id;
    }

    public function getEnterPetType() : String
    {

        return $this->pet->getPetType();
    }

    public function __toString()
    {
        return json_encode([
            'id' => $this->id,
            'type' => $this->pet->getPetType()
            ]);
    }

}
猫狗队列

上面的类Pet、Cat、Dog、PetWrapper都是准备。

use App\Services\Cat;
use App\Services\Dog;
use App\Services\Pet;
use App\Services\PetWrapper;

class DogCatQueue
{
    protected $dogQ;

    protected $catQ;

    protected $count;

    public function __construct()
    {
        $this->dogQ = new \SplQueue();
        $this->catQ = new \SplQueue();
        $this->count = 0;
    }

    // 用户可以调用add方法将cat类或dog类的实例放入队列中
    public function add(Pet $pet)
    {
        if (strcmp($pet->getPetType(), 'dog') === 0) {

            $this->dogQ->enqueue(new PetWrapper($pet, $this->count++));
        } else if (strcmp($pet->getPetType(), 'cat') === 0) {
            $this->catQ->enqueue(new PetWrapper($pet, $this->count++));

        } else {
            throw new \Exception("Error, neither dog or cat");
        }
    }


    // 用户可以调用pollAll方法,
    // 将队列中所有的实例按照进队列的先后顺序依次弹出
    public function pollAll() : Pet
    {
        // 一.狗队列不为空 且 猫队列也不为空
        if (! $this->isDogEmpty() && ! $this->isCatEmpty()) {
     
            $minIdOfDogQ = $this->front($this->dogQ)->getId();
            $minIdOfCatQ = $this->front($this->catQ)->getId();

            // 比较猫队列队头的属性id 与 狗队列队头的属性id 大小
            // 谁小谁被弹出队列
            if ($minIdOfCatQ < $minIdOfDogQ) {

                return $this->pollCat();
            } else {

                return $this->pollDog();
            }
        // 二.狗队列为空 且 猫队列不为空
        } else if ($this->isDogEmpty() && ! $this->isCatEmpty()) {

            return $this->pollCat();
        // 三.狗队列不为空 且 猫队列为空   
        } else if (! $this->isDogEmpty() && $this->isCatEmpty()) {
            
            return $this->pollDog();
        }


        // 四.猫狗总队列为空
        throw new \Exception('猫狗队列为空');
    }


    // 用户可以调用pollDog方法,将队列中dog类的实例按照
    // 进队列的先后顺序依次弹出;
    public function pollDog() : Dog
    {
        if (! $this->isDogEmpty()) {
            $this->count--; // 队列数量-1

            return $this->dogQ->dequeue()->getPet();
        }

        throw new \Exception('dog queue is empty');
    }   


    // 用户可以调用pollCat方法,将队列中cat类的实
    // 例按照进队列的先后顺序依次弹出; 
    public function pollCat() : Cat
    {
        if (! $this->isCatEmpty()) {
            $this->count--; // 队列数量-1

            return $this->catQ->dequeue()->getPet();
        }

        throw new \Exception('cat queue is empty');
    }

    // 用户可以调用isEmpty方法,
    // 检查队列中是否还有dog或cat的实例;
    public function isEmpty() : bool
    {

        return  $this->isDogEmpty() && $this->isCatEmpty();
    }

    // 用户可以调用isDogEmpty方法,
    // 检查队列中是否有dog类的实例; 
    public function isDogEmpty() : bool
    {

        return $this->dogQ->isEmpty();
    }

    // 用户可以调用isCatEmpty方法,
    // 检查队列中是否有cat类的实例
    public function isCatEmpty() : bool
    {

        return $this->catQ->isEmpty();
    }




    public function __toString() : String
    {
        // 打印猫队列
        $stringCat = "[cat queue]: " . PHP_EOL;
        foreach ($this->catQ as $petWrapper) {
            $stringCat .= $petWrapper . PHP_EOL;
        }

        // 打印狗队列
        $stringDog = "[dog queue]: " . PHP_EOL;
        foreach ($this->dogQ as $petWrapper) {
            $stringDog .= $petWrapper . PHP_EOL;
        }

        return $stringCat . $stringDog;
    }


    // 返回队列队头
    public function front (\SplQueue $q) : PetWrapper 
    {
        return $q->offsetGet(0);
    }
}

五.转圈打印矩阵

题目: 给定一个整型矩阵matrix,请按照转圈的方式打印它。

例如:

 1 	2 	3 	4 
 5 	6 	7 	8 
 9 	10 	11 	12 
 13	14	15 	16 

打印结果为:1,2,3,4,8,12,16,15,14,13,9,5,6,7,11, 10

要求: 额外空间复杂度为O(1)。
class PrintMatrixSpiraOrder
{
    // 构建矩阵
    public function createMatrix (int $number) : Array
    {
        // 判断能否构成方形矩阵
        $fixeArraySqrt = sqrt($number);
        $fixeArraySqrtTmp = ceil($fixeArraySqrt);
        if ($fixeArraySqrt != $fixeArraySqrtTmp) {
            
            throw new \Exception('数组构不成方形矩阵');
        }

        // 构建一维数组
        for ($i=0; $i < $number; $i++) { 
            $fixeArray[$i] = $i + 1;
        }
        // 构成矩阵(二维数组)
        $matrix = [];
        for ($i=0; $i < 16; $i++) { 
            $firstIndex = floor($i / $fixeArraySqrt);
            $secondIndex = $i % $fixeArraySqrt;

            $matrix[$firstIndex][$secondIndex] = $fixeArray[$i];
        }

        return $matrix;
    }

    public function spiralOrderPrint($matrix)
    {
        $tR = 0; // 左上角顶点行坐标
        $tC = 0; // 左上角顶点列坐标
        $dR = count($matrix) - 1; // 右下角行坐标
        $dC = count($matrix[0]) - 1; // 右下角列坐标
        while ($tR <= $dR && $tC <= $dC) {
            $this->printEdge($matrix, $tR++, $tC++, $dR--, $dC--);
        }
    }


    public function printEdge($matrix, $tR, $tC, $dR, $dC)
    {
        // 一行
        if ($tR == $dR) {
            die;
            for ($i=$tC; $i < $dC; $i++) { 
                echo $matrix[$tR][$i];echo '<br>';
            }
        // 一列
        } else if ($tC == $dC) {
            die;
            for ($i=$tR; $i < $dR; $i++) { 
                echo $matrix[$i][$tR];echo '<br>';
            }
        // 多行多列
        } else {
            $curR = $tR;
            $curC = $tC;

            // 上行(行相等,列+1)
            while ($curC != $dC) {
                echo $matrix[$curR][$curC++]; echo '<br>';
            }
            
            // 右列 (列相等,行+1)
            while ($curR != $dR) {
                echo $matrix[$curR++][$curC]; echo '<br>';
            }
            
            // 下行 (行相等,列-1)
            while ($curC != $tC) {
                echo $matrix[$curR][$curC--]; echo '<br>';
            }
            
            // 左列 (列相等,行-1)
            while ($curR != $tR) {
                echo $matrix[$curR--][$curC]; echo '<br>';
            }

        }

    }

}

六.旋转正方形矩阵

题目: 给定一个整型正方形矩阵matrix,请把该矩阵调整成顺时针旋转90度的样子。
要求: 额外空间复杂度为O(1)。
    public function rotateEdgePrint(&$matrix)
    {

        $tR = 0; // 左上角顶点行坐标
        $tC = 0; // 左上角顶点列坐标
        $dR = count($matrix) - 1; // 右下角行坐标
        $dC = count($matrix[0]) - 1; // 右下角列坐标
        while ($tR <= $dR && $tC <= $dC) {
            $this->rotateEdge($matrix, $tR++, $tC++, $dR--, $dC--);
        }
    }
    public function rotateEdge(&$matrix, $tR, $tC, $dR, $dC)
    {
        $times = $dR - $tR;
        $tmp = 0;

        for ($i=0; $i < $times; $i++) { 
            $tmp = $matrix[$tR][$tC + $i];
            $matrix[$tR][$tC + $i] = $matrix[$dR - $i][$tC];
            $matrix[$dR - $i][$tC] = $matrix[$dR][$dC - $i];
            $matrix[$dR][$dC - $i] = $matrix[$tR + $i][$dC];
            $matrix[$tR + $i][$dC] = $tmp;
        }
    }

七.“之”字形打印矩阵

题目: 给定一个矩阵matrix,按照“之”字形的方式打印这个矩阵,

例如:

1 	2 	3 	4
5 	6 	7 	8
9 	10 	11 	12

“之”字形打印的结果为:1,2,5,9,6,3,4,7,10,11,8,12
额外空间复杂度为O(1)。