前言：

本系列内容将记录我跟随左神（左程云老师）的课程学习算法的过程，首先要感谢左神，太厉害了，在他的课上真的收获很多。博客内容与左神的课程高度重合，主要是我对于学习过程的梳理，一些思考和我在写代码过程中踩过的一些坑的总结，另外因为左程云老师的视频里都是java实现，如果想要看C++实现，本博客代码可供参考（都是本人认认真真写过改过的，如有错误，欢迎指正），下面我们开始。

二分搜索：

让我们从二分搜索开始这段旅程吧！

基础实现：

先看代码

int binary_search(vector<int>& arr,int num){ //传入的数组必须是有序的，此处默认为升序的。 int n=arr.size(); int ans=-1; if(n==0) return -1; int l=0,r=n-1; while(l<=r){ int m=l+(r-l)/2; //此处还可以写为m=(l+r)/2,区别为第一种写法可以防止数组很大时m溢出，还有m=l+(r-l)>>1,这个写法就是用位运算代替除2. if(num==arr[m]){ ans=m; return m; } else if(arr[m]>num){ r=m-1; } else{ l=m+1; } } return ans; }

小的注意点会在代码中标注，接下来我们梳理一下思路：

首先传入一个有序数组，取得数组的左右边界位置，计算出中间位置->将中间位置的数与要找的数比较，等于直接返回，大于右侧向左缩，小于左侧向右缩，直到找到该数或左边界等于右边界（全部找完，没找到）->返回-1/位置。

由该类型的题目再扩展一下，二分搜索还可在有序数组中找某个范围->找大于等于某数的最左位置或小于等于某数的最大位置（其实就是找数组中大于等于指定数的最小数/小于等于指定数的最大数）。

此处以找大于等于该数的最左位置为例：

int find_left(vector<int> arr,int num){ int l=0,r=arr.size()-1; int m=0; int ans=-1; while(l<=r){ m=l+(r-l)/2; if(arr[m]>=num){ r=m-1; ans=m; //找到一个大于等于该数的就记一下，后面再找到的一定是这个位置再往左的 } else{ l=m+1; } } return ans; }

再扩展，二分搜索在无序数组中的应用呢？那就是------寻找峰值问题：寻找给定数组中任意一个峰值（比左右两边的数都大的数，左右边界也可做峰值）（前提：数组中任意相邻两数不相等）

寻找峰值问题：

int find_peak(vector<int> arr){ int n=arr.size(); if(n==1) return 0; //如果只有一个元素，0位置的就是峰值 if(arr[n-1]>arr[n-1]) return n-1; //检查两侧是否存在峰值 if(arr[0]>arr[1]) return 0; int l=1,r=n-2,m=0; //能走到这里就说明两侧无峰值，此时整个数组范围内两侧的趋势为左侧上升右侧下降，峰值必在[l,r]中。 int ans=-1; while(l<=r){ m=l+(r-l)/2; if(arr[m]<arr[m+1]) l=m+1; //范围缩小到[m+1,r] else if(arr[m]<arr[m-1]) r=m-1; //范围缩小到[l,m-1] else{ //上面两条都不满足，说明m比两侧的值都大，m处为峰值，跳出循环 ans=m; break; } return ans; } }

这个题自己在纸上画一画趋势会直观很多，感受一下它的妙处吧

栈和队列 的链表，数组实现：

这部分之前应该还有一部分链表，但我现在不太想写，后面会补上，我们先看栈和队列！

链表实现队列：

struct QueueNode{ int data; QueueNode* next; QueueNode(int val):data(val),next(nullptr){}//链表节点结构体 的构造函数 初始化列表写法 //作用： 在创建QueueNode对象时，直接把传入的val赋值给data成员，同时把next指针初始化为空，避免出现未初始化的野指针。 }; class LinkedQueue{ private: QueueNode* front; QueueNode* rear; int size; public: LinkedQueue(){ //构造函数，用于初始化空队列 front=nullptr; rear=nullptr; size=0; } bool is_empty(){ if(size==0) return true; return false; } void push(int val){ QueueNode* newNode=new QueueNode(val); if(is_empty()){ front=newNode; rear=newNode; } else{ rear->next=newNode; rear=rear->next; } size++; } void pop(){ if(is_empty()){ cout<<"队列为空，无法出队！"<<endl; return; } QueueNode* temp=front; front=front->next; delete temp; size--; if(front==nullptr){ //如果删除的是最后一个节点，那删前front->next是指向空的，front=front->next后front就变空了 rear=nullptr; //删后front指向空了，可rear仍指向被删掉的节点，这块内存已经变成了被系统回收的无效内存，rear变成了野指针，不能这样所以把他手动指向nullptr } } int getFront(){ if(is_empty()){ cout<<"队列为空"<<endl; return -1; } return front->data; } int getBack(){ if(is_empty()){ cout<<"队列为空"<<endl; return -1; } return rear->data; } int getSize(){ return size; } void display(){ QueueNode* p=front; cout<<"队列所有元素（队头到队尾）："<<endl; while(p!=nullptr){ cout<<p->data<<" "; p=p->next; } cout<<endl; } ~LinkedQueue(){ //析构函数，释放所有节点内存，防止内存泄露。 while(!is_empty()){ pop(); } } };

数组实现队列：

class Queue{ //常数时间更好，但要明确加入操作的总次数(一定注意是加入操作的总次数)，更常用 private: //区间[l,r)存元素 static const int LIMIT=100;//该常量值根据题目描述变化 //加上static就说明这个常量属于整个类，而不是该类的某个对象，那么只要不改LIMIT创建出来的Queue就都是这个大小 int queue[LIMIT]; int l,r; public: Queue(){ //不需要写queue，因为C++在创建Queue对象时 ，会自动给这个固定数组在栈上分配完整的LIMIT大小的连续内存，构造函数执行前数组的空间就已经全部准备就绪了 //写了queue反而会报错，因为数组名在C++中是指向数组首元素的常量指针，常量指针是不能被直接赋值的 l=0; r=0; } //构造函数 bool is_full(){ return r-l==LIMIT; } bool is_empty(){ return l==r; } bool push(int value){ if(is_full()) return false; else{ queue[r++]=value; return true; } } int pop(){ if(is_empty()) return -1; return queue[l++]; } int get_head(){ if(is_empty()) return -1; return queue[l]; } int get_tail(){ return queue[r-1]; } int size(){ return r-l; } };

理解上述代码之后我们可以知道，在操作这个队列一段时间以后，可能会假溢出（弹出一些值后，数组有空间，但无法再次利用），所以我们接下来看数组实现的环状队列。

数组实现环状队列：

方式一：

class CircleQueue{ private: static const int LIMIT=5; //同时在队列里的数字个数不要超过LIMIT，同样根据题意自行改变。 int queue[LIMIT]; int r,l,size; public: CircleQueue(){ l=0; r=0; size=0; } bool is_full(){ return size==LIMIT; } bool is_empty(){ return size==0; } bool enQueue(int value){ if(is_full()){ return false; } else{ queue[r]=value; r=r==LIMIT-1?0:(r+1); //实现循环，走到数组尾部，已知队列还不满，直接到0位置。 size++; return true; } } bool deQueue(){ if(is_empty()){ return false; } else{ l=l==LIMIT-1?0:(l+1); //类似右边界，因为是删除元素，不用对数组有什么操作，如果后面还会用到这个位置数据会直接覆盖 size--; return true; } } int front(){ if(is_empty()){ return -1; } else{ return queue[l]; } } int rear(){ if(is_empty()){ return -1; } else{ int last=r==0?(LIMIT-1):(r-1); //因为r是最新存入元素的下一个位置 return queue[last]; } } void printQueue(){ if(is_empty()){ cout<<"队列为空！"<<endl; } else{ int cur=l; for(int i=0;i<size;i++){ cout<<queue[cur]<<" "; cur=cur==LIMIT-1?0:cur+1; } cout<<endl; } } };

除了这种实现方法。额外补充一个数组实现循环队列的方法，这种方法要牺牲数组一个位置的空间，但不需要额外定义size变量。

方式二：

class circleQueue{ private: static const int MAXN=100; int q[MAXN]; int l,r; public: circleQueue(){ l=0; r=0; } bool is_empty(){ return l==r; } bool is_full(){ return (r+1)%MAXN==l; //图形上理解就是r再向顺时针方向走一下就到l } bool push(int value){ if(is_full()) return false; q[r]=value; r=(r+1)%MAXN; return true; } bool pop(){ if(is_empty()) return false; l=(l+1)%MAXN; return true; } int getfront(){ if(is_empty()) return -1; return q[l]; } int getrear(){ if(is_empty()) return -1; return q[(r-1+MAXN)%MAXN]; //防止r在0位置时数组越界。 } int getsize(){ return (r - l + MAXN) % MAXN; //"+MAXN"->防止(r-l)为负数，"%MAXN"->抵消(r-l)不为负数时加的MAXN } };

这部分要注意l就是指向队头元素，r指向队尾元素的下一个位置，这个队列的实际储存空间只有MAXN-1。

如果有些想不通可以自己画一个环形模拟该队列，要注意储存了元素的位置一直是l顺时针转向r。

链表实现栈的话写法和实现队列差不多（但要注意插入元素时是放在链表头部，头指针向后移动），自己根据结构特征变化即可，我们直接来看数组实现栈。

数组实现栈：

很简单，一个size就都控制了。

class stack1{ private: static const int LIMIT=100; //同时在栈里的元素不能超过LIMIT个 int stack[LIMIT]; int size; public: stack1(){ size=0; } bool is_empty(){ return size==0; } bool is_full(){ return size==LIMIT; } bool push(int value){ if(is_full()){ return false; }else{ stack[size++]=value; return true; } } bool pop(){ if(is_empty()) return false; else{ size--; return true; } } int top(){ if(is_empty()) return -1; else{ return stack[size-1]; //注意，size是栈中最后一个元素的下一个位置 } } int count(){ return size; } };

栈和队列的相互实现：

两个栈实现队列：

一个in栈，一个out栈，有两个原则：out栈空了才能往里倒数据；如果要倒数据，in栈里的元素一定得全部倒完。

class stack_to_queue{ private: stack<int> in; stack<int> out; public: stack_to_queue(){ } void in_to_out(){ if(out.empty()){ while(!in.empty()){ out.push(in.top()); in.pop(); } } } void push(int value){ in.push(value); in_to_out(); //可以没有，压入数据后习惯性看一看能不能倒嘛 } void pop(){ in_to_out(); //一定得有，如果能倒没倒，说明out栈已经空了，怎么正确弹出数据呢。（其实还应该判断一下是否全空，真正用到的时候别忘了就行，这里只是简单介绍一下实现） out.pop(); } int front(){ in_to_out(); //一定要有，和pop很像 return out.top(); } bool is_empty(){ return in.empty()&&out.empty(); } };

一个队列实现栈：

主要是push操作的实现，可以把队列想象为一个横着的栈，左侧（队头）是栈顶，在队尾加元素相当于没有把元素压到栈顶而是放在了栈底，那我们就在添加元素之前计数，再把新元素放到栈底，然后把之前的元素都弹出来再放到倒栈底（均由队列实现，不过为了方便理解语言上与栈结合），这样就和栈的效果一样了！

class queue_to_stack{ private: queue<int> q; public: queue_to_stack(){ } void push(int value){ int n=q.size(); q.push(value); for(int i=0;i<n;i++){ int x=q.front(); q.pop(); q.push(x); } } void pop(){ q.pop(); } int top(){ return q.front(); } bool empty(){ return q.empty(); } };

最小栈：

支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。

用两个栈实现，一个data栈正常存入数据，一个min栈存对应data栈的每个位置及其以下的这一部分栈的最小值。

访问栈顶元素就是访问data栈顶，出栈data栈和min栈同时出，进栈时data栈进正常数据，min栈进当前数据与栈原有数据共同的最小值，访问最小值就是访问min栈顶。

#include<bits/stdc++.h> using namespace std; //支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 class minStack{ private: stack<int> min; stack<int> data; public: minStack(){ } void push(int value){ data.push(value); if(min.empty()||value<min.top()){ min.push(value); } else{ min.push(min.top()); } } void pop(){ data.pop(); min.pop(); } int top(){ return data.top(); } int getMin(){ return min.top(); } };

这是用库中的栈实现的，还可以自己用数组实现的栈来实现最小栈，比较简单，这块主要时讲最小栈怎么实现的，无就不再写第二个方法了，结合前面数组实现栈的内容很容易就能写出来，我们看下一部分。

双端队列（设计循环双端队列）：

641. 设计循环双端队列 - 力扣（LeetCode）

用系统自带循环双端队列实现：

C++库内的双端队列为：deque

这个方法很简单，只需要简单的调用库函数就能实现循环效果了。

这个方法常数操作慢，但数据量小的话看不太出来劣势。

不再做具体代码实现，简要说一下deque的常用操作：

deque<int> dq; //声明 deque<int> dq(5,0); //5个0 deque<int> dq={1,2,3}; //初始化列表 dq.push_back(x); //尾插 dq.push_front(x); //头插 dq.pop_back(); //删除尾部元素 dq.pop_front(); //删除尾部元素 dq.front(); //返回头部 dq.back(); //返回尾部 dq[i]; dq.at(i); //随机访问i位置的元素，第一个没有越界检查，可能读到乱值或崩溃；第二个会检查是否越界，越界抛异常 dq.size(); //返回大小 dq.empty(); //判断是否为空 dq.clear(); //清空队列

固定数组实现循环双端队列：

这个方法常数操作快，数据量大的能看出优势。

class CircleDeque{ private: static const int LIMIT=100; int cdeque[LIMIT]; int l,r,size; public: CircleDeque(){ l=0; r=0; size=0; } bool is_empty(){ return size==0; } bool is_full(){ return size==LIMIT; } bool insertFront(int val){ if(is_full()) return false; else{ if(is_empty()){ l=0; r=0; cdeque[0]=val; } else{ l=l==0?(LIMIT-1):(l-1); cdeque[l]=val; } size++; return true; } } bool insertLast(int val){ if(is_full()) return false; else{ if(is_empty()){ l=0; r=0; cdeque[0]=val; } else{ r=r==LIMIT-1?0:r+1; cdeque[r]=val; } size++; return true; } } bool deletelast(){ if(is_empty()) return false; else{ r=r==0?(LIMIT-1):(r-1); size--; return true; } } bool deletefront(){ if(is_empty()) return false; else{ l=l==(LIMIT-1)?0:(l+1); size--; return true; } } int getfront(){ if(is_empty()) return -1; return cdeque[l]; } int getlast(){ if(is_empty()) return -1; return cdeque[r]; } int getsize(){ return size; } };

这里简要梳理一下l和r（l指向队头元素，r指向队尾元素），首先要明确队列中有元素的位置就是l往右，r往左。我们可以先把l和放在不是边界且还没有位置被循环利用的简单情况下想一想，在头部加入元素l是不是要向左，那么我们此时要考虑的特殊位置是不是不能再向左的位置，那就是0位置，所以l如果等于0（注意此时讨论的已经是在队列不为空而l在0的情况下了，所以已经有位置被循环利用过了），我们把l移到最后一个位置，接下来在尾部加元素以及头删，尾删都是这一套思路。

二叉树：

队列和栈先暂时告一段落，我们看一下二叉树。

先说一下二叉树的三种遍历方式：

先序遍历：中左右

中序遍历：左中右

后序遍历：左右中

我们先看三种遍历方式的递归实现：

遍历的递归实现：

看代码：

#include<bits/stdc++.h> using namespace std; struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode(int v): val(v),left(nullptr),right(nullptr) {} }; //先序遍历： void preOrder(TreeNode* head){ if(head==nullptr) return; cout<<head->val<<" "; preOrder(head->left); preOrder(head->right); } //中序遍历： void inOrder(TreeNode* head){ if(head==nullptr) return; inOrder(head->left); cout<<head->val<<" "; inOrder(head->right); } //后序遍历： void posOrder(TreeNode* head){ if(head==nullptr) return; posOrder(head->left); posOrder(head->right); cout<<head->val<<" "; } int main(){ TreeNode* head = new TreeNode(1); head->left = new TreeNode(2); head->right = new TreeNode(3); head->left->left = new TreeNode(4); head->left->right = new TreeNode(5); head->right->left = new TreeNode(6); head->right->right = new TreeNode(7); cout<<"先序遍历："<<endl; preOrder(head); cout<<endl; cout<<"中序遍历："<<endl; inOrder(head); cout<<endl; cout<<"后序遍历："<<endl; posOrder(head); cout<<endl; return 0; }

如果不理解递归的走向，可以自己画一下类似代码中的二叉树顺一顺。先序遍历为例，设我们来到了x（第一次来到x），先打印x处的值，然后在调用他的左子树的同样的函数，左子树的函数全部完成后，返回到x（第二次来到x），调用右子树的同样函数，返回到x （第三次来到x）。

类似上述过程，一层一层的向下调用，再一层一层的返回，直到函数全部返回完毕。

结合上述过程，我们还可以得知：

先序遍历在第一次到达x时就打印

中序遍历在第二次到达x时打印

后序遍历在第三次到达时才打印

这样就完美符合了三种遍历的打印顺序，挺妙。

遍历的非递归实现（迭代+栈）：

先序遍历：

一定要注意先压入右树再压入左树，也不需要担心head的重复使用，这就体现了栈的用处了，head在变值之前它原来的节点就已经被压入栈了，即使不打印也不会丢失，而且head是一直往后走的，每个节点都仅会当一次head。

中序遍历：

栈辅助的目的其实就是方便head向树的上一层跳，我们梳理一下整个过程，首先head树的为最上方的节点，此时肯定不为空，head就一直往左树走，知道来到左边最后一个节点，它的左右树都是空，和整个题的逻辑结合我们可以近似认为它的左子树处理完了，那就来到else分支，取栈顶（正好就是我们现在看的这个节点）打印他，弹出它，再看看它的右子树，也可以认为整个右子树处理完了，依旧是到栈顶取，正好就是它上一层的中间（左处理完，才可以打印中），因为前面的代码走完了，我们就可知道当前节点的左子树已全部处理完，中也打印了，去看右子树，欸！右子树没处理呢（处理完左中才能处理右），所以又来到第一个if分支，先压入这个节点再去看它的左侧（注意，此时我们看这个子树的话，该节点为以它为头的子树的中间），是不是有一种循环往复的感觉了~，就这样一遍遍左中右地处理，直到头指针为空且栈为空，那么就全部都处理完啦！

总结一下就是分为三步：

1.从最顶上的头开始一直往左走，都压入栈，直到左子树为空：

2.弹出一个节点x打印，再去看这个节点的右子树，以x的右节点再做头，重复1：

3.直到head为空，栈为空，最后应该结束在真个树的最右侧的最后一个节点。

后序遍历：

后续遍历有两种方法，一种是由两个栈实现且可以看作先序遍历的改编，我们先看第一种方法。

我们知道先序遍历的输出顺序为：中左右 后序遍历的输出顺序为左右中，而先序遍历的非递归实现里先压入右树再压入左树输出时才符合中左右的顺序，如果先压入左树再压入右树，输出时会是 中右左，那我们把这个顺序反过来呢？左右中，发现了吧！这就是后序遍历的顺序，所以我们将先序遍历的方法稍作改编，再多添一个栈来辅助实现倒序，后序遍历就完成啦！看代码：

void posOrder_twostacks(TreeNode* head){ if(head!=nullptr){ stack<TreeNode*> s; stack<TreeNode*> help; s.push(head); while(!s.empty()){ head=s.top(); help.push(head); s.pop(); if(head->left!=nullptr){ s.push(head->left); } if(head->right!=nullptr){ s.push(head->right); } } while(!help.empty()){ cout<<help.top()->val<<" "; help.pop(); } } }

和先序遍历的区别就是加了一个栈，把原来的打印操作变成压入help栈，颠倒一下左子树和右子树处理的顺序，最后help栈正常出栈打印就行。

接下来我们看只需要一个栈就能完成的方法：

void posOrder_onestack(TreeNode* head){ if(head!=nullptr){ stack<TreeNode*> s; s.push(head); while(!s.empty()){ TreeNode* cur=s.top(); if(cur->left!=nullptr&&head!=cur->left&&head!=cur->right){ s.push(cur->left); } else if(cur->right!=nullptr&&head!=cur->right){ s.push(cur->right); } else{ head=s.top(); cout<<head->val<<" "; s.pop(); } } } }

我们先明确一下，head在代码中的意义，一开始没进循环那就是树的最头上节点，进了while循环，如果一直没有走到打印那一步，那head一直指向最头上的哪个节点，如果到了else这个分支，也就是将要打印节点了，head就指向要打印的节点，在这之后如果head再改变指向，那也一定是指向下一个要打印的节点，所以在head指向下一个节点之前它指向的一直都是上一个打印的节点。

我们梳理一下思路，首先常规地判断传进来的树不是空的，建一个栈，把头节点压入栈，之后以栈不为空为循环条件进入一个while循环（因为我们的元素都会进栈，出栈的时候也就是这个节点打印出来，被处理完的时候，栈里没有元素就证明排序完成），在每一轮while循环的开头让cur永远指向栈顶，然后先判断cur指向的节点的左侧是否有未被处理的节点，有就压入栈然后再往左看，直到左侧最后一个节点x，因为它既没有未处理的左子树也没有未处理的右子树（这个节点被允许处理，因为后序遍历啊），来到else分支，打印弹出该节点，head指向这个被打印完的节点，然后循环更新又看到栈顶，因为我们首先压入的是左侧一排，栈顶为x的父亲节点，左节点被打印了可右节点没有，右节点y压入栈，成为栈顶，无左右树，打印弹出y，head来到y，cur到栈顶，这时的栈顶元素的左右子树可是实打实的被打印完了的，那么该栈顶元素也可以被打印弹出了，cur又来到新的栈顶，重复。

我们来到每一个节点可以把它都看成一个子树的中间节点（只不过有的左右子树为空有的不为空），只有这个节点的左右子树都被处理了它才能被打印（else分支的含义），另外因为head指向的是上一个被打印的节点或头节点，所以if和else if分支用head的指向判断左右子树是否被打印。

自己可以画栈和二叉树多模拟几遍这个过程。

到这里我们算法基础的第一篇就告一段落了，后续会有第二三四五六七八篇（应该会有这么多吧），我们下篇见！