数据结构Day6

深藏阁楼爱情的钟 2023-07-09 06:27 31阅读 0赞

### 1、盛水最多的容器 ###

> 给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且 n 的值至少为 2。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]  
> 图中垂直线代表输入数组 \[1,8,6,2,5,4,8,3,7\]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。  
> 示例:  
> 输入: \[1,8,6,2,5,4,8,3,7\]  
> 输出: 49

#define MIN(a, b) (a<b)?a:b
    #define SIZE(na, nb, a, b) ( MIN(na, nb) ) * (b - a)
    
    int maxArea(int* height, int heightSize){ 
        int i = 0, pmin = 0, pmax = heightSize-1;
        int result = 0, temp;
        while(pmin != pmax)
        { 
            temp = SIZE(height[pmin], height[pmax], pmin, pmax);
            if( temp > result)
            { 
                result = temp;
            }
            else
            { 
                if(height[pmin] < height[pmax])
                { 
                    pmin++;
                }
                else
                { 
                    pmax--;
                }
            }
        }
        return result;
    }

![在这里插入图片描述][20200228102952370.png]  
**总结**：这个题目有两种解法，一种是直接暴力循环遍历，算出所有的值，然后比较其中的最大值，这种方式的时间复杂度为O(n2)，很显然不是一个最优的解。第二种方式的实现方法为设置两个指针，一个头指针，一个尾指针，两个指针从两边不断的向中间减小，因为最终的输出为( MIN(na, nb) ) \* (b - a)，因此每一次移动的时候取两个指针的内容最小的那个向内侧移动，而每一次的移动必然会导致这个长方形的底边的值变小，因此这种移动可以保证不会有遗漏的情况出现，而最终的代码实现则很简单，一遍就写好，然后没有任何的错误就直接运行通过了。P.s.另外发现了Leetcode上的执行用时和内存消耗的这个值不是很准确，同样的代码每次执行出来的结果都不一样，按理来说应该每次的测试用例都是一样的，那么也就是说每次的执行时间应该也是一样的才对，很神奇。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]

### 2. 设计循环队列 ###

> 设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。你的实现应该支持如下操作：
> 
> MyCircularQueue(k): 构造器，设置队列长度为 k 。 Front: 从队首获取元素。如果队列为空，返回 -1 。  
> Rear: 获取队尾元素。如果队列为空，返回 -1 。  
> enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。  
> deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。  
> isEmpty(): 检查循环队列是否为空。  
> isFull(): 检查循环队列是否已满。

typedef struct { 
        int * data;
        int head, tail;
        int size;
    } MyCircularQueue;
    
    /** Initialize your data structure here. Set the size of the queue to be k. */
    
    MyCircularQueue* myCircularQueueCreate(int k) { 
        k=k+1;
        MyCircularQueue * CirQ;
        CirQ = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
        CirQ->data = (int *)malloc(sizeof(int) * k);
        CirQ->head = 0;
        CirQ->tail = 0;
        CirQ->size = k;
        return CirQ;
    }
    
    /** Checks whether the circular queue is empty or not. */
    bool myCircularQueueIsEmpty(MyCircularQueue* obj) { 
        return ( (obj->head == obj->tail) ? true : false );
    }
    
    /** Checks whether the circular queue is full or not. */
    bool myCircularQueueIsFull(MyCircularQueue* obj) { 
        return ( (obj->tail+1)%obj->size == obj->head  ) ? true : false;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { 
        if(myCircularQueueIsFull(obj)) 
        { 
            return false;
        }    
        obj->data[obj->tail] = value;
        obj->tail = (obj->tail+1)%obj->size;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool myCircularQueueDeQueue(MyCircularQueue* obj) { 
        if(myCircularQueueIsEmpty(obj))
        { 
            return false;
        }    
        obj->head = (obj->head+1)%obj->size;
        return true;
    }
    
    /** Get the front item from the queue. */
    int myCircularQueueFront(MyCircularQueue* obj) { 
        if(myCircularQueueIsEmpty(obj)) return -1;
        return obj->data[obj->head];
    }
    
    /** Get the last item from the queue. */
    int myCircularQueueRear(MyCircularQueue* obj) { 
        if(myCircularQueueIsEmpty(obj)) return -1;
        return obj->data[(obj->tail + obj->size -1) % obj->size];
    }
    
    void myCircularQueueFree(MyCircularQueue* obj) { 
        if(obj == NULL)        return;
        free(obj->data);
        obj->data = NULL;
        free(obj);
        obj = NULL;
        
    }
    
    /** * Your MyCircularQueue struct will be instantiated and called as such: * MyCircularQueue* obj = myCircularQueueCreate(k); * bool param_1 = myCircularQueueEnQueue(obj, value); * bool param_2 = myCircularQueueDeQueue(obj); * int param_3 = myCircularQueueFront(obj); * int param_4 = myCircularQueueRear(obj); * bool param_5 = myCircularQueueIsEmpty(obj); * bool param_6 = myCircularQueueIsFull(obj); * myCircularQueueFree(obj); */

**总结**：在该题目中，圆形队列实际上是一个很常用的队列类型，在之前的项目中也有所应用，貌似还被其他项目组的拿去当轮子了。圆形队列中实际上最主要的是判断队列是否满和是否空的两个判断条件；判断为空时是判断头尾两个指针重叠时，则该队列为空；判断为满时则是判断头指针和尾指针之间相差队列长度-1，由于是循环队列，因此用了求余。需要注意一点的是在该圆形队列中，队列的长度设置为了输入长度+1的长度，

### 3.用队列实现栈 ###

> 使用队列实现栈的下列操作：
> 
> push(x) – 元素 x 入栈  
> pop() – 移除栈顶元素  
> top() – 获取栈顶元素  
> empty() – 返回栈是否为空  
> 注意:  
> 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

#define QUEUE_MAX_SIZE 10
    
    typedef struct { 
        int data[QUEUE_MAX_SIZE];
        int front;
        int rear;
    } MyStack;
    
    /** Returns whether the stack is full. */
    bool myStackFull(MyStack* obj);
    
    /** Initialize your data structure here. */
    
    MyStack* myStackCreate() { 
        MyStack * st = NULL;
        st = (MyStack *) malloc( sizeof(MyStack) );
        memset(st, 0, sizeof(MyStack) );
        st->front = 0;
        st->rear = 0;
        return st;
    }
    
    /** Push element x onto stack. */
    void myStackPush(MyStack* obj, int x) { 
        obj->front++;
        obj->data[obj->front] = x;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int myStackPop(MyStack* obj) { 
        int pop = 0;
        pop = obj->data[obj->front];
        obj->front--;
        return pop;
    }
    
    /** Get the top element. */
    int myStackTop(MyStack* obj) { 
        return obj->data[obj->front];
    }
    
    /** Returns whether the stack is full. */
    bool myStackFull(MyStack* obj) { 
        return (obj->front - obj->rear == QUEUE_MAX_SIZE-1) ? true : false;
    }
    
    /** Returns whether the stack is empty. */
    bool myStackEmpty(MyStack* obj) { 
        return (obj->front == obj->rear) ? true : false;
    }
    
    void myStackFree(MyStack* obj) { 
        if(obj != NULL)
        { 
            free(obj);
            obj = NULL;
        }
    }
    
    /** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj); */

![在这里插入图片描述][20200301144541830.png]  
**总结**：上述代码为第一次实现时的代码，使用了圆形队列实现了出栈和入栈的操作，代码编译通过也调试成功，但是后来发现实现的方法完全不对，没有用到队列的思想去实现。重新再梳理一下，栈是采用先进后出的实现方式，而队列是采用先进先出的实现方式，那么如果要用队列的方式实现堆栈，则需要先实现一个队列，然后再调用该队列从而实现堆栈。  
最终该程序的代码如下：

typedef struct MyQueue { 
        int *data;
        int head, tail;
        int size, cnt;
    } MyQueue;
    
    MyQueue *MyQueueCreate(int size) { 
        MyQueue *q = (MyQueue *)malloc(sizeof(MyQueue));
        q->data = (int *)malloc(sizeof(int) * size);
        memset(q->data, 0, sizeof(int) * size);
        q->head = q->tail = 0;
        q->cnt = 0;
        q->size = size;
        return q;
    }
    
    void MyQueuePush(MyQueue *obj, int x) { 
        if (obj == NULL) return ;
        if (obj->cnt == obj->size) return ;
        obj->data[obj->tail++] = x;
        if (obj->tail == obj->size) obj->tail -= obj->size;
        obj->cnt += 1;
        return ;
    }
    
    int MyQueuePop(MyQueue *obj) { 
        if (obj == NULL) return 0;
        if (obj->cnt == 0) return 0;
        int temp = MyQueueFront(obj);
        obj->head += 1;
        if (obj->head == obj->size) obj->head -= obj->size;
        obj->cnt -= 1;
        return temp;
    }
    
    int MyQueueFront(MyQueue *obj) { 
        return obj->data[obj->head];
    }
    
    int MyQueueEmpty(MyQueue *obj) { 
        return obj->cnt == 0;
    }
    
    void MyQueueFree(MyQueue *obj) { 
        if (obj == NULL) return ;
        free(obj->data);
        free(obj);
        return ;
    }
    
    
    #define STACK_SIZE 100;
    
    typedef struct { 
        MyQueue *q;
        int size;
    } MyStack;
    
    /** Initialize your data structure here. */
    
    MyStack* myStackCreate() { 
        MyStack * st = NULL;
        st = (MyStack *) malloc( sizeof(MyStack) );
        st->size = STACK_SIZE;
        st->q = MyQueueCreate(st->size);
        return st;
    }
    
    /** Push element x onto stack. */
    void myStackPush(MyStack* obj, int x) { 
        MyQueuePush(obj->q, x);
        int sz = obj->q->cnt;
        int temp;
        while (sz > 1) { 
            temp = MyQueuePop(obj->q);
            MyQueuePush(obj->q, temp);
            sz--;
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int myStackPop(MyStack* obj) { 
        return MyQueuePop(obj->q);
    }
    
    /** Get the top element. */
    int myStackTop(MyStack* obj) { 
        return MyQueueFront(obj->q);
    }
    
    /** Returns whether the stack is empty. */
    bool myStackEmpty(MyStack* obj) { 
        return MyQueueEmpty(obj->q);
    }
    
    void myStackFree(MyStack* obj) { 
        if(obj == NULL)
            return;
        MyQueueFree(obj->q);
        free(obj);
    }
    
    /** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj); */

**总结**：在该程序中，首先程序的前半部分先通过数组的方式实现了队列的基础操作，包括push、pop、empty、top等功能，然后在程序的后半部分实现题目中要求的函数操作，其核心的思路是在入栈的时候将队列的值实现反转，即将最后进入的元素移至队列的头部，即实现了有先进先出到先进后出的功能。其核心代码见下：

while (sz > 1) { 
            temp = MyQueuePop(obj->q);
            MyQueuePush(obj->q, temp);
            sz--;
        }

在上述代码中，当输入一个元素时，将该元素作为一个标杆，依次将队列头部的数据移到该元素的最后，反过来想，也就是将该元素移动到了队列的头部，从而实现了用队列实现栈，该算法的时间复杂度为O(n)，空间复杂度为O(1)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200228101621250.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200228102952370.png]: https://img-blog.csdnimg.cn/20200228102952370.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200228103252716.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200301144541830.png]: https://img-blog.csdnimg.cn/20200301144541830.png