算法总结3

Author Avatar
Xzhah 8月 26, 2019
  • 在其它设备中阅读本文章

字符串编辑距离

动态规划

把两个字符串变成相同的三个基本操作定义如下:

  1. 修改一个字符(如把a 变成b)
  2. 增加一个字符(如abed 变成abedd)
  3. 删除一个字符(如jackbllog 变成jackblog)
    针对于jackbllog 到jackblog 只需要删除一个或增加一个l 就可以把两个字符串变为相同。
    把这种操作需要的最小次数定义为两个字符串的编辑距离L。
    编写程序计算指定文件中字符串的距离。输入两个长度不超过512 字节的ASCII 字符串,在
    屏幕上输出字符串的编辑距离。
    输入样例
    Hello world!
    Hello word!
    输出样例
    13

    设置从字符串s1[i]点变换至s2[j]点的最短距离为dp[i][j],dp[i][j]可以分成三种情况来看(以Hello和Hllll为例):

1.替换:以最后一个字符为例,将o替换为l,那么dp[i][j]=dp[i-1][j-1]+1。

2.增加:dp[i][j]=dp[i][j-1]+1

3.删除:dp[i][j]=dp[i-1][j]+1

4.dp[0][i]=dp[i][0]=i

所以只要从第一个字符开始,每次都选三种状态里的最短距离,就能得到编辑距离了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<fstream>
#include<algorithm>
#include<string>
#include<vector>
#include<stdio.h>
typedef long long ll;
using namespace std;
int dp[1002][1002]={0};
//char str1[1002],str2[1002];
string str1,str2;
int min_get(int a,int b ,int c){
int minn=a;
if(a>b)
minn=b;
if(minn>c)
minn=c;
return minn;
}
int get_distance(int len1,int len2){
for(int i=0;i<=len1;++i)
dp[i][0]=i;
for(int j=0;j<=len2;++j)
dp[0][j]=j;
for (int i=1;i<=len1;++i)
for(int j=1;j<=len2;++j)
{
int res1=str1[i]==str2[j]?0:1;
int add=dp[i][j-1]+1;
int sub=dp[i-1][j]+1;
int equl=dp[i-1][j-1]+res1;
dp[i][j]=min_get(add,sub,equl);
}
return dp[len1][len2];
}
int main(){
ofstream outFile("p.out");
ifstream inFile("p.in");
streambuf *in_buf=cin.rdbuf();
streambuf *out_buf=cout.rdbuf();
cin.rdbuf(inFile.rdbuf());
cout.rdbuf(outFile.rdbuf());
getline(cin,str1);
getline(cin,str2);
cout<<get_distance(str1.length(),str2.length());
/*freopen("E:\\vs2010\\string_edit_distance\\Debug\\p.in","r",stdin);
freopen("E:\\vs2010\\string_edit_distance\\Debug\\p.out","w",stdout);
scanf("%[^\n]",&str1);
scanf("%[^\n]",&str2);
printf("%d",get_distance(strlen(str1),strlen(str2)));*/
return 0;
}

二分法

这个没啥好说的,需要注意的是每次二分left=mid+1,right=mid-1。

大家一定都能熟练掌握二分查找啦!那么来计算二分的次数吧!
约定二分的中点mid = (left + right) / 2。
输入:
第一行输入一个整数N(N<=10000)。
第二行输入N个升序整数。
第三行输入一个待查找的整数(必定在第二行中出现过)。
输出:
输出二分查找该整数时,进行过多少次二分。
输入样例
5
18 53 54 74 99
53
输出样例
2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int main(){
ifstream inFile("p.in");
ofstream outFile("p.out");
streambuf *out_stream=cout.rdbuf();
streambuf *in_stream=cin.rdbuf();
cin.rdbuf(inFile.rdbuf());
cout.rdbuf(outFile.rdbuf());
int N;
vector<int> a;
cin>>N;
for(int i=0;i<N;++i){
int tmp;
cin>>tmp;
a.push_back(tmp);
}
int found;
cin>>found;
int left=0;
int right=N-1;
int res=0;
while(right>=left){
int mid=(right-left)/2+left;
if(a[mid]>found){
right=mid-1;
res+=1;
}
if(a[mid]<found){
left=mid+1;
res+=1;}
if(a[mid]==found){
cout<<res;
break;
}
}
return 0;
}

快速找素数

欧拉筛,就是用已有素数把每个数都乘一遍可以遍历所有合数(如果该数是已有素数的倍数,可以break,因为该素数会乘所有数,所以会重复工作)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<algorithm>
#include<fstream>
#include<string>
#include<vector>
#include<math.h>
#include<memory.h>
using namespace std;
//typedef long long ll;
bool isPrime[100000001];
int prime[100000001]={0};
int main(){
/*ifstream inFile("p.in");
ofstream outFile("p.out");
streambuf* outBuf=cout.rdbuf();
streambuf* inBuf=cin.rdbuf();
cin.rdbuf(inFile.rdbuf());
cout.rdbuf(outFile.rdbuf());*/
//int tmp_sqrt=sqrt(100000001);
memset(isPrime,true,100000001);
int N;
cin>>N;
isPrime[0]=isPrime[1]=false;
//int sqrtN=sqrt(N);
int current=0;
for(int i=2;i<=N;++i){
if(isPrime[i]==true)
{
prime[current++]=i;
//prime[current++]=i;
}
for(int j=0;j<=current&&prime[j]*i<=N;++j){
//isPrime[j]=false;
isPrime[prime[j]*i]=false;
if(i%prime[j]==0)
break;
}}
//for(int i=0;i<=N;++i)
//{
// if(isPrime[i])
// prime[current++]=i;
//}
//if(N==0)
//break;
int num=0;
for(int Cur=0;Cur<N;++Cur){
if(prime[Cur]!=0&&prime[Cur]<=N)
//cout<<prime[Cur]<<" ";
++num;
else{
//cout<<endl;
break;
}
}
cout<<num<<endl;
return 0;
}

优先队列

给出优先队列的实现,实现4个操作

• ADD N P:往队列里加入id为N的优先级为P的任务
• NEXT:输出下一个最高优先级的任务的id,如果优先级相同输出id小的任务,若队列中没有任务输出-1
• REMOVE N:移除id为N的任务
• COUNT:输出队列中的任务数量

使用briority_queue就行了,需要在结构体里重载<符号,这样才能给节点排序。使用set记录删除节点,完成remove功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
struct Node{
int id,p;
friend bool operator < (Node a, Node b){
if(a.p==b.p)
return a.id>b.id;
return a.p<b.p;
}
Node(){}
Node(int a,int b){
id=a;
p=b;
}
};
int sum;
vector<int> logg;
priority_queue<Node> que;
void add(int id,int p){
que.push(Node(id,p));
++sum;
}
void dele(int id){
logg.push_back(id);
--sum;
}
void next(){
if(sum==0)
return;
Node tmp;
while(true){
tmp=que.top();
if(find(logg.begin(),logg.end(),tmp.id)!=logg.end())
{
que.pop();
logg.erase(find(logg.begin(),logg.end(),tmp.id));
}
else
break;
}
cout<<tmp.id<<endl;
}
void count(){
cout<<sum<<endl;
}
int main(){
int choice,idt,pt;
while(true){
cin>>choice;
if(choice==1){
cin>>idt>>pt;
add(idt,pt);
}
if(choice==2){
next();
}
if(choice==3){
cin>>idt;
dele(idt);
}
if(choice==4){
count();
}
if(choice==5)
break;
}
return 0;
}