字符串编辑距离
动态规划
把两个字符串变成相同的三个基本操作定义如下：
- 修改一个字符（如把a 变成b）
- 增加一个字符(如abed 变成abedd)
删除一个字符（如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};
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());
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;
bool isPrime[100000001];
int prime[100000001]={0};
int main(){
memset(isPrime,true,100000001);
int N;
cin>>N;
isPrime[0]=isPrime[1]=false;
int current=0;
for(int i=2;i<=N;++i){
if(isPrime[i]==true)
{
prime[current++]=i;
}
for(int j=0;j<=current&&prime[j]*i<=N;++j){
isPrime[prime[j]*i]=false;
if(i%prime[j]==0)
break;
}}
int num=0;
for(int Cur=0;Cur<N;++Cur){
if(prime[Cur]!=0&&prime[Cur]<=N)
++num;
else{
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;
}
|
