每日三百行代码第一天
------b站学习篇
//单链表 ACwing
#include<iostream>
using namespace std;
const int N=1000000+10;
int e[N],ne[N],idx,head;
void Init(){
head=-1;
idx=0;
}
void add_head(int x){
e[idx]=x;
ne[idx]=head;
head=idx++;
}
void remove(int k){
ne[k-1]=ne[ne[k-1]];
}
void add(int x,int k){
e[idx]=x;
ne[idx]=ne[k-1];
ne[k-1]=idx++;
}
int main(){
int m,k,x;
cin>>m;
while(m--){
char ch;
cin>>ch;
Init();
if(ch=='H'){
cin>>x;
add_head(x);
}else if(ch=='D'){
cin>>k;
if(k==0){
head=ne[head]; //删除头结点
}else{
remove(k);
}
}else{
cin>>k>>x;
add(k,x);
}
}
for(int i=head;i!=-1;i=ne[i]){
cout<<e[i]<<' ';
}
return 0;
}
//双链表 ACwing
#include<iostream>
#include<string>
using namespace std;
const int N=1000000+10;
int l[N],r[N],e[N],idx;
void Init(){
r[0]=1;
l[1]=0;
idx=2;
}
void add_L(int x){
e[idx]=x;
l[idx]=0;
r[idx]=r[0];
r[0]=idx;
l[r[idx]]=idx;
idx++;
}
void add_R(int x){
e[idx]=x;
r[idx]=1;
l[idx]=l[1];
l[1]=idx;
r[l[idx]]=idx;
idx++;
}
void remove(int k){
r[l[k+1]]=r[k+1];
l[r[k+1]]=l[k+1];
}
void add_k_l(int x,int k){
k++;
e[idx]=x;
l[idx]=l[k];
r[idx]=k;
r[l[idx]]=idx;
l[k]=idx++;
}
void add_k_r(int x,int k){
k++;
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[idx]]=idx;
r[k]=idx++;
}
int main(){
int m,k,x;
string s;
Init();
cin>>m;
while(m--){
cin>>s;
if(s=="L"){
cin>>x;
add_L(x);
}else if(s=="R"){
cin>>x;
add_R(x);
}else if(s=="D"){
cin>>k;
remove(k);
}else if(s=="IL"){
cin>>k>>x;
add_k_l(k,x);
}else{
cin>>k>>x;
add_k_r(k,x);
}
}
for(int i=r[0];i!=1;i=r[i]){
cout<<e[i]<<' ';
}
return 0;
}
//栈和队列
#include<iostream>
using namespace std;
const int N=1000010;
int stk[N],tt;//栈 先进后出 、
stk[++tt]=x;//入栈
tt--;//出栈
if(tt==0) true; //判空
else false;
stk[tt]//栈顶元素
int q[N],hh,tt=-1;//队列 先进先出
q[++tt]=x;//入队
hh++;//出队
q[hh];//获取队头和队尾的元素
q[tt];
if(tt>=hh)false;//判空
else true;
//洛谷p5788
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000010;
int stk[N],tt,e[N],a[N],q[N],qq;
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=n;i>0;i--){
while(tt&&stk[tt]<=a[i])
{
tt--;
}
if(tt==0){
q[qq++]=0;
}else{
q[qq++]=e[tt];
}
stk[++tt]=a[i];
e[tt]=i;
}
for(int i=qq-1;i>=0;i--){
printf("%d ",q[i]);
}
return 0;
}
//树
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int p[N][27],cnt[N],idx=1;
char s[N];
void add(char *s){
int j=0;//当前所用节点的地址
for(int i=0;s[i];i++){
int u=s[i]-'a';
if(p[j][u]==0){
p[j][u]=idx++;
}
j=p[j][u];
}
cnt[j]++;
}
int insert(char *s){
int j=0;
for(int i=0;s[i];i++){
int u=s[i]-'a';
if(p[j][u]==0){
return 0;
}
j=p[j][u];
}
return cnt[j];
}
int main(){
int n;
char op[2];
scanf("%d",&n);
while(n--){
scanf("%s%s",op,s);
if(op[0]=='I'){
add(s);
}else{
printf("%d\n",insert(s));
}
}
return 0;
}
//快速选择排序 ACwing 785
#include<iostream>
#include<cstdio>
using namespace std;
const int N=10000+10;
int q[N],n;
void quick_sort(int l,int r){
if(l>=r)return;
int x=q[l+r>>1],i=l-1,j=r+1;
while(i<j){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j)swap(q[i],q[j]);
}
quick_sort(l,j);
quick_sort(j+1,r);
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&q[i]);
}
quick_sort(0,n-1);
for(int i=0;i<n;i++){
printf("%d ",q[i]);
}
return 0;
}
//归并排序
#include<iostream>
using namespace std;
const int N=100000+10;
int q[N],res[N],n;
void merge_sort(int l,int r){
if(l>=r) return;
int mid=l+r>>1;//l+r的值右移1位 相当l+r的值除以2取整
//是比特操作,可以看做是除2，如
//12的二进制表示是00001100,12>>1将00001100右移一位，变为00000110，即6.
//15的二进制表示是00001111,15>>1将00001111右移一位，变为00000111，即7.
//另外<<就是左移，相当于乘以2.
merge_sort(l,mid);
merge_sort(mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(q[i]<q[j]){
res[k++]=q[i++];
}else{
res[k++]=q[j++];
}
}
while(i<=mid) res[k++]=q[i++];
while(j<=r) res[k++]=q[j++];
for(i=0,j=l;j<=r;j++){
q[j]=res[i++];
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&q[i]);
}
merge_sort(0,n-1);
for(int i=0;i<n;i++){
printf("%d ",q[i]);
}
return 0;
}
//归并排序CSDN转载照打
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
void merge(int a[],int l,int r,int mid)
{
int aux[r-l+1],i,j,k;
for(k=l;k<=r;k++)
aux[k-l]=a[k];
i=l;
j=mid+1;
for(k=l;k<=r;k++)
{
if(i>mid)
{
a[k]=aux[j-l];
j++;
}
else if(j>r)
{
a[k]=aux[i-l];
i++;
}
else if(aux[i-l]>aux[j-l])
{
a[k]=aux[j-l];
j++;
}
else
{
a[k]=aux[i-l];
i++;
}
}
}
void merge_sort(int a[],int l,int r)
{
if(l>=r)
return ;
int mid=(l+r)/2;
merge_sort(a,l,mid);
merge_sort(a,mid+1,r);
merge(a,l,r,mid);
}
void mergesort(int a[],int l,int r)
{
merge_sort(a,l,r-1);
}
int main()
{
int a[105],n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n);
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
京公网安备 11010502036488号