面试常考代码

07/13 10:02

``````#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\n",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;
}``````

``````#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\n",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\n",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\n",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\n",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\n",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\n",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;
}``````

合并两个有序链表

``````/**
* 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);
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;
}
};``````

链表反转

``````Node* Reverse_list(Node* head)
{
Node* forward_node=nullptr;
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;
while(l)
{
if(m[l]) return true;//成环
m[l]=true;
l=l->nxt;
}
return false;
}``````

0
0 收藏

0 评论
0 收藏
0