常用板子

栈

LIFO

用数组模拟栈

int st[N];//元素数量，栈顶下标
//压栈
st[++*st]=var1;
//取栈顶
int u =st[*st];
//弹栈，*st==0时不能继续弹出
if(*st) --*st;
//清空栈
*st =0 ;

STL中的栈

//引入stack头文件，container默认使用stf::deque
template<
     class T,class Container = std:deque<T>
>class stack;

容器必须提供以下函数，如std::vector,std::deque和std::list

back()
push_back()
pop_back()

stack容器常用函数

st.top()
st.push()
st.pop()
st.empty()
st.size()

//新建两个栈st1和st2
std:stack<int> st11,st2;
//为st1装入1
st1.push(1);
//赋值
st2=st1
//输出栈顶
cout << st2.top() << endl;

队列

FIFO

用数组模拟一个队列，用两个变量标记队列的首尾

int q[size],ql=1,qr;

插入元素：q[++qr]=x;

删除元素：ql++;

访问队首：q[ql];

访问队尾：q[qr];

清空队列：ql=1，qr=0；

双端队列

//引入<deque>头文件
template<
    class T,//数据类型
    class Allocator = std:allocator<T>//适配器
>class deque;

std::deque容器常用函数

元素访问

q.front();
q.back();

修改

q.push_back()
q.pop_back()
q.push_front()
q.pop_front()
q.insert()
q.erase()

容器

q.empty()
q.size()

循环队列

采用循环的方式组织存放队列元素的数组，将下标为0的位置看作最后一个位置后继，如(n+1)%size

例题

一个双端队列（deque），m 个事件：

在前端插入 (w,v)
在后端插入 (w,v)
删除前端的二元组
删除后端的二元组

链表

构建链表

单向链表

struct Node{
    int value;
    Node *next;
};

双向链表

struct Node{
int value;
Node *next;
Node *right;
}

向链表插入数据

单向链表

void insertNode(int i,Node *p){
    Node *node = new Node;
    node->value = i;
    node->next = p->next;
    p->next = node;
}

单向循环链表

先判断原链表是否为空，为空则自身循环，不为空则插入数据

void insertNode(int i,Node *p){
//初始化
    Node *node = new Node;
    node->value =i;
    node->next = NULL;
//判断是否为空
    if(p == NULL){
        p = node;
        node->next = node;//指向自己
    }else{
       node->next = p->next;
       p->next=node;
    }   
}

双向循环链表

除了要判断给定链表是否为空外，还要修改左右指针

void insertNode(int i,Node *p){
    Node *node =new node;
    node->value=i;
    if(p == NULL){
        p = node;
        node->left=node;
        node->right=node;
    }else{
     node->right = node->right;
     node->left=node;
     p->right->left=node;
     p->right=node;
    }
}

从链表中删除数据

单向链表

利用虚拟节点

删除 t。此时虽然原结点 p 的地址还在使用，删除的是原结点 p->next 的地址，但 p 的数据被 p->next 覆盖，p 名存实亡。

void deleteNode(Node *p){
   p->value = p->next->value;//保存p下一个结点的值
   Node *t = p->next;//利用虚拟结点保存p->next
   p->next = p->next->next;
   delete t;
}

双向循环链表

void deleteNode(Node *p){
    p->left->right=p->right;
    p->right->left=p->left;
    Node *t =p;
    p=p->right;//将 p 的右节点地址赋给 p，以避免 p 变成悬垂指针；
    delete t;
}

树

存储

父节点parent[N]

左右兄弟

int v=child[u];

while(v!=EMPTY_NODE){
//...
  v=sib[v];

}

二叉树，记录每个节点的左右子节点

int parent[N];
int lch[N],rch[N];
//
int child[N][2];

先序遍历（根，左，右）

void preorder(BiTree* root){
  if(root){
    cout << root->key<< "";
    preorder(root->left);
    preorder(root->right);
  }
}

中序遍历(左，根，右)

void inorder(BiTree* root){
  if(root){
    inorder(root->left);
    cout<<root->key<<"";
    inorder(root->right);
  }
}

后序遍历（左，右，根）

void postorder(BiTree* root){
  if(root){
  postorder(root->left);
  postorder(root->right);
  count<<root->key<<"";
  }
}

BFS遍历

vector<vector<int>> levelOrder(Node* root){
  if(!root){
    return {};
  }
  vector<vector<int>> res;
  queue<Node*> q;//队列
  q.push(root);//将根节点加入队列
  while(!q.empty()){
    int currentLevelSize = q.size();//获取当前层节点数
    res.push_back(vector<int>()); //为当前层创建新的向量
    //处理当前层的所有节点
    for(int i =0;i<currentLevelSize;++i){
      Node* cur = q.front(); //获取队首节点
      q.pop(); //弹出队首节点
      res.back().push_back(cur->val);//将节点值加入当前层
      //将子节点加入队列
      for(Node* child:cur->children){
        q.push(child);
      }
    }
  }
}

Morris遍历

Morris 遍历的实质是避免使用栈，利用底层节点空闲的 right 指针指回上层的某个节点，从而完成下层到上层的移动。

void mooris(TreeNode* root){
  TreeNode* cur = root;
  while(cur){
    if(!cur->left){
    std::cout<<cur->val<<" ";
    cur=cur->right;
    continue;
    }
    //找到当前节点的左子树的最右节点
    TreeNode* mostRight = cur->left;
    while (mostRight->right && mostRight ->right !=cur){
      mostRight = mostRight->right;
    }
    if(!mostRight->right){
    //如果最右节点的right指针为空，将其指向当前节点，并进入左子树
      mostRight -> right =cur;
      cur = cur ->left;
    }else{
    //如果最右节点的right指针指向当前节点，说明左子树已经遍历完毕，输出当前节点的值并进入右子树
    mostRight->right =nullptr;
    std::cout << cur->val << " ";
    cur = cur->right;
    }
  }
}

排序

稳定性？指相等的元素经过排序之后相对顺序是否发生了改变

选择排序

用数组实现不稳定

每次找出第i小的元素，然后将这个元素与数组第i个位置上的元素交换

#include <utility>
void selection_sort(int* a,int n){
    for(int i=1;i<n;++i){
      int ith = i;
      for(int j=i+1;j<=n;++j){
        if(a[j]<a[ith]){
          ith =j;
        }
      }
      std::swap(a[i],a[ith]);
    }
}

每次遍历i=1-n，固定i，遍历后面所有数(j)，如果后面数比前面数小，记住这个数的位置，结束后将他们交换

冒泡排序

稳定

每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。

最坏情况，要会执行n-1+n-2+……+1次交换操作

void bubble_sort(int *a,int n){
    bool flag =true;
    while(flag){
    flag= false;
    for(int i=1;i<n;++i){
      if(a[i]>a[i+1]){
        flag=true;
        int t=a[i];
        a[i]=a[i+1];
        a[i+1]=t;//交换
      }
    }
   }
}

QA：为什么flag放在循环里面？

只要找到不满足条件的立即停止

插入排序

稳定，最优n，最坏n^2

插入排序（英语：Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。

一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张牌。

void insertion_sort(int arr[],int len){
    for(int i =1;i<len;++i){
        int key = arr[i];
        int j =i-1;
        while(j >=0 && arr[j]>key){
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=key;
    }
}

从第1个元素开始排序，再取第二个元素，和第一个元素比较，排序，再取第三个元素，和刚跟排序好的最后一个元素比较……

计数排序

线性时间，稳定

计数排序的工作原理是使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数，然后根据数组C来讲A中的元素排到正确的位置

计算每个数出现了几次；

求出每个数出现次数的前缀和；

利用出现次数的前缀和，从右至左计算每个数的排名。

n是数组长度，w是元素值域范围/最大值

#include <cstring>
constexpr int MAXN =1010;//数组最大长度
constexpr int MAXW = 100010;//元素至于范围
int cnt[MAXW];//计数数组，用于统计每个元素出现的次数
int b[MAXN];//输出数组，存储排序后的结果
int* counting_sort(int* a,int n,int w){
    memset(cnt,0,sizeof(cnt));//初始化计数数组
    for(int i=0;i<=n;++i) ++cnt[a[i]];//统计每个元素出现的次数
    for(int i=1;i<=w;++i) cnt[i]+=cnt[i-1];//计算前缀和，确定每个元素最后出现的的位置
    for(int i=n;i>=1;--i) b[cnt[a[i]]--]=a[i];//从后向前遍历，将元素放到正确位置
}

输入数组 a: [0, 2, 1, 3, 2, 1] n = 5, w = 3

步骤1：统计次数 cnt[0] = 1 cnt[1] = 2 cnt[2] = 2 cnt[3] = 1

步骤2：计算前缀和 cnt[0] = 1 cnt[1] = 3 cnt[2] = 5 cnt[3] = 6

步骤3：从后向前放置元素 i = 5: a[5] = 1 cnt[1] = 3 b[3] = 1 cnt[1] = 2

i = 4: a[4] = 2 cnt[2] = 5 b[5] = 2 cnt[2] = 4

…以此类推

最终结果：b = [1, 1, 2, 2, 3]

MSD基数排序

基于 k - 关键字元素的比较方法，可以想到：先比较所有元素的第关键字，就可以确定出各元素大致的大小关系；然后对 具有相同第关键字的元素，再比较它们的第关键字……以此类推。

void MSD_radix_sort(u32ptr first,u32ptr last){

}

通常而言，基数排序比基于比较的排序算法（比如快速排序）要快。但由于需要额外的内存空间，因此当内存空间稀缺时，原地置换算法（比如快速排序）或许是个更好的选择。

快速排序

不稳定，平均 O(nlogn)，最坏 O(n²)

分治思想

将数列划分为两部分
递归到两个子序列中分别进行快速排序
不用合并，此时数列已经有序

struct Range{
    int start,end;
    Range(int s=0,int e=0){
    start =s,end =e;
    }
};
template <typename T>
void quick_sort(T arr[],const int len){
   if(len<=0) return;
   Range r[len];//使用数组模拟栈
   int p=0;     //栈顶指针
   r[p++]=Range(0,len-1);//压入整个数组范围
   while(p){//当栈不为空
   Range range = r[--p];//弹出栈顶范围
   if (range.start >= range.end) continue;//范围无效跳过
   T mid = arr[range.end];//选择最右边的元素作为基准值
   int left = range.start,right=range.end-1;
   //分区过程
   while(left<right){
   while(arr[left]<mid && left<right) left++;
   while(arr[left])>=mid&&left<right) right--;
   std:swap(arr[left],arr[right]);//左边小就不交换，比较下一个，右边同理
   }
   //处理基准值
   if(arr[left]>=arr[range.end])
       std::swap(arr[left],arr[range.end]);
   else
       left++;
   }
   r[p++]=Range(range.start,left-1);
   r[p++]=Range(left+1,range.end);
}

选一个基值，一个左指针，一个右指针，左指针指到的数字比基准小就不处理，左指针右移动，否则交换后，左指针右移动，然后右指针，数字大不处理，小的话交换，左移，当左右指针相遇，取这个数和最右边的元素比较，再次重复

归并排序

最优，平均，最坏情况下均为nlogn，空间复杂度为n

比较两个数组每个元素（有序），把小的放入新数组，如果还有剩下没比较的全部放入（因为有序）

void merge(const int *a,size_t aLen,const int *b,size_t bLen,int *c){
  size_t i=0,j=0,k=0;
  while(i<aLen && bLen){
       if(b[j]<a[i]){
       c[k]=b[j];
       ++j;
       }else{
       c[k]=a[i];
       ++i
       }
       ++k;
  }
  for(;i<aLen;++i,++k) c[k]=a[i];
  for(;j<bLen;++j,++k) c[k]=b[j];
}

分治法实现归并排序

mid=（l+r）/2

void merge_sort(int *a,int l,int r){
  if(r-l<=1)  return;
  int mid = l+((r-l)>>1);//每次都加总长度的1/2
  merge_sort(a,l,mid),merge_sort(a,mid,r);
  //合并
  int tmp[1024]={};
  merge(a+l,a+mid,a+r,a+mid,tmp+l);
  for(int i=l;i<r;++i) a[i]=tmp[i];
}

堆排序

不稳定，时间复杂度nlogn

1.建堆

iParent(i)=(i-1)/2
iLeftChild(i)=2*i+1
iRightChild(i)=2*i+2

2.排序

void sift_dowmn(int arr[],int start,int end){
   int parent = start;
   int child =parent*2+1;
   while(child<=end){
   //先比较两个子节点大小，选择最大的
   if(child+1<=end&&arr[child]<arr[child+1]) child++;
   //如果父节点比子节点大，代表调整完毕，直接跳出函数
   if(arr[parent]>=arr[child])
       return;
   else{//否则交换父子内容，子节点在和孙节点比较
       swap(arr[parrent],arr[child]);
       parent = child;
       child = parent*2+1;
   }
   }
}
void heap_sort(int arr[],int len){
  //从最后一个节点的父节点开始
  for(int i=(len-1-1)/2;i>=0;i++) sift_down(arr,i,len-1);
  for(int i = len-1;i>0;i--){
  swap(arr[0],arr[i]);
  sift_down(arr,0,i-1);
  }
}

桶排序

稳定，时间平均复杂度n+n*n/k+k,最坏n^2

1.设定一个定量的数组当作空桶

2.遍历，放入相应桶

3.对非空桶内部排序

4.把非空桶中的元素拿出

constexpr int N=100010;
int n,w,a[N];//n是元素个数，w是值域范围，a是待排序数组
vector<int> bucket[N];
//排序函数
void insertion_sort(vector<int>&A){
  for(int i=1;i<A.size();++i){
      int key=A[i];
      int j=i-1;
      //将比key大的元素后移
      while(j>=0&&A[j]>key){
      A[j+1]=A[j];
      --j;
      }
      A[j+1]=key;//插入key
  }
}
void bucket_sort(){
    //计算每个桶的大小
    int bucket_size=w/n+1;
    //清空所有桶
    for(int i=0;i<n;++i){
        bucket[i].clear();
    }
    //将元素分配到桶中
    for(int i=1;i<=n;++i){
       bucket[a[i]/bucket_size].push_back(a[i]);
    }
    //对每个桶排序合并结果
    int p=0;
    for(int i=0;i<n;++i){
        insertion_sort(bucket[i]);
        for(int j=0;j<bucket[i].size();++j){
           a[++p]=bucket[i][j];
        }
    }
}

二分法

int binary_search(int start,int end,int key){
  int ret =-1;//未搜索到数据返回-1下标
  int mid;
  while(start<=end){
    mid = start+((end-start)>>1);//直接取平均可能会溢出
    if(arr[mid]<key)
      start = mid + 1;
    else if(arr[mid]>key)
      end = mid-1;
    else{
        ret = mid;
        break;
    }
  }
  return ret;
}

三分法

如果需要求出单峰函数的极值点

while(r-l>eps){
  mid = l+((r-l)>>1);
  lmid = mid-eps;
  rmid = mid+eps;
  if(f(lmid)<f(rmid))
    r = mid;
  else
    l = mid;
}

DFS(图论)

用栈来实现

时间复杂度位n+m,空间复杂度为n，n表示点数，m表示边数

DFS(v) // v 可以是图中的一个顶点，也可以是抽象的概念，如 dp 状态等。
  在 v 上打访问标记
  for u in v 的相邻节点
    if u 没有打过访问标记 then
      DFS(u)
    end
  end
end

非递归版本

vector<vector<int>> adj;//邻接表
vector<bool> vis;//记录节点是否已经遍历

void dfs(int s){
    stack<int> st;
    st.push(s);
    vis[s]=true;
    
    while(!st.empty()){
        int u=st.top();
        st.pop();
        
        for(int v:adg[u]){
        if(!vis[v]){
            vis[v]=true;
            st.push(v);
        }
        }
    }
}

递归实现

vector<vector<int>> adj;//邻接表
vector<bool> vis;//记录节点是否已经遍历

void dfs(const int u){
     vis[u]=true;
     for(int v:adj[u])
     if(!vis[v]) dfs(v)
}

例题：把正整数n分解成3个不同的正整数，排在后面的数必须大于等于前面的数

int m,arr[103];//m是划分的最大个数，arr[103]存储当前划分方案
void dfs(int n,int i,int a){//n是待划分的数，a是可以取到的最小值
  if(n == 0){//划分完了，找到以恶搞完整的划分方案，遍历打印
     for(int j=1;j<=i-1;++j){
         printf("%d",arr[j]);
     printf("\n");
     }
  if(i<=m){
    for(int j=a;j<=n;++j){//从a开始尝试每个可能的数
    arr[i]=j;//记录当前选择
    dfs(n-j,i+1,j);//递归处理剩余部分
    }
  }
  }
}

Frederick

Welcome to my Alter Ego's site!

常用板子

栈

用数组模拟栈

STL中的栈

队列

用数组模拟一个队列，用两个变量标记队列的首尾

双端队列

循环队列

链表

构建链表

向链表插入数据

双向循环链表

从链表中删除数据

单向链表

树

存储

排序

选择排序

冒泡排序

插入排序

计数排序

MSD基数排序

快速排序

归并排序

分治法实现归并排序

堆排序

桶排序

二分法

三分法

DFS(图论)