[数据结构与算法]ARTS006

ARTS是什么？
Algorithm：每周至少做一个 leetcode 的算法题
Review：阅读并点评至少一篇英文技术文章
Tip：学习至少一个技术技巧
Share：分享一篇有观点和思考的技术文章

Algorithm

LC622 设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

注意：重点在判断循环队列为空和为满的条件，可以有两种方式，一是在class中设置length和size成员变量，len表示目前队列的长度，size表示队列的容量大小，如果len==size表示队满，len==0表示队空；二是通过head和tail下标来判断，如果(tail+1)%size==front表示队满，front==-1表示队空。
下面代码用下标的方式判断：

class MyCircularQueue {
private:
    vector<int> data;
    int front;
    int tail;
    int len;

public:
    MyCircularQueue(int k) {
        data.resize(k);
        front = -1;
        tail = -1;
        len = k;
    }
    
    bool enQueue(int value) {
        if(isFull()){
            return false;
        }
        if(isEmpty()){
            front = 0;
        }
        tail = (tail+1)%len;
        data[tail]=value;
        return true;
    }
    
    bool deQueue() {
        if(isEmpty()){
            return false;
        }
        if(front == tail){
            front = -1;
            tail = -1;
        }else{
            front = (front+1)%len;
        }
        return true;
    }
    
    int Front() {
        if(isEmpty())
            return -1;
        return data[front];
    }
    
    int Rear() {
        if(isEmpty())
            return -1;
        return data[tail];
    }
    
    bool isEmpty() {
        return front==-1;
    }
    
    bool isFull() {
        return ((tail+1)%len) == front;
    }
};

Review

How to Return Several Values from a Function in C++
本文主要讲了在C++函数中如何返回多个值？主要讲了三种方式：

1. 函数的多个参数作为返回值
2. 返回一个包含多个值的std:pair或std::tuple
3. 用结构体来实现

Tip

grep用法：
什么是grep？Grep is an acronym that stands for Global Regular Expression Print. grep是全局正则表达式打印，用于在指定文件中搜索字符串。

grep string filename # 在filename中搜索string
grep string filename1 filename2 filename3 # 在filename123中搜索string
grep string * # 在当前文件夹中搜索string
grep -w string filename # 在filename中完整匹配string单词，不包含stringabc等字符串
grep -i string filename # 忽略string的大小写
grep -r string * # 递归搜索当前文件夹及其子文件夹
grep -v string filename # 搜索filename中不含string的所有行
grep -x “string” filename # 在filename中匹配整行为string
grep -A num string filename # 打印匹配及其之后的num行，A--after
grep -B num string filename # 打印匹配及其之前的num行，B--before
grep -C num string filename # 打印匹配及其前后的num行
grep -n string filename # 显示打印的行号
grep -m2 string filename # 如果匹配的行数比较多（log日志），-m2显示打印的行数为2，m--limit

Share

Git配置