快排
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<queue> #include<cmath> #include<list> using namespace std; typedef long long LL; typedef unsigned long long ull; #define sc1(a) scanf("%lld",&a) #define pf1(a) printf("%lld ",a) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const LL INF=1e18; const ull base=2333; const int maxn=1e2+55; const int maxm=1e2+50; const int maxv=1e6+5; const int maxk=1e8+5; const int mod=1e9+7; int split(int a[],int low,int high) { int i=low; int x=a[i];//以最左边的元素为基值 for(int j=low+1;j<=high;j++) { if(a[j]<=x)//小于x的往前放 { i++; swap(a[i],a[j]); } } swap(a[i],a[low]); return i; } void Quick_sort(int a[],int low,int high) { if(low<high) { int i=split(a,low,high); Quick_sort(a,low,i-1); Quick_sort(a,i+1,high); } } int main() { int a[]={1,5,4,2,3}; Quick_sort(a,0,4); for(int i=0;i<5;i++) cout<<a[i]<<" ";cout<<endl; }
求数组中第k大的元素
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<queue> #include<cmath> #include<list> using namespace std; typedef long long LL; typedef unsigned long long ull; #define sc1(a) scanf("%lld",&a) #define pf1(a) printf("%lld ",a) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const LL INF=1e18; const ull base=2333; const int maxn=1e2+55; const int maxm=1e2+50; const int maxv=1e6+5; const int maxk=1e8+5; const int mod=1e9+7; priority_queue<int,vector<int>,greater<int> > q; void solve_k(int a[],int k) //求第k大的元素 { //维护一个优先队列 小根堆 保证小根堆从小到大存储最大的k个元素 则小根堆第一个就是第k大 for(int i=0;i<5;i++) { if(q.size()<k) q.push(a[i]); else { if(a[i]>q.top()) //出队列 存一个更大的值 { q.pop(); q.push(a[i]); } } } cout<<q.top()<<endl; } int main() { int a[]={1,5,4,2,3}; solve_k(a,3); }
插入排序
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<queue> #include<cmath> #include<list> using namespace std; typedef long long LL; typedef unsigned long long ull; #define sc1(a) scanf("%lld",&a) #define pf1(a) printf("%lld ",a) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const LL INF=1e18; const ull base=2333; const int maxn=1e2+55; const int maxm=1e2+50; const int maxv=1e6+5; const int maxk=1e8+5; const int mod=1e9+7; //插入排序 //类似扑克牌思想 从后往前找到满意的位置 后面的位置全部往后移一位 void solve_sort(int a[]) { for(int i=1;i<5;i++) { int key=a[i]; for(int j=i-1;j>=0;j--) { if(key<a[j]) { a[j+1]=a[j];//往后移一位 } else { a[j+1]=key; break; } } } for(int i=0;i<5;i++) cout<<a[i]<<" ";cout<<endl; } int main() { int a[]={1,5,4,2,3}; solve_sort(a); }
希尔排序：在插入排序的基础上进行一种粗调，将数组分组，分组进行插入排序，不稳定
归并排序
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<queue> #include<cmath> #include<list> using namespace std; typedef long long LL; typedef unsigned long long ull; #define sc1(a) scanf("%lld",&a) #define pf1(a) printf("%lld ",a) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const LL INF=1e18; const ull base=2333; const int maxn=1e2+55; const int maxm=1e2+50; const int maxv=1e6+5; const int maxk=1e8+5; const int mod=1e9+7; // 归并排序 // 划分区间 排序 再进行合并 void Merge(int a[],int low,int high) { int mid=(low+high)/2; // 合并 a[low,mid] a[mid+1,high] int len1=mid-low+1; int len2=high-mid; int *l=new int[len1]; int *r=new int[len2]; int k=0; for(int i=low;i<=mid;i++) l[k++]=a[i]; k=0; for(int i=mid+1;i<=high;i++) r[k++]=a[i]; k=low; int i=0,j=0; for(;i<len1&&j<len2;) { if(l[i]<=r[j]) { a[k++]=l[i]; i++; } else { a[k++]=r[j]; j++; } } for(;i<len1;i++) a[k++]=l[i]; for(;j<len2;j++) a[k++]=r[j]; delete []l; delete []r; } void MergeSort(int a[],int low,int high) { if(low<high) { int mid=(low+high)/2; MergeSort(a,low,mid); MergeSort(a,mid+1,high); Merge(a,low,high); } } int main() { int a[]={1,5,4,2,3}; MergeSort(a,0,4); for(int i=0;i<5;i++) cout<<a[i]<<" ";cout<<endl; }
冒泡排序
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<queue> #include<cmath> #include<list> using namespace std; typedef long long LL; typedef unsigned long long ull; #define sc1(a) scanf("%lld",&a) #define pf1(a) printf("%lld ",a) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const LL INF=1e18; const ull base=2333; const int maxn=1e2+55; const int maxm=1e2+50; const int maxv=1e6+5; const int maxk=1e8+5; const int mod=1e9+7; //冒泡排序 // 外层循环是排序趟数 //内层比较相邻元素 void bubble_sort(int a[],int len) { for(int i=0;i<len-1;i++) //len个数只需要len-1躺就能排好序了 { for(int j=0;j<len-1-i;j++) { if(a[j]>a[j+1]) swap(a[j],a[j+1]); } } } int main() { int a[]={1,5,4,2,3}; bubble_sort(a,5); for(int i=0;i<5;i++) cout<<a[i]<<" ";cout<<endl; }
选择排序：每次循环选择最小的那个跟没排序的最下的那个交换位置
堆排序：后续发表
最长上升子序列：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<queue> #include<cmath> #include<list> using namespace std; typedef long long LL; typedef unsigned long long ull; #define sc1(a) scanf("%lld",&a) #define pf1(a) printf("%lld ",a) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const LL INF=1e18; const ull base=2333; const int maxn=1e2+55; const int maxm=1e2+50; const int maxv=1e6+5; const int maxk=1e8+5; const int mod=1e9+7; int g[maxn];//g[i]表示长度为i的最长上升子序列的末尾最小值 void solve_lis(int a[],int len) { for(int i=0;i<=len;i++) g[i]=INT_MAX; int ans=-1; for(int i=0;i<len;i++) { int p=lower_bound(g,g+len,a[i])-g; g[p]=a[i];//更新值 ans=max(ans,p+1); } cout<<ans<<endl; } int main() { int a[]={1,5,4,2,3}; solve_lis(a,5); return 0; }
最长公共子序列
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<queue> #include<cmath> #include<list> using namespace std; typedef long long LL; typedef unsigned long long ull; #define sc1(a) scanf("%lld",&a) #define pf1(a) printf("%lld ",a) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const LL INF=1e18; const ull base=2333; const int maxn=1e2+55; const int maxm=1e2+50; const int maxv=1e6+5; const int maxk=1e8+5; const int mod=1e9+7; int dp[maxn][maxn]; //dp[i][j]表示以a前i个和b前b个最长公共子序列长度 void solve_lcs(int a[],int lena,int b[],int lenb) { for(int i=0;i<lena;i++) { for(int j=0;j<lenb;j++) { if(a[i]==b[j]) { dp[i+1][j+1]=dp[i][j]+1; } else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]); } } cout<<dp[lena][lenb]<<endl; } int main() { int a[]={1,5,4,2,3}; int b[]={1,4,5,2,3}; solve_lcs(a,5,b,5); return 0; }
合并两个有序链表
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* ans=new ListNode(0); ListNode* head=ans; while(l1&&l2) { if(l1->val<=l2->val) { ans->next=l1; l1=l1->next; } else { ans->next=l2; l2=l2->next; } ans=ans->next; } if(l1) ans->next=l1; if(l2) ans->next=l2; return head->next; } };
链表反转
Node* Reverse_list(Node* head) { Node* forward_node=nullptr; Node* cur_node=head->nxt;//去除头结点的第一个节点 Node* nxt_node=cur_node->nxt;//第二个节点 while(1) { cur_node->nxt=forward_node; forward_node=cur_node; cur_node=nxt_node; if(cur_node==nullptr) break; nxt_node=cur_node->nxt; } return forward_node; }
判断链表成环
bool judge_palindromic(Node* head) { map<Node*,bool>m; Node* l=head->nxt; while(l) { if(m[l]) return true;//成环 m[l]=true; l=l->nxt; } return false; }
生产者消费者模型
#include <unistd.h> #include <cstdlib> #include <condition_variable> #include <iostream> #include <mutex> #include <thread> #include<windows.h> static const int kItemRepositorySize = 10; // Item buffer size. static const int kItemsToProduce = 1000; // How many items we plan to produce. struct ItemRepository { int item_buffer[kItemRepositorySize]; // 产品缓冲区, 配合 read_position 和 write_position 模型环形队列. size_t read_position; // 消费者读取产品位置. size_t write_position; // 生产者写入产品位置. std::mutex mtx; // 互斥量,保护产品缓冲区 std::condition_variable repo_not_full; // 条件变量, 指示产品缓冲区不为满. std::condition_variable repo_not_empty; // 条件变量, 指示产品缓冲区不为空. } gItemRepository; // 产品库全局变量, 生产者和消费者操作该变量. typedef struct ItemRepository ItemRepository; void ProduceItem(ItemRepository *ir, int item) { std::unique_lock<std::mutex> lock(ir->mtx); while(((ir->write_position + 1) % kItemRepositorySize) == ir->read_position) { // item buffer is full, just wait here. std::cout << "Producer is waiting for an empty slot... "; (ir->repo_not_full).wait(lock); // 生产者等待"产品库缓冲区不为满"这一条件发生. } (ir->item_buffer)[ir->write_position] = item; // 写入产品. (ir->write_position)++; // 写入位置后移. if (ir->write_position == kItemRepositorySize) // 写入位置若是在队列最后则重新设置为初始位置. ir->write_position = 0; (ir->repo_not_empty).notify_all(); // 通知消费者产品库不为空. lock.unlock(); // 解锁. } int ConsumeItem(ItemRepository *ir) { int data; std::unique_lock<std::mutex> lock(ir->mtx); // item buffer is empty, just wait here. while(ir->write_position == ir->read_position) { std::cout << "Consumer is waiting for items... "; (ir->repo_not_empty).wait(lock); // 消费者等待"产品库缓冲区不为空"这一条件发生. } data = (ir->item_buffer)[ir->read_position]; // 读取某一产品 (ir->read_position)++; // 读取位置后移 if (ir->read_position >= kItemRepositorySize) // 读取位置若移到最后，则重新置位. ir->read_position = 0; (ir->repo_not_full).notify_all(); // 通知消费者产品库不为满. lock.unlock(); // 解锁. return data; // 返回产品. } void ProducerTask() // 生产者任务 { for (int i = 1; i <= kItemsToProduce; ++i) { // sleep(1); std::cout << "Produce the " << i << "^th item..." << std::endl; ProduceItem(&gItemRepository, i); // 循环生产 kItemsToProduce 个产品. } } void ConsumerTask() // 消费者任务 { static int cnt = 0; while(1) { Sleep(1); int item = ConsumeItem(&gItemRepository); // 消费一个产品. std::cout << "Consume the " << item << "^th item" << std::endl; if (++cnt == kItemsToProduce) break; // 如果产品消费个数为 kItemsToProduce, 则退出. } } void InitItemRepository(ItemRepository *ir) { ir->write_position = 0; // 初始化产品写入位置. ir->read_position = 0; // 初始化产品读取位置. } int main() { InitItemRepository(&gItemRepository); std::thread producer(ProducerTask); // 创建生产者线程. std::thread consumer(ConsumerTask); // 创建消费之线程. producer.join(); consumer.join(); }