algorithm008-class02 · wenshengr · Apr 19, 2020 · Apr 19, 2020 · Apr 26, 2020 · Apr 26, 2020
diff --git a/Week_01/MyCircularDeque.php b/Week_01/MyCircularDeque.php
@@ -0,0 +1,173 @@
+<?php
+/**
+ * @filename MyCircularDeque.php
+ * @desc 设计一个双端队列
+ * @date 2020/4/18 20:06
+ * @author: wsr
+ */
+
+class MyCircularDeque {
+
+    /**
+     * 队列
+     * @var array
+     */
+    protected $queue = [];
+
+    /**
+     * 容量
+     * @var int
+     */
+    protected $capacity = 0;
+
+    /**
+     * 队首
+     * @var null
+     */
+    protected $head = 0;
+
+    /**
+     * 队尾
+     * @var null
+     */
+    protected $tail = 0;
+
+
+    /**
+     * Initialize your data structure here. Set the size of the deque to be k.
+     * @param Integer $k
+     */
+    function __construct($k) {
+        $this->capacity = $k + 1;
+    }
+
+    /**
+     * Adds an item at the front of Deque. Return true if the operation is successful.
+     * @param Integer $value
+     * @return Boolean
+     */
+    function insertFront($value) {
+        if ($this->isFull()) {
+            return false;
+        }
+
+        if ($this->isEmpty()) {
+           $this->queue[$this->head] = $value;
+        } else {
+            $this->head = ($this->capacity + $this->head -1) % $this->capacity;
+            $this->queue[$this->head] = $value;
+        }
+        return true;
+    }
+
+    /**
+     * Adds an item at the rear of Deque. Return true if the operation is successful.
+     * @param Integer $value
+     * @return Boolean
+     */
+    function insertLast($value) {
+        if ($this->isFull()) {
+            return false;
+        }
+
+        $this->queue[$this->tail] = $value;
+        $this->tail = ($this->tail + 1) % $this->capacity;
+        return true;
+    }
+
+    /**
+     * Deletes an item from the front of Deque. Return true if the operation is successful.
+     * @return Boolean
+     */
+    function deleteFront() {
+        if ($this->isEmpty()) {
+            return false;
+        }
+        $this->head = ($this->head + 1) % $this->capacity;
+        return true;
+    }
+
+    /**
+     * Deletes an item from the rear of Deque. Return true if the operation is successful.
+     * @return Boolean
+     */
+    function deleteLast() {
+        if ($this->isEmpty()) {
+            return false;
+        }
+
+        $this->head = ($this->tail - 1 + $this->capacity) % $this->capacity;
+        return true;
+    }
+
+    /**
+     * Get the front item from the deque.
+     * @return Integer
+     */
+    function getFront() {
+        if ($this->isEmpty()) {
+            return false;
+        }
+        return $this->queue[$this->head];
+    }
+
+    /**
+     * Get the last item from the deque.
+     * @return Integer
+     */
+    function getRear() {
+        if ($this->isEmpty()) {
+            return false;
+        }
+
+        return $this->queue[$this->tail];
+    }
+
+    /**
+     * Checks whether the circular deque is empty or not.
+     * @return Boolean
+     */
+    function isEmpty() {
+        return count($this->queue) == 0;
+    }
+
+    /**
+     * Checks whether the circular deque is full or not.
+     * @return Boolean
+     */
+    public function isFull() {
+        return $this->capacity == count($this->queue);
+    }
+}
+
+/**
+ * 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();
+ */
+
+$obj = new MyCircularDeque(10);
+$ret_1 = $obj->insertFront('k4');
+$ret_11 = $obj->insertFront('k5');
+$ret_2 = $obj->insertLast('tail_001');
+$ret_3 = $obj->deleteFront();
+$ret_4 = $obj->deleteLast();
+$ret_5 = $obj->getFront();
+$ret_6 = $obj->getRear();
+$ret_7 = $obj->isEmpty();
+$ret_8 = $obj->isFull();
+var_dump($ret_1);
+var_dump($ret_2);
+var_dump($ret_3);
+var_dump($ret_4);
+var_dump($ret_5);
+var_dump($ret_6);
+var_dump($ret_7);
+var_dump($ret_8);
diff --git a/Week_01/NOTE.md b/Week_01/NOTE.md
@@ -1 +1,60 @@
-学习笔记
+【G20200343040108-Week 01】 - 学习总结
+
+### 数据结构与算法的重要性
+业界最具有说明该两者重要性的一个通用公式为：
+
+程序 = 数据结构 + 算法
+
+1. 基本概念
+算    法: 解决程序问题的流程和步骤
+数据结构: 将数据按照某种特定结构保存
+
+2. 二者之间的关系
+数据结构是底层，算法高层；
+数据结构为算法提供服务；
+算法围绕数据结构操作
+
+要想在互联网行业成为一个大牛，就必须具备非常扎实的基础，但算法与数据结构是其中的一小部分，也是不可或缺的重要部分。
+在 - 【程序设计的基础，是内功和心法】
+
+
+### 时间复杂度与空间复杂度分析
+#### 空间换时间
+
+### 数组、链表、跳表、栈、队列、双端队列、优先队列
+#### 1. 数组的特性
+- 访问快（即：时间复杂度为O(1)）
+- 删除、新增（即：时间复杂度为O(n)）
+
+#### 2. 链表的特性
+- 单向链表： node、 上下元素链接用指针、head/next
+- 双向链表： entry
+- 新增节点：前继节点的next指针指向新节点，新节点的next指针指向之前的下一个节点
+- 新增节点：前驱节点的next指针打掉，移到后继的节点去
+- 访问慢（即：时间复杂度为O(n)）
+- 删除、新增（即：时间复杂度为O(1)）
+
+#### 3. 跳表的特性
+- 只能用于链表元素有序的情况
+- 跳表是基于链表的
+- 跳表原理：升维思想 + 空间换时间（索引）
+- 跳表对标的是平衡树（AVL Tree）和二分查找，是一种插入、删除、搜索都是O(logn)的数据结构 
+- 其最大的优势是原理简单、容易实现、方便扩展、效率更高。
+
+#### 4. 栈（stack）的特性
+- 先入后出(LIFO:Last in - First out); 
+- 添加、删除皆为O(1)
+
+#### 5. 队列（Queue）的特性
+- 先入先出(FIFO:Fist in - First out)
+- 添加、删除皆为O(1)
+
+#### 6. 双端队列（Deque:Double-End Queue）的特性
+- 两端都可以进出的队列
+- 添加、删除皆为O(1)
+- 查询时 O(n)--遍历元素
+
+#### 7. 优先队列（Priority Queue）的特性
+- 添加、删除皆为O(1)
+- 取出操作： O(logN)--按照元素的优先级取出
+- 底层具体实现的数据结构较为多样和复杂：heap(堆)、treap等
diff --git a/Week_01/trapping-rain-water.php b/Week_01/trapping-rain-water.php
@@ -0,0 +1,81 @@
+<?php
+/**
+ * @filename trapping-rain-water.php
+ * @desc this is file description
+ * @date 2020/4/19 13:05
+ * @author: wsr
+ */
+class Solution {
+    /**
+     * 根据双指针法
+     * @param $height
+     * @return int|mixed
+     */
+    function trap($height){
+        $max_val = 0;
+        $max_index = 0;
+        for($i=0; $i<count($height); $i++) {
+            if ($height[$i] > $max_val) {
+              $max_val = $height[$i];
+              $max_index = $i;
+            }
+        }
+
+        // 左边到最大高度
+        $left_height = $height[0];
+        $area = 0;
+        for ($i = 0; $i < $max_index; $i++) {
+            if ($left_height < $height[$i]) {
+                $left_height = $height[$i];
+            } else {
+                $area += $left_height - $height[$i];
+            }
+        }
+
+        // 右边到最大高度
+        $right_height = $height[count($height)-1];
+        for ($i = count($height)-1; $i > $max_index; $i--) {
+            if ($right_height < $height[$i]) {
+                $right_height = $height[$i];
+            } else {
+                $area += $right_height - $height[$i];
+            }
+        }
+        return $area;
+
+    }
+
+    /**
+     * 【未测试-待优化】
+     * 根据栈：比栈顶元素小就入栈，如果下一个元素比栈顶元素大，则该部分就是凹槽，即计算面积
+     * @param $height
+     * @return int|mixed
+     */
+    function trap_stack($height){
+//        $stack = new SplStack();
+//        $res = 0;
+//        for($i=0; $i<count($height); $i++) {
+//            if ($stack->isEmpty() || $height[$i] < $height[$stack->top()]) {
+//                $stack->push($i);
+//            } else {
+//                while (!$stack->isEmpty() && $height[$i] > $height[$stack->top()]) {
+//                    $top = $stack->top();
+//                    if (!$stack->isEmpty()) {
+//                        $width = $i - $stack->top();
+//                        $height_new =  min($height[$i], $height[$stack->top()]) - $height[$top];
+//                        $res += $width * $height_new;
+//                    }
+//                }
+//                $stack->push($i);
+//            }
+//        }
+//
+//        return $res;
+
+    }
+}
+
+$obj = new Solution();
+$arr = [0,1,0,2,1,0,1,3,2,1,2,1];
+$result = $obj->trap_stack($arr);
+print_r($result);