[数据结构与算法]22.2.4~2.5

1.储存一个数的二进制

int k=0;
int jc[1000];
int n1;
cin>>n1;	
while(n1){
			jc[k++]=n1%2;
			n1/=2;
		}

注意jc数组储存的是倒序的n1的二进制，例如n1=8=1000（B），在jc数组中是0001；

2.所以想要知道一个数是2的几次方的范围，可以对它/=2，记录次数，次数减一即几次方；

    int num=0;
    int n;    
    cin>>n;
    while(n){
        num++;
        n/=2;
            }

num-1；

3.register 关键字；

(2条消息) C语言中的register关键字_ccjoe的专栏-CSDN博客_register在c语言中是什么意思https://blog.csdn.net/ccjoe/article/details/44756395?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164398064716781685368720%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=164398064716781685368720&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-44756395.first_rank_v2_pc_rank_v29&utm_term=register+&spm=1018.2226.3001.41874.最短编辑距离

①状态表示（下标含义）：f[i,j]表示将a(1~i）操作到b(1~j)所需的最小操作次数；

因为属性是min，所以不想之前做的默认元素为0可以直接做，此题需要全部初始化为大数；

②状态转移方程：有3种操作，对应3种集合，将3种操作的状态转移方程理解写出即可；

删除操作：删除第i个元素（末尾元素）即保证前1~（i-1）是和b匹配的，加上本次的操作次数1，

所以f[i,j]=f[i-1,j]+1；

插入操作：插入后a1~（i+1）与b1~j相等，即a1~i与b1~（j-1）相等，所以此时的状态由f[i,j-1]转移而来；即f[i,j]=f[i,j-1]+1;

替换操作：将ai替换为bj，所以a1~i-1与b1~j-1相等，所以状态由f[i-1,j-1]转移而来；

f[i,j]=f[i-1,j-1]+1；特别的，当ai==bj时，不用操作，即f[i,j]=f[i-1,j-1]+0；

预处理就是考虑遍历时数组用到的边界问题和初始情况；

a=0时只能插入，b=0时同理，只能删除；

#include<bits/stdc++.h>
#define rep1(i,a,n) for(int i=a;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<=n;i++)
#define per1(i,n,a)	for(int i=n;i>a;i--)
#define per2(i,n,a) for(int i=n;i>=a;i--)
using ll=long long ;
using namespace std;
const int N=1010;
int f[N][N];
char a[N],b[N];
int main()
{
	int n,m;
	cin>>n;
	scanf("%s",a+1);
	cin>>m;
	scanf("%s",b+1);
	rep2(i,1,n)
	rep2(j,1,m)
	f[i][j]=INT_MAX;
	rep2(i,1,n)f[i][0]=i;a=0的情况
	rep2(i,1,m)f[0][i]=i;b=0的情况
	rep2(i,1,n){
		rep2(j,1,m){
			f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
			if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
			else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
		}
	}
	cout<<f[n][m];
	return 0;		 
}

5.一个简单的输入知识

?按照4.的做法，我无法初始1000个char类型，那么该如何输入此题呢？

①可以用结构体；结构体里面一个char，用结构体的数组下标，也行；但是在结构体输入中，scanf("%s",&z[i].a+1);无法完成从下标1开始的输入，需要在后边额外操作，也有不便；

②可以char一个二维数组，s[15][1005]，这样输入的s[i]不是单个字符元素，而是每一行的字符串；可以把i看作行号了就；

偶然间对memset初始化char数组，会不会影响其长度产生影响

?看得出来填充0字节时没有影响的，直接理解为空字节就好，真正要表示0，需要填充'0'，带单引号的0，这样就是填进去0了；

并且char的定义里也有解释：

?即0；

6.编辑距离；

主要是输入问题的方面，以段错误，一般数组还是开1e3起步比较好，就算小了；

#include<bits/stdc++.h>
#define rep1(i,a,n) for(int i=a;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<=n;i++)
#define per1(i,n,a)	for(int i=n;i>a;i--)
#define per2(i,n,a) for(int i=n;i>=a;i--)
using ll=long long ;
using namespace std;
const int N=1010;
int f[N][N];
char a[N][N],b[N];
int n,m;
int solve(char *a,char*b)
{
	int lena=strlen(a+1);
	int lenb=strlen(b+1);
	rep2(i,0,lena)f[i][0]=i;
	rep2(i,0,lenb)f[0][i]=i;
	rep2(i,1,lena){
	rep2(j,1,lenb){
		f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
		f[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));
			}
		}
	return f[lena][lenb];
}
int main()
{
	cin>>n>>m;
	rep2(i,1,n)cin>>(a[i]+1);
	while(m--){
		int ans=0;
		char b[15];
		int xz;
		cin>>b+1>>xz;
		rep2(i,1,n){
			if(solve(a[i],b)<=xz)ans++;
		}
		cout<<ans<<endl;
	}
	return 0;		 
}