队列和堆栈
队列:是一种先进先出的线性表 利用他的性质可以做一些O(n)的简化,从队头出队,队尾进队;
堆栈:是一种后进先出的线性表 ,在栈顶进行操作,在程序设计时 如果需要按照保存数据时的相反顺序来使用数据,用栈来实现;
一般用数组来实现对队列和堆栈的操作。
下面进行最简单的数组模拟堆栈(不是完全用数组实现)(可以用数组完全模拟实现 )
//进行队列和堆栈的操作
stack<char>st1,st2 //首先 声明一下字符数组的类型
queue<char>q
//队列
while(n--) //这个堆栈的数量
{
char t;
cin >>t;
q.push(t);
}
while(!q.empty())
{
cout <<q.front()<<' '; //输出队列的第一个元
q.pop(); //
}
堆栈
while(n--) //这个堆栈的数量
{
char t;
cin >>t;
st.push(t);
}
while(!st.empty())
{
cout <<st.top()<<' '; //输出栈顶元素
st.pop();
}
运算符
与 & :只有x,y 都是1的时候,运算结果才是1, 其余情况都是0;
,(1&1 = 1,1&0 = 0)、
或 | : x,y中只要有一个是1,结果就是1,其余情况是0; 1|1 = 1,0 | 0= 0;
非 !: !x 如果是x是0 ,!x=1 ,x是1 结果是0;
异或 ^ : x^y ,相同是0,不同是1; 1 ^1 = 0 ,0 ^ 0=0 ,0 ^ 1=1;
反码和补码
int t=5在计算机中是32为二进制
有符号整型
1: 0000 …001
-1: 1000…001
-5 的二进制数是 100000…00101
反码是 011111.11010;
补码是 :
如果是正数;正数的补码等于反码
如果是负数,补码是其反码的基础加一;
左移和右移
表示:>>(右移) ,<<(左移); n>>k &1(这种操作是可以看n的二进制数的第k位是几) k =0,1,2…
#include<iostream>
//查看m的二进数中一的个数
using namespace std;
int lowbit(int x)
{
return x&-x; //x&-x = x&(~x+1) 返回最后一个 1;
} //也可以最后返回lowbit () 看一下最后一个 1 的个位数;
int main()
{
int n;
cin >>n;
while(n--)
{
int x;
cin >>x;
int res=0;
while(x)
x-=lowbit(x),res ++;
cout <<res; //结果是二进制数中一的个数
}
return 0;
}
kmp算法代码实现
最好用题模拟一下
此题输入一个模式串,父串,一般都是下标从一开始读入
查找一下在父串中模式串中所有可以匹配情况下的
在父串的开始下标
输入
3
ABA
5
ABABA
输出
0 2
#include<iostream>
#include<cstdio>
#define N 10010
#define M 10010
using namespace std;
int n,m;
char a[N],p[M];
int ne[N];
int main()
{
//输入
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf(" %c",&p[i]);//父串
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf(" %c",&a[i]);//模式串
//用 c++读入
//cin >>m >>p+1 >>n >>a+1
//求next[] 数组的过程
for(int i=2,j=0;i<=m;i++)
{
while(j&&p[i]!=p[j+1]) j=ne[j];
if(p[i]==p[j+1]) j++;
ne[i]=j;
}
//kmp 匹配过程
for(int i=1,j=0;i<=n;i++)
{
while (j&&a[i]!=p[j+1]) j=ne[j];
if(a[i]==p[j+1]) j++;
if(j==m)
{
//匹配成功
printf("%d ",i-m+1); //输出在父串中的开始位置;
j=ne[j];
}
}
return 0;
}
O(2) 算法优化
先用暴力做法对其分析
再看其中多做了那些(没用的操作)结合队列堆栈和数学的思想进行简化